4.4.2 情况2—当某些节点为NULL
情况2：remove 树节点时，若 root、root.left、root.right、root.left.left 有一个为 null ，也会退化为链表
退化过程图解:
备注:
检查节点是在移除之前进行的,如果移除(以上四种)之前存在,则移除之后依旧不会退化
当执行resize也就是扩容的情况下是判断元素小等于6，而在执行remove时才去判断root节点及子孙。两个情况不一样。 所以图中,在remove过程中即使节点数<=6,也不会退化成链表.
4.5 索引计算
4.5.1 索引计算方法
首先，计算对象的 hashCode() ,也就是原始Hash
再进行调用 HashMap 的 hash() 方法进行二次哈希
二次 hash() 是为了综合高位数据，让哈希分布更为均匀
最后 & (capacity – 1) 得到索引 (等价于取模运算,但是逻辑运算效率更高)
补充: 取模运算和逻辑运算的关系
4.5.2 为何要二次Hash
观察源码
代码验证
当使用随机产生的数放入容量为16的Hash表中
public static void main(String[] args) { int[] array = Utils.randomArray(1000); System.out.println(Arrays.toString(array)); int[] sizes = {16}; printHashResult(array, sizes); } public static int[] randomArray(int n) { int lastVal = 1; Random r = new Random(); int[] array = new int[n]; for (int i = 0; i < n; i++) { int v = lastVal + Math.max(r.nextInt(10), 1); array[i] = v; lastVal = v; } shuffle(array); return array; } public static void printHashResult(int[] array, int[] sizes) { List<Map<Integer, AtomicInteger>> maps = new ArrayList<>(); for (int size : sizes) { maps.add(getMap(size)); } for (int hash : array) { for (int j = 0; j < sizes.length; j++) { maps.get(j).get(hash % sizes[j]).incrementAndGet(); } } for (Map<Integer, AtomicInteger> map : maps) { System.out.printf("size:[%d] %s%n", map.size(), map); } }
运行结果:
- 当使用非随机数(特殊处理过)放入容量为16的Hash表中
public static void main(String[] args) { int[] array = Utils.lowSameArray(1000); System.out.println(Arrays.toString(array)); int[] sizes = {16}; printHashResult(array, sizes); } //产生特殊的随机数 public static int[] lowSameArray(int n) { int[] array = new int[n]; Random r = new Random(); for (int i = 0; i < n; i++) { array[i] = r.nextInt() & 0x7FFF0002; } return array; }
运行结果:
改进:模仿jdk的hash算法进行二次Hash
总结:二次Hash可以让数在HashMap上分布更为均匀,防止出现超长链表.
4.5.3 容量为何是2的n次幂
计算索引时效率更高：如果是 2 的 n 次幂可以使用位与运算代替取模
扩容时重新计算索引效率更高： hash & oldCap == 0 的元素留在原来位置 ，否则新位置 = 旧位置 + oldCap
图解演示
4.5.4 容量不是2的n次幂行不行
答案:可以的
代码演示
// .net 是原始容量 * 2 开始找下一个质数作为新容量 public static void main(String[] args) { int[] array = Utils.lowSameArray(1000); // int[] array = Utils.evenArray(1000); System.out.println(Arrays.toString(array)); int[] sizes = {11, 16, 23}; printHashResult(array, sizes); } public static int[] evenArray(int n) {//产生n个随机偶数 int[] array = new int[n]; for (int i = 0; i < n; i++) { array[i] = i * 2; } return array; } public static int[] lowSameArray(int n) {//产生n个特殊的数 int[] array = new int[n]; Random r = new Random(); for (int i = 0; i < n; i++) { array[i] = r.nextInt() & 0x7FFF0002; } return array; }
结论
计算对象的HashCode(),在进行调用HashMap的hash()方法进行二次哈希,最后 & (capacity - 1)得到索引
二次hash()是为了提高数位数据,让哈希分布更为均匀.
计算索引时,如果是2的n次幂可以使用位于运算代替取模,效率更高; 扩容时hash & oldCap==0的元素保留在原来位置,否则新位置 = 旧位置 + oldCap
但 1、2、3都是为了配合容量为2的n次幂时的优化手段.也就是说如果 hash 表的容量不是 2 的 n 次幂，则不必二次 hash. 设计者应该是综合了各种因素,最终选择了使用2的n次幂作为容量.
没有采用这一设计的典型例子是 Hashtable
一句话:容量是 2 的 n 次幂 这一设计计算索引效率更好，但 hash 的分散性就不好，需要二次 hash 来作为补偿. 如果容量不是 2 的 n 次幂,那么1,2,3这些手段也用不上.
**补充:**HashTable的扩容机制
可以看到扩容的容量中有一些还并不是质数. 微软的.NET中的Dictionary每次扩容的时候，容量大于等于原有空间的2倍的最小质数,这种扩容规则就会让Hash分布更为均匀.
所以:如果要追求效率,则选择2^n作为容量.如果想要追求各个挺好的Hash分布性,则选择一个质数选择Hash容量.
4.6 HashMap的put方法
4.6.1 put过程分析
HashMap 是懒惰创建数组的，首次使用才创建数组 (首次使用put方法才创建数组)
计算索引（桶下标） (通过key计算hash值,然后进行二次hash,进行位与运算得到下标)
如果桶下标还没人占用，创建 Node(JDK1.7是Entry对象) 占位返回
如果桶下标已经有人占用
已经是 TreeNode 走红黑树的添加或更新逻辑
是普通 Node，走链表的添加或更新逻辑，如果链表长度超过树化阈值，走树化逻辑
返回前检查容量是否超过阈值，一旦超过进行扩容 (添加完成才进行扩容的)
