源码：常用集合类之 HashMap

た入场券 2021-10-24 00:14 346阅读 0赞

### 文章目录 ###

*   *   *   *  0 前言
             *  1 属性的声明
             *  2 构造方法
             *  3 添加 put
             *  4 扩容 resize
             *  5 获取 get
             *  6 删除 remove
             *  7 位运算

--------------------

#### 0 前言 ####

Hashmap 内部结构是数组加链表或数组加红黑树实现。table表示数组，存放map中每个 K-V 都封装成node结构放入链表或者树中。table的每个下标位置就是一个桶，桶内是链表或红黑树。size则表示当前map中node个数。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70]  
  Node 结构：  
![在这里插入图片描述][20190817162910570.PNG]

#### 1 属性的声明 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70 1]DEFAULT\_INITIAL\_CAPACITY：默认初始容量16  
MAXIMUM\_CAPACITY：最大容量2^30  
DEFAULT\_LOAD\_FACTOR：默认负载因子0.75  
TREEIFY\_THRESHOLD：树化阈值8，大于等于尝试从链表变为红黑树  
UNTREEIFY\_THRESHOLD：小于等于尝试从红黑树变为链表  
MIN\_TREEIFY\_CAPACITY：最小树化容量64，map中node个数超过此值才会真正变为红黑树  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70 2]  
table：桶个数  
size：map中node节点个数，就是map中元素个数  
threshold：阈值默认为默认容量×默认负载因子，16×0.75  
loadFactor：负载因子  
modeCount：实现fail-fast机制

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70 3]

*  无参构造方法，只是指定负载因子为默认值。在**添加元素时候才舒适化table容量**。
 *  指定容量和负载因子的构造方法，并不会按照我们给的容量初始化table大小（这点和ArrayLisst不同）。  
    tableSizeFor(int cap)方法可以看出，容量总是2的n次方，n的取值为2^n-1 < cap <= 2^n。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70 4]

#### 3 添加 put ####

![在这里插入图片描述][20190817172852756.png]  
![在这里插入图片描述][20190817172924586.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70 5]

*  1 计算key的hash值，没有直接使用hashcode而是hash方法主要增加了hash值得随机性。
 *  2 如果table为空则将容量和负载因子先初始化到默认值，调用resize方法。
 *  3 根据hash值计算应该放在哪个桶中，如果桶中没有元素（每个元素是一个node结构），则直接放入，如有有元素则执行步骤4
 *  4.1 每个桶中的元素最初以链表方式存储，挨个遍历链表中元素，寻找hash值与key都相同的node，然后将node的值进行更新，没有找到则直接放入链表尾部，当链表长度达到8会尝试树化。
 *  4.2 如果元素已经是按红黑树的结构存储，则在树中找节点或者加入树。
 *  5 不论是加入链表还是加入树结构中，表示map元素数量size加一，同时说明map结构发生修改，modCount值加一。
 *  6 当size超出扩容阈值threshold（容量\*负载因子），调用resize方法扩容。

**注意：** 1.通过key的hash值与table.length-1做&位运算计算应该放入那个下标的桶中（所以容量为2^n）。2.如果添加的元素的链表达到8会尝试树化（table.length<64只会扩容），下图，链表变为红黑树。3.当map中元素个数达到扩容阈值时，就会调用resize方法扩容（添加完再扩容）。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70 6]

#### 4 扩容 resize ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70 7]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70 8]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70 9]

*  1 计算原容量和原扩容阈值
 *  2.1 如果原容量大于0并且超过默认容量最大值2^30 ，则将原扩容阈值设置为maxint并返回；如果没有超过 2^30，则新容量为原来2倍，新容量不超过最大值，将阈值也扩大为原来2倍。
 *  2.2 如果原容量小于等于0，但是原阈值大于0，将原阈值设置为新容量。
 *  2.3 如果原容量和原扩容阈值都为0，则设置为默认值16和16\*0.75，无参构造方法第一次put时走此分支。
 *  3 map中table和扩容阈值都设置为新值，不是初次初始化容量，则需要对原来链表或者树进行拆分，重新散列，根据hash值重新分配到新table的桶中。
 *  4 遍历原table每个桶中元素。如果桶只有一个node则直接散列到新数组中；如果桶中是树，则将树拆分为两个子树，放到新数组中；如果是链表则按hash&oldcap=0拆分为低位高位两个链表，低位链表放在与原table相同下标index的新table的桶中，高位链表放在新table下标index+oldcap的桶中。

**注意：** 可以发现扩容后对于元素的散列并不是将所有元素取出重新hash&newCap-1计算。考虑最常见情况就是每次容量扩大两倍。下标oldindex的桶中只有一个元素时候，hash&newCap-1计算出来值只可能为oldindex或者是index+oldsize，比如oldindex为6，那么newindex为6或22。oldindex桶中是一个链表的化，拆分的低位链还放在oldindex，高位链在oldindex+oldsize，这样保证了原来不在一个桶中的元素现在也不会在同一个桶中。另外在拆分高低位链表时，根据hash&oldcap=0来判断，从概率上说是50%（只关心hash值右起第五位是否为1）。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70 10]  
假设key的hash值为54，如上图，所在node节点会放在下标为6的桶中，扩容后重新计算的下标为22。如果在node链表中，则hash&oldcap计算不为0，会放在高位链表，直接放在oldindex+oldsize=6+16=22下标的桶中，所以不需要重新计算hash值。

#### 5 获取 get ####

![在这里插入图片描述][20190818103905491.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70 11]

*  1 计算key的hash值
 *  2 如果table为空或者根据hash计算出桶为空直接返回空，如果不为空，从树结构或者是链表中寻找相同hash值和key值的node并返回，如果没找到返回null
 *  3 如果node不为null返回node中的值，否则返回null

**注意：** 返回null并不能说明node不存在，也可能是node的值为null，所以避免歧义通常value为null的元素不应该put。

#### 6 删除 remove ####

![在这里插入图片描述][20190818104641313.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70 12]

*  1 计算key的hash值
 *  2 如果table为空或者根据hash计算出桶为空直接返回空，如果不为空，从树结构或者是链表中寻找相同hash值和key值的node并返回，如果没找到返回null
 *  3 如果node不为null，则将node删除
 *  4 将修改次数modCount加一，size减一。

#### 7 位运算 ####

**&  与**：二进制数假设1为真，0为假。a&b就是二进制每一位&，都为真时结果为真。  
  **|   或**：有一位为真就为真。  
  **^  异或**：二进制每一位，相同为0，不同为1。

![在这里插入图片描述][20190818105858273.PNG]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70]: /images/20211023/4316a309490f4442b61a39e3c3372d4f.png
[20190817162910570.PNG]: /images/20211023/c6c38444417a474698cbc9895379017e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70 1]: /images/20211023/7df04a4818cf4bf4a27e72387fcbd689.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70 2]: /images/20211023/42454ab98b30437382cd4bd12735ac09.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70 3]: /images/20211023/2f7102155feb4479b497721817c72ef8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70 4]: /images/20211023/7b4b22f9cf694f2e96648ec45a5e597c.png
[20190817172852756.png]: /images/20211023/dca4400cdcec48a8835dc763ef4265c2.png
[20190817172924586.png]: /images/20211023/9f38195d1b864ba3ac1d8ec6699592f6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70 5]: /images/20211023/0077f8165abc486e81d81b442f4eb33b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70 6]: /images/20211023/f68a812df1c247afa2c2d461fc0ee853.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20190818095440937.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20190818100745122.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70 9]: /images/20211023/ed5a77f9d29d49acbfe708fbd89aa20b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70 10]: /images/20211023/6b79521e91af4e73aa96af5bcfbfd687.png
[20190818103905491.png]: /images/20211023/dee32a38fe47474390541af6922c2e3a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70 11]: /images/20211023/869d45ed61fb4e5ab4b200b1c531f74c.png
[20190818104641313.png]: /images/20211023/91cdd3f837724eb88702ba8c6226681e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRlX2Zyb2c_size_16_color_FFFFFF_t_70 12]: /images/20211023/85b2b2cd8fc94d15a4fbfef31e241380.png
[20190818105858273.PNG]: /images/20211023/69cffacb90194c0d89742e95aabaab13.png