HashMap原理

HashMap原理

简单陈述：
HashMap的主干是一个Entry数组。每一个Entry包含一个key-value键值对,jdk1.8版本是数组+链表+红黑树，1.8之前是数组+链表。

问题一  索引如何计算？hashCode都有了，为何还要提供hash()方法，数组容量为何是2的N次幂？
  1调用HashMap的hash()方法进行哈希，最后&(当前容量-1) 得到下标值
hash()方法如下 ：   

 //先调用了hashCode()方法然后右移16位 在进行异或运算  
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

 2二次hash()是为了综合高位数据，让哈希分布更均匀
 3计算索引时，如果是2的n次幂可以使用位与运算代替取模，效率更高，扩容时hash&oldCap(原始容量)=0的元素留在原来位置， 否则新位置=旧下标+oldCap(原始容量)
 4 但1,2,3都是为了配合容量为2的n次幂时的优化手段，例如hashtable的容量就不是2的n次幂，并不能说明哪种设计更优 应该是设计者综合了各种因素，最终选择了使用2的n次幂作为容量

问题二，为何要用红黑树，为何一上来不树化，树化阈值为何是8，何时会树化，何时会退化为链表？

 1.红黑 树是用来避免DoS攻击，防止链表超长时性能下降，树 化是偶然情况
     1.1红黑树的查找比链表慢，占用的内存也比链表大，如非必要，尽量还是使用链表。
     1.2hash值如果足够随机，则在hash表内按泊松分布，在负载因子0.75的情况下，
         长度超过8的链表的出现概率是亿分之6，选择8就是为了让树化几率足够小
2.树化两个条件，链表长度超过树化阈值(大于8)，数组容量>=64,(如果数组容量小于64会首先进行扩容，因为扩容后容量值发生变化会重新计算下标,计算下标的代码:hash&(容量-1))
3退化情况1 ，在扩容时如果拆分树时，树元素个数<=6则会退化链表
4退化情况2，remove树节点时，或root,root.left,root.right,root.left.left有一个为null,也会退化为链表

问题三.   put方法流程：
1.hashMap是懒惰创建数组的，首次使用才创建数组
2.计算索引(桶下标)
3.如果桶下标没人占用，创建Node点位返回
4如果桶下标已经有人占用
    4.1已经是TreeNode走红黑树的添加或更新逻辑
    4.2是普通node,走链表的添加或更新逻辑，如果链表长度超过树化阈值，走树化逻辑
5返回前检查容量是否超过阈值，一旦超过进行扩容，如果初始容量16时，添加完第13个元素后检查是否超过阈值，不是添加前检查。
 

问题四:    1.7和1.8版本的hashMap有什么不同？
(1).链表插入节点时，1.7是头插法，1.8是尾插法
(2) 1.7版本是大于等于阈值且没有空位时才扩容，而1.8是大于阈值就扩容
(3) 1.8在扩容计算node索引时，会优化
 

问题五:    加载因子为何默认是0.75f?
1.在空间占用与查询时间之间取得较好的权衡
2大于这个值，空间节省了，但链表就会比较长影响性能
3小于这个值，冲突减少了，但扩容就会更频繁，空间占用多
 

问题六：String对象的hashCode()如何设计的，为啥每次乘的是31
目标是达到较为均匀的散列效果，每个字符串的hashCode足够独特
 

最重要的putVal方法源码解析

static final int TREEIFY_THRESHOLD = 8;

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node[] tab; Node p; int n, i;
        //如果tab为空，第一次put时初始化容量，resize方法里处理
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //(n - 1) & hash 计算下标 n 是当前容量,如果该下标为空则创建一个node
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            //否则该下标不为空
            Node e; K k;
            //判断当前key是否相等，相等则覆盖
            if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //判断是否是红黑树结构，是则走红黑树的增加逻辑
            else if (p instanceof TreeNode)
                e = ((TreeNode)p).putTreeval(this, tab, hash, key, value);
            else {
                 遍历链表，只在两种情况下才会跳出循环
                for (int binCount = 0; ; ++binCount) {
                    //第一种：已经遍历到尾部,在最后插入新节点跳出，因节点数量+1 判断是否需要树化
                    if ((e = p.next) == null) {
                        // 在尾部插入新结点
                        p.next = newNode(hash, key, value, null);
                        // 判断是否需要树化
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        // 跳出循环
                        break;
                    }
                    // 第二种：e指向的节点与要插入节点的key相同，此次put为覆盖 *** 作
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                        // 相等，跳出循环
                        break;
                    // 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

 判断是否需要树化binCount >= TREEIFY_THRESHOLD - 1怎么是8-1？
因为：遍历过程中p从第一个节点遍历到最后一个节点，但由于binCount是从0开始计数，所以binCount的值等于 链表长度 - 1（注意此时的链表长度没有算新插入的节点）判断条件为 binCount >= TREEIFY_THRESHOLD - 1 => binCount+1(链表长度) >= TREEIFY_THRESHOLD
但此时链表新插入了一个节点   p.next = newNode(hash, key, value, null);
所以链表树化的那一刻，它的真实长度应该时binCount+1+1 => 链表长度>TREEIFY_THRESHOLD(8)
即：链表长度大于8时，treeifyBin()方法被调用 

treeifyBin方法:

   final void treeifyBin(Node[] tab, int hash) {
        int n, index; Node e;
        // static final int MIN_TREEIFY_CAPACITY = 64;
        //当tab为空或长度小于64时先进行扩容resize方法里会扩容
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        //否则长度大于等于64则树化，转成红黑树
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode hd = null, tl = null;
            do {
                TreeNode p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

  按位与运算符（&） 
 参加运算的两个数据，按二进制位进行“与”运算。
 运算规则：0&0=0;  0&1=0;   1&0=0;    1&1=1;
 即：两位同时为“1”，结果才为“1”，否则为0
  
 按位或运算符（|）
参加运算的两个对象，按二进制位进行“或”运算。
运算规则：0|0=0；  0|1=1；  1|0=1；   1|1=1；
即 ：参加运算的两个对象只要有一个为1，其值为1。
例如:3|5　即 00000011 | 0000 0101 = 00000111  因此，3|5的值得7。

异或运算符（^）
参加运算的两个数据，按二进制位进行“异或”运算。
运算规则：0^0=0；  0^1=1；  1^0=1；   1^1=0；
即：参加运算的两个对象，如果两个相应位为“异”（值不同），则该位结果为1，否则为0。

、、、、、、、、、  自己总结一下、、、、、、、

1.当一个put *** 作时，调用hashMap的hash()方法,(hash方法里首先获得hashCode值然后右移16位在做异或运算)然后hash&(容量-1) 的值就是存放的下标，如果该下标不为空，1判断是否key相等，相等则替换。2判断是否是红黑树，是则添加到红黑树。3添加到链表，如果链表长度大于8判断当前容量如果小于64则首先扩容(因为扩容后容量值变化会重新计算下标)，如果当前容量大于等于64则树化(就是转成红黑树)，红黑树退化为6个或者remove让其不平衡了后会退化为链表
2.负载因子是0.75也就是说当前容量*0.75的值，当这个值+1添加完后就会进行扩容，扩容是当前容量*2.就是扩一倍。
3扩容时当前hash值&原始容量=0代表保留在原有位置，否则，旧下标+原始容量就是新下标