HashMap与HashTable的小细节笔记

1. 继承树

继承类型	HashMap	HashTable
类	AbstractMap<K,V>	Dictionary<K,V>
接口	Map<K,V>, Cloneable, Serializable	Map<K,V>, Cloneable, Serializable

继承的接口是一样的，都是Map，Cloneable，Serializable 接口

继承的类不一样。

1. 数据存储结构

HashMap	HashTable
Node<K,V>[] 链表数组（后面会转红黑树）	Entry<K,V>[] 链表数组

其中Node，Entry 都是接口 Map.Entry 的一个实现。大体上没有什么差别。

1. 实例化过程的区别

类目	HashMap	HashTable
是否实例化数组	不会实例化 Node 数组	会根据初始数组容量，初始化Entry 空数组
默认数组容量	默认初始数组容量大小是16	默认数组大小是11
默认扩容因子	0.75f	0.75f

实例化对象的时候，最大的差别是：

• HashMap 是仅仅做了一些基本的参数设置，不会生产数组。
• HashTable 是出了数组容量、扩容因子的设置，还会生成一个空数组

1. Hash 和index 计算的区别

类目	HashMap	HashTable
hash 计算	h=h==0?: (h = key.hashCode()) ^ (h >>> 16)	h=h=0?0:key.hashCode()，直接调用hashcode 方法 获取 hash值
index定位	(n-1)& hash	(hash & 0x7FFFFFFF) % tab.length

• >>>

  是逻辑右移，就是不管符号，右移的时候，左边补0，如1101>>>1= 0110；

• hashMap 在hash 的时候，特意的把hash值进行了一次异或运算。得到的结果是：

  高16不会变。低16变成了高16位和低16位的异或结果，使得低16位也有了高16位的特征；尽量的做到只有有1位的变化，就会是的 异或结果不一样，从而降低了Hash冲突。

  • 0^1=1
  • 1^1=0
  • 0^0=0
• index的计算，涉及两个点
  • hash值为可能出现负数，需要把hash值修改为 正数 ，index 一定是 正数
  • 在当前的数组长度范围内。

HashTable 做法

• 为了确保 hash值不会出现负数，HashTable 做法比较简单 hash & 0x7FFFFFFF 的效果相当于Math.abs(hash); 取绝对值；0x7FFFFFFF 的二进制： 0111 1111 1111 1111 1111 1111 1111； 做 & 运算后，最高位的符号位一定是 0； 其余位不变。
  • 0&1=0，1&1=1
• 为了确保index 不会超出数组容量，那么HashTable 进行了取模运算，得到的余数就是当前插入的index.

HashMap 做法

• n=tab.length 为2n，那么n-1 一定是一个正数，因此最高位一定是0，就是类似与上面的0x7FFFFFFF=232 -1 ；
• （n-1）& hash 直接确定了 结果是一个正数，并且（n-1）& hash <= n-1;

综合上面的对比，index 计算上，HashMap 全部都是位运算，会快一些。在Hash的分布上，HashMap 更加能够避免Hash碰撞 。

1. 新增元素

类目	HashMap	HashTable
Value 是否能够为空	可以 value == null	value != null
是否线程同步	否	是，synchronized 修饰方法
扩容顺序	确认Hash是否冲突，否则先插入元素 ，冲突则确认是否存在， 判断是否需要扩容	复制一遍当前的table，判断是否需要扩容 ，取出index位置的数据, 插入元素
Hash 冲突处理	通过(n-1)&hash 定位数组位置找到链表的第一个元素，开始遍历next 是否为空；空则新增元素在链表【最后一个】位置，不为空则 修改next的value	通过(hash & 0x7FFFFFFF) % tab.length 来定位数组位置找到链表的第一个元素，开始遍历next 是否为空；不为空则修改，则修改对应的value，否则添加新的元素在链表的【第一个】位置

因此结构图如下

小细节点：

• HashTable 在Hash冲突的情况下，新增元素，是取两次，第一次判断是否重复；第二次 把老的index值关联到新的值的next上，把最新值放到 index 位置上。HashMap 则是沿着index 定位到元素，判断是否重复，否则关联到最后的next 上去。

1. 扩容过程

类目	HashMap	HashTable
判断条件	++size>threshold ；同时没有超过默认的最大容量1<<30 (230)	count >= threshold ; 没有超过默认的最大容量Integer.MAX_VALUE - 8
扩容后大小	newCap = oldCap << 1,原来的2倍；也是为了index 定位的时候使用位运算更加高效率	(oldCapacity << 1) + 1，原来的大小* 2 +1 ；保持扩容后的大小为奇数；可以让后续的取模运算拿到的index 更加均匀些。就是为了均匀分布
扩容后元素的位置变化	分高位为0和高位不为0 的情况；hash&oldCap== 0 属于高位为0的 保留在原阿里位置上tab[i]，高位为1的进行oldCap的偏移 tab[i+oldCap]	同一个Hash值的定位没有变化，但是，定位到的Hash值的链表顺序变成来反序。比如，第3个位置的链表是A->B->C,变成来 C->B->A

hash& oldCap == 0 的讲解：

能够得出上面的结果的前提：1. oldCap = 2n;2. hash = h0?: (h = key.hashCode()) ^ (h >>> 16)；

上面的结构就是可以得出两个中数据类型：

oldCap=2n的二进制：10000000……；

那么在进行&操作的时候，除了（最）高位，其他的一定都是0；低位结果就是0；高位的结果是1或者0；

因此就是两种情况：

hash& oldCap == 0 的情况，记录为低位数据，疑问点：((newCap = oldCap<<1)-1)& hash 是否和（oldCap-1）&hash 相等； 结果是相等的。论证过程如下：

• oldCap-1 结果是：0000 1111，24-1 ；15，默认大小-1; oldCap=0001 0000
• newCap-1 结果是：0001 1111，25-1; 31，默认大小*2-1
• 又因为 是 hash & oldCap==0；那么得出结果就是 hash 的第5位的一定是0；也就是在这种情况下，能够对 hash & （oldCap-1）操作的结果有效的只有前4位。newCap-1和oldCap-1 都是右边4位得到有效的计算，其余的都是0，所以它们的结果是一样的。
• 那么就是说，这情况在扩容后，位置不变的。还在原来的index 上。

hash& oldCap != 0 的情况下，记录为高位数据， 疑问点：（newCap-1）& hash 是多少？

• 我们看newCap-1 和oldCap-1 差别就是 就是一个oldCap，下面通过二进制来论证一下& hash 之后是否也是一个oldCap。
• 在&计算下，hash& oldCap != 0, 那么可以直接得出是第5位一定不是0就是1。通过二进制的计算比对：
• oldCap-1 结果是：0000 1111，24-1 ；15，默认大小-1
• newCap-1 结果是：0001 1111，25-1; 31，默认大小*2-1
• 结合上面的两个结论得出：(oldCap-1)& hash = 0000 XXXX,(newCap-1)& hash = 0001 XXXX, 他们差就是 0001 0000， 这个对应的十进制值就是：24 = oldCap; XXXX 表示，低位的结果和1 做& 运算结果是一样的。
• 所以，hash&oldCap !=0 的情况下，index 定位，发生了一个oldCap 的偏移。属于高位偏移的数据。

因此 代码上，在遍历的时候，会出现了 loHead，loTail，hiHead，hiTail； 分别来记录原来的链表。

简单的理解就是原来的index 对应的链表是：tab[i]=A-B-C-D; 扩容后可能结果是：tab[i]=A-C;tab[i+oldCap]=B-D; 使得原本冲突的值，再次分散了。这个就是为什么HashMap的Hash 冲突会比HashTable 低的直接体现。

上面的过程是在HashMap 对应的链表的长度不超过8的时候，会进行的操作，如果链表的长度超过了8并且 HashMap.length>= 64 的时候，那么就会冲链表的结构重新转成 红黑树

1. Get 取值

类目	HashMap	HashTable
index定位	(n-1)& hash	(hash & 0x7FFFFFFF) % tab.length

定位完成之后，返回key和hash 都相同的值。都会遍历 链表。

1. 删除：

   定位过程和Get 取值是一样的。

   拿到 tab[index] 上，如果是链表上的数据，断开next 指针，重连到下一个元素就好了