JAVA笔记 —— HashMap（1.7）底层实现原理

曾经终败给现在 2022-05-10 13:36 238阅读 0赞

# HashMap 底层实现原理   #

两年前，我总觉得很多东西会用就行，不喜欢总结，不喜欢深入了解，这或许就是因为当时太懒。一年前，我觉得必须要把在工作积累到的东西、遇到的问题及解决方法给总结记录下来，以便快速提升自己，所以从那时候起就开始写 txt 文本，做一些简单记录。而至今，工作近三年，我越来越觉得了解底层原理的重要性。

## ##

### 一、HashMap本质：数组 + 链表 ###

在JAVA数据结构中，常用数组和链表这两种结构来存储数据。

**数组**的存储区间(在内存的地址)是连续的，其大小固定，一旦分配就不能被其他引用占用，占用内存严重。数组的特点是：寻址容易，查询操作快，时间复杂度为O(1)；但插入和删除的操作比较慢，时间复杂度是O(n)。

**链表**的存储区间是非连续（离散）的，其大小不固定，可以扩容，占用内存比较宽松，故空间复杂度很小。链表的特点是：寻址困难，查询速度慢，复杂度是O(n)，插入快，时间复杂度为O(1)。

**　　HashMap**的数据结构：**数组** \+ **链表（单链表）**，结合了两者的优点。HashMap的主干是一个**Entry**数组，数组每一个元素的初始值都是**Null**。Entry是HashMap的基本组成单元，每一个Entry包含一个key-value键值对。

![70][]

**　　HashMap**的初始长度为**16**，且每次自动扩容或者手动初始化的时候必须是2的幂（以2次方增长）。所以，HashMap 的容量值都是 **2^n** 大小。

![70 1][]

**　　**Entry是HashMap中的一个静态内部类。源码如下：

static class Entry<K,V> implements Map.Entry<K,V> {
            final K key;
            V value;
            Entry<K,V> next;  // 存储指向下一个Entry的引用，单链表结构
            int hash;         // 对key的hashcode值进行hash运算后得到的值，存储在Entry，避免重复计算
    
            /**
             * Creates new entry.
             */
            Entry(int h, K k, V v, Entry<K,V> n) {
                value = v;
                next = n;
                key = k;
                hash = h;
            }
    
            public final K getKey() {
                return key;
            }
    
            public final V getValue() {
                return value;
            }
    
            public final V setValue(V newValue) {
                V oldValue = value;
                value = newValue;
                return oldValue;
            }
    
            public final boolean equals(Object o) {
                if (!(o instanceof Map.Entry))
                    return false;
                Map.Entry e = (Map.Entry)o;
                Object k1 = getKey();
                Object k2 = e.getKey();
                if (k1 == k2 || (k1 != null && k1.equals(k2))) {
                    Object v1 = getValue();
                    Object v2 = e.getValue();
                    if (v1 == v2 || (v1 != null && v1.equals(v2)))
                        return true;
                }
                return false;
            }
    
            public final int hashCode() {
                return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
            }
    
            public final String toString() {
                return getKey() + "=" + getValue();
            }
    
            /**
             * This method is invoked whenever the value in an entry is
             * overwritten by an invocation of put(k,v) for a key k that's already
             * in the HashMap.
             */
            void recordAccess(HashMap<K,V> m) {
            }
    
            /**
             * This method is invoked whenever the entry is
             * removed from the table.
             */
            void recordRemoval(HashMap<K,V> m) {
            }
        }

## ##

### **二、HashMap --** Put **方法实现**  ###

**方法实现：**将指定值与此映射中的指定键关联。如果映射以前包含了键的映射，则值被替换。

**　　**执行put存值时，HashMap首先会获取key的哈希值，通过哈希值快速找到某个存放位置，这个位置可以被称之为**bucketIndex**。当计算出来的bucketIndex相同(hash碰撞)时，则通过**hashCode**和**equals**最终判断出K(key)是否已存在，如果已存在，则使用新V值替换旧V值，并返回旧V值；如果不存在 ，则存放新的键值对<K, V>到bucketIndex位置。对于一个key，如果hashCode不同，equals一定为false，如果hashCode相同，equals不一定为true。

**　　**源码如下：

// 将指定值与此映射中的指定键关联。如果映射以前包含了键的映射，则值被替换。
        public V put(K key, V value) {
            if (table == EMPTY_TABLE) {
                inflateTable(threshold);
            }
            // 当key为null，调用putForNullKey方法，将该键值对添加到table[0]中，这是HashMap允许为null的原因 
            if (key == null)
                return putForNullKey(value);
            // 计算key的hash值
            int hash = hash(key);
            // 计算key hash 值在 table 数组中的位置
            int i = indexFor(hash, table.length);
            // 从i出开始迭代 e,找到 key 保存的位置 
            for (Entry<K,V> e = table[i]; e != null; e = e.next) {
                Object k;
                // 判断该条链上是否有hash值相同的(key相同)  
                // 若存在相同，则直接覆盖value，返回旧value，equals方法是hash碰撞时才会执行的方法 
                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                    V oldValue = e.value;   // 旧值 = 新值
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;        // 返回旧值 
                }
            }
            // modCount++代表修改次数+1，与迭代相关
            modCount++;
            // 增加新的节点，将key、value添加至i位置处
            addEntry(hash, key, value, i);
            return null;
        }

**例子 : hashMap.put(“clear”, 888)**

**　　**首先计算key的hash值：**int hash = hash(“clear”)；**

**　　**接着计算key hash 值在 table 数组中的位置bucketIndex：**int i = indexFor(hash, table.length)；**

![70 1][]

**　　**假定最后计算出的bucketIndex是**1**，那么结果如下 ：

![70 2][]

**　　**HashMap通过键的hashCode存取元素，HashCode是使用Key通过Hash函数计算出来的，当插入的Entry越来越多时，由于不同的Key，通过此Hash函数可能会算的同样的HashCode，即发生了**HashCode碰撞**，也叫**Hash冲突**。此时，HashMap通过**单链表**来解决，把对应节点以链表的形式存储，将新元素加入链表表头，通过next指向原有的元素。

**　　头插法：**新节点都增加到头部，新节点的next指向老节点；如下图中新的 Entry 2 指向旧的 Entry 1 。

![70 3][]

**Put 方法执行流程：**

**　　**1、首先判断key是否为**null**，当插入的key为null时，调用**putForNullKey**方法，默认存储到**table\[0\]**开头的链表。然后遍历table\[0\]的链表的每个节点Entry，如果发现其中存在节点Entry的key为null，就替换新的value，然后返回旧的value，如果没发现key等于null的节点Entry，就增加新的节点。

/**
         * Offloaded version of put for null keys
         * 获取key为null的键值对，HashMap将此键值对存储到table[0]的位置 
         */
        private V putForNullKey(V value) {
            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++;   // 修改次数+1
            addEntry(0, null, value, 0);  // 增加新的节点到 table[0] 位置
            return null;  // 返回 null
        }

**　　**2、计算key的hash值，**int hash = hash(key.hashCode())**，再用计算的结果二次hash（indexFor(hash, table.length))，找到Entry数组的索引 **i** 。

**　　**3、遍历以**table\[i\]**为头节点的链表，如果发现hash，key都相同的节点时，就替换为新的value，然后返回旧的value，只有hash相同时，循环内并没有做任何处理。

**　　**4、对于hash相同但key不相同的节点以及hash不相同的节点，就增加新的节点（ **addEntry()** ）。

void addEntry(int hash, K key, V value, int bucketIndex) {
            if ((size >= threshold) && (null != table[bucketIndex])) {
                resize(2 * table.length);
                hash = (null != key) ? hash(key) : 0;
                bucketIndex = indexFor(hash, table.length);
            }
    
            createEntry(hash, key, value, bucketIndex);
        }

5、**HashMap**的**扩容**问题。由于table数组的默认初始长度是固定的（16），随着HashMap中的元素数量越来越多的时候，发生hash碰撞的概率就越来越大，所产生的链表长度就会越来越长，这样就会影响HashMap的查询速度。为了提高HashMap的查询效率，就要对HashMap的数组table进行扩容。系统必须要在某个临界点进行扩容处理，该临界点在当HashMap中元素的数量等于**table数组长度 \* 加载因子**（如 **16 \* 0.75 = 12** ）。

**　　resize(2 \* table.length)；//** 当HashMap中元素个数超过**16**\*0.75=12时，就把数组的大小扩展为 **2\*16**=32，即**扩大一倍**。

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数组中的位置并进行复制处理。所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。

## ##

### **三、HashMap -- G**et **方法实现** ###

**Get 方法执行流程：**

**      ** 首先会判断key，若为null，调用**getForNullKey**方法返回相对应的value；

源码如下：

public V get(Object key) {
            if (key == null)
                return getForNullKey();
            Entry<K,V> entry = getEntry(key);
            return null == entry ? null : entry.getValue();
        }

private V getForNullKey() {
            if (size == 0) {
                return null;
            }
            for (Entry<K,V> e = table[0]; e != null; e = e.next) {
                if (e.key == null)
                    return e.value;
            }
            return null;
        }

**      ** 把输入的Key做一次Hash映射，得到对应的index：**int hash = (key == null) ? 0 : hash(“clear”)；**由于存在Hash冲突，同一个位置有可能匹配到多个Entry，这时候就需要顺着对应链表的头节点，一个一个向下来查找。 **e.next**

final Entry<K,V> getEntry(Object key) {
            if (size == 0) {
                return null;
            }
            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;
        }

## ##

### 四、HashMap的构造函数 ###

**　　public class HashMap<K,V>    extends AbstractMap<K,V>    implements Map<K,V>, Cloneable, Serializable \{ ... \}**

HashMap实现了**Map**接口，继承**AbstractMap**。其中Map接口定义了键映射到值的规则，而AbstractMap类提供 Map 接口的骨干实现。

**　　**HashMap提供了三个构造函数：

**HashMap()**：构造一个具有**默认初始容量** (**16**) 和**默认加载因子** (**0.75**) 的空 HashMap。

**HashMap(int initialCapacity)**：构造一个带**指定初始容量**和**默认加载因子** (**0.75**) 的空 HashMap。

**HashMap(int initialCapacity, float loadFactor)**：构造一个带**指定初始容量**和**指定加载因子**的空 HashMap。

**　　**源码如下：

// HashMap的三个构造函数  -- 源码查看
        /**
         * Constructs an empty <tt>HashMap</tt> with the default initial capacity (16) and the default load factor (0.75).
         *使用默认初始容量（16）和默认负载因子（0.75）来构造空<TT> HashMap </TT>
         */
        public HashMap() {
            this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
        }
    
        /**
         * Constructs an empty <tt>HashMap</tt> with the specified initial capacity and the default load factor (0.75).
         * 用指定的初始容量和默认负载因子（0.75）来构造空<TT> HashMap </TT>
         * 如果初始容量为负值，则抛出非法的异常。
         */
        public HashMap(int initialCapacity) {
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
        }
    
        /**
         * Constructs an empty <tt>HashMap</tt> with the specified initial capacity and load factor.
         * 用指定的初始容量和负载系数 来构造空<TT> HashMap </TT>
         * initialCapacity 设置的初始化容量,或者说是 HashMap 扩充数组时的阀值  
         * loadFactor 负载因子，默认时 0.75  
         * 如果初始容量为负值或负载因子为非正，则抛出非法逻辑异常   
         */
        public HashMap(int initialCapacity, float loadFactor) {
            // 初始容量不能<0 
            if (initialCapacity < 0)             
                throw new IllegalArgumentException("Illegal initial capacity: " +
                                                   initialCapacity);
            // 初始容量不能 > 最大容量值，HashMap的最大容量值为2^30
            if (initialCapacity > MAXIMUM_CAPACITY)
                initialCapacity = MAXIMUM_CAPACITY;
            // 负载因子不能 < 0 
            if (loadFactor <= 0 || Float.isNaN(loadFactor))         
                throw new IllegalArgumentException("Illegal load factor: " +
                                                   loadFactor);
    
            this.loadFactor = loadFactor;
            threshold = initialCapacity;
            init();
        }

# #

## 五、HashMap线程不安全原因 ##

**　　**Hashmap在 HashMap.Size >= Capacity \* LoadFactor 时，就会调用 resize 方法，进行**扩容**和**ReHash**两个步骤 。此时，若在单线程情况下，rehash 不会出现任何问题；若在**多线程**情况下，**rehash** 则可能会导致hashmap出现**链表闭环**，程序就会进入**死循环**，所以HashMap是**非线程安全**的。

**　　**因此，在**高并发**场景下，我们通常采用另一个集合类**ConcurrentHashMap**，这个集合类兼顾了**线程安全**和性能。

### 六、总结 ###

1、HashMap结合了**数组**和(单)**链表**的优点，使用Hash算法加快访问速度，使用**链表解决hash碰撞冲突**的问题，其中数组的每个元素是单链表的头结点。  
　　2、HashMap的put方法中，当HashMap中元素的数量大于等于**table数组长度 \* 加载因子**时，要对hashMap进行**扩容**，扩容过程始终以2次方增长，因此，HashMap 的容量一定是2的整数次幂，**即 2^n** 。  
　　3、从HashMap的put和get方法中可以看出，HashMap是**泛型**类，key和value可以为任何类型，包括**null**类型。key为null的键值对永远都放在以**table\[0\]**为头结点的中，当然不一定是存放在头结点table\[0\]中。  
　　4、HashMap有三个构造函数，有两个重要参数：**初始容量**和**加载因子**。默认初始容量（**16**）和默认负载因子（**0.75**）。  
　　5、HashMap**非线程安全**。

[70]: /images/20220505/30fa5afb145349088be8f0fa621624a7.png
[70 1]: /images/20220505/90375287535e45aab8147ede62cebb80.png
[70 2]: /images/20220505/0821f529fd134112bf2a1fdb0b1a9b7e.png
[70 3]: /images/20220505/bfbcb5cdf811405e9f698defc96eeacd.png