|
功能实现-方法 HashMap的内部功能实现很多，本文主要从根据key获取哈希桶数组索引位置、put方法的详细执行、扩容过程三个具有代表性的点深入展开讲解。 1. 确定哈希桶数组索引位置不管增加、删除、查找键值对，定位到哈希桶数组的位置都是很关键的第一步。前面说过HashMap的数据结构是数组和链表的结合，所以我们当然希望这个HashMap里面的元素位置尽量分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，不用遍历链表，大大优化了查询的效率。HashMap定位数组索引位置，直接决定了hash方法的离散性能。先看看源码的实现(方法一+方法二): - 方法一：
- static final int hash(Object key) { //jdk1.8 & jdk1.7
- int h;
- // h = key.hashCode() 为第一步 取hashCode值
- // h ^ (h >>> 16) 为第二步 高位参与运算
- return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
- }
- 方法二：
- static int indexFor(int h, int length) { //jdk1.7的源码，jdk1.8没有这个方法，但是实现原理一样的
- return h & (length-1); //第三步 取模运算
- }
这里的Hash算法本质上就是三步：取key的hashCode值、高位运算、取模运算。 对于任意给定的对象，只要它的hashCode()返回值相同，那么程序调用方法一所计算得到的Hash码值总是相同的。我们首先想到的就是把hash值对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。但是，模运算的消耗还是比较大的，在HashMap中是这样做的：调用方法二来计算该对象应该保存在table数组的哪个索引处。 这个方法非常巧妙，它通过h & (table.length -1)来得到该对象的保存位，而HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当length总是2的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。 在JDK1.8的实现中，优化了高位运算的算法，通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。 下面举例说明下，n为table的长度。  2. 分析HashMap的put方法HashMap的put方法执行过程可以通过下图来理解，自己有兴趣可以去对比源码更清楚地研究学习。  ①.判断键值对数组table是否为空或为null，否则执行resize()进行扩容； ②.根据键值key计算hash值得到插入的数组索引i，如果table==null，直接新建节点添加，转向⑥，如果table不为空，转向③； ③.判断table的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals； ④.判断table 是否为treeNode，即table 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤； ⑤.遍历table，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可； ⑥.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。 JDK1.8HashMap的put方法源码如下: - 1 public V put(K key, V value) {
- 2 // 对key的hashCode()做hash
- 3 return putVal(hash(key), key, value, false, true);
- 4 }
- 5
- 6 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
- 7 boolean evict) {
- 8 Node<K,V>[] tab; Node<K,V> p; int n, i;
- 9 // 步骤①：tab为空则创建
- 10 if ((tab = table) == null || (n = tab.length) == 0)
- 11 n = (tab = resize()).length;
- 12 // 步骤②：计算index，并对null做处理
- 13 if ((p = tab[i = (n - 1) & hash]) == null)
- 14 tab[i] = newNode(hash, key, value, null);
- 15 else {
- 16 Node<K,V> e; K k;
- 17 // 步骤③：节点key存在，直接覆盖value
- 18 if (p.hash == hash &&
- 19 ((k = p.key) == key || (key != null && key.equals(k))))
- 20 e = p;
- 21 // 步骤④：判断该链为红黑树
- 22 else if (p instanceof TreeNode)
- 23 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
- 24 // 步骤⑤：该链为链表
- 25 else {
- 26 for (int binCount = 0; ; ++binCount) {
- 27 if ((e = p.next) == null) {
- 28 p.next = newNode(hash, key,value,null);
- //链表长度大于8转换为红黑树进行处理
- 29 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
- 30 treeifyBin(tab, hash);
- 31 break;
- 32 }
- // key已经存在直接覆盖value
- 33 if (e.hash == hash &&
- 34 ((k = e.key) == key || (key != null && key.equals(k)))) break;
- 36 p = e;
- 37 }
- 38 }
- 39
- 40 if (e != null) { // existing mapping for key
- 41 V oldValue = e.value;
- 42 if (!onlyIfAbsent || oldValue == null)
- 43 e.value = value;
- 44 afterNodeAccess(e);
- 45 return oldValue;
- 46 }
- 47 }
- 48 ++modCount;
- 49 // 步骤⑥：超过最大容量 就扩容
- 50 if (++size > threshold)
- 51 resize();
- 52 afterNodeInsertion(evict);
- 53 return null;
- 54 }
3. 扩容机制扩容(resize)就是重新计算容量，向HashMap对象里不停的添加元素，而HashMap对象内部的数组无法装载更多的元素时，对象就需要扩大数组的长度，以便能装入更多的元素。当然Java里的数组是无法自动扩容的，方法是使用一个新的数组代替已有的容量小的数组，就像我们用一个小桶装水，如果想装更多的水，就得换大水桶。 我们分析下resize的源码，鉴于JDK1.8融入了红黑树，较复杂，为了便于理解我们仍然使用JDK1.7的代码，好理解一些，本质上区别不大，具体区别后文再说。 - 1 void resize(int newCapacity) { //传入新的容量
- 2 Entry[] oldTable = table; //引用扩容前的Entry数组
- 3 int oldCapacity = oldTable.length;
- 4 if (oldCapacity == MAXIMUM_CAPACITY) { //扩容前的数组大小如果已经达到最大(2^30)了
- 5 threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
- 6 return;
- 7 }
- 8
- 9 Entry[] newTable = new Entry[newCapacity]; //初始化一个新的Entry数组
- 10 transfer(newTable); //！！将数据转移到新的Entry数组里
- 11 table = newTable; //HashMap的table属性引用新的Entry数组
- 12 threshold = (int)(newCapacity * loadFactor);//修改阈值
- 13 }
这里就是使用一个容量更大的数组来代替已有的容量小的数组，transfer()方法将原有Entry数组的元素拷贝到新的Entry数组里。 - 1 void transfer(Entry[] newTable) {
- 2 Entry[] src = table; //src引用了旧的Entry数组
- 3 int newCapacity = newTable.length;
- 4 for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
- 5 Entry<K,V> e = src[j]; //取得旧Entry数组的每个元素
- 6 if (e != null) {
- 7 src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
- 8 do {
- 9 Entry<K,V> next = e.next;
- 10 int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置
- 11 e.next = newTable[i]; //标记[1]
- 12 newTable[i] = e; //将元素放在数组上
- 13 e = next; //访问下一个Entry链上的元素
- 14 } while (e != null);
- 15 }
- 16 }
- 17 }
newTable的引用赋给了e.next，也就是使用了单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置；这样先放在一个索引上的元素终会被放到Entry链的尾部(如果发生了hash冲突的话），这一点和Jdk1.8有区别，下文详解。在旧数组中同一条Entry链上的元素，通过重新计算索引位置后，有可能被放到了新数组的不同位置上。 下面举个例子说明下扩容过程。假设了我们的hash算法就是简单的用key mod 一下表的大小（也就是数组的长度）。其中的哈希桶数组table的size=2， 所以key = 3、7、5，put顺序依次为 5、7、3。在mod 2以后都冲突在table[1]这里了。这里假设负载因子 loadFactor=1，即当键值对的实际大小size 大于 table的实际大小时进行扩容。接下来的三个步骤是哈希桶数组 resize成4，然后所有的Node重新rehash的过程。  下面我们讲解下JDK1.8做了哪些优化。经过观测可以发现，我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。看下图可以明白这句话的意思，n为table的长度，图（a）表示扩容前的key1和key2两种key确定索引位置的示例，图（b）表示扩容后key1和key2两种key确定索引位置的示例，其中hash1是key1对应的哈希与高位运算结果。  元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：  因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”，可以看看下图为16扩充为32的resize示意图：  这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK1.8新增的优化点。有一点注意区别，JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，但是从上图可以看出，JDK1.8不会倒置。有兴趣的同学可以研究下JDK1.8的resize源码，写的很赞，如下: - 1 final Node<K,V>[] resize() {
- 2 Node<K,V>[] oldTab = table;
- 3 int oldCap = (oldTab == null) ? 0 : oldTab.length;
- 4 int oldThr = threshold;
- 5 int newCap, newThr = 0;
- 6 if (oldCap > 0) {
- 7 // 超过最大值就不再扩充了，就只好随你碰撞去吧
- 8 if (oldCap >= MAXIMUM_CAPACITY) {
- 9 threshold = Integer.MAX_VALUE;
- 10 return oldTab;
- 11 }
- 12 // 没超过最大值，就扩充为原来的2倍
- 13 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
- 14 oldCap >= DEFAULT_INITIAL_CAPACITY)
- 15 newThr = oldThr << 1; // double threshold
- 16 }
- 17 else if (oldThr > 0) // initial capacity was placed in threshold
- 18 newCap = oldThr;
- 19 else { // zero initial threshold signifies using defaults
- 20 newCap = DEFAULT_INITIAL_CAPACITY;
- 21 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
- 22 }
- 23 // 计算新的resize上限
- 24 if (newThr == 0) {
- 25
- 26 float ft = (float)newCap * loadFactor;
- 27 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
- 28 (int)ft : Integer.MAX_VALUE);
- 29 }
- 30 threshold = newThr;
- 31 @SuppressWarnings({"rawtypes"，"unchecked"})
- 32 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
- 33 table = newTab;
- 34 if (oldTab != null) {
- 35 // 把每个bucket都移动到新的buckets中
- 36 for (int j = 0; j < oldCap; ++j) {
- 37 Node<K,V> e;
- 38 if ((e = oldTab[j]) != null) {
- 39 oldTab[j] = null;
- 40 if (e.next == null)
- 41 newTab[e.hash & (newCap - 1)] = e;
- 42 else if (e instanceof TreeNode)
- 43 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
- 44 else { // 链表优化重hash的代码块
- 45 Node<K,V> loHead = null, loTail = null;
- 46 Node<K,V> hiHead = null, hiTail = null;
- 47 Node<K,V> next;
- 48 do {
- 49 next = e.next;
- 50 // 原索引
- 51 if ((e.hash & oldCap) == 0) {
- 52 if (loTail == null)
- 53 loHead = e;
- 54 else
- 55 loTail.next = e;
- 56 loTail = e;
- 57 }
- 58 // 原索引+oldCap
- 59 else {
- 60 if (hiTail == null)
- 61 hiHead = e;
- 62 else
- 63 hiTail.next = e;
- 64 hiTail = e;
- 65 }
- 66 } while ((e = next) != null);
- 67 // 原索引放到bucket里
- 68 if (loTail != null) {
- 69 loTail.next = null;
- 70 newTab[j] = loHead;
- 71 }
- 72 // 原索引+oldCap放到bucket里
- 73 if (hiTail != null) {
- 74 hiTail.next = null;
- 75 newTab[j + oldCap] = hiHead;
- 76 }
- 77 }
- 78 }
- 79 }
- 80 }
- 81 return newTab;
- 82 }
| 
发表于 2021-4-25 16:53:13
收藏
