HashMap源码解析（基于JDK1.7）

「爱情、让人受尽委屈。」 2022-06-09 00:38 231阅读 0赞

## 一、HashMap简介 ##

哈希表（hash table）也叫散列表，是一种非常重要的数据结构，应用场景及其丰富，许多缓存技术（比如memcached）的核心其实就是在内存中维护一张大的哈希表，而HashMap的实现原理就是基于此。那么什么是哈希表呢？  
在讨论哈希表之前，我们先大概了解下其他数据结构在新增，查找等基础操作执行性能

*  数组：采用一段连续的存储单元来存储数据。对于指定下标的查找，时间复杂度为O(1)；通过给定值进行查找，需要遍历数组，逐一比对给定关键字和数组元素，时间复杂度为O(n)，当然，对于有序数组，则可采用二分查找，插值查找，斐波那契查找等方式，可将查找复杂度提高为O(logn)；对于一般的插入删除操作，涉及到数组元素的移动，其平均复杂度也为O(n)。对应到集合实现，代表就是ArrayList。
 *  线性链表：对于链表的新增，删除等操作（在找到指定操作位置后），仅需处理结点间的引用即可，时间复杂度为O(1)，而查找操作需要遍历链表逐一进行比对，复杂度为O(n)。对应的集合类是LinkedList。
 *  二叉树：对一棵相对平衡的有序二叉树，对其进行插入，查找，删除等操作，平均复杂度均为O(logn)。对应的集合类有TreeSet和TreeMap。
 *  哈希表：相比上述几种数据结构，在哈希表中进行添加，删除，查找等操作，性能十分之高，不考虑哈希冲突的情况下，仅需一次定位即可完成，时间复杂度为O(1)。对应的集合类就是HashMap。

哈希表的主干就是数组。我们要新增或查找某个元素，我们通过把当前元素的关键字 通过某个函数映射到数组中的某个位置，通过数组下标一次定位就可完成操作。即：

存储位置 = f(关键字)

其中，这个函数f一般称为哈希函数，这个函数的设计好坏会直接影响到哈希表的优劣。这会涉及到哈希冲突。

当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的哈希冲突，也叫哈希碰撞。前面我们提到过，哈希函数的设计至关重要，好的哈希函数会尽可能地保证计算简单和散列地址分布均匀。但是，我们需要清楚的是，数组是一块连续的固定长度的内存空间，再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。那么哈希冲突如何解决呢？哈希冲突的解决方案有多种:开放定址法（发生冲突，继续寻找下一块未被占用的存储地址）、再散列函数法、链地址法。而HashMap即是采用了链地址法，也就是数组+链表的方式。  
简单来说，HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）,那么对于查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度依然为O(1)，因为最新的Entry会插入链表头部，急需要简单改变引用链即可，而对于查找操作来讲，此时就需要遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。

## 二、HashMap的源码实现 ##

### 1、存储结构 ###

HashMap的内部存储结构其实是数组和链表的结合。当实例化一个HashMap时，系统会创建一个长度为Capacity的Entry数组，这个长度被称为容量(Capacity)，在这个数组中可以存放元素的位置我们称之为“桶”(bucket)，每个bucket都有自己的索引，系统可以根据索引快速的查找bucket中的元素。 每个bucket中存储一个元素，即一个Entry对象，但每一个Entry对象可以带一个引用变量，用于指向下一个元素，因此，在一个桶中，就有可能生成一个Entry链。 Entry是HashMap的基本组成单元，每一个Entry包含一个key-value键值对。 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;
            }

经过以上分析，HashMap的存储结构图如下：  
![这里写图片描述][20170823152551068]  
![这里写图片描述][20170823152737666]  
一个长度为16的数组中，每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢。一般情况是通过hash(key)%len获得，也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中，12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。

在存储一对值时（Key—->Value对），实际上是存储在一个Entry的对象e中，程序通过key计算出Entry对象的存储位置。换句话说，Key—->Value的对应关系是通过key—-Entry—-value这个过程实现的，所以就有我们表面上知道的key存在哪里，value就存在哪里。

### 2、构造方法 ###

先看HashMap中的几个重要属性：

//默认初始化化容量,即16  
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
    
    //最大容量，即2的30次方  
    static final int MAXIMUM_CAPACITY = 1 << 30;  
    
    //默认装载因子  
    static final float DEFAULT_LOAD_FACTOR = 0.75f;  
    
    //HashMap内部的存储结构是一个数组，此处数组为空，即没有初始化之前的状态  
    static final Entry<?,?>[] EMPTY_TABLE = {};  
    
    //空的存储实体  
    transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;  
    
    //实际存储的key-value键值对的个数
    transient int size;
    
    //阈值，当table == {}时，该值为初始容量（初始容量默认为16）；当table被填充了，也就是为table分配内存空间后，threshold一般为 capacity*loadFactory。HashMap在进行扩容时需要参考threshold
    int threshold;
    
    //负载因子，代表了table的填充度有多少，默认是0.75
    final float loadFactor;
    
    //用于快速失败，由于HashMap非线程安全，在对HashMap进行迭代时，如果期间其他线程的参与导致HashMap的结构发生变化了（比如put，remove等操作），需要抛出异常ConcurrentModificationException
    transient int modCount;
    
    //默认的threshold值  
    static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

HashMap有4个构造器，其他构造器如果用户没有传入initialCapacity 和loadFactor这两个参数，会使用默认值。initialCapacity默认为16，loadFactory默认为0.75。

//计算Hash值时的key  
        transient int hashSeed = 0;  
    
        //通过初始容量和状态因子构造HashMap  
        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;  
            threshold = initialCapacity;  
            init();//init方法在HashMap中没有实际实现，不过在其子类如 linkedHashMap中就会有对应实现
        }  
    
        //通过扩容因子构造HashMap,容量去默认值，即16  
        public HashMap(int initialCapacity) {  
            this(initialCapacity, DEFAULT_LOAD_FACTOR);  
        }  
    
        //装载因子取0.75，容量取16，构造HashMap  
        public HashMap() {  
            this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);  
        }  
    
        //通过其他Map来初始化HashMap,容量通过其他Map的size来计算，装载因子取0.75  
        public HashMap(Map<? extends K, ? extends V> m) {  
            this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);  
            inflateTable(threshold);//初始化HashMap底层的数组结构  
            putAllForCreate(m);//添加m中的元素  
        }

从上面这段代码我们可以看出，在常规构造器中，并没有马上为数组table分配内存空间（有一个入参为指定Map的构造器例外），事实上是在执行第一次put操作的时候才真正构建table数组。

### 3、put操作 ###

如果两个key通过hash%Entry\[\].length得到的index相同，会不会有覆盖的危险？为了解决这个问题，HashMap里面用到链式数据结构的一个概念。上面我们提到过Entry类里面有一个next属性，作用是指向下一个Entry。打个比方， 第一个键值对A进来，通过计算其key的hash得到的index=0，记做:Entry\[0\] = A。一会后又进来一个键值对B，通过计算其index也等于0，现在怎么办？HashMap会这样做:B.next = A,Entry\[0\] = B,如果又进来C,index也等于0,那么C.next = B,Entry\[0\] = C；这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起。所以疑问不用担心。也就是说数组中存储的是最后插入的元素。到这里为止，HashMap的大致实现，我们应该已经清楚了。

public V put(K key, V value) {
            //如果table数组为空数组{}，进行数组填充（为table分配实际内存空间），入参为threshold，此时threshold为initialCapacity 默认是1<<4(=16)
            if (table == EMPTY_TABLE) {
                inflateTable(threshold);//分配数组空间
            }
           //如果key为null，存储位置为table[0]或table[0]的冲突链上
            if (key == null)
                return putForNullKey(value);
            int hash = hash(key);//对key的hashcode进一步计算，确保散列均匀
            int i = indexFor(hash, table.length);//获取在table中的实际位置
            for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            //如果该对应数据已存在，执行覆盖操作。用新value替换旧value，并返回旧value
                Object k;
                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);//调用value的回调函数，其实这个函数也为空实现
                    return oldValue;
                }
            }
            modCount++;//保证并发访问时，若HashMap内部结构发生变化，快速响应失败
            addEntry(hash, key, value, i);//新增一个entry
            return null;
        }

inflateTable的源码如下：

private void inflateTable(int toSize) {
            int capacity = roundUpToPowerOf2(toSize);//capacity一定是2的次幂
            threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);//此处为threshold赋值，取capacity*loadFactor和MAXIMUM_CAPACITY+1的最小值，capaticy一定不会超过MAXIMUM_CAPACITY，除非loadFactor大于1
            table = new Entry[capacity];//分配空间
            initHashSeedAsNeeded(capacity);//选择合适的Hash因子
        }

inflateTable这个方法用于为主干数组table在内存中分配存储空间，通过roundUpToPowerOf2(toSize)可以确保capacity为大于或等于toSize的最接近toSize的二次幂，比如toSize=13,则capacity=16；to\_size=16，capacity=16；to\_size=17,capacity=32。其实现如下：

private static int roundUpToPowerOf2(int number) {
            // assert number >= 0 : "number must be non-negative";
            return number >= MAXIMUM_CAPACITY
                    ? MAXIMUM_CAPACITY
                    : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
        }

roundUpToPowerOf2中的这段处理使得数组长度一定为2的次幂，Integer.highestOneBit是用来获取最左边的bit（其他bit位为0）所代表的数值。

在对数组进行空间分配后，会根据hash函数计算散列值，其实现如下：

//用了很多的异或，移位等运算，对key的hashcode进一步进行计算以及二进制位的调整等来保证最终获取的存储位置尽量分布均匀
    final int hash(Object k) {
            int h = hashSeed;
            if (0 != h && k instanceof String) {
       //这里针对String优化了Hash函数，是否使用新的Hash函数和Hash因子有关  
                return sun.misc.Hashing.stringHash32((String) k);
            }
    
            h ^= k.hashCode();
    
            h ^= (h >>> 20) ^ (h >>> 12);
            return h ^ (h >>> 7) ^ (h >>> 4);
        }

从上面的操作看以看出，影响HashMap元素的存储位置的只有key的值，与value值无关。

通过hash函数得到散列值后，再通过indexFor进一步处理来获取实际的存储位置，其实现如下：

//返回数组下标
        static int indexFor(int h, int length) {
            return h & (length-1);
        }

h&（length-1）保证获取的index一定在数组范围内，举个例子，默认容量16，length-1=15，h=18,转换成二进制计算为  
![这里写图片描述][20170823160413646]  
最终计算出的index=2。有些版本的对于此处的计算会使用 取模运算，也能保证index一定在数组范围内，不过位运算对计算机来说，性能更高一些（HashMap中有大量位运算）。  
通过以上分析，我们看到，要得到一个元素的存储位置，需要如下几步：  
1、获取该元素的key值  
2、通过hash方法得到key的散列值，这其中需要用到key的hashcode值。  
3、通过indexFor计算得到存储的下标位置。

最后，得到存储的下标位置后，我们就可以将元素放入HashMap中，具体通过addEntry实现：

void addEntry(int hash, K key, V value, int bucketIndex) {
            if ((size >= threshold) && (null != table[bucketIndex])) {
                resize(2 * table.length);//当size超过临界阈值threshold，并且即将发生哈希冲突时进行扩容，新容量为旧容量的2倍
                hash = (null != key) ? hash(key) : 0;
                bucketIndex = indexFor(hash, table.length);//扩容后重新计算插入的位置下标
            }
    
            //把元素放入HashMap的桶的对应位置
            createEntry(hash, key, value, bucketIndex);
        }
    //创建元素  
        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++;//元素个数+1  
        }

通过以上代码能够得知，当发生哈希冲突并且size大于阈值的时候，需要进行数组扩容，扩容时，需要新建一个长度为之前数组2倍的新的数组，然后将当前的Entry数组中的元素全部传输过去，扩容后的新数组长度为之前的2倍，所以扩容相对来说是个耗资源的操作。

### 4、扩容操作 ###

扩容操作通过resize操作实现：

//按新的容量扩容Hash表  
        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;//修改HashMap的底层数组  
            threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);//修改阀值  
        }

如果数组进行扩容，数组长度发生变化，而存储位置 index = h&(length-1),index也可能会发生变化，需要重新计算index，我们先来看看transfer这个方法：

//将老的表中的数据拷贝到新的结构中  
        void transfer(Entry[] newTable, boolean rehash) {  
            int newCapacity = newTable.length;//容量  
            for (Entry<K,V> e : table) { //遍历所有桶
                while(null != e) {  //遍历桶中所有元素（是一个链表）
                    Entry<K,V> next = e.next;  
                    if (rehash) {
       //如果是重新Hash，则需要重新计算hash值  
                        e.hash = null == e.key ? 0 : hash(e.key);  
                    }  
                    int i = indexFor(e.hash, newCapacity);//定位Hash桶  
                    e.next = newTable[i];//元素连接到桶中,这里相当于单链表的插入，总是插入在最前面
                    newTable[i] = e;//newTable[i]的值总是最新插入的值
                    e = next;//继续下一个元素  
                }  
            }  
        }

这个方法将老数组中的数据逐个链表地遍历，重新计算后放入新的扩容后的数组中，我们的数组索引位置的计算是通过 对key值的hashcode进行hash扰乱运算后，再通过和 length-1进行位运算得到最终数组索引位置。  
**注意**：HashMap数组元素长度的设计  
通过源码可以发现，hashMap的数组长度一定保持2的次幂，这样做有什么好处呢？

//根据Hash值和Hash表的大小选择合适的Hash桶  
        static int indexFor(int h, int length) {  
            return h & (length-1);  
        }

如果length为2的次幂，其二进制表示就是100….0000；则length-1 转化为二进制必定是0111….11的形式，在于h的二进制与操作效率会非常的快，而且空间不浪费；如果length不是2的次幂，比如length为15，则length-1为14，对应的二进制为1110，再于h与操作，  
最后一位都为0，所以0001，0011，0101，1001，1011，0111，1101这几个位置永远都不会存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！这样就会造成空间的浪费。

### 5、get操作 ###

//获取key值为key的元素值  
        public V get(Object key) {  
            if (key == null)//如果Key值为空，则获取对应的值，这里也可以看到，HashMap允许null的key，其内部针对null的key有特殊的逻辑  
                return getForNullKey();  
            Entry<K,V> entry = getEntry(key);//获取实体  
    
            return null == entry ? null : entry.getValue();//判断是否为空，不为空，则获取对应的值  
        }  
    
        //获取key为null的实体  
        private V getForNullKey() {  
            if (size == 0) {
       //如果元素个数为0，则直接返回null  
                return null;  
            }  
            //key为null的元素存储在table的第0个位置  
            for (Entry<K,V> e = table[0]; e != null; e = e.next) {  
                if (e.key == null)//判断是否为null  
                    return e.value;//返回其值  
            }  
            return null;  
        }

get方法通过key值返回对应value，如果key为null，直接去table\[0\]处检索。我们再看一下getEntry这个方法：

//获取键值为key的元素  
        final Entry<K,V> getEntry(Object key) {  
            if (size == 0) {
       //元素个数为0  
                return null;//直接返回null  
            }  
    
            int hash = (key == null) ? 0 : hash(key);//获取key的Hash值  
            for (Entry<K,V> e = table[indexFor(hash, table.length)];//根据key和表的长度，定位到Hash桶  
                 e != null;  
                 e = e.next) {
       //进行遍历  
                Object k;  
                if (e.hash == hash &&  
                    ((k = e.key) == key || (key != null && key.equals(k))))//判断Hash值和对应的key，合适则返回值  
                    return e;  
            }  
            return null;  
        }

可以看出，get方法的实现相对简单，key(hashcode)–>hash–>indexFor–>最终索引位置，找到对应位置table\[i\]，再查看是否有链表，遍历链表，通过key的equals方法比对查找对应的记录。要注意的是，有人觉得上面在定位到数组位置之后然后遍历链表的时候，e.hash == hash这个判断没必要，仅通过equals判断就可以。其实不然，试想一下，如果传入的key对象重写了equals方法却没有重写hashCode，而恰巧此对象定位到这个数组位置，如果仅仅用equals判断可能是相等的，但其hashCode和当前对象不一致，这种情况，根据Object的hashCode的约定，不能返回当前对象，而应该返回null。  
下面来举一个例子看一下：

package com.kang.test;
    
    import java.util.HashMap;
    
    public class Test {
    
        private static class Person {
            int ID;
            String name;
    
            public Person(int idCard, String name) {
                this.ID = idCard;
                this.name = name;
            }
    
            @Override
            public boolean equals(Object o) {
                if (this == o) {
                    return true;
                }
                if (o == null || getClass() != o.getClass()) {
                    return false;
                }
                Person person = (Person) o;
                // 两个对象是否等值，通过ID来确定
                return this.ID == person.ID;
            }
    
        }
    
        public static void main(String[] args) {
            HashMap<Person, String> map = new HashMap<>();
            Person person = new Person(1234, "kang");
            map.put(person, "25岁");
            // get取出，从逻辑上讲应该能输出“25岁”
            System.out.println("结果:" + map.get(new Person(1234, "kang")));//注意这里是new一个对象
        }
    }

程序运行结果是：`结果:null`  
为什么会出现这样的结果呢？我们只重写了Person的equal方法，尽管我们在进行get和put操作的时候，使用的key从逻辑上讲是等值的（通过equals比较是相等的），但由于没有重写hashCode方法，而我们在进行get操作时使用的是`map.get(new Person(1234, "kang")))`，注意是new操作新建了一个对象。因为没有重写hashcode方法，所以两者的hashcode是不同的。所以put操作时得到的hashcode1和get操作时得到的hashcode2是不同的。由于hashcode1不等于hashcode2，导致没有定位到一个数组位置而返回逻辑上错误的值null（也有可能碰巧定位到一个数组位置，但是也会判断其entry的hash值是否相等，上面get方法中有提到。）。  
解决方法很简单，只需要重写hashcode方法即可。如下：

@Override
            public int hashCode() {
                return this.ID;//这里为了简单起见，直接将ID值作为hashcode的值
            }
    
        }

如此一来，输出结果便是正确的。所以，在重写equals的方法的时候，必须注意重写hashCode方法，同时还要保证通过equals判断相等的两个对象，调用hashCode方法要返回同样的整数值。而如果equals判断不相等的两个对象，其hashCode可以相同（只不过会发生哈希冲突，应尽量避免）。

## 三、HashMap的使用总结 ##

*  HashMap是基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变（发生扩容时，元素位置会重新分配）。
 *  迭代 collection 视图所需的时间与 HashMap 实例的“容量”（桶的数量）及其大小（键-值映射关系数）成比例。所以，如果迭代性能很重要，则不要将初始容量设置得太高（或将加载因子设置得太低）。
 *  HashMap 的实例有两个参数影响其性能：初始容量 和加载因子。容量 是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。通常，默认加载因子 (.75) 在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数 HashMap 类的操作中，包括 get 和 put 操作，都反映了这一点）。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少 rehash 操作次数。如果初始容量大于最大条目数除以加载因子，则不会发生 rehash 操作。  
    如果很多映射关系要存储在 HashMap 实例中，则相对于按需执行自动的 rehash 操作以增大表的容量来说，使用足够大的初始容量创建它将使得映射关系能更有效地存储。
 *  HashMap的实现不是同步的。如果在多线程操作下，应该使用 `Collections.synchronizedMap` 方法来“包装”该映射。最好在创建时完成这一操作，以防止对映射进行意外的非同步访问，如下所示：  
    `Map m = Collections.synchronizedMap(new HashMap(…));`
 *  由所有此类的“collection 视图方法”所返回的迭代器都是快速失败 的：在迭代器创建之后，如果从结构上对映射进行修改，除非通过迭代器本身的 remove 方法，其他任何时间任何方式的修改，迭代器都将抛出 ConcurrentModificationException。

[20170823152551068]: /images/20220609/5d745bf93739476f8d8f41db43767d2e.png
[20170823152737666]: /images/20220609/9d8b814e1b3741098b4640ec20169ae1.png
[20170823160413646]: /images/20220609/a14722faef314ecf8c45da4df9aea418.png