1.7

数组+ 链表 头插法

初始化大小 数组的大小,必须是 2 << 30,初始化会根据传入大小匹配最近的值 例如:

new HashMa(3); -> length = 4
new HashMa(5); -> length = 8
new HashMa(10); -> length = 16
new HashMa(17); -> length = 32

计算下标 得到key的hash Code 和数组长度进行逻辑与& 操作

示例: Key的 Hash Coed = 0011 1101

#初始化大小为10 匹配的值为16 ,将(size -1)得到 15
对应hash code   =  00000 1111
#进行 & 运算    
0011 1101
0000 1111    
得到
0000 1101  -> 得到对应的下标:13

#初始化大小为17 匹配的值为32 ,将(size -1)得到 31
对应hash code   =  0011 1111
#进行 & 运算    
0011 1101
0001 1111    
得到
0001 1101  -> 得到对应的下标:29 ==（13+16）

Key的 Hash Coed = 0010 1101

#初始化大小为10 匹配的值为16 ,将(size -1)得到 15
对应hash code   =  00000 1111
#进行 & 运算    
0010 1101
0000 1111    
得到
0000 1101  -> 得到对应的下标:13

#初始化大小为17 匹配的值为32 ,将(size -1)得到 31
对应hash code   =  0011 1111
#进行 & 运算    
0010 1101
0001 1111    
得到
0000 1101  -> 得到对应的下标:13  

由上面两图得到结果:

Hash根据key的值进行散列计算，将key分别放置于数组中， 由于hash code 会存在相同情况,此时会发生hash碰撞，hashMap 中使用链地址法, 但不同的是，HashMap会将冲突的数据链接到链表头部（PS:避免遍历去找到最后一个数据） 然后将链表下移。

伪代码

class HashMap<K,V> {

    Node<K, V> nodes;
    
    int size;
    
    public V put(K k,V v){
         //创建节点
        if(null == nodes || nodes.length == 0){
            nodes = resize();
            size =nodes.length;
        } 
         //根据k得到hash编码后，取出对应的节点
        int index = getIndex(getHash(k));
        //根据下标得到老节点
        Node<K,V> oldVal =  nodes[index];
        //得到节点为null
        if( null == oldVal){
            //创建一个新节点
           nodes[index] = new  Node(k,v,null);
        }else{
            //创建一个新节点，并将老节点设置为子节点
		   nodes[index] = new  Node(k,v,oldVal);
        }
        size++;
        //此处省略链表内部数据替换的代码。。。
        return 新插入一个key返回null,重复插入相同的Key，返回被替换值;
    }
    
    //为什么效率好，直接返回效率能不高吗
    public int size() { return size}
}

class Node<K,V> {
//键
private K key;
//值
private K val;
//子节点
private Node<K,V> next;

    public Node(K k,V v){
       this.k = k;
       this.v = v;
    }
    public Node(K k,V v,Node<K,V> next){
	   this.k = k;
       this.v = v;
       this.next = next;
    }
}

1.8

数组+链表 + 红黑树

Hash冲突解决

链地址法:

将所有hash编码相同的字符生成一个链表,发生冲突是链接到链表尾部

待续...