目录
目录.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());
}
