HashMap源码分析（基于JDK1.6）

港控/mmm° 2022-08-07 03:50 126阅读 0赞

# 源码分析 #

要分析**HashMap**，先来回顾一下数据结构中的哈希表。什么是哈希表？是根据关键码值(**Key**)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数，存放记录的数组叫哈希表。  
比如关键字为**k**，则其值存放在**f(k)**的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系**f**为哈希函数，按这个思想建立的表为散列表（哈希表）。

![这里写图片描述][20150306093710437]

从这张图上我们可以知道：  
1. 哈希表的大小是16  
2. 哈希函数采用的是除留余数法，具体是 关键字对16取余  
3. 处理冲突采用的是 链地址法（拉链法）

下面结合哈希表的结构来分析**HashMap**：

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

**HashMap**实现了**Map**接口，这个接口是**Java1.2**引入的，里面抽象了Map所要提供方法，并且其中还包含了一个**Map.Entry**接口。这个接口封装了**Key-Value对**，将其看成一个整体，那么其实`Map<K, V>`就变成了`Set<Entry<K, V>>`

再看**HashMap**中实现的**Entry**：

static class Entry<K,V> implements Map.Entry<K,V> { 
            final K key;
            V value;
            Entry<K,V> next;
            final int hash;
        }

在该类的属性中，key、value这两个比较好理解。另外还包含了一个自身类型的next，是不是很熟悉，想到了数据结构中的链表？对，**HashMap**中处理冲突就是使用了拉链法。而int类型的hash就表示了这个Entry的哈希值。先对这个结构有个大概的了解

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

/** * 增长的哈希表，长度必须是2的N次方 */
        transient Entry[] table;
    
        /** * map中存储的key-value对数 */
        transient int size;
    
        /** * 临界值，即存储的key-value对的数量到达这个值时就要扩充了（等于size*loadFactor） */
        int threshold;
    
        /** * 负载因子（用于计算threshold） */
        final float loadFactor;

大致有一定了解后，下面来看看构造函数：

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);
    
            // Find a power of 2 >= initialCapacity
            int capacity = 1;
            while (capacity < initialCapacity)
                capacity <<= 1;
    
            this.loadFactor = loadFactor;
            threshold = (int)(capacity * loadFactor);
            table = new Entry[capacity];
            init();
        }
    
        public HashMap(int initialCapacity) {
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
        }
    
        public HashMap() {
            this.loadFactor = DEFAULT_LOAD_FACTOR;
            threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
            table = new Entry[DEFAULT_INITIAL_CAPACITY];
            init();
        }

对于这三个构造函数，总的来说，只需要两个参数，一个是哈希表的初始化大小，另一个是负载因子。通过这两个参数可以算出**threshold**，当**HashMap**中存储的**key-value对**的数量到达**threshold**后，那么哈希表就会扩容，一会我们分析**put**方法的时候来验证这一点。  
下面就分析下**put**方法，这也是**HashMap**中最重要的方法之一：

public V put(K key, V value) {
            if (key == null)
                return putForNullKey(value);
            int hash = hash(key.hashCode());
            int i = indexFor(hash, table.length);
            for (Entry<K,V> e = table[i]; e != null; e = e.next) {
                Object k;
                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }
    
            modCount++;
            addEntry(hash, key, value, i);
            return null;
        }

**HashMap**中可以存在**null**的**key**或**null**的**value**（这点和**HashTable**不同）。所以这里单独处理了**key**为**null**的情况——调用了**putForNullKey()**方法：

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++;
            addEntry(0, null, value, 0);
            return null;
        }

由于**null**的**key**不能进行hash计算，这里就直接将它的hash值置为0了，并且存到哈希表的第一个**bucket**中。若该**bucket**中没有存储数据，那么直接将该**null-value**作为**Entry**存进去。如果已经有**Entry**，那么判断是否存在key为null的**Entry**，如果有的话，则直接将**oldValue**替换掉，并返回**oldValue**。**Entry**究竟是如何添加到哈希表中的呢？我们来看下**addEntry()**方法：

void addEntry(int hash, K key, V value, int bucketIndex) {
            Entry<K,V> e = table[bucketIndex];
            table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
            if (size++ >= threshold)
                resize(2 * table.length);
        }

先得到之前哈希表中该**bucket**的链表头，然后创建一个新的Entry将其作为新的链表头（也就是把**next**设为之前的链表头），所以后添加的**entry**会在链头的位置。并且每次在添加完之后都要判断size是否到达**threshold**，若到了临界值，那么就需要扩容了（**resize**）：

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);
            table = newTable;
            threshold = (int)(newCapacity * loadFactor);
        }

若此时哈希表的长度已经到达了最大容量：`1 << 30`，那么该方法并不再扩容哈希表，只是将**threshold**的值设置为`Integer.MAX_VALUE`。而对于一般情况来说，用新的容量创建一个哈希表，然后再将老的哈希表的内容拷贝到新表中去，并指定新表作为**HashMap**中的哈希表，最后重新计算**threshold**。  
其中新老表转换的方法是**transfer()**：

void transfer(Entry[] newTable) {
            Entry[] src = table;
            int newCapacity = newTable.length;
            for (int j = 0; j < src.length; j++) {
                Entry<K,V> e = src[j];
                if (e != null) {
                    src[j] = null;
                    do {
                        Entry<K,V> next = e.next;
                        int i = indexFor(e.hash, newCapacity);
                        e.next = newTable[i];
                        newTable[i] = e;
                        e = next;
                    } while (e != null);
                }
            }
        }

这里包含了两层循环：第一层是对表中每个**bucket**的遍历，而第二层就是对每个**bucket**中存储的链表的遍历。当然，由于底层哈希表结构发生了变化，那么对于原来存储的**entry**需要重新计算它应该放置的**bucket**的位置，然后再将它放置到该位置的链表头上去。这里计算**bucket**位置用到了**indexFor()**方法：

static int indexFor(int h, int length) {
            return h & (length-1);
        }

对于我这种不懂位运算的小白来说，一时间真是无法了解其中的奥秘了。网上说：当`length=2^n`时，`hashcode & (length-1) == hashcode % length`。当然对于具体的原理我还是不清楚，这里且将它先当做取模运算，那就很好理解了。

刚才讲**putForNullKey()**方法而后调用了很多方法，下面分析一般非null的key的**put**，其实和**putForNullKey()**类似：

首先计算出key的哈希值，然后得到该key在哈希表中bucket的位置，若该bucket上存在Entry链，遍历该链表查找是否已经存在该key的Entry，若存在则用新的value替换老的value，若不存在，调用**addEntry()**方法添加到哈希表中去。

差不多**put**方法就分析完了，下面分析另一个重要的方法——**get**方法：

public V get(Object key) {
            if (key == null)
                return getForNullKey();
            int hash = hash(key.hashCode());
            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.equals(k)))
                    return e.value;
            }
            return null;
        }

其实清楚了**put**方法之后，**get**方法也就很好理解了。和**put**一样，首先处理key为null的情况，**getForNullKey()**方法，还记得之前key为null存储在哪里吗？对，就是哈希表的第一个**bucket**上，所以应该是去遍历第一个bucket上的链表，找到其中key为null的Entry：

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

而对于key非null的情况呢，首先计算出key的哈希值，然后得到该key在哈希表中的bucket位置，这个过程是非常快速高效的，否则只能通过遍历来查找，性能可想而知。找到bucket后，若该bucket中只有一个Entry，那么此时直接就找到了，这也是HashMap性能最好的情况——每个bucket上只有一个Entry。但实际情况往往不会这么理想，当某个bucket上有多个Entry时，则需要遍历Entry链来和key做匹配。

# 性能分析 #

讲完了HashMap的核心方法，下面对HashMap的性能进行一下分析，回顾上面的方法中，哪个方法是最耗时的？那肯定是resize方法了，因为它要重新创建一个哈希表，并将之前哈希表上的数据全部重新散列到新的哈希表上去。可以想象，随着HashMap的size越来越大，这样的resize肯定会消耗大量的性能。再想想我们为什么需要resize？因为往往需要resize的时候，哈希表中存储的数据已经很多，链表可能已经比较长，对于查找的性能会有比较严重的影响，基于此，才采用了resize的方法，让负载因子降下来。  
那么，若早就知道HashMap大概的存储量时，我们可以在初始化时就指定好initCapacity，这样就能避免大量的resize计算了。比如说，我们有1000个元素`new HashMap(1024)`，这里为什么不`new HashMap(1000)`，还记得**HashMap**的构造函数吗？它会保证底层哈希表的长度为2的次方，也就是最小的大于传入的**initCapacity**的2的次方。但是若设为1000，还要进入while循环，所以1024更加妥当。 但是`new HashMap(1024)`还不是更合适的，因为`0.75 * 1000 < 1000,` 那么此时调用**put**就会进行**resize**，也就是说为了让`0.75 * size > 1000`, 我们必须这样`new HashMap(2048)`才最合适，既考虑了构造**HashMap**时的性能的问题，也避免了**resize**的问题。

[20150306093710437]: /images/20220805/a5b7c37ac3354188b83eb4948c05fab3.png