大工篇|Java集合——HashMap源码 java|红黑树|Java集合|HashMap源码

Java集合知识图谱：
https://www.processon.com/view/link/61bf27a17d9c087834f1d352

问题：

链表中的key放的到底是什么，Hash值吗，hash会有冲突吗，hash生成的原理是什么
map中的阈值是如何确定下来的，意义是什么

一、二三树 2-3树是一种绝对平衡多叉树，在这棵树中他的任意一个节点的左右节点高度是相同的。2-节点表示节点中保存一个元素，3-节点则表示节点中保存两个元素。

文章图片

二、红黑树 1、红黑树的五大概念

每个节点要么是红色要么是黑色
根节点一定是黑色
每个叶子节点一定是黑色（这里面说的叶子节点是指空的叶子节点）
如果一个节点是红色那么他的左右节点一定都是黑色
从任意一个节点到叶子节点所经过的黑色节点数量一样多

三、基础知识简介 List 的具体实现包括 ArrayList 和 Vector，它们是可变大小的列表，比较适合构建、存储和操作任何类型对象元素列表。List 适用于按数值索引访问元素的情形。
从概念上而言，您可以将 List 看作是具有数值键的 Map。而实际上，除了 List 和 Map 都在定义 java.util 中外，两者并没有直接的联系。本文将着重介绍核心 Java 发行套件中附带的 Map，同时还将介绍如何采用或实现更适用于您应用程序特定数据的专用 Map。

list的实现方式中一个是数组一个是链表，如果要是通过数组形式实现的还可以理解索引就是key但是如果是通过链表实现的，那么键值对的实现就只能说是一种你看到的，他实际上是没有索引的只不过是能够通过一定的算法找到固定位置上的相应元素，这里面采用的是优化过后的二分查找算法。

1、Map中相关的方法

被覆盖的方法

方法	备注
equals(Object o)	比较指定对象与此 Map 的等价性
hashCode()	返回此 Map 的哈希码

可以更改Map的方法

方法	备注
clear()	从 Map 中删除所有映射
remove(Object key)	从 Map 中删除键和关联的值
put(Object key, Object value)	将指定值与指定键相关联
putAll(Map t)	将指定 Map 中的所有映射复制到此 map

纵然假设忽略构建一个需要传递给 putAll() 的 Map 的开销，使用 putAll() 通常也并不比使用大量的 put() 调用更有效率，但 putAll() 的存在一点也不稀奇。这是因为，putAll() 除了迭代 put() 所执行的将每个键值对添加到 Map 的算法以外，还需要迭代所传递的 Map 的元素。但应注意，putAll() 在添加所有元素之前可以正确调整 Map 的大小，因此如果您未亲自调整 Map 的大小（我们将对此进行简单介绍），则 putAll() 可能比预期的更有效。

查看Map

如果需要迭代Map中的元素则需要获取到Map中对应的视图，其中有三种可能的视图可以供我们使用，之所以是视图是因为他们并不是Map的完整副本：

所有键值对 — 参见 entrySet()

所有键 — 参见 keySet()

有值 — 参见 values()

【大工篇|Java集合——HashMap源码】前两个视图返回的是Set对象，第三个返回的是Collection,如果需要进行迭代还需要获得他们的迭代器：

Iterator keyValuePairs = aMap.entrySet().iterator(); Iterator keys = aMap.keySet().iterator(); Iterator values = aMap.values().iterator();

遍历Map的几种方式

一种是借助于迭代器来进行访问的，这时候每当一个next应该就会在视图中移除一个元素，也就是说一个视图是能用来被遍历一次，第二次还是使用这个视图（iterator）的话是不行的。鉴于这个原理我们可以使用hasNext（）、以及固定的个数来进行迭代，从而保证不为零

@Test public void test01(){ //map创建过程中两种性能的比较 HashMap hashMap = new HashMap<>(); hashMap.put("a1","b1"); hashMap.put("a2","b2"); hashMap.put("a3","b3"); hashMap.put("a4","b4"); //这几通过迭代器的方式进行访问 System.out.println("~~~Iterator类型访问~~~"); Iterator iterator = hashMap.entrySet().iterator(); int mapSize = hashMap.size(); for (int i=0; i entry:hashMap.entrySet()){ System.out.println("Key: "+entry.getKey()+"Value: "+entry.getValue()); } hashMap.values().forEach(item->{ System.out.println(item); }); System.out.println("~~~Array类型的访问~~~"); Object[] array = hashMap.entrySet().toArray(); for (int i = 0; i < array.length; i++) { Map.Entry entry = (Map.Entry) array[i]; System.out.println("Key: "+entry.getKey()+"Value: "+entry.getValue()); } }

Map的访问与测试

get(Object key)	返回与指定键关联的值
containsKey(Object key)	如果 Map 包含指定键的映射，则返回 true
containsValue(Object value)	如果此 Map 将一个或多个键映射到指定值，则返回 true
isEmpty()	如果 Map 不包含键-值映射，则返回 true
size()	返回 Map 中的键-值映射的数目

对使用 containsKey() 和 containsValue() 遍历 HashMap 中所有元素所需时间的测试表明，containsValue() 所需的时间要长很多。实际上要长几个数量级！因此，如果 containsValue() 是应用程序中的性能问题，它将很快显现出来，并可以通过监测您的应用程序轻松地将其识别。这种情况下，我相信您能够想出一个有效的替换方法来实现 containsValue() 提供的等效功能。但如果想不出办法，则一个可行的解决方案是再创建一个 Map，并将第一个 Map 的所有值作为键。这样，第一个 Map 上的 containsValue() 将成为第二个 Map 上更有效的 containsKey()。
2、核心Map

通用 Map，用于在应用程序中管理映射，通常在 java.util 程序包中实现
- HashMap
- Hashtable
- Properties
- LinkedHashMap
- IdentityHashMap
- TreeMap
- WeakHashMap
- ConcurrentHashMap
专用 Map，您通常不必亲自创建此类 Map，而是通过某些其他类对其进行访问
- java.util.jar.Attributes
- javax.print.attribute.standard.PrinterStateReasons
- java.security.Provider
- java.awt.RenderingHints
- javax.swing.UIDefaults
一个用于帮助实现您自己的 Map 类的抽象类
- AbstractMap

3、内部哈希：哈希映射技术
哈希映射结构由一个存储元素的内部数组组成。由于内部采用数组存储，因此必然存在一个用于确定任意键访问数组的索引机制。

int hashvalue = https://www.it610.com/article/Maths.abs(key.hashCode()) % table.length; int hashvalue = (key.hashCode() & 0x7FFFFFFF) % table.length;

put() 方法还包含相应 get() 的算法，这是因为插入包括搜索映射索引处的项以查明该键是否已经存在。（即 get() 方法与 put() 方法具有相同的算法，但 get() 不包含插入和覆盖代码。）使用链接列表并不是解决冲突的唯一方法，某些哈希映射使用另一种“开放式寻址”方案
将您的所有 Map 变量声明为 Map，而不是任何具体实现，即不要声明为 HashMap 或 Hashtable，或任何其他 Map 类实现。

Map criticalMap = new HashMap(); //好 HashMap criticalMap = new HashMap(); //差

直到需要时再选择 Map 实现 — 如果随处使用“Map”声明的变量，则更改应用程序中任何特殊 Map 的 Map 实现只需要更改一行，这是一种开销很少的调整选择。
4、使用负载因子
为确定何时调整大小，而不是对每个存储桶中的链接列表的深度进行记数，基于哈希的 Map 使用一个额外参数并粗略计算存储桶的密度。Map 在调整大小之前，使用名为“负载因子”的参数指示 Map 将承担的“负载”量，即它的负载程度。负载因子、项数（Map 大小）与容量之间的关系简单明了：

如果（负载因子）x（容量）>（Map 大小），则调整 Map 大小

例如，如果默认负载因子为 0.75，默认容量为 11，则 11 x 0.75 = 8.25，该值向下取整为 8 个元素。因此，如果将第 8 个项添加到此 Map，则该 Map 将自身的大小调整为一个更大的值。相反，要计算避免调整大小所需的初始容量，用将要添加的项数除以负载因子，并向上取整，例如，

对于负载因子为 0.75 的 100 个项，应将容量设置为 100/0.75 = 133.33，并将结果向上取整为 134（或取整为 135 以使用奇数）

奇数个存储桶使 map 能够通过减少冲突数来提高执行效率。虽然我所做的测试（关联文件中的并未表明质数可以始终获得更好的效率，但理想情形是容量取质数。1.4 版后的某些 Map（如 HashMap 和 LinkedHashMap，而非 Hashtable 或 IdentityHashMap）使用需要 2 的幂容量的哈希函数，但下一个最高 2 的幂容量由这些 Map 计算，因此您不必亲自计算。
负载因子本身是空间和时间之间的调整折衷。较小的负载因子将占用更多的空间，但将降低冲突的可能性，从而将加快访问和更新的速度。使用大于 0.75 的负载因子可能是不明智的，而使用大于 1.0 的负载因子肯定是不明知的，这是因为这必定会引发一次冲突。使用小于 0.50 的负载因子好处并不大，但只要您有效地调整 Map 的大小，应不会对小负载因子造成性能开销，而只会造成内存开销。但较小的负载因子将意味着如果您未预先调整 Map 的大小，则导致更频繁的调整大小，从而降低性能，因此在调整负载因子时一定要注意这个问题。
四、HashMap基础数据结构

HashMap中说的链表是单链表但是红黑树中也是有链表的，这个链表是双向链表。那么红黑树的数据结构是怎么构成的？以及为什么为在里面存在双向链表他存在的意义是什么？

当需要对红黑树进行遍历的时候树结构的遍历速度太慢而链表形式的就要快很多
1、HashMap的构造函数

public HashMap(int initialCapacity, float loadFactor)

如果要是参数小于0则会报IllegalArgumentException的异常，如果是过大的话则会进行一个默认值赋值。这里并没有将异常处理隐藏掉而是将异常抛出来：

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); }

public HashMap(int initialCapacity)

this的使用

public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); }

public HashMap()

对负载因子进行默认值赋值，负载因子的默认值是0.75

public HashMap(Map m)

public HashMap(Map m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }

2、创建Table数组
判定条件就是table为空或是长度为0，这里面有一个防空指针的操作是值得学习的，在有的情况下是通过&&进行连接的（逻辑与、逻辑或）

if ((tab = table) == null || (n = tab.length) == 0) { // eg1: resize返回(Node[]) new Node[16]，所以：tab=(Node[]) new Node[16]， n=16 n = (tab = resize()).length; }

进行条件判断之后开始进行resize（），在这个操作中主要分为两种场景：

原来没有数组：

有数组但是容量不够了:需要考虑进行数据重构因为hash后的位置会不同

不管是那种场景都是需要根据已有的信息通过对容量、阈值来进行重置，重置之后再进行统一的新数组创建。在对容量以及阈值进行重置的时候会进行越界相关的判断，同时也会对扩容后的安全进行一个判定：

/** 如果将老Table的长度增长2倍作为新的容量长度(newCap)，是否小于2^30(1 << 30) 并且老Table长度是否大于等于16(1 << 4) * 这一步也是确保数组扩容的安全性*/ else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) { // eg6: newCap=32, newThr=24 newThr = oldThr << 1; }

关于数值重置这一块的代码写的是很优雅的，思路变现为通过在判断体中进行赋值精简代码的结构、对数值进行确定之后再统一的使用这些数值来进行新数组的创建。

文章图片

3、插值时候的两种简单操作
如果没有发生Hash冲突我们只需要将创建的节点赋值给tab，这是属于第一种情况，如果发生了冲突但是在寻找插入位置的时候发现这个key已经存在，这时候会根据put中的参数值进行判断是否进行覆盖。同时这个覆盖也不是立即的而是确定下来之后统一进行一个插入
如果发生了Hash冲突但是查找下来却也没有已经存在的相同的Hash值这时候有会分为我们要插入的是树节点还是普通节点，这个判断判断的是tab节点：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Efx4uspI-1639917521939)(F:\typroa\aimages\image-20211208205004374.png)]
4、单向链表中插入元素
5、putTreeVal——寻址根节点