【容器源码篇】Map容器（HashTable，HashMap，TreeMap的特点）

逃离我推掉我的手 2024-04-17 06:45 66阅读 0赞

#### 文章目录 ####

*  ⭐容器继承关系
 *   *  ?Map容器
     *   *  ?️HashTable源码解析
         *   *  构造方法
             *  put方法
             *  remove方法
             *  rehash扩容
         *  ?️HashMap源码解析
         *   *  构造函数
             *  get方法
             *  put方法
             *   *  详解
             *  扩容方法
             *   *  详解
             *  ?️TreeMap源码解析

![在这里插入图片描述][b49da993dba6490997d7f6f23a039ca6.png_pic_center]

## ⭐容器继承关系 ##

![在这里插入图片描述][0b9b3ff8e7d440539a6ef83315bb5ebd.png]

### ?Map容器 ###

键值对映射：Map容器中的元素是以`键值对`的形式存储的，每个键对应一个值。通过键可以快速查找对应的值。

键不重复：Map中的`键是唯一的，每个键对应一个值`。如果添加已经存在的键，则会更新对应的值。

常用操作：Map提供了添加键值对、获取值、判断是否包含某个键等基本操作。

遍历：可以通过键集、值集或者键值对集合来遍历Map中的元素。

#### ?️HashTable源码解析 ####

`线程安全`：Hashtable 是同步的，可以在多线程环境中安全地使用。这意味着多个线程可以同时读写 Hashtable 而不会出现并发问题。

`不允许 null 键或值`：Hashtable 不允许键或值为 null，如果尝试插入 null 键或值，会抛出 NullPointerException 异常。

初始容量和加载因子：Hashtable 有一个初始容量和加载因子，`当哈希表中的元素数量超过加载因子乘以容量时，哈希表会自动扩容。`

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

![在这里插入图片描述][1411aa3db7f144fd881ac3be6f58dc37.png]  
默认容量是11，加载因子是0.75  
![在这里插入图片描述][70a7c5cd2044494e8e977e2f7f607e7a.png]  
指定装载容量，加载因子是0.75  
![在这里插入图片描述][77dc26e996f6456681dd3d85532a1ec5.png]  
如果用户传入的initialCapacity为0，将初始容量设为1，确保哈希表至少有一个桶用于存储元素。  
计算哈希表的扩容阈值，其值为initialCapacity乘以loadFactor的结果与MAX\_ARRAY\_SIZE + 1之间的较小值。当哈希表中的元素数量超过这个阈值时，会触发扩容操作以保证哈希表的性能。  
![在这里插入图片描述][e7636a87050d491995370d2b802937d8.png]

在函数内部，首先根据传入的map的大小计算出一个初始容量，并将其和11中的较大值作为Hashtable的容量，并设置加载因子为0.75。然后调用putAll方法将传入的map中的所有键值对复制到新创建的Hashtable中。

##### put方法 #####

![在这里插入图片描述][202131103fe24ae98fad848af81b0b10.png]

将指定的键（key）映射到指定的值（value），并将其添加到哈希表中。`如果该键已经存在于哈希表中，则用新值替换旧值，并返回旧值。如果该键不存在，则将新键值对添加到哈希表中`。该方法是同步的，可以避免多线程环境下的并发问题。需要注意的是，键和值都不能为null。  
![在这里插入图片描述][a4344e9d5ef74912b231bd73804f352f.png]

hash 是传入键对象（Key）的hashCode值。  
0x7FFFFFFF 是一个32位的整数，其二进制表示为一串1，与操作符 “&” 用来获取 hash 的正向32位整数值，确保结果非负。  
% tab.length 是对得到的无符号32位整数取模运算，目的是`将哈希码映射到哈希表的实际索引位置上，这样即使哈希表大小不同也能保证键均匀分布。`  
整体来说，这段代码的作用是根据给定的键对象的hashCode值确定其在哈希表数组中的索引位置。

##### remove方法 #####

![在这里插入图片描述][79db00683a60481fad129303ab5eddf0.png]

##### rehash扩容 #####

![在这里插入图片描述][d1a5920c55fa4f3d93a9f33016e0fc0d.png]  
获取旧哈希表的容量和映射数组。  
计算新哈希表的容量，当新容量超过最大数组大小时，将其设置为最大数组大小。  
创建新哈希表映射数组。  
更新哈希表的修改次数和阈值。  
将旧哈希表中的每个键值对重新哈希到新哈希表中。

#### ?️HashMap源码解析 ####

`非线程安全`：HashMap 不是同步的，因此不适合在多线程环境中直接使用。如果需要在多线程环境中使用，可以通过 Collections.synchronizedMap 方法来创建一个线程安全的 Map。

`允许 null 键和值`：在 Java 8 之后，HashMap 允许 null 作为键和值。

初始容量和负载因子：HashMap 有一个初始容量和负载因子。当哈希表中的元素数量超过负载因子乘以容量时，哈希表会自动扩容。

##### 构造函数 #####

![在这里插入图片描述][c52890a456ec4bc58401b354bd5d78c6.png]  
这一段代码和上面HashTable的构造函数很像

##### get方法 #####

![在这里插入图片描述][ac3fc9d1e7c7424c82187319862e017b.png]  
首先根据哈希值和表的长度计算出节点在表中的索引位置，然后获取该位置上的节点。如果该节点存在并且与 给定的键 相等，则返回该节点。如果该节点存在但是是一个TreeNode（红黑树节点），则将获取节点的操作委托给TreeNode的getTreeNode方法。如果该节点存在但是下一个节点不为空，则遍历下一个节点，重复上述判断操作，直到找到相等的节点或者遍历结束。如果在整个表中找不到相等的节点，则返回null。

##### put方法 #####

![在这里插入图片描述][610367d15d7246b1930d12a989c10dbc.png]  
![在这里插入图片描述][edb4cdfd57294126a856fa6a8aef2c89.png]

###### 详解 ######

![在这里插入图片描述][7e2d9c4d96ff41be9e4d6a004fdbc39d.png]  
Node<K,V>\[\] tab中tab表示的就是数组。Node<K,V> p中p表示的就是当前插入的节点  
![在这里插入图片描述][ec0f704be38240b0aefd969e29f82aab.png]  
如果数组是空的，那么就通过resize方法来创建一个新的数组  
![在这里插入图片描述][9f01a8e64aa447ec83b49671297484cb.png]  
i表示在数组中插入的位置，计算的方式为(n - 1) & hash。在这里需要判断插入的位置是否是冲突的，如果不冲突就直接newNode，插入到数组中即可

如果冲突了，进入下面的分析

![在这里插入图片描述][921bf15ff7de496b91ba184851c71f19.png]

判断table\[i\]中的元素是否与插入的key一样，若相同那就直接使用插入的值p替换掉旧的值e。  
![在这里插入图片描述][2414fe7a265248c5903146fb5ab35dd7.png]  
判断插入的数据结构是红黑树还是链表，在这里表示如果是红黑树，那就直接putTreeVal到红黑树中

如果是链表，就进入下面的分析  
![在这里插入图片描述][6a0d8a73c75e4116911205bd54822b34.png]

如果数据结构是链表，首先要遍历table数组是否存在，如果不存在直接newNode(hash, key, value, null)。如果存在了直接使用新的value替换掉旧的。

注意一点：不存在并且在链表末尾插入元素的时候，会判断binCount >= TREEIFY\_THRESHOLD - 1。也就是判断当前链表的长度是否大于阈值8，如果大于那就会把当前链表转变成红黑树，方法是treeifyBin  
![在这里插入图片描述][968e3c13cc1f480381293e6f845325ac.png]  
插入成功之后，还要判断一下实际存在的键值对数量size是否大于阈值threshold。如果大于那就开始扩容了。

##### 扩容方法 #####

![在这里插入图片描述][22ccdd5f66ca45d0835cf59980247111.png]

###### 详解 ######

![在这里插入图片描述][bf9d8eeae7ce4c35a4c7086b5c406ec8.png]  
首先如果超过了数组的最大容量，那么就直接将阈值设置为整数最大值，然后如果没有超过，那就扩容为原来的2倍，这里要注意是oldThr << 1，移位操作来实现的。  
![在这里插入图片描述][77f01631ec844a288028b05b9ad8658f.png]

第一个else if表示如果阈值已经初始化过了，那就直接使用旧的阈值。然后第二个else表示如果没有初始化，那就初始化一个新的数组容量和新的阈值。

##### ?️TreeMap源码解析 #####

有序性：TreeMap中的键值对根据键的自然顺序或自定义排序规则进行排序，因此可以按照键的顺序进行遍历。

红黑树：TreeMap内部使用红黑树作为数据结构，这种自平衡二叉搜索树能够保持键值对的有序性，并且提供了较快的插入、删除和查找操作。

键的唯一性：TreeMap中的键是唯一的，如果尝试插入一个已存在的键，则会覆盖原有的值。

性能：TreeMap提供了对数时间复杂度的插入、删除和查找操作，适合于需要有序存储和查找的场景。

导航方法：TreeMap提供了许多导航方法，如firstKey()、lastKey()、lowerKey(K key)、higherKey(K key)等，可以方便地进行范围查找和导航操作。

[b49da993dba6490997d7f6f23a039ca6.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/de2bd9457bcc408baacd82f0cdc79524.png
[0b9b3ff8e7d440539a6ef83315bb5ebd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/d7e203ed7f124dffa11c65173fe0c880.png
[1411aa3db7f144fd881ac3be6f58dc37.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/efe9d9a8ecc24952af8d1a24dabddade.png
[70a7c5cd2044494e8e977e2f7f607e7a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/33e0e64be94149dfab784053899b8e00.png
[77dc26e996f6456681dd3d85532a1ec5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/4c24bfdb14474bca99e5185bb3f72664.png
[e7636a87050d491995370d2b802937d8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/8a56b0a075d9424ca6993ea58a20b453.png
[202131103fe24ae98fad848af81b0b10.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/3b79e37823774087a495859bb1e0d00e.png
[a4344e9d5ef74912b231bd73804f352f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/0cb07bc3a0f54b1d98b8330109d84c78.png
[79db00683a60481fad129303ab5eddf0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/c33d83ba26cf4b84970fc21118eea56b.png
[d1a5920c55fa4f3d93a9f33016e0fc0d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/717826cf04c649c582a7faadb427204f.png
[c52890a456ec4bc58401b354bd5d78c6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/79180f7586cd41b8aa1005536f3d5fe6.png
[ac3fc9d1e7c7424c82187319862e017b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/6873710cffa24d268c51db985b0e0feb.png
[610367d15d7246b1930d12a989c10dbc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/afcfcaaa7732495ba426793403a7a49f.png
[edb4cdfd57294126a856fa6a8aef2c89.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/57231b70645d4ca48ba4e4f66f953750.png
[7e2d9c4d96ff41be9e4d6a004fdbc39d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/cf97ee03dd0d4b64b0d68a05ca425519.png
[ec0f704be38240b0aefd969e29f82aab.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/b636c87ad5c145edbd567d99e9de223a.png
[9f01a8e64aa447ec83b49671297484cb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/42920b6ed1e640f4acba1bb2e7dccc10.png
[921bf15ff7de496b91ba184851c71f19.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/0dcf0f22a3434f659246b9cd5d51928f.png
[2414fe7a265248c5903146fb5ab35dd7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/0b16b740c1f74be1aa09a6ebeb5cfbea.png
[6a0d8a73c75e4116911205bd54822b34.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/8fd740de795547388c05970da200e044.png
[968e3c13cc1f480381293e6f845325ac.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/ac8a707fa40b42c6bfe926e8b2cf8ea5.png
[22ccdd5f66ca45d0835cf59980247111.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/c8db98ab15b542d899b117df311ecc50.png
[bf9d8eeae7ce4c35a4c7086b5c406ec8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/2856eb94bbb04cbca8af32fe4066b3f8.png
[77f01631ec844a288028b05b9ad8658f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/833b3089c92449c7aecd473514cfdb6c.png