手撕HashMap
❝在JDK7中HashMap的底层数据结构为：数组+链表 在JDK8中HashMap的底层数据更改为：数组+链表+红黑树 本文以JDK8源码为例！ ❞
在我扒拉那么多大厂面试题目后，发现HashMap的出现频率是非常高的，当然也会拿出一些类似的进行对比解析，比如HashTable、ConCurrentHashMap、LinkedHashMap，不着急我们后面慢慢聊它们。在讲HashMap前我们先简单回忆一下Hash的相关内容。
哈希算法
- 直接定值法：取关键字或者关键字的某个线性函数为哈希地址，即h(key) = key或h(key) = a*key+b;
- 平方取值法：先求出关键字的平方值，然后取出中间几位作为哈希地址。
- 折叠法：将关键字分隔成位数相同的几部分，然后取这几部分的叠加和作为哈希地址。
- 随机数法：选择一个随机函数，取关键字的随机函数值作为Hash地址，通常用于关键字长度不同的场合。
- 除留余数法：取关键字某个不大于Hash表长m的数p除后所得的余数为哈希地址,即h(key)=key%p。p值的的选择很重要，如果p选不好容易产生同义词。由经验可得:p的长度最好为一个不大于表长m的质数、或者不包含小于20的质因数的合数。
- Java中的HashCode:在java中Object类提供了一个HashCode方法，而每个类对于其重写的方案也不相同，这里我们介绍Integer和String类中的hashCode方法:
「Integer类，返回其本身value:」
public static int hashCode(int value) {
return value;
}
「String类: h(key) = s[0] * 31^(n-1) + s[1] * 31^(n-2) + ... + s[n-1]」
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
哈希表
❝给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。在哈希表中进行添加，删除，查找等操作，性能非常高。我们知道哈希表的主干是数组，所以在不考虑哈希冲突的情况下，仅需一次定位即可完成，时间复杂度为O(1)。 ❞
哈希冲突
我们上面介绍了几种计算哈希地址的哈希算法，但是不可避免的是会出现两个不同的元素通过一个哈希函数，会得到相同的哈希地址。具体情况就是，我们在对某个元素进行hash运算，得到一个哈希地址，在进行插入操作的时候，发现该哈希地址已存在别的元素，这就是哈希冲突，也叫做哈希碰撞。
「哈希表和HashMap」哈希表是一种逻辑数据结构，HashMap是Java中的一种数据类型（结构类型集合），它通过代码实现了哈希表这种数据结构，并在此结构上定义了一系列操作。
HashMap的一些属性
「我们先来了解一下HashMap中源码的一些基本属性:」
// 默认容量，默认为16，必须是2的幂
static final int DEFAULT_INITIAL_CAPACITY = 1<< 4;
// 最大容量，值是2^30
static final int MAXIMUM_CAPACITY = 1<< 30
// 负载因子，默认的负载因子是0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 解决冲突的数据结构由链表转换成树的阈值，默认为8
static final int TREEIFY_THRESHOLD = 8;
// 解决冲突的数据结构由树转换成链表的阈值，默认为6
static final int UNTREEIFY_THRESHOLD = 6;
/* 当桶中的bin被树化时最小的hash表容量。
* 如果没有达到这个阈值，即hash表容量小于MIN_TREEIFY_CAPACITY，当桶中bin的数量太多时会执行resize扩容操作。
* 这个MIN_TREEIFY_CAPACITY的值至少是TREEIFY_THRESHOLD的4倍。
*/
static final int MIN_TREEIFY_CAPACITY = 64;
//table数组，大小在resize()中初始化
transient Node<K,V>[] table;
//元素个数
transient int size;
//容量阈值(元素个数大于等于该值时会自动扩容)
int threshold;
「table数组里面存放的是Node对象，Node是HashMap的一个内部类，也可以说是数据节点。」
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
「四个构造函数」
1：
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
构造一个空的HashMap，具有默认的初始容量（16）和默认负载系数（0.75）。
2：
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
构造一个空的HashMap，具有指定的初始容量和默认负载系数(0.75)
参数：initialCapacity -指定初始容量
异常：IllegalArgumentException -如果初始容量为**负数**
3：
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
构造一个空的HashMap，具有指定的初始容量和负载因子。
参数：initialCapacity - 初始容量
loadFactor - 负载因子
异常：IllegalArgumentException - 如果初始容量为负值或负载系数为**非负值**
4：
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
构造一个新的HashMap与指定的相同的映射Map。该HashMap与默认负载因数(0.75)和初始容量足以容纳映射在指定Map创建。
参数：m - 其映射将放置在此映射中的映射。
异常：NullPointerException - 如果指定的地图为空
HashMap的真面目##
❝JDK8的是数组+链表+红黑树 一个数组，然后结点类型是链表，在链表的元素大于8的时候，会变成红黑树（当数组长度大于64并且链表长度大于8时，才会转换为红黑树。 如果链表长度大于8，但是数组长度小于64时，还是会进行扩容操作，不会转换为红黑树。因为数组的长度较小，应该尽量避开红黑树。因为红黑树需要进行左旋，右旋，变色操作来保持平衡，所以当数组长度小于64，使用数组加链表比使用红黑树查询速度要更快、效率要更高） 在红黑树的元素小于6的时候会变成链表（这里需要注意，不是元素小于6的时候一定会变成链表，只有resize的时候才会根据UNTREEIFY_THRESHOLD 进行转换，同样也不是到8的时候就变成红黑树（不是等到扩容的时候） 链表与红黑树的转换详情）元素进行尾插HaspMap的数组默认大小为16数组也叫做Hash桶。 ❞
三个基本参数：
- capacity:当前数组的容量，默认为16，可用扩容，每次扩容为原来的二倍，而且该值始终为2的幂次方。
- loadFactor：负载因子，默认为0.75。
- threshold：扩容的阈值，其值等于capacity*loadFactor。
「负载因子决定着哈希表的扩容和冲突，负载因子调高会导致哈希冲突的概率增高和查询速度变慢。」
Table数组的初始化：
我们前面提到过，哈希表的主体是数组，那么HashMap的主体就是一个Node类型的table数组，而且table数组的长度永远是2的幂次方,它的具体算法就是由下面代码实现的，这是一个非常巧妙的算法。
/*得到一个大于或者等于cap的最小的2的幂，用来作为阈值*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
❝"|"按位或：按照所给数二进制位进行计算，只要有一个为1则对应位位1！ “>>“带符号右移：低位移除（舍弃），高位的空位补符号！ “>>>”无符号右移：低位移除（舍弃），高位的空位补零！ ❞
「上述算法让最高位的1后面的位全变为1，再进行n+1操作，那么最终将会返回一个大于或者等于cap的最小的2的幂的结果。」
int cap = 64;
System.out.println(Integer.toBinaryString(cap)); ===》1000000
int n = cap - 1;
System.out.println(Integer.toBinaryString(n)); ===》111111
n |= n >>> 1;
System.out.println(Integer.toBinaryString(n)); ===》111111
n |= n >>> 2;
System.out.println(Integer.toBinaryString(n)); ===》111111
n |= n >>> 4;
System.out.println(Integer.toBinaryString(n)); ===》111111
n |= n >>> 8;
System.out.println(Integer.toBinaryString(n)); ===》111111
n |= n >>> 16;
System.out.println(Integer.toBinaryString(n)); ===》111111
System.out.println(n+1); ===》64
「这里的cap-1操作也是为了使结果达到这一条件，如果不是cap-1，而是直接使用cap进行操作最终输出的将是1111111,也就是128。很明显这并不是最终结果！」
从前面HashMap的构造函数来看，当我们调用HashMap有关的设置初始容量的构造方法的时候，它会调用tableSizeFor(int cap)方法对初始容量数据进行规格化。其实在刚初始化一个HashMap的时候，它的table是为null的，通过它的构造函数就可以看出，它是没有对table进行相应的初始化赋值的，在进行put操作的时候通过调用resize()方法进行初始化，且其大小始终为2的幂次方！
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
Put操作
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; //局部tab指向全局的hash数组
Node<K,V> p; //key所在位置的元素
int n, i;//n为数组长度，i为索引
// 如果tab为空,或长度为0，则通过resize()函数初始化table数组
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//若该位置不存在元素，则直接新建结点插入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//否则，发生哈希碰撞
else {
Node<K,V> e; //e为临时结点，指向碰撞结点
K k; //值
//如果hash值，和key值相等，则第一个结点就是碰撞结点，则用e指向p
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果该结点是，树结点，则调用相应的红黑树的插入方法
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//遍历链表
for (int binCount = 0; ; ++binCount) {
//如果在链表中不包含要插入的结点，即找不到同key元素，则选择新建结点，通过尾插法插入
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//如果链表长度已经大于或者等于树化阈值，则将链表转为红黑树或进行扩容操作，只有当数组结点元素数量大于64且链表结点数量大于8才会进行化树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果在链表中包含要插入的结点，即找到了同key元素，则终止遍历操作，此时e指向该结点
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//如果e不为null，则说明在该链表中要插入的位置已存在结点元素，则更新旧值
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//为LinkedHashMap留的后路
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//如果结点元素数量大于阈值，则进行扩容
if (++size > threshold)
resize();
//为LinkedHashMap留的后路
afterNodeInsertion(evict);
return null;
}
「尽管有注释源码看着还是不太爽？我们来图解源码：」
Put操作就是存放元素的操作，它有着初始化Table数组的作用，而且由于它的位置计算算法，它是不保证插入数据的顺序，既然是存放元素的操作那么位置计算算法就是其关键，那么我们接下来就来探究一下HashMap是如何计算的到自己的哈希地址的。
tab[index = (n - 1) & hash] //这里的n是tab的长度
「1.为什么要通过（数组长度-1）位与hash值得到具体的哈希地址？」
首先明确jdk中定义int占4个字节32位,其大概有40的映射空间，我们内存难以支撑如此庞大的数据量，而且我们也希望在插入元素的时候位置尽可能分布的均匀些，使得每个位置上都只存在一个或者较少的数据，这样我们在取值时就可以更快的得到这个元素。所以我们在得到相应的hash值后应该对其经行相应处理，我们首先想到的肯定是进行（hash % n）的取模操作，而源码采用的是(hash & (n-1))值得到具体的哈希地址。那么这两种操作有什么区别呢？
System.out.println(126&15); ===》12
System.out.println(126%16); ===》12
其实当数组长度始终为2的幂次方时，对于哈希地址的最终的取值而言这两种操作是没有区别的，只是由于位运算直接对内存数据进行操作，所以它是相对较快的。
「2.在进行Put操作时是如何得到Hash值的，为什么要有(h = key.hashCode()) ^ (h >>> 16)这个操作？？？」
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
❝由源码可以看出，HashMap中是通过HashCode方法算出的Hash值，然后与其高十六位做异或运算，得到最终的哈希值，这样可以增加随机性。具体的原理是： 我们都知道jdk中规定int占4个字节32位，那么右移16位后得到的正好是高十六位，然后再与自己进行异或就是自己的高十六位与低十六位做异或，这样做不仅可以加大低十六的随机性，而且可以使低位掺杂高位的部分特征，让高位有些参与感。 ❞
❝这一步的存在，是有很大的实际意义的，我们上面提到过，「hash地址其实是（数组长度-1）&hash值得到的」，而且在绝大多数情况下数组长度都是小于2^16的，那么这时hash地址始终都是(数组长度-1)与hash值的低十六位进行位运算得到的，这就会导致哈希冲突的概率增大，所以这时源Hash值的低十六位与高十六位进行异或后得到的新低十六位可以增加最终的随机性，减少哈希冲突的产生。 ❞
「3.把数组长度设计成2的幂次方的原因:」
- 当将数组长度设置为2的幂次方时，使用位与和取模的结果相同，也就是当数组长度为2的幂次方时，可以使用位运算替代取模运算，即h&(length-1)==h%length，提高效率。
- 当数组长度为2得幂次方时，其长度length-1后得到得数为奇数，也就是说其二进制位数上全为1，这样就可以使得每个位置都可以参与最终的位与运算，相反，当数组长度不为2的幂次方时，在进行length-1后，其最后一位必定为0，进行位与运算得到的最终结果的最后一位也必将为0，不仅会导致最终地址的映射范围减小，从而导致哈希冲突的增加，而且也会导致空间浪费和位运算操作和取模操作结果不同，即h&(length-1)！=h%length。
continue
腾讯云开发者
