Java不得不知道的八股文之哈希表

缺乏、安全感 2023-09-23 16:11 104阅读 0赞

## 哈希表简介 ##

在哈希表中进行添加，删除，查找等操作，性能十分之高，不考虑哈希冲突的情况下（后面会探讨下哈希冲突的情况），仅需一次定位即可完成，时间复杂度为O(1)，接下来我们就来看看哈希表是如何实现达到惊艳的常数阶O(1)的。

我们知道，数据结构的物理存储结构只有两种：**顺序存储结构**和**链式存储结构**（像栈，队列，树，图等是从逻辑结构去抽象的，映射到内存中，也这两种物理组织形式），而在上面我们提到过，在数组中根据下标查找某个元素，一次定位就可以达到，哈希表利用了这种特性，**哈希表的主干就是数组**。

**比如我们要新增或查找某个元素，我们通过把当前元素的关键字 通过某个函数（散列函数，哈希函数）映射到数组中的某个位置，通过数组下标一次定位就可完成操作。**

这个函数可以简单描述为：**存储位置 = f(关键字)** ，这个函数f一般称为哈希函数，这个函数的设计好坏会直接影响到哈希表的优劣。

我们第一时间能想到的最简单的哈希函数就是取余`%`操作

例如我**新增或查找某个元素**，当前数组的长度为8，我们按照`存储位置=f(关键字)`。散列函数f就为`f(i%8)`（范围为\[0,7\]正好是数组的索引范围）。

![format_png][]

同理当我们想要获取到元素时，只需要把i传过去然后通过散列函数计算

但是可以看到这样散列函数的方式是存在一个问题的！！按照上图所示，当我们的`i=10`的时候**通过哈希函数得出的实际存储地址相同**。也就是说，当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的**哈希冲突**，也叫**哈希碰撞**。

![format_png 1][]

前面我们提到过，哈希函数的设计至关重要，好的哈希函数会尽可能地保证 计算简单和散列地址分布均匀,但是，我们需要清楚的是，数组是一块连续的固定长度的内存空间，再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。那么哈希冲突如何解决呢？

哈希冲突的解决方案有多种:开放定址法（发生冲突，继续寻找下一块未被占用的存储地址），再散列函数法，链地址法，而HashMap即是采用了**链地址法**，也就是**数组+链表**(JDK7)的方式。

## JDK7 ##

**JDK7版本的HashMap底层采用的是链地址法，也就是数组+链表的方式。**

HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元，每一个Entry包含一个key-value键值对。（其实所谓Map其实就是保存了两个对象之间的映射关系的一种集合）

![format_png 2][]

//HashMap的主干数组，可以看到就是一个Entry数组，初始值为空数组{}，主干数组的长度一定是2的次幂。
    //至于为什么这么做，后面会有详细分析。
    transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
    复制代码

**HashMap的主干数组，可以看到就是一个Entry数组，初始值为空数组\{\}。**

**主干数组的长度(HashMap长度)一定是2的次幂。** 不过为什么呢？？？后面会讲到

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;
            } 
    复制代码

![format_png 3][]

所以，HashMap的总体结构如下：

![format_png 4][]

简单来说，**HashMap由数组+链表组成的**，Entry数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）,那么查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，**HashMap中的链表出现越少，性能才会越好。**

其他几个重要字段

/**默认初始容量默认为16 */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    
    /**实际存储的key-value键值对的个数*/
    transient int size;
    
    /**阈值，当table == {}时，该值为初始容量（初始容量默认为16）；当table被填充了，也就是为table分配内存空间后，
    threshold一般为 capacity*loadFactory。HashMap在进行扩容时需要参考threshold，后面会详细谈到*/
    int threshold;
    
    /**负载因子，代表了table的填充度有多少，默认是0.75
    加载因子存在的原因，还是因为减缓哈希冲突，如果初始桶为16，等到满16个元素才扩容，某些桶里可能就有不止一个元素了。
    所以加载因子默认为0.75，也就是说大小为16的HashMap，到了第13个元素，就会扩容成32。
    */
    final float loadFactor;
    
    /**HashMap被改变的次数，由于HashMap非线程安全，在对HashMap进行迭代时，
    如果期间其他线程的参与导致HashMap的结构发生变化了（比如put，remove等操作），
    需要抛出异常ConcurrentModificationException*/
    transient int modCount;
    复制代码

### 构造器 ###

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

`initialCapacity`默认为16，`loadFactory`默认为0.75

/**
         * Constructs an empty <tt>HashMap</tt> with the specified initial
         * capacity and load factor.
         *
         * @param  initialCapacity the initial capacity
         * @param  loadFactor      the load factor
         * @throws IllegalArgumentException if the initial capacity is negative
         *         or the load factor is nonpositive
         */
        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();
        }
    
        /**
         * Constructs an empty <tt>HashMap</tt> with the specified initial
         * capacity and the default load factor (0.75).
         *
         * @param  initialCapacity the initial capacity.
         * @throws IllegalArgumentException if the initial capacity is negative.
         */
        public HashMap(int initialCapacity) {
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
        }
    
        /**
         * Constructs an empty <tt>HashMap</tt> with the default initial capacity
         * (16) and the default load factor (0.75).
         */
        public HashMap() {
            this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
        }
    
        /**
         * Constructs a new <tt>HashMap</tt> with the same mappings as the
         * specified <tt>Map</tt>.  The <tt>HashMap</tt> is created with
         * default load factor (0.75) and an initial capacity sufficient to
         * hold the mappings in the specified <tt>Map</tt>.
         *
         * @param   m the map whose mappings are to be placed in this map
         * @throws  NullPointerException if the specified map is null
         */
        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);
    
            putAllForCreate(m);
        }
    
    复制代码

我们以默认构造器为例查看一下源码。

![format_png 5][]

public HashMap() {
        //this(16,0.75);
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }
    复制代码

这里调用的是另一个重载构造器`public HashMap(int initialCapacity, float loadFactor)`

![format_png 6][]

这构造方法主要就是设置赋值负载因子`loadFactor`默认值为0.75，设置阈值`threshold`，当前为16。threshold一般为`capacity *loadFactory`

**init方法在HashMap中没有实际实现，不过在其子类如 linkedHashMap中就会有对应实现**

public HashMap(int initialCapacity, float loadFactor) {
    　　　　　//此处对传入的初始容量进行校验，最大不能超过MAXIMUM_CAPACITY = 1<<30(230)
            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中就会有对应实现
        }
    复制代码

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

![format_png 7][]

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);
    
        putAllForCreate(m);
    }
    复制代码

### put() ###

我们在看看`put()`方法

![format_png 8][]

public V put(K key, V value) {
            //如果table数组为空数组{}，进行数组填充（为table分配实际内存空间），入参为threshold，
            //此时threshold为initialCapacity 默认是1<<4(24=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);
                    return oldValue;
                }
            }
            modCount++;//保证并发访问时，若HashMap内部结构发生变化，快速响应失败
            addEntry(hash, key, value, i);//新增一个entry
            return null;
        }
    复制代码

此时我们在去看看`inflateTable()`方法

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

![format_png 9][]

private void inflateTable(int toSize) {
            int capacity = roundUpToPowerOf2(toSize);//capacity一定是2的次幂
            /**此处为threshold赋值，取capacity*loadFactor和MAXIMUM_CAPACITY+1的最小值，
            capaticy一定不会超过MAXIMUM_CAPACITY，除非loadFactor大于1 */
            threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
            table = new Entry[capacity];
            initHashSeedAsNeeded(capacity);
        }
    复制代码

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

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;
        }
    
    复制代码

接着我们在回头看put中的`hash()`

![format_png 10][]

**这是一个神奇的函数，用了很多的异或，移位等运算对key的hashcode进一步进行计算以及二进制位的调整等来保证最终获取的存储位置尽量分布均匀。**

![format_png 11][]

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

以上hash函数计算出的值，通过`indexFor()`进一步处理来获取实际的存储位置

![format_png 12][]

static int indexFor(int h, int length) {
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
        return h & (length-1);
    }
    复制代码

`h & (length-1);`这里的length传入的也就是HashMap的数组长度，当前为16。但是它是怎么保证通过该方法得到的数组下标是符合数组下标范围的呢？也就是`[0,15]`

![format_png 13][]

假设我们的得到的h二进制为`0101 0101`，length为16二进制为`0001 0000`,减1变成15二进制变成了`0000 1111`此时再与h做`&`运算，得到的数也就是h二进制的后四位数`0101`。而h是根据key的hashCode方法和hash()方法，是具有随机性的！**但是只要我们保证HashMap的数组长度为2的次方，例如这里得到的索引下标范围就是二进制的\[0000,1111\]也就是\[0,15\]。从而保证了下标的范围的合理性！**

![format_png 14][]

同样有一个问题，为啥不使用我们之前设想过的`%`操作，而是使用`&`操作呢？？

**这是因为`&`在任何操作系统上都是比较二进制位的操作。所以都不会慢,效率远比`%`高～**

得到了我们想要的数组下标之后，我们在来看看put()方法中的后续操作。

![format_png 15][]

for循环中的我们首先可以不用查看，我们可以看到调用了`addEntry()`方法

![format_png 16][]

void addEntry(int hash, K key, V value, int bucketIndex) {
            if ((size >= threshold) && (null != table[bucketIndex])) {
                resize(2 * table.length);//当size超过临界阈值threshold，并且即将发生哈希冲突时进行扩容
                hash = (null != key) ? hash(key) : 0;
                bucketIndex = indexFor(hash, table.length);
            }
    
            createEntry(hash, key, value, bucketIndex);
        }
    复制代码

**`size>=threshold` HashMap的数组元素个数已经大于等于12。且当前要添加的数组下标位置已经存在元素了(准备添加时发生哈希冲突)。`resize(2*table.length)`将其扩容2倍**。

我们来看看`resize()`方法

![format_png 17][]

void resize(int newCapacity) {
        //旧Entry数组
        Entry[] oldTable = table;
        //旧Entry数组长度
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }
        //新Entry数组，长度为旧的两倍（2 * table.length）
        Entry[] newTable = new Entry[newCapacity];
        //将旧Entry数组中的值重新计算，添加到新Entry数组中
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        //指向新Entry数组
        table = newTable;
        //得到新的阈值（2*table.length*0.75=2*16*0.75=24）
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }
    
    /**
     * Transfers all entries from current table to newTable.
     */
    void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        //循环遍历table（旧Entry数组）
        for (Entry<K,V> e : table) {
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                //得到新Entry数组索引
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }
    复制代码

`transfer()`方法，将旧Entry数组重新计算数组索引，添加到新Entry数组。这里添加的位置是有两种的！，一种是`原来的位置`，一种是`原来位置+原先数组长度`。为什么是这个两个位置呢？我们来分析一下～还是使用之前分析的假设值

![format_png 18][]

说完扩容resize方法,回到addEntry方法中，查看`createEntry（）`方法

![format_png 19][]

![format_png 20][]

void createEntry(int hash, K key, V value, int bucketIndex) {
        //首先获取该下标位置的元素，赋值给e
        Entry<K,V> e = table[bucketIndex];
        //在这个下标创建一个新Entry元素，next指向e。头插法
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        //HashMap元素加1
        size++;
    }
    复制代码

![format_png 21][]

到此为此为止我们HashMap终于通过构造器创建，并成功添加一个元素啦。

我们再回到`put()` 方法。看一下该for循环。

![format_png 22][]

该循环是遍历该数组下标位置的链表，判断是否存在相同Key，存在则覆盖值value，返回旧值。

![format_png 23][]

`e.hash == hash && ((k = e.key) == key || key.equals(k))`判断键是否相同。

hash值不相等，对象一定不相等。

hash值相等，对象不一定相等。

两键是同一个对象，首先比较两个的hash值是否相同，如果相同再比较两个的内存地址值是否相同。

或者equals()方法比较是否相等。

**HashMap是允许我们添加一个键为`null`的键值对的。**

![format_png 24][]

当我们的键为`null`添加的时候调用的是`putForNullKey()`方法。

![format_png 25][]

**在数组下标为0的位置添加null键值对，添加前同样遍历一遍，看是否存在相同键。存在覆盖值，返回旧值。**

![format_png 26][]

*  ①如果定位到的数组位置没有元素 就直接插入。
 *  ②如果定位到的数组位置有元素，遍历以这个元素为头结点的链表，依次和插入的key比较，如果key相同就直接覆盖，不同就采用头插法插入元素。

### get() ###

分析了一遍put()，之后再看get()就会简单许多。

![format_png 27][]

public V get(Object key) {
        //如果key为null调用getForNUllKey方法
        if (key == null)
            return getForNullKey();
        //根据key调用getEntry方法获取到Entry对象
        Entry<K,V> entry = getEntry(key);
        //返回获取到的Entry对象的值
        return null == entry ? null : entry.getValue();
    }
    复制代码

private V getForNullKey() {
        //如果当前HashMap元素个数为0，直接返回null
        if (size == 0) {
            return null;
        }
        //循环遍历第一个下标位置的链表，获取到Entry对象，返回值
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            //键为null固定存放在这位置
            if (e.key == null)
                return e.value;
        }
        return null;
    }
    复制代码

查看源码可以得知最重要的是调用`getEntry()`方法，我们来查看这个方法。

![format_png 28][]

final Entry<K,V> getEntry(Object key) {
        //HashMap元素个数为0，直接返回null
        if (size == 0) {
            return null;
        }
        //通过hash()方法得到该key的hash值
        int hash = (key == null) ? 0 : hash(key);
        //indexFor()通过hash值计算得到数组下标后遍历
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
           //判断key是否相同
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                //返回该Entry对象
                return e;
        }
        return null;
    }
    复制代码

到此为止JDK7版本的HashMap核心源码基本分析完成。

## JDK8 ##

在JDK8中`Entry`对象名字变成了`Node`。底层数据结构也不单单是`数组+链表`而是会变成`数组+红黑树`

![format_png 29][]

final int hash;
            final K key;
            V value;
            Node<K,V> next;
    
            Node(int hash, K key, V value, Node<K,V> next) {
                this.hash = hash;
                this.key = key;
                this.value = value;
                this.next = next;
            }
    复制代码

### 参数 ###

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
        // 序列号
        private static final long serialVersionUID = 362498820763181265L;    
        // 默认的初始容量是16
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;   
        // 最大容量
        static final int MAXIMUM_CAPACITY = 1 << 30; 
        // 默认的填充因子
        static final float DEFAULT_LOAD_FACTOR = 0.75f;
        // 当桶(bucket)上的结点数大于这个值时会转成红黑树
        static final int TREEIFY_THRESHOLD = 8; 
        // 当桶(bucket)上的结点数小于这个值时树转链表
        static final int UNTREEIFY_THRESHOLD = 6;
        // 桶中结构转化为红黑树对应的table的最小大小
        static final int MIN_TREEIFY_CAPACITY = 64;
        // 存储元素的数组，总是2的幂次倍
        transient Node<k,v>[] table; 
        // 存放具体元素的集
        transient Set<map.entry<k,v>> entrySet;
        // 存放元素的个数，注意这个不等于数组的长度。
        transient int size;
        // 每次扩容和更改map结构的计数器
        transient int modCount;   
        // 临界值 当实际大小(容量*填充因子)超过临界值时，会进行扩容
        int threshold;
        // 加载因子
        final float loadFactor;
    }
    复制代码

**loadFactor加载因子**

loadFactor加载因子是控制数组存放数据的疏密程度，loadFactor越趋近于1，那么 数组中存放的数据(entry)也就越多，也就越密，也就是会让链表的长度增加，loadFactor越小，也就是趋近于0，数组中存放的数据(entry)也就越少，也就越稀疏。

**loadFactor太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。loadFactor的默认值为0.75f是官方给出的一个比较好的临界值**。

给定的默认容量为 16，负载因子为 0.75。Map 在使用过程中不断的往里面存放数据，当数量达到了 16 \* 0.75 = 12 就需要将当前 16 的容量进行扩容，而扩容这个过程涉及到 rehash、复制数据等操作，所以非常消耗性能。

**threshold**

**threshold = capacity \* loadFactor**，**当Size>=threshold**的时候，那么就要考虑对数组的扩增了，也就是说，这个的意思就是 **衡量数组是否需要扩增的一个标准**。

当桶(bucket)上的结点数大于这个值时会转成红黑树 `static final int TREEIFY_THRESHOLD = 8;`

当桶(bucket)上的结点数小于这个值时树转链表 `static final int UNTREEIFY_THRESHOLD = 6;`

**只所以不是小于8而是小于6转就是为了防止出现反复转换底层结构的情况出现。**

### 构造方法 ###

// 默认构造函数。
        public HashMap() {
            this.loadFactor = DEFAULT_LOAD_FACTOR; // all   other fields defaulted
         }
         
         // 包含另一个“Map”的构造函数
         public HashMap(Map<? extends K, ? extends V> m) {
             this.loadFactor = DEFAULT_LOAD_FACTOR;
             putMapEntries(m, false);//下面会分析到这个方法
         }
         
         // 指定“容量大小”的构造函数
         public HashMap(int initialCapacity) {
             this(initialCapacity, DEFAULT_LOAD_FACTOR);
         }
         
         // 指定“容量大小”和“加载因子”的构造函数
         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;
             this.threshold = tableSizeFor(initialCapacity);
         }
    复制代码

这里使用默认构造器实例化对象`this.loadFactor = DEFAULT_LOAD_FACTOR;`把loadFactor设置为0.75。

### putVal() ###

JDK1.8版本的HashMap的向里面的添加元素的put()方法实际调用的就是`putVal()`方法。

public V put(K key, V value) {
            return putVal(hash(key), key, value, false, true);
        }
    复制代码

不过先使用了`hash()`方法得到了key的hash值，这个hash()方法相比JDK7，简单了一点（因为后面用到了红黑树保证效率）

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    复制代码

**执行put操作的时候才真正构建table数组**

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // table未初始化或者长度为0，进行扩容
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中)
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        // 桶中已经存在元素
        else {
            Node<K,V> e; K k;
            // 比较桶中第一个元素(数组中的结点)的hash值相等，key相等
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                    // 将第一个元素赋值给e，用e来记录
                    e = p;
            // hash值不相等，即key不相等；为红黑树结点
            else if (p instanceof TreeNode)
                // 放入树中
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            // 为链表结点
            else {
                // 在链表最末插入结点
                for (int binCount = 0; ; ++binCount) {
                    // 到达链表的尾部
                    if ((e = p.next) == null) {
                        // 在尾部插入新结点
                        p.next = newNode(hash, key, value, null);
                        // 结点数量达到阈值，转化为红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        // 跳出循环
                        break;
                    }
                    // 判断链表中结点的key值与插入的元素的key值是否相等
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        // 相等，跳出循环
                        break;
                    // 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
                    p = e;
                }
            }
            // 表示在桶中找到key值、hash值与插入元素相等的结点
            if (e != null) { 
                // 记录e的value
                V oldValue = e.value;
                // onlyIfAbsent为false或者旧值为null
                if (!onlyIfAbsent || oldValue == null)
                    //用新值替换旧值
                    e.value = value;
                // 访问后回调
                afterNodeAccess(e);
                // 返回旧值
                return oldValue;
            }
        }
        // 结构性修改
        ++modCount;
        // 实际大小大于阈值则扩容
        if (++size > threshold)
            resize();
        // 插入后回调
        afterNodeInsertion(evict);
        return null;
    } 
    复制代码

`if ((tab = table) == null || (n = tab.length) == 0)`table未初始化或者长度为0，进行扩容。`n = (tab = resize()).length;` **resize方法即是初始化方法，也是扩容方法。**

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            // 超过最大值就不再扩充了，就只好随你碰撞去吧
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            // 没超过最大值，就扩充为原来的2倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else { 
            // signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        // 计算新的resize上限
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            // 把每个bucket都移动到新的buckets中
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { 
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            // 原索引
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            // 原索引+oldCap
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        // 原索引放到bucket里
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        // 原索引+oldCap放到bucket里
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }
    复制代码

此时我们符合的是这个条件

else { 
        // signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;//16
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//16*0.75=12
    }
    
    复制代码

threshold = newThr;//阈值赋值为12
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//创建新数组长度为16
    table = newTab;//指向新数组
    复制代码

**此时才完成对存储数组的初始化，大小为16,阈值为12。**

//当前数组下标没有元素，直接插入 此时p已经被赋值为数组索引的第一个位置，也就是链表头或者树根。
    if ((p = tab[i = (n - 1) & hash]) == null)  
        tab[i] = newNode(hash, key, value, null);
    复制代码

**`if ((p = tab[i = (n - 1) & hash]) == null)`只要经过这个判断p就被赋值了，该位置数组元素为空时，p为null。只要不为空就是链表头或者树根节点。**

**键相等情况，都是覆盖值，返回旧值**。

![format_png 30][]

![format_png 31][]

Node<K,V> e; K k;
    //当该数组下标第一个对象的key就相等时
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
        e = p;
    复制代码

//首先判断是否为树节点
    else if (p instanceof TreeNode)
        //为树节点则采用添加树节点的方法添加
        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    复制代码

**使用的是尾插法插入**

// 为链表结点
            else {
                // 在链表最末插入结点
                for (int binCount = 0; ; ++binCount) {
                    // 到达链表的尾部
                    if ((e = p.next) == null) {
                        // 在尾部插入新结点
                        p.next = newNode(hash, key, value, null);
                        // 结点数量达到阈值，转化为红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        // 跳出循环
                        break;
                    }
                    // 判断链表中结点的key值与插入的元素的key值是否相等
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        // 相等，跳出循环
                        break;
                    // 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
                    p = e;
                }
            }
    复制代码

if (e != null) { // existing mapping for key key已经存在
        V oldValue = e.value;
        if (!onlyIfAbsent || oldValue == null)
            //覆盖值
            e.value = value;
        afterNodeAccess(e);
        //返回旧值
        return oldValue;
    }
    复制代码

// 实际大小大于阈值则扩容
        if (++size > threshold)
            resize();
        // 插入后回调
        afterNodeInsertion(evict);
        return null;
    复制代码

当HashMap元素大于阈值12时调用resize()。阈值，数组长度扩大为2倍。

// 没超过最大值，就扩充为原来的2倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
    复制代码

*  ①如果定位到的数组位置没有元素 就直接插入。
 *  ②如果定位到的数组位置有元素就和要插入的key比较，如果key相同就直接覆盖，如果key不相同，就判断p是否是一个树节点，如果是就调用`e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value)`将元素添加进入。如果不是就遍历链表插入(插入的是链表尾部)。

### treeifyBin() ###

// 结点数量达到阈值8，转化为红黑树
     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
      treeifyBin(tab, hash);
    复制代码

当我们的链表节点大于阈值8点时候，调用treeifyBin()方法，

final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            do {
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }
    复制代码

`if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)`当我们链表长度为8的时候也不一定树化，而是要判断数组长度是否要大于`static final int MIN_TREEIFY_CAPACITY = 64;`如果不满足则会扩容。也就是树化的条件有两个

*  **链表长度要大于等于8**
 *  **数组长度要大于等于64**

### get() ###

public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
    复制代码

final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            // 数组元素相等
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            // 桶中不止一个节点
            if ((e = first.next) != null) {
                // 在树中get
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                // 在链表中get
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }
    复制代码

**e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))) 前面比较的是hash值，后面比较的是对象是否相等。（==相等，或者equals相等）。**

## 总结 ##

1.  哈希表的存储实际容量是2的次幂。
2.  JDK7底层采用数组+链表方式存储，使用头插法。JDK8底层采用数组+链表+红黑树方式存储，使用尾插法。
3.  哈希表中元素个数大于等于阈值的时候才会进行扩容。
4.  哈希表中的table数组只有执行put操作的时候才会真正构建。
5.  JDK8中树化的条件必须满足链表「大于等于」8，数组长度「大于等于」64。

[format_png]: https://img-blog.csdnimg.cn/img_convert/63a0b1664188623633a60082343adf63.webp?x-oss-process=image/format,png
[format_png 1]: https://img-blog.csdnimg.cn/img_convert/c3b55ff399858fc3350104138c808145.webp?x-oss-process=image/format,png
[format_png 2]: https://img-blog.csdnimg.cn/img_convert/ff27693b1670280b6dfd1da42fe15ed0.webp?x-oss-process=image/format,png
[format_png 3]: https://img-blog.csdnimg.cn/img_convert/d87f727a5afbaf351c18921eb3fadefb.webp?x-oss-process=image/format,png
[format_png 4]: https://img-blog.csdnimg.cn/img_convert/9735f7f5bf1d503224c1521fe95545cb.webp?x-oss-process=image/format,png
[format_png 5]: https://img-blog.csdnimg.cn/img_convert/2955c3ef915bea64991e584e07836279.webp?x-oss-process=image/format,png
[format_png 6]: https://img-blog.csdnimg.cn/img_convert/c818b50a9519c0c5b1b77a2be89cd469.webp?x-oss-process=image/format,png
[format_png 7]: https://img-blog.csdnimg.cn/img_convert/8c7efcbef0b17fd06005e8fd04a40bf5.webp?x-oss-process=image/format,png
[format_png 8]: https://img-blog.csdnimg.cn/img_convert/f735df8a622a2ccfa06e9df8a84cdcf0.webp?x-oss-process=image/format,png
[format_png 9]: https://img-blog.csdnimg.cn/img_convert/1d708512359b0bddef28dad549b1c962.webp?x-oss-process=image/format,png
[format_png 10]: https://img-blog.csdnimg.cn/img_convert/d02afb6f7054522435abfc0cf44f87d1.webp?x-oss-process=image/format,png
[format_png 11]: https://img-blog.csdnimg.cn/img_convert/58561dacb7f3fd5db71acca1d979ffd7.webp?x-oss-process=image/format,png
[format_png 12]: https://img-blog.csdnimg.cn/img_convert/6152136bde4a25ed05fe367bd1beb16c.webp?x-oss-process=image/format,png
[format_png 13]: https://img-blog.csdnimg.cn/img_convert/f65dfe5c17d8f95fcf9c042af48e2386.webp?x-oss-process=image/format,png
[format_png 14]: https://img-blog.csdnimg.cn/img_convert/80f7766e222e9eb201c12876d5c40ee9.webp?x-oss-process=image/format,png
[format_png 15]: https://img-blog.csdnimg.cn/img_convert/b5e813a32561a000aa31226b483ddb6c.webp?x-oss-process=image/format,png
[format_png 16]: https://img-blog.csdnimg.cn/img_convert/8eee980349e4585cf4a4828070088d45.webp?x-oss-process=image/format,png
[format_png 17]: https://img-blog.csdnimg.cn/img_convert/17ed57df98a1378b368b6e0fad779262.webp?x-oss-process=image/format,png
[format_png 18]: https://img-blog.csdnimg.cn/img_convert/4961ae3b392e28073ce503084949cca1.webp?x-oss-process=image/format,png
[format_png 19]: https://img-blog.csdnimg.cn/img_convert/2248c59fa0e58ebf9584ff6f8afc8b62.webp?x-oss-process=image/format,png
[format_png 20]: https://img-blog.csdnimg.cn/img_convert/aebeb3cb2633a5e617c0897bd06b1690.webp?x-oss-process=image/format,png
[format_png 21]: https://img-blog.csdnimg.cn/img_convert/9b7714b1e05e78c5efeff9f5e280cb5e.webp?x-oss-process=image/format,png
[format_png 22]: https://img-blog.csdnimg.cn/img_convert/f90b1a82f645ce9f17c6193646bdfc65.webp?x-oss-process=image/format,png
[format_png 23]: https://img-blog.csdnimg.cn/img_convert/e8f1893359b0a4a454354af97091bac2.webp?x-oss-process=image/format,png
[format_png 24]: https://img-blog.csdnimg.cn/img_convert/126e784acd40085492d4c63ffbb00124.webp?x-oss-process=image/format,png
[format_png 25]: https://img-blog.csdnimg.cn/img_convert/a356e94e4d44f0f9bf5f7cfea78a2f04.webp?x-oss-process=image/format,png
[format_png 26]: https://img-blog.csdnimg.cn/img_convert/9478df907b593e1b5e345342b152b833.webp?x-oss-process=image/format,png
[format_png 27]: https://img-blog.csdnimg.cn/img_convert/bfb283b13f59715f198983d58e733283.webp?x-oss-process=image/format,png
[format_png 28]: https://img-blog.csdnimg.cn/img_convert/e73d08dfff01a3a5ab9b46974d93a18e.webp?x-oss-process=image/format,png
[format_png 29]: https://img-blog.csdnimg.cn/img_convert/f5d4c0a1c3065e12fc274df8105d1263.webp?x-oss-process=image/format,png
[format_png 30]: https://img-blog.csdnimg.cn/img_convert/5923072e5317028bc6596ec99dc37e07.webp?x-oss-process=image/format,png
[format_png 31]: https://img-blog.csdnimg.cn/img_convert/3e78ac51b798d13a7dcb72c7d44c2532.webp?x-oss-process=image/format,png