目录

目录.png

---

构造器

• 构造器只是初始化负载因子，和扩容阈值。并没有初始化table。
• 阈值是比传入的大的最小2的幂次方（传入1时，为1），我们想得到比n大的最小2次幂只需要在最高位的前一位置1，后面全置0就ok。

 this.threshold = tableSizeFor(initialCapacity);
 static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

确定哈希桶数据索引位置

• 这也就是为啥，初始化要初始化2的n次方，数组大小为2^n-1（即二进制所有位都是1，如：3,7,15,31...）才能保按位与运算得到的 index 均匀分布

static int indexFor(int h, int length) {  
      return h & (length-1); 
 }

补充：二进制的按位与运算举例：23 & 15 = 7
0 1 0 1 1 1
0 0 1 1 1 1    
-------------
0 0 0 1 1 1

HashMap的put方法实现

• put参数key可为null, null总是放在table[0]里面，因为hash为0, (n - 1) & hash肯定就为0，table[0]上有其他Node就走正常put流程。
• 数组位初始化就调用resieze进行初始化数组(阈值等于初始化容量 * 负载因子)。初始化完后，继续往下走并没有结束。是if(){}的判断。
• 根据索引(n - 1) & hash定位到table[index]，如果这个值为null，新建节点插入这里
• hash值且key相同则落入第一个bucket中，更新值，否则是树节点则插入红黑树，否则就遍历链表看下是更新值，还是尾部插入值。尾部插入值时会判断(链表长度是否超过红黑树转换阈值8)是否要换红黑树。
• evict可以用来决定是否更新值，modCount增加，快速失败用
• 根据size是否大于阈值判断是否需要resize。

hashmap的get方法

• 根据(n - 1) & hash(如果null key hash为0，就在table[0]找)，定位table[index]
• 判断索引处第一个key与传入key是否相等，如果相等直接返回
• 是树从树取，不是树从链表遍历取

hashmap的扩容

• 通过old table是否存在能判断是初始化还是已有数组扩容
• 0.75负载因子取这个的原因是出于时间和空间的衡量。

初始化部分

• 默认构造器创建HashMap，当第一次添加元素时进行扩容，此时数组容量为16，threshold为16 * 0.75 = 12。
• 当我们指定指定initialCapacity的时候，threshold一开始表示的是大于等于initialCapacity最小的2的幂次方数，直到第一次添加元素时进行扩容，数组容量为threshold的值，而threshold此时为指定负载因子与数组容量的乘积
• 若数组已经初始化，即数组容量>0时，再扩容，新容量变为原容量的两倍，如果新容量小于最大容量，并且老容量>=16,此时threshold也变为原来的两倍，否则threshold不变。
• 以上都不可超时Integer最大值

已有数组扩容

• 遍历table，table[index]中bucket为空则跳过，不为空只有一个元素时直接搬到新数组newTab[e.hash & (newCap - 1)] = e;
• 如果是树形节点，则执行树形节点操作
• 如果是链表则， 遍历链表，e.hash&oldCap为0，节点在新数组中的索引不变，newTab[j], e.hash&oldCap为1，节点在新数组中的索引值 = 老数组容量+原索引值，newTab[j + oldCap]。
• 然后新建一个链表，值还是原来的，根据e.hash&oldCap的值觉得链表放入newTab[j]或者newTab[j + oldCap]。
• 扩容会重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知hashmap中元素的个数，那么预设元素的个数能够有效的提高hashmap的性能。

既然红黑树那么好，为啥hashmap不直接采用红黑树，而是当大于8个的时候才转换红黑树？

• 因为红黑树需要进行左旋，右旋操作， 而单链表不需要。如果元素小于8个，查询成本高，新增成本低。如果元素大于8个，查询成本低，新增成本高。

Hashmap为什么不用平衡树

• 红黑树是平衡树的一种，平衡树是特殊的二叉查找树。B树也是特殊的二叉查找树。
• 红黑树查找时间期望是O(log n) ，有点类似二分查找。
• 插入效率比平衡二叉树高，查询效率比普通二叉树高。所以选择性能相对折中的红黑树。

解决hash冲突的办法

• 开放定址法（线性探测再散列(插入元素时，如果发生冲突，算法将从该槽位向后遍历哈希表，直到找到表中的下一个空槽，并将该值放入到空槽当中)，二次探测再散列，伪随机探测再散列）
• 再哈希法(产生冲突时，用另一个hash函数计算，直到不冲突为止)
• 链地址法(hashmap使用)

hashmap为何线程不安全

• 在jdk1.7中，在多线程环境下，扩容时头插会造成环形链而死循环。
• 在jdk1.8中，在多线程环境下，会发生数据覆盖的情况。put操作时如果没有hash碰撞则会直接插入元素。如果线程A和线程B同时进行put操作，刚好这两条不同的数据hash值一样，并且该位置数据为null，所以这线程A、B都会进入第6行代码中。假设一种情况，线程A进入后还未进行数据插入时挂起，而线程B正常执行，从而正常插入数据，然后线程A获取CPU时间片，此时线程A不用再进行hash判断了，问题出现：线程A会把线程B插入的数据给覆盖，发生线程不安全。

hashmap排序高级用法

• key排序, TreeHashMap或者:

ArrayList<Integer> list = new ArrayList<>(hashMap.keySet());
//调用sort方法并重写比较器进行升/降序
Collections.sort(list, (o1, o2) -> o1> o2 ? 1 : 0);

Iterator<Integer> iterator = list.iterator();
//迭代排序后的key的list
while ((iterator.hasNext())){
    Integer key = iterator.next();
    String value = hashMap.get(key);
    System.out.print(key+"="+value+",");
}

• value排序

ArrayList<Map.Entry<Integer,String>> list = new ArrayList<>(hashMap.entrySet());
// Comparator升序
Collections.sort(list, Map.Entry.comparingByValue());
Iterator<Map.Entry<Integer,String>> iterator = list.iterator();
for(Map.Entry<Integer,String> m : list){
    System.out.println(m.getKey()+"="+m.getValue());
}

---

参考文献

• HashMap 为什么线程不安全？
• HashMap JDK1.8实现原理
• 【JDK1.8】 Java小白的源码学习系列：HashMap
• 【深入Java基础】HashMap高级用法（一）：排序