您现在的位置是：首页 > Java

当前栏目

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

JAVA 容器哈希原理

2023-03-02 11:48:39 时间

# **一、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

猜你喜欢

最长无重复子串
写技术博客的一些心得分享
Java 多线程（七）：线程池
Java 多线程（五）：锁（三）
Java 多线程（四）：锁（二）
Java 多线程（三）：锁（一）
Java 多线程（二）：并发编程的三大特性
线性时间非比较类排序
Java 多线程（一）：基础
合并k个已排序的链表
HDFS 高可用分布式环境搭建
合并两个有序数组
连续子数组的最大和
HDFS 分布式环境搭建
容器盛水问题
大数加法
HDFS 伪分布式环境搭建
设计LRU缓存结构
两数之和
使用单调栈来解决的一些问题

zl程序教程

当前栏目

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

相关文章