目录

引言

HashMap存储结构

调用put()方法添加元素

HashMap什么时候扩容？

---

 

引言

HashMap实现了Map接口，它是双列集合中的一员，与单列集合不同的是，单列集合中只能存储某一类元素，它是一组值，而HashMap存储的是一个个key-value键值对，由一个键映射一个value。HashMap是无序，键唯一的。

HashMap存储结构

• HashMap内部数据结构使用数组+链表+红黑树进行存储。

  

• 数组：数组类型为Node[]，默认长度为16，每个Node都保存了某个KV键值对元素的key、value、hash、next等值。由于next的存在，所以每个Node对象都是一个单向链表中的组成节点。
• 链表：当新添加一个KV键值对元素时，通过该元素的key的hash值，计算该元素在数组中应该保存的下标位置。如果该下标位置如果已经存在其它Node对象（产生哈希冲突），则采用链地址法处理，即将新添加的KV键值对元素将以链表形式存储。将新元素封装成一个新的Node对象，插入到该下标位置的链表尾部（尾插法）。
• 红黑树：当链表的长度超过8并且数组长度大于64时，为了避免查找搜索性能下降，该链表会转换成一个红黑树。

调用put()方法添加元素

1.通过HashMap对象调用put()方法，在这个方法中调用putVal()方法。

   public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
 
   final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node[] tab; Node p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode)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;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

2.在putVal()方法中首先调用hash()方法，将键key传入这个方法。重新计算这个键的哈希值。并将这个哈希值传入putVal()方法。这个参数是决定元素存储位置的关键因素之一。

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

3.在 putVal()方法中，判断数组是否为空，如果为空则将数组进行初始化。

4.如果不为空，用传入putVal()方法中的hash(即上文中调用hash()方法算出)，通过数组长度（n-1)&hash 计算元素应当存放在Node数组中的下标index。

5.查看table[index]中是否有数据。

6.如果没有数据，就将要存入的key，value封装成一个Node节点。存放在table[index]中。

 

 

7.如果存在数据，说明发生哈希冲突，继续判断key是否相同。如果相同，用新的value替换原数据。

8.如果不相同，判断当前节点是不是TreeNode树型的节点。

9.如果是 树形节点，就将key，value封装成树型节点插入红黑树中。

10.如果不是树型节点， 将key，value封装成一个Node节点。链接在链表尾部。

 

11.判断链表长度是否大于8，并且数组长度大于64，如果满足，就将链表转换为红黑树；如果不满足，数组扩容；

 

 

12.元素添加完成，判断当前节点数是否大于实际存储空间的大小；

13.如果大于，调用resize()方法，按照原数组的长度，扩容一倍（扩容后容量小于或等于64）。然后将原数组的内容复制至新数组。

 

 扩容：

 复制：

HashMap什么时候扩容？

在添加元素的过程中，势必会造成HashMap扩容，什么时候扩容呢？

• 当HashMap中的元素个数超过数组大小 x 加载因子（LoadFactor）时，就会进行数组扩容，加载因子默认是0.75。
• 加入元素时，如果链表长度大于8，并且数组长度小于64，会进行数组扩容。
• 加入元素时，如果链表长度大于8，并且数组长度等于64，会将链表转换为红黑树。

每次扩容，元素都会重新散列。