飞利浦·斯塔克|重温数据结构经典：HashMap原理删除

文章图片

昨天难得没那么多扯淡的会议，有时间好好重温一下数据结构的知识，在此跟大家一起重温一下数据结构经典：hashCode及HashMap原理
一、HashCode为什么使用31作为乘数1、选择数字31是因为它是一个奇质数，如果选择一个偶数会在乘法运算中产生溢出，导致数值信息丢失，因为乘二相当于移位运算。选择质数的优势并不是特别的明显，但这是一个传统。
2、数字31有一个很好的特性，即乘法运算可以被移位和减法运算取代，来获取更好的性能：31 * i == (i << 5) - i ，现代的 Java 虚拟机可以自动地完成这个优化。
二、数组与链表的特点数组的特点是：寻址容易，插入和删除困难
链表的特点是：寻址困难，插入和删除容易
三、HashMap原理

允许null健及null值， null健，值为0
HashMap 不保证键值对的顺序，操作时，键值对的顺序会发生变化
HashMap是非线程安全类，在多线程环境下会发生问题
HashMap是JDK 1.2时推出的，底层基于散列算法实现
在JDK 1.8中涉及比较多：1、散列表实现、2、扰动函数、3、初始化容量、4、负载因子、5、扩容元素拆分、6、链表树化、7、红黑树、8、插入、9、查找、10、删除、11、遍历、12、分段锁等

(1) 扰动函数static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

扰动函数就是为了增加随机性，让数据元素更加均衡地散列，减少碰撞。

(2) 负载因子static final float DEFAULT_LOAD_FACTOR = 0.75f;
负载因子，可以理解成一辆车可承重重量超过某个阀值时，把货放到新的车上。在 HashMap 中，负载因子决定了数据量多少了以后进行扩容
0.75 是一个默认构造值，在创建 HashMap 也可以调整，如何希望用更多的空间换取时间，可以把负载因子调得更小一些，减少碰撞。
(3) 扩容元素拆分扩容最直接的问题，就是需要把元素拆分到新的数组中，在JDK1.7中，会重新计算哈希值，但在JDK1.8后，进行了优化，

扩容时计算出新的newCap、newThr ，这是两个单词的缩写，一个是Capacity，另一个是阀Threshold
newCap用于创新的数组桶 new Node[newCap
;
随着扩容后，原来那些因为哈希碰撞，存放成链表和红黑树的元素，都需要进行拆分存放到新的位置中

(4) 数据迁移(5) 数据插入

首先进行哈希值的扰动，获取一个新的哈希值。 (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
判断tab是否为空或者长度为0 ，如果是则进行扩容操作。
if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length;
根据哈希值计算下标，如果对应小标正好没有存放数据，则直接插入即可否则需要覆盖。 tab[i = (n - 1) & hash
)
判断tab[i
是否为树节点，否则向链表中插入数据，否则向树中插入节点。
如果链表中插入节点的时候，链表长度大于等于8 ，则需要把链表转换为红黑树。 treeifyBin(tab hash);
最后所有元素处理完成后，判断是否超过阈值；threshold ，超过则扩容。
treeifyBin是一个链表转树的方法，但不是所有的链表长度为8后都会转成树，还需要判断存放key值的数组桶长度是否小于64 MIN_TREEIFY_CAPACITY 。如果小于则需要扩容，扩容后链表上的数据会被拆分散列的相应的桶节点上，也就把链表长度缩短了。

(6) 链表树化

链表树化的条件有两点；链表长度大于等于8、桶容量大于64 ，否则只是扩容，不会树化。
链表树化的过程中是先由链表转换为树节点，此时的树可能不是一颗平衡树。同时在树转换过程中会记录链表的顺序， tl.next = p ，这主要方便后续树转链表和拆分更方便。
链表转换成树完成后，再进行红黑树的转换。先简单介绍下，红黑树的转换需要染色和旋转，以及比对大小。在比较元素的大小中，有一个比较有意思的方法， tieBreakOrder加时赛，这主要是因为HashMap没有像TreeMap那样本身就有Comparator的实现。