Java容器（四）：HashMap（Java 7）的实现原理

妖狐艹你老母 2022-05-16 03:26 183阅读 0赞

# **一、HashMap的定义和构造函数** #

<code>public class HashMap<K,V>
 extends AbstractMap<K,V>
 implements Map<K,V>, Cloneable, Serializable</code>

HashMap继承自AbstractMap，AbstractMap是Map接口的骨干实现，AbstractMap中实现了Map中最重要最常用和方法，这样HashMap继承AbstractMap就不需要实现Map的所有方法，让HashMap减少了大量的工作。   
而在这里仍然实现Map结构，没有什么作用，应该是为了让map的层次结构更加清晰

### **HashMap的成员变量** ###

int DEFAULT\_INITIAL\_CAPACITY = 16：默认的初始容量为16  
　　int MAXIMUM\_CAPACITY = 1 << 30：最大的容量为 2 ^ 30  
　　float DEFAULT\_LOAD\_FACTOR = 0.75f：默认的加载因子为 0.75f  
　　Entry< K,V>\[\] table：Entry类型的数组，HashMap用这个来维护内部的数据结构，它的**长度由容量决定**  
　　int size：HashMap的大小  
　　int threshold：HashMap的极限容量，**扩容临界点（容量和加载因子的乘积）**

谨记这些成员变量，在HashMap内部经常看到

### **HashMap的四个构造函数** ###

public HashMap()：构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap  
　　public HashMap(int initialCapacity)：构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap  
　　public HashMap(int initialCapacity, float loadFactor)：构造一个带指定初始容量和加载因子的空 HashMap  
　　public HashMap(Map< ? extends K, ? extends V> m)：构造一个映射关系与指定 Map 相同的新 HashMap

这里有两个很重要的参数：**initialCapacity**（初始容量）、**loadFactor**（加载因子），看看JDK中的解释：  
　　HashMap 的实例有两个参数影响其性能：初始容量 和加载因子。  
　　**容量** ：是哈希表中桶的数量，**初始容量只是哈希表在创建时的容量**，实际上就是Entry< K,V>\[\] table的容量  
　　**加载因子** ：是哈希表在**其容量自动增加之前可以达到多满的一种尺度**。它衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。对于使用链表法的散列表来说，查找一个元素的平均时间是O(1+a)，因此如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。系统默认负载因子为0.75，一般情况下我们是无需修改的。  
　　当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约**两倍的桶数**。

# **二、HashMap的数据结构** #

我们知道在Java中最常用的两种结构是数组和模拟指针(引用)，几乎所有的数据结构都可以利用这两种来组合实现，HashMap也是如此。实际上HashMap是一个“链表散列”，如下是它数据结构：   
![这里写图片描述][SouthEast]

从上图我们可以看出HashMap底层实现还是数组，只是数组的每一项都是一条链。其中参数initialCapacity就代表了该数组的长度。下面为HashMap构造函数的源码：

<code> public HashMap(int initialCapacity, float loadFactor) {
 //容量不能小于0
 if (initialCapacity < 0)
 throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
 //容量不能超出最大容量
 if (initialCapacity > MAXIMUM_CAPACITY)
 initialCapacity = MAXIMUM_CAPACITY;
 //加载因子不能<=0 或者 为非数字
 if (loadFactor <= 0 || Float.isNaN(loadFactor))
 throw new IllegalArgumentException("Illegal load factor: " +
 loadFactor);
 
 //计算出大于初始容量的最小 2的n次方作为哈希表table的长度，下面会说明为什么要这样
 int capacity = 1;
 while (capacity < initialCapacity)
 capacity <<= 1;
 
 this.loadFactor = loadFactor;
 //设置HashMap的容量极限，当HashMap的容量达到该极限时就会进行扩容操作
 threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
 //创建Entry数组
 table = new Entry[capacity];
 useAltHashing = sun.misc.VM.isBooted() &&
 (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
 init();
 }</code>

可以看到，这个构造函数主要做的事情就是：   
　　1. 对传入的 容量 和 加载因子进行判断处理   
　　2. 设置HashMap的容量极限   
　　3. 计算出大于初始容量的最小 2的n次方作为哈希表table的长度，然后用该长度创建Entry数组（table），这个是最核心的

可以发现，一个HashMap对应一个Entry数组，来看看Entry这个元素的内部结构：

<code> static class Entry<K,V> implements Map.Entry<K,V> {
 final K key;
 V value;
 Entry<K,V> next;
 int hash;
 
 /**
 * Creates new entry.
 */
 Entry(int h, K k, V v, Entry<K,V> n) {
 value = v;
 next = n;
 key = k;
 hash = h;
 }</code>

Entry是HashMap的一个内部类，它也是维护着一个key-value映射关系，除了key和value，还有**next引用（该引用指向当前table位置的链表），hash值（用来确定每一个Entry链表在table中位置）**

# **三、HashMap的存储实现put（K,V）** #

<code> public V put(K key, V value) {
 //如果key为空的情况
 if (key == null)
 return putForNullKey(value);
 //计算key的hash值
 int hash = hash(key);
 //计算该hash值在table中的下标
 int i = indexFor(hash, table.length);
 //对table[i]存放的链表进行遍历
 for (Entry<K,V> 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;
 }
 }
 
 //修改次数+1
 modCount++;
 //把当前key，value添加到table[i]的链表中
 addEntry(hash, key, value, i);
 return null;
 }</code>

从上面的过程中，我们起码可以发现两点：   
　　1. 如果为null，则调用putForNullKey：**这就是为什么HashMap可以用null作为键的原因**，来看看HashMap是如何处理null键的：

<code> private V putForNullKey(V value) {
 //查找链表中是否有null键
 for (Entry<K,V> e = table[0]; e != null; e = e.next) {
 if (e.key == null) {
 V oldValue = e.value;
 e.value = value;
 e.recordAccess(this);
 return oldValue;
 }
 }
 modCount++;
 //如果链中查找不到，则把该null键插入
 addEntry(0, null, value, 0);
 return null;
 }</code>

<code> void addEntry(int hash, K key, V value, int bucketIndex) {
 if ((size >= threshold) && (null != table[bucketIndex])) {
 resize(2 * table.length);
 //这一步就是对null的处理，如果key为null，hash值为0，也就是会插入到哈希表的表头table[0]的位置
 hash = (null != key) ? hash(key) : 0;
 bucketIndex = indexFor(hash, table.length);
 }
 
 createEntry(hash, key, value, bucketIndex);
 }</code>

2. 如果链中存在该key，则用传入的value覆盖掉旧的value，同时把旧的value返回：**这就是为什么HashMap不能有两个相同的key的原因**

对于hash操作，最重要也是最困难的就是如何通过确定hash的位置，我们来看看HashMap的做法：   
　　首先求得key的hash值：hash(key)

<code> final int hash(Object k) {
 int h = 0;
 if (useAltHashing) {
 if (k instanceof String) {
 return sun.misc.Hashing.stringHash32((String) k);
 }
 h = hashSeed;
 }
 
 h ^= k.hashCode();
 h ^= (h >>> 20) ^ (h >>> 12);
 return h ^ (h >>> 7) ^ (h >>> 4);
 }</code>

这是一个数学计算，可以不用深入，关键是下面这里：   
　　计算该hash值在table中的下标

<code> static int indexFor(int h, int length) {
 return h & (length-1);
 }</code>

对于HashMap的table而言，数据分布需要均匀（最好每项都只有一个元素，这样就可以直接找到），不能太紧也不能太松，太紧会导致查询速度慢，太松则浪费空间。计算hash值后，怎么才能保证table元素分布均与呢？我们会想到取模，但是由于取模的消耗较大，而HashMap是通过&运算符（按位与操作）来实现的：h & (length-1)

在构造函数中存在：capacity <<= 1，这样做总是能够保证HashMap的底层数组长度为2的n次方。当length为2的n次方时，h&(length - 1)就相当于对length取模，而且速度比直接取模快得多，这是HashMap在速度上的一个优化。至于为什么是2的n次方下面解释。  
　　我们回到indexFor方法，该方法仅有一条语句：h&(length - 1)，这句话除了上面的取模运算外还有一个非常重要的责任：均匀分布table数据和充分利用空间。  
　　这里我们假设length为16(2^n)和15，h为5、6、7。  
　　![这里写图片描述][SouthEast 1]  
　　  
　　当length-1 = 14时，6和7的结果一样，这样表示他们在table存储的位置是相同的，也就是产生了碰撞，6、7就会在一个位置形成链表，这样就会导致查询速度降低详细地看看当length-1 = 14 时的情况：  
　　![这里写图片描述][SouthEast 2]  
　　可以看到，这样发生发生的碰撞是非常多的，1,3,5,7,9,11,13都没有存放数据，空间减少，进一步增加碰撞几率，这样就会导致查询速度慢，  
　　分析一下：当length-1 = 14时，二进制的最后一位是0，在&操作时，一个为0，无论另一个为1还是0，最终&操作结果都是0，这就造成了结果的二进制的最后一位都是0，这就导致了所有数据都存储在2的倍数位上，所以说，**所以说当length = 2^n时，不同的hash值发生碰撞的概率比较小，这样就会使得数据在table数组中分布较均匀，查询速度也较快。**  
　　  
　　然后我们来看看计算了hash值，并用该hash值来求得哈希表中的索引值之后，如何把该key-value插入到该索引的链表中：  
　　调用 addEntry(hash, key, value, i) 方法：

<code> void addEntry(int hash, K key, V value, int bucketIndex) {
 //如果size大于极限容量，将要进行重建内部数据结构操作，之后的容量是原来的两倍，并且重新设置hash值和hash值在table中的索引值
 if ((size >= threshold) && (null != table[bucketIndex])) {
 resize(2 * table.length);
 hash = (null != key) ? hash(key) : 0;
 bucketIndex = indexFor(hash, table.length);
 }
 //真正创建Entry节点的操作
 createEntry(hash, key, value, bucketIndex);
 }</code>

<code> void createEntry(int hash, K key, V value, int bucketIndex) {
 Entry<K,V> e = table[bucketIndex];
 table[bucketIndex] = new Entry<>(hash, key, value, e);
 size++;
 }</code>

首先取得bucketIndex位置的Entry头结点，并创建新节点，把该新节点插入到**链表中的头部**，该新节点的next指针指向原来的头结点   
　　   
　　这里有两点需要注意：   
　　一、链的产生   
　　这是一个非常优雅的设计。系统总是将新的Entry对象添加到bucketIndex处。如果bucketIndex处已经有了对象，那么新添加的Entry对象将指向原有的Entry对象，形成一条Entry链，但是若bucketIndex处没有Entry对象，也就是e==null,那么新添加的Entry对象指向null，也就不会产生Entry链了。   
　　二、扩容问题   
　　还记得HashMap中的一个变量吗，threshold，这是容器的容量极限，还有一个变量size，这是指HashMap中键值对的数量，也就是node的数量

<code>threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);</code>

什么时候发生扩容？   
　　当不断添加key-value，size大于了容量极限threshold时，会发生扩容   
　　如何扩容？   
　　扩容发生在resize方法中，也就是扩大数组（桶）的数量，如何扩容参考：[http://blog.csdn.net/jeffleo/article/details/63684953][http_blog.csdn.net_jeffleo_article_details_63684953]

### **我们重新来理一下存储的步骤：** ###

1. 传入key和value，判断key是否为null，如果为null，则调用putForNullKey，以null作为key存储到哈希表中；   
　　2. 然后计算key的hash值，根据hash值搜索在哈希表table中的索引位置，若当前索引位置不为null，则对该位置的Entry链表进行遍历，如果链中存在该key，则用传入的value覆盖掉旧的value，同时把旧的value返回，结束；   
　　3. 否则调用addEntry，用key-value创建一个新的节点，并把该节点插入到该索引对应的链表的头部

# **四、HashMap的读取实现get（key，value）** #

<code> public V get(Object key) {
 //如果key为null，求null键
 if (key == null)
 return getForNullKey();
 // 用该key求得entry
 Entry<K,V> entry = getEntry(key);
 
 return null == entry ? null : entry.getValue();
 }</code>

<code> final Entry<K,V> getEntry(Object key) {
 int hash = (key == null) ? 0 : hash(key);
 for (Entry<K,V> e = table[indexFor(hash, table.length)];
 e != null;
 e = e.next) {
 Object k;
 if (e.hash == hash &&
 ((k = e.key) == key || (key != null && key.equals(k))))
 return e;
 }
 return null;
 }</code>

读取的步骤比较简单，调用hash（key）求得key的hash值，然后调用indexFor（hash）求得hash值对应的table的索引位置，然后遍历索引位置的链表，如果存在key，则把key对应的Entry返回，否则返回null

# **五、HashMap键的遍历，keySet()** #

HashMap遍历的核心代码如下：

<code> private abstract class HashIterator<E> implements Iterator<E> {
 Entry<K,V> next; // next entry to return
 int expectedModCount; // For fast-fail
 int index; // current slot
 Entry<K,V> current; // current entry
 
 //当调用keySet().iterator()时，调用此代码
 HashIterator() {
 expectedModCount = modCount;
 if (size > 0) { // advance to first entry
 Entry[] t = table;
 //从哈希表数组从上到下，查找第一个不为null的节点，并把next引用指向该节点
 while (index < t.length && (next = t[index++]) == null)
 ;
 }
 }
 
 public final boolean hasNext() {
 return next != null;
 }
 
 //当调用next时，会调用此代码
 final Entry<K,V> nextEntry() {
 if (modCount != expectedModCount)
 throw new ConcurrentModificationException();
 Entry<K,V> e = next;
 if (e == null)
 throw new NoSuchElementException();
 
 //如果当前节点的下一个节点为null，从节点处罚往下查找哈希表，找到第一个不为null的节点
 if ((next = e.next) == null) {
 Entry[] t = table;
 while (index < t.length && (next = t[index++]) == null)
 ;
 }
 current = e;
 return e;
 }
 
 public void remove() {
 if (current == null)
 throw new IllegalStateException();
 if (modCount != expectedModCount)
 throw new ConcurrentModificationException();
 Object k = current.key;
 current = null;
 HashMap.this.removeEntryForKey(k);
 expectedModCount = modCount;
 }
 }</code>

从这里可以看出，HashMap遍历时，按哈希表的每一个索引的链表从上往下遍历，由于HashMap的存储规则，最晚添加的节点都有可能在第一个索引的链表中，这就造成了HashMap的遍历时无序的。

[SouthEast]: /images/20220516/9b4341e53e564ff882d0167802c36fe8.png
[SouthEast 1]: /images/20220516/c8086adfcd0b48d6b99685bb2998f411.png
[SouthEast 2]: /images/20220516/7cbc47a638554f00b70d7c81a52a9a89.png
[http_blog.csdn.net_jeffleo_article_details_63684953]: http://blog.csdn.net/jeffleo/article/details/63684953