深入理解HashMap的扩容机制

2024-07-05 00:31| 来源: 网络整理| 查看: 265

深入理解HashMap的扩容机制

——原创：转载请注明出处 http://www.cnblogs.com/yanzige/p/8392142.html

注：本文分两部分讲解，第一部分讲解Java7，第二部分讲解Java8

Java 7 中Hashmap扩容机制

一、什么时候扩容：

网上总结的会有很多，但大多都总结的不够完整或者不够准确。大多数可能只说了满足我下面条件一的情况。

扩容必须满足两个条件：

1、存放新值的时候当前已有元素的个数必须大于等于阈值

2、存放新值的时候当前存放数据发生hash碰撞（当前key计算的hash值换算出来的数组下标位置已经存在值）

二、下面我们看源码，如下：

首先是put()方法

public V put(K key, V value) { 　　　　//判断当前Hashmap(底层是Entry数组)是否存值（是否为空数组）　　　　if (table == EMPTY_TABLE) { 　　　　　　inflateTable(threshold);//如果为空，则初始化　　　　} 　　　　　　　　//判断key是否为空　　　　if (key == null) 　　　　　　return putForNullKey(value);//hashmap允许key为空　　　　　　　　//计算当前key的哈希值　　　　　　　　int hash = hash(key); 　　　　//通过哈希值和当前数据长度，算出当前key值对应在数组中的存放位置　　　　int i = indexFor(hash, table.length); 　　　　for (Entry e = table[i]; e != null; e = e.next) { 　　　　　　Object k; 　　　　　　//如果计算的哈希位置有值（及hash冲突），且key值一样，则覆盖原值value，并返回原值value 　　　　　　if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 　　　　　　　　V oldValue = e.value; 　　　　　　　　e.value = value; 　　　　　　　　e.recordAccess(this); 　　　　　　　　return oldValue; 　　　　　　} 　　　　} 　　　　modCount++; 　　　　//存放值的具体方法　　　　addEntry(hash, key, value, i); 　　　　return null; 　　}

在put()方法中有调用addEntry()方法，这个方法里面是具体的存值，在存值之前还要判断是否需要扩容

void addEntry(int hash, K key, V value, int bucketIndex) { 　　　　//1、判断当前个数是否大于等于阈值　　　　//2、当前存放是否发生哈希碰撞　　　　//如果上面两个条件否发生，那么就扩容　　　　if ((size >= threshold) && (null != table[bucketIndex])) { 　　　　　　//扩容，并且把原来数组中的元素重新放到新数组中　　　　　　resize(2 * table.length); 　　　　　　hash = (null != key) ? hash(key) : 0; 　　　　　　bucketIndex = indexFor(hash, table.length); 　　　　} 　　　　createEntry(hash, key, value, bucketIndex); 　　}

贴上Entry类的源码

static class Entry implements Map.Entry { final K key; V value; Entry next;// 通过next构成一个单向链表 int hash; /** * Creates new entry. */ Entry(int h, K k, V v, Entry n) { value = v; next = n; key = k; hash = h; } ｝

如果需要扩容，调用扩容的方法resize()

void resize(int newCapacity) { 　　　　Entry[] oldTable = table; 　　　　int oldCapacity = oldTable.length; 　　　　//判断是否有超出扩容的最大值，如果达到最大值则不进行扩容操作　　　　if (oldCapacity == MAXIMUM_CAPACITY) { 　　　　　　threshold = Integer.MAX_VALUE; 　　　　　　return; 　　　　} 　　　　Entry[] newTable = new Entry[newCapacity]; 　　　　// transfer()方法把原数组中的值放到新数组中　　　　transfer(newTable, initHashSeedAsNeeded(newCapacity)); 　　　　//设置hashmap扩容后为新的数组引用　　　　table = newTable; 　　　　//设置hashmap扩容新的阈值　　　　threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); 　　}

transfer()在实际扩容时候把原来数组中的元素放入新的数组中

void transfer(Entry[] newTable, boolean rehash) { 　　　　int newCapacity = newTable.length; 　　　　for (Entry e : table) { 　　　　　　while(null != e) { 　　　　　　　　Entry next = e.next; 　　　　　　　　if (rehash) { 　　　　　　　　　　e.hash = null == e.key ? 0 : hash(e.key); 　　　　　　　　} 　　　　　　　　//通过key值的hash值和新数组的大小算出在当前数组中的存放位置　　　　　　　　int i = indexFor(e.hash, newCapacity); 　　　　　　　　e.next = newTable[i]; 　　　　　　　　newTable[i] = e; 　　　　　　　　e = next; 　　　　　　} 　　　　} 　　}

JDK7版本及以前使用是：头插法（对比JDK8使用的是尾插法）

注：使用头插法在多线程扩容的时候可能会导致循环指向，从而在获取数据get()的时候陷入死循环，导致线程执行无法结束。

头插法：

　　后来的（新插入的）节点会被插入到头部，并将head节点指向当前新节点，再将当前新节点的next指针指向之前的头部节点，这样整个链表越早插入的就逐渐到了链表的尾部，越晚插入的就存放在了链表的头部。

　　在扩容的时候，先取头部节点，然后把头部节点放到新对应数组下标的链表处，由于头插法，最早取出的节点会被最先放进，并逐步变成链表的最尾部，如果多线程执行扩容，将数组下标3位置处链表存入的A->B->C，扩容时存入到新的数组（假设扩容后A/B/C还在同一个链表上），线程1取第一个节点A被挂起，挂起的A节点的next指向B节点，而线程2扩容将头部B节点（原头部A节点已经被取走，B节点成为原链表的头结点）放入新的链表时，A节点被先放但没有完成，线程2在放入B节点后，B节点的next指向之前放入的A节点，当线程1执行的时候本身A的next指向B，这样就行程了循环引用，最后存入C节点，并将C节点的next指向B，最终就变成C->B->= threshold) && (null != table[bucketIndex])) { resize(2 * table.length); hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); } createEntry(hash, key, value, bucketIndex); } void createEntry(int hash, K key, V value, int bucketIndex) { Entry e = table[bucketIndex]; // bucketIndex 为数组下标，第一个元素进来时table[下标位置]=null,所以对应代码 put(1,1) 上图node第一个节点的 next 就为空 table[bucketIndex] = new Entry(hash, key, value, e);// e表示上一个节点，将上一个节点放到新节点的next处——》并且将新new Entry对象给到当前table[数组下标位置] size++; }

所以这个过程下来，新节点就在链表的头部位置，最早被加入的Entry节点在最尾的位置。

三、总结：

Hashmap的扩容需要满足两个条件：当前数据存储的数量（即size()）大小必须大于等于阈值；当前加入的数据是否发生了hash冲突。

因为上面这两个条件，所以存在下面这些情况

（1）、就是hashmap在存值的时候（默认大小为16，负载因子0.75，阈值12），可能达到最后存满16个值的时候，再存入第17个值才会发生扩容现象，因为前16个值，每个值在底层数组中分别占据一个位置，并没有发生hash碰撞。

（2）、当然也有可能存储更多值（超多16个值，最多可以存27个值）都还没有扩容。原理：前11个值全部hash碰撞，存到数组的同一个位置（虽然hash冲突，但是这时元素个数小于阈值12，并没有同时满足扩容的两个条件。所以不会扩容），[在存入第12个元素的时候，还是存入前面11个元素所在的下标位置，因为存入之前此时比较当前元素个数 11= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash);//该方法判断是扩容还是需要将该链表转红黑树 break; }　　　　　　　　　　　　// 如果存入链表的下一个位置有值，且该key和存入对象“一样”，直接break,将给key相同的node节点赋值给e(在上一步if中已经赋值了)，在外面做统一处理 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break;　　　　　　　　　　　　// 每遍历一次在第一个if((e=p.next) == null)中从头到尾将每一个Node()节点复制给e,然后再将e赋值给p,使得链表完成从头到尾的遍历过程 p = e; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; // 如果不是替换数据存入，而是新增位置存入后，则将map的size进行加1，然后判断容量是否超过阈值，超过则扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }

　　treeifyBin()方法判断是扩容还是将当前链表转红黑树 /** * Replaces all linked nodes in bin at index for given hash unless * table is too small, in which case resizes instead. * 从指定hash位置处的链表nodes头部开始，全部替换成红黑树结构。 * 除非整个数组对象（Map集合）数据量很小（数组长度小于64），该情况下则通过resize()对这个Map进行扩容，而代替将链表转红黑树的操作。 */ final void treeifyBin(HashMap.Node[] tab, int hash) { int n, index; HashMap.Node e; // 如果Map（数组）为空或者当前存入数据数组长度小于64便进行扩容 if (tab == null || (n = tab.length) =7,从0开始，及第8个开始判断是否转化成红黑树），如果数组的长度还小于64的时候，则会扩容数组。如果数组的长度大于等于64的话，才会将该节点的链表转换成树。在扩容完成之后，如果某个节点是树结构，同时现在该节点的node个数小于等于6，则会将该树转为链表。

【本文地址】

公司简介

联系我们