HashMap如何与冲突作斗争

HashMap如何与冲突作斗争

文章目录

• • 哈希表
  • • 1.1概念
    • 1.2哈希冲突
    • • 1.21冲突-避免-负载因子调节（重点）
    • 1.22哈希冲突-解决
    • • 1.23 冲突-解决-闭散列
      • 1.23 冲突-解决-开散列/哈希桶（重点）
    • 1.3一些有助于了解学习HashMap的文章

哈希表

1.1概念

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O( log2N)，搜索的效率取决于搜索过程中元素的比较次数。
理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。
当向该结构中:

• 插入元素
  根据待插入元素的关键码，以此函数计算出存储位置并存放至计算出的位置
• 搜索元素
  对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功
  该方式即为哈希（散列）方法，哈希方法中使用的转换函数称为哈希（散列）函数，构造出来的结构称为哈希表（HashTable）（散列表）。

1.2哈希冲突

首先，我们需要明确一点，由于我们哈希表底层数组的容量往往是小于实际要存储的关键字的数量的，这就导致一个问题，冲突的发生是必然的，但我们能做的应该是尽量的降低冲突率
引起哈希冲突的一个可能原因就是哈希函数设计不合理，哈希函数有其自己的设计原则，感兴趣的同学可以自己去了解一下。

1.21冲突-避免-负载因子调节（重点）

哈希表中已有关键字的个数是不可以改变的而降低负载因子其实就是增加哈希表中数组长度的大小(resize)
HashMap底层负载因子默认大小：

• 什么时候需要扩容？
  我们在调用HashMap的put方法时，如果当前的数组（HashMap的底层数据结构就是数组）为null，或者数组的长度大于阈值（数组长度*负载因子）时，会发生扩容。数组为null时，会扩容成默认长度或指定长度；数组超过阈值时，会扩容成原数组的两倍。

为什么是负载因子0.75呢？可以看上面负载因子是如何计算的，我认为这是一种折中的思想，如果负载因子太小，就会造成空间的浪费，太大那么冲突的概率就会更大。（这是我自己认为的，具体原因请大家子行了解）。
数组一旦初始化后大小就无法改变了，所以就有了 ArrayList这种“动态数组”，可以自动扩容。
在Java中，数组是无法自动扩容的，所以如果要扩容的话，就需要新建一个大的数组，然后把小数组的元素复制过去。

-resize方法的源码

//jdk1.7 resize源码
// newCapacity为新的容量
void resize(int newCapacity) {// 小数组，临时过度下Entry[] oldTable = table;// 扩容前的容量int oldCapacity = oldTable.length;// MAXIMUM_CAPACITY 为最大容量，2 的 30 次方 = 1<<30if (oldCapacity == MAXIMUM_CAPACITY) {// 容量调整为 Integer 的最大值 0x7fffffff（十六进制）=2 的 31 次方-1threshold = Integer.MAX_VALUE;return;}// 初始化一个新的数组（大容量）Entry[] newTable = new Entry[newCapacity];// 把小数组的元素转移到大数组中transfer(newTable, initHashSeedAsNeeded(newCapacity));// 引用新的大数组table = newTable;// 重新计算阈值threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

关于扩容后为什么容量要保持2的幂次方，这也是一个面试经常会被问的问题，这个问题大家自行了解。网上有很多，讲的都很好，在此不赘述

1.22哈希冲突-解决

解决哈希冲突两种常见方法是：闭散列和开散列

1.23 冲突-解决-闭散列

也叫开放地址法，当发生哈希冲突时，如果哈希表未被装满，那说明哈希表中必然有空位置，于是我们就可以把key存放到发生冲突位置的“下一个”空位置中，如何寻找下一个位置？

1.23 冲突-解决-开散列/哈希桶（重点）

开散列法又叫链地址法，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。单链表中插入是采用尾插法（jdk1.8开始）。链表长度超过8，这个链表会变为红黑树。
从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。
开散列，可以认为是把一个在大集合中的搜索问题转化为在小集合中做搜索了。
具体细节可参考此文：
hashmap如何解决哈希冲突

1. HashMap 和 HashSet 即 java 中利用哈希表实现的 Map 和 Set
2. java 中使用的是哈希桶方式解决冲突的
3. java 会在冲突链表长度大于一定阈值后，将链表转变为搜索树（红黑树）
4. java 中计算哈希值实际上是调用的类的 hashCode 方法**，进行 key 的相等性比较是调用 key 的 equals 方法。所以如果要用自定义类作为 HashMap 的 key 或者 HashSet 的值，必须覆写 hashCode 和 equals 方 法，而且要做到 equals 相等的对象，hashCode 一定是一致的。**

1.3一些有助于了解学习HashMap的文章

详细的HashMap源码解析

HashMap的底层实现原理