江苏龙网

  1. 主页 > 生活百科 > >

HashMap的底层数据结构( 二 )

HashMap


四、HashMap是如何解决hash碰撞问题hash冲突问题，链表+红黑树，O(n)和O(logN) 。
hashmap采用的就是链地址法（拉链法），jdk1.7中 ， 当冲突时，在冲突的地址上生成一个链表，将冲突的元素的key ， 通过equals进行比较，相同即覆盖，不同则添加到链表上 ， 此时如果链表过长，效率就会大大降低，查找和添加操作的时间复杂度都为O(n)；但是在jdk1.8中如果链表长度大于8，链表就会转化为红黑树 ， 时间复杂度也降为了O(logn)，性能得到了很大的优化 。

HashMap的底层数据结构

文章插图
HashMapJDK1.8链表和红黑树转化
HashMap的底层数据结构

文章插图
五、HashMap是如何进行扩容的HashMap底层是一个数组 ， 当这个数组满了之后，他就会自动进行扩容，变成一个更大数组 。
1、JDK1.7下的扩容机制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(newTable, initHashSeedAsNeeded(newCapacity));table = newTable;threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);}代码中可以看到，如果原有table长度已经达到了上限，就不再扩容了 。如果还未达到上限，则创建一个新的table，并调用transfer方法：
/*** Transfers all entries from current table to newTable.*/void transfer(Entry[] newTable, boolean rehash) {int newCapacity = newTable.length;for (Entry<K,V> e : table) {while(null != e) {Entry<K,V> next = e.next;//注释1if (rehash) {e.hash = null == e.key ? 0 : hash(e.key);}int i = indexFor(e.hash, newCapacity); //注释2e.next = newTable[i];//注释3newTable[i] = e;//注释4e = next;//注释5}}}transfer方法的作用是把原table的Node放到新的table中，使用的是头插法，也就是说 ， 新table中链表的顺序和旧列表中是相反的，在HashMap线程不安全的情况下，这种头插法可能会导致环状节点 。
2、JDK1.8下的扩容机制源码如下：
final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;int oldCap = (oldTab == null) ? 0 : oldTab.length; // 记录原来的数组长度int oldThr = threshold;int newCap, newThr = 0;if (oldCap > 0) {if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold // 重新计算TREEIFY_THRESHOLD}else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;else {// zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold = newThr;@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;if (oldTab != null) {// 重新计算原来链表中的值的hash值在新表对应的hash值for (int j = 0; j < oldCap; ++j) {Node<K,V> e;if ((e = oldTab[j]) != null) {oldTab[j] = null;if (e.next == null)// 如果元素e的下一个位置没有值，则说明可以存放元素newTab[e.hash & (newCap - 1)] = e;else if (e instanceof TreeNode) // 如果已经是红黑树的节点，那就对其重新划分((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else { // preserve order// loHead: 下标不变情况下的链表头// loTAIl: 下标不变情况下的链表尾// hiHead: 下标改变情况下的链表头// hiTail: 下标改变情况下的链表尾// 如果Node<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {next = e.next;if ((e.hash & oldCap) == 0) { // 元素e的最新hash如果与原来的值与计算之后如果值为0，就说明是使用原来的index// 尾插法插入元素eif (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {// 与运算不等于0则说明使用新的indexif (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);if (loTail != null) {loTail.next = null;newTab[j] = loHead;}if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;}
正常情况下 ， 计算节点在table中的下标的方法是：hash&(oldTable.length-1) ， 扩容之后 ， table长度翻倍 ， 计算table下标的方法是hash&(newTable.length-1) ， 也就是hash&(oldTable.length*2-1)，于是我们有了这样的结论：这新旧两次计算下标的结果，要不然就相同，要不然就是新下标等于旧下标加上旧数组的长度 。


推荐阅读


上一篇：Spring Cloud Gateway提供的简易网关实现方式，你使用过吗？

下一篇：如何利用Kurukshetra以交互式的方式学习如何进行安全编码