HashMap介绍

---

HashMap 可以说是使用频率最高的处理键值映射的数据结构，它不保证插入顺序，允许插入 null 的键和值。

1、HashMap容量解密

了解过HashMap都应该知道，HashMap内部会创建一个Entry<K, V> table数组来存放元素，而且这个数组的长度永远都是2的指数次方。那么问题来了，为什么选择2的指数次方呢？

1.1 容量为什么是2的指数冥

由于HashMap是数据+链表+红黑树结构，在对HashMap进行操作时，选通过定位数组下标去添加或查找数据。为了保证数据能均匀的分布在数组中，需要通过一种算法实现。而对KEY取hashcode取模是较好的实现数据的均匀分布，但由于在HashMap中存在大量的存取数据以及数据再分布，都大量涉及到取模运算，由于取模运算效率相对于加、减等效率低，为了能达到取模的效果，HashMap采取了容量为2的指数冥。

假设，HashMap的容量为32，KEY的HASHCODE为45，如果通,过取模运算，得到的数组下标为13,32的二进制为100000，45的二进制为101101，然后将101101&011111(100000-1)=0001101=13

通过以上分析HashMap将容量设为2的指数冥有以下好处：

• &运算速度快，至少比%取模运算块
• 能保证 索引值 肯定在 capacity 中，不会超出数组长度
• (n - 1) & hash，当n为2次幂时，会满足一个公式：(n - 1) & hash = hash % n

1.2 构造函数说明

HashMap有带参与不带参的构造函数，如果在初始化时不带参数，会默认初始化容量大小为16，另一个带参数的构造函数如下：

public HashMap(int initialCapacity)

对于带参数的构造函数，是不是填入什么值，初化该值大小的容量呢？我们知道HashMap的容量总是为2的指数冥，所以对于传进来的值，会被转成2的指数次冥。源码如下：

    /**
     * Returns a power of two size for the given target capacity.
     */
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

分析如下:
假设传入的容量参数为23，

n = 23-1 (10110)   //int n = cap - 1;
n=  (n >>> 1)01011|10110=11111  // n |= n >>> 1;
n= 11111 | 00111=11111
n= 11111|01111=11111
n=11111|00000=11111
n=11111|00000=11111

计算结果为31+1=32，通过计算得出，对于传入的初始容量，HashMap会重新计算出一个大于或等于该数的最接近的2的指数冥。

2 基本结构

HashMap 基于散列表实现，使用拉链法处理碰撞，在 JDK8 中，当链表长度大于 8 时转为红黑树存储，基本结构如下：

HashMap 基本结构

HashMap 有一个 Node<K,V>[] table 字段，即哈希桶数组，数组元素是 Node 对象