hashmap1.8源码,hashmap菜鸟教程
Yyds干货库存
深度解析HashMap源代码* HashMap底层数据结构(为什么要引入红黑树，存储数据的过程，哈希碰撞相关问题)
* HashMap成员变量(什么是初始化容量，加载因子，为什么数组长度是2的n次方)
* HashMap扩展机制(什么时候需要扩展？怎么拓展？)
*与Jdk8相比，JDK7进行了优化？1定义基于哈希表的HashMap接口的实现，哈希表是以键值存储的形式存在的，即主要用来存储键值对。HashMap的实现不是同步的，这意味着它不是线程安全的。它的键和值可以为空。此外，HashMap中的映射是无序的。
JDK1.7 HashMap数据结构：数组链表JDK1.8 HashMap数据结构：数组链表/红黑树思考：为什么1.8以后的HashMap数据结构要加入红黑树？
2哈希表哈希表也叫哈希表，也直接翻译成哈希表。哈希表是一种可以根据键值直接访问的数据结构。也就是说，它通过将键值映射到表中的某个位置来访问记录，从而加快搜索速度。在链表、数组等数据结构中，通常需要遍历整个数据结构，也就是O(N)的时间级，但对于哈希表，只是O(1)的时间级。
哈希表，通过将键值映射到表中的某个位置来访问记录，以加快搜索速度。这个映射函数叫做hash函数，存储记录的数组叫做* *哈希表，只需要O(1)**的时间级
思考：多个键通过hash函数会得到相同的值。这时候我该怎么办？
解决：
(1)开放地址法
(2)链地址法
对于开放地址方法，可能会有两个冲突和三个冲突，所以需要一个好的哈希函数。分布越均匀越好。对于链地址法，虽然不会造成二次冲突，但是如果一次冲突很多，就会导致子数组或者子链表很长，我们搜索需要的遍历时间会很长。
3哈希表在JDK1.8之前的数据结构在JDK8之前，哈希表在JDK 8之前的实现是数组链表。即使哈希函数实现的很好，也很难做到元素100%均匀分布。当HashMap中的大量元素存储在同一个桶中时，这个桶下就有一个很长的链表。在极端情况下，HashMap相当于单个链表。如果单个链表中有n个元素，遍历时间复杂度为O(n)，完全失去优势。
JDK1.8之后HashMap的数据结构JDK 8之后HashMap的实现是数组链表。红黑树桶中的结构可以是链表或红黑树。当链表的长度大于阈值(或红黑树的边界值，默认值为8)且当前数组的长度大于64时，该索引位置的所有数据将改为存储在红黑树中。
5\.类构造函数公共类hashmap k，v扩展抽象映射k，v
实现映射K，V，可克隆，可序列化{
JDK为我们提供了一个抽象类AbstractMap，它继承了Map接口，所以如果我们不想实现所有的Map接口方法，可以选择继承抽象类AbstractMap。
HashMap set实现了Cloneable接口和Serializable接口，分别用来克隆和序列化对象。
注意：HashMap类继承了AbstractMap接口并实现了Map接口。这样做不是没有必要吗？
根据java Collection Framework创始人Josh Bloch的说法，这种写法是一个错误。在java集合框架中，有很多方法可以这样写。在开始写java集合框架的时候，他认为有些地方可能是有价值的，直到他意识到自己的错误。显然，JDK的维护者认为这个小错误不值得修改，所以它存在了。6字段属性//序列化和反序列化时，通过该字段验证版本一致性。
private static final long serialVersionUID=362498820763181265 l；
//默认HashMap集初始容量是16(必须是2的倍数)
static final int DEFAULT _ INITIAL _ CAPACITY=1 4；//又名16
//集合的最大容量。如果参数construction指定的最大容量超过了这个数字，默认情况下仍将使用这个数字。
静态最终int MAXIMUM _ CAPACITY=1 30
//默认填充因子
静态最终浮动DEFAULT _ LOAD _ FACTOR=0.75f
//当桶上的节点数大于该值时，会变成红黑树(JDK1.8新增)
静态最终int tree ify _ THRESHOLD=8；
//当桶上的节点数小于该值时，会转换为链表(JDK1.8新增)
静态最终int un treify _ THRESHOLD=6；
/* *(JDK 1.8中的新功能)
*当集合中的容量大于该值时，可以对表中的桶进行树化，否则桶中的元素过多会展开，
*而不是爬树。为了避免容量扩展和树化之间的冲突，该值不能小于4 * TREEIFY_THRESHOLD。
*/
静态最终int MIN _ TREEIFY _ CAPACITY=64
/**
*初始化时，长度总是2的幂。
*/
暂态节点K，V []表；
/**
*保存缓存的entrySet()
*/
瞬态集图。条目K，V entrySet
/**
*此映射中包含的键值映射的数量。(集合存储键值对的数量)
*/
瞬态int大小；
/**
*与ArrayList和LinkedList集合中的字段modCount一样，记录集合被修改的次数。
*主要用于迭代器中的快速失败。
*/
瞬态int modCount
/**
resize的下一个大小值(容量*装载因子)。容量*负载系数
*/
int阈值；
/**
*哈希表的加载因子。
*/
最终浮动负载系数；让我们关注以上领域：
、节点K，V []表
我们说HashMap是由数组链表中的红黑树组成的，这里的数组就是表字段。最近一次初始化长度是DEFAULT_INITIAL_CAPACITY=16。此外，JDK指出，数组的长度总是2的n次方(它必须是一个合数)。为什么这里要求是合数？一般我们知道哈希算法为了避免冲突，要求长度是质数，这里要求是合数。这里先介绍一下HashMap的hashCode()方法(hash函数)，然后再解释。
**、尺寸**
存储在集合中的键值的实时对数。
、负载系数
加载因子用于衡量哈希表的充满程度。HashMap的实时加载因子是用size/capacity的方法计算的，而不是用被占用的桶数除以容量。容量是桶的数量，也就是表的长度。
默认的加载因子0.75是空间和时间效率的平衡选择。建议大家不要修改，除非有特殊的时空。如果内存空间很大，时间效率很高，可以降低load factor的值。相反，如果内存空间紧张，时间效率不高，可以增加loadFactor的值，可以大于1。
、阈值
计算公式：容量*负载系数。该值是当前占用数组的最大长度。在这个数字之后，再次resize (expand)，扩展后的HashMap容量是之前容量的两倍。
7构造函数，默认无参数构造函数
/**
*默认构造函数，初始化加载因子loadFactor=0.75
*/
public HashMap() {
this . LOAD FACTOR=DEFAULT _ LOAD _ FACTOR；
} 、指定初始容量的建造师。
/**
*
* @param initialCapacity指定初始容量。
* @param loadFactor负载系数为0.75
*/
public HashMap(int initial capacity，float loadFactor) {
//初始化容量不能小于0，否则会抛出异常。
if (initialCapacity 0)
抛出新的IllegalArgumentException(非法初始容量：
初始容量)；
//如果初始化容量大于2的30次方，则初始化容量为2的30次方。
if(初始容量最大容量)
initial CAPACITY=max _ CAPACITY；
//如果加载因子小于0，或者加载因子是非数值，则引发异常
if(load factor=0 float . isnan(load factor))
抛出新的IllegalArgumentException(非法加载因子：
负载系数)；
this.loadFactor=负载系数；
this . threshold=tablesize for(initial capacity)；
}
//返回大于或等于initialCapacity的最小功率值。
//运算符表示无符号右移，高位取0。
//按位或运算
静态最终int tableSizeFor(int cap) {
int n=cap-1；
n =n
n =n
n =n
n =n
n =n
返回(n 0)？1 : (n=MAXIMUM_CAPACITY)？MAXIMUM _ CAPACITY:n1；
}8确定哈希桶数组的索引位置。当我们在前面解释哈希表时，我们知道哈希函数用于确定索引位置。散列函数设计得越好，元素分布得越均匀。HashMap是数组链表中红黑树的组合。我们希望当数组位置有限时，每个位置尽可能只有一个元素。那么当我们使用hash函数获取索引位置时，就可以立刻知道对应位置的元素是否是我们想要的，而不用遍历链表或者红黑树，这样会大大优化我们的查询效率。让我们看看HashMap中的哈希算法：
静态最终int哈希(对象键){
int h；
return (key==null)？0:(h=key . hashcode())^(h 16)；
}
i=(table.length - 1)哈希；//这一步是确定后面添加元素putVal()的方法中的位置。有三个步骤：
取hashCode: key.hashCode()的值
高位参与运算：h 16
模运算：(n-1)哈希
在这里，获取hashCode()方法的值是一个变量，但是我们知道，对于任何给定的对象，只要它的hashCode()返回值相同，那么通过调用hash(Object key)计算出来的hash代码值总是相同的。
为了让数组元素均匀分布，我们首先想到的是用得到的哈希码(hash%length)对数组的长度取模。但是计算机都是二进制运算，模运算的相对成本还是很高的，那么如何优化呢？
HashMap使用的方法很巧妙。它通过hash (table.length -1)获取对象的保存位。如前所述，HashMap底部数组的长度始终是2的n次方，这是对HashMap速度的优化。当length总是2的n次方时，hash (length-1)运算相当于模长度，即hash%length，但比%更高效。例如，n% 32=n (32 -1)
这也解释了为什么数组的长度应该总是2的n次方。
在JDK1.8中，有一个高位参与运算。hashCode()得到一个32位的int值，通过hashCode()的高16位或低16位的异或来实现：(h=k. Hashcode ()) (h 16)，主要考虑速度、功效和质量。当数组表的长度相对较小时，可以做到这一点。
例如，n是表的长度：
添加9个元素//hash(key)就是上面提到的哈希方法，处理第一步和第二步。
公共V put(K键，V值){
返回putVal(hash(key)，key，value，false，true)；
}
/**
*
* @param哈希索引位置
* @param key key
* @param value值
* @param onlyIfAbsent true表示不更改现有值。
* @param evict false表示该表处于创建模式。
* @返回
*/
final V putVal(int hash，K key，V value，boolean onlyIfAbsent，
布尔逐出){
节点K，V[]tab；节点K，V int n，I；
//如果表为空或长度为0，则初始化它
////resize()方法最初用于容量扩展。由于初始化时没有实际的空间分配，所以这里使用这个方法进行空间分配，后面会详细解释。
if((tab=table)==null (n=tab . length)==0)
n=(tab=resize())。长度；
//注意：这里用的是前面解释的获取key哈希码的第三步，模运算。下面的if-else是tab[i]分别为null和not null。
if ((p=tab[i=(n - 1) hash])==null)
tab[i]=newNode(hash，key，value，null)；//tab[i]为空，所以新键值直接插入到计算出的索引I位置。
Else {//tab[i]不为null，表示该位置已经有值。
节点K，V K k
if (p.hash==hash
((k=p.key)==key (key！=null key.equals(k))))
e=p；//节点键已经有值，直接用新值覆盖。
//链条是一棵红黑树
else if(p TreeNode的实例)
e=((TreeNode K，V )p)。putTreeVal(this，tab，hash，key，value)；
//这个链是一个链表
否则{
for(int bin count=0；binCount) {
if ((e=p.next)==null) {
p.next=newNode(hash，key，value，null)；
//如果链表长度大于8，就转换成红黑树。
第一个if(bin count=tree ify _ THRESHOLD-1)//-1
treeifyBin(tab，hash)；
打破；
}
//键已经有直接重写值。
如果(例如，哈希==哈希
((k=e.key)==key (key！=null key.equals(k))))
打破；
p=e；
}
}
如果(e！=null) { //键的现有映射
V oldValue=e.value
如果(！onlyIfAbsent oldValue==null)
e.value=值；
afterNodeAccess(e)；
返回旧值；
}
}
modCount//用作快速失败修改添加。
If(大小阈值)//如果超过最大容量，请扩展容量。
resize()；
afterNodeInsertion(驱逐)；
返回null
} 、判断键值对数组表是否为空或null，否则执行resize()进行扩展；
根据键值key计算哈希值得到插入的数组索引I，如果table[i]==null，直接新建一个节点添加，转，如果table[i]不为空，转；
判断表[i]的第一个元素是否与key相同，如果相同，则直接覆盖value，否则转到，这里相同指hashCode和equals；
判断table[i]是否为treeNode，即table[i]是否为红黑树，如果是，直接将键值对插入树中，否则转；
遍历表[i]，判断链表长度是否大于8。如果大于8，则将链表转换为红黑树，插入红黑树，否则插入链表；在遍历过程中，如果发现键已经存在，可以直接覆盖值；
插入成功后，判断键-值对的实际数量大小是否超过最大容量阈值，如果是，则扩展容量。
如果新插入的键不存在，则返回null如果新插入的键确实存在，它将返回对应于原始键的值(注意，新插入的值将覆盖原始值)
1:其中代码：
If(大小阈值)//如果超过最大容量，请扩展容量。
resize()；这里是一个测试点。我们知道HashMap是由红黑树(JDK1.8)，一个数组链表组成的。如果添加元素时有冲突，冲突的数量将放在链表中。当链表长度超过8时，会自动转换为红黑树。
然后有以下问题：数组上有5个元素，链表上有3个元素。这个散列表的大小是多少？
我们分析代码的时候很容易知道，只要调用put()方法添加一个元素，那么就会调用size(这里有一个例外，就是插入一个有重复key的键值对，但是重复的key元素不会影响大小)。所以，上面的答案是7。
10容量扩展机制(resize)，我们知道集合是由数组链表中的红黑树组成的。在HashMap中插入元素时，如果HashMap集合的元素已经大于最大承载能力阈值(capacity * loadFactor)，这里的阈值不是数组的最大长度。那么必须扩展数组的长度。在Java中，数组不能自动扩展。我们采用的方法是把这个小数组换成一个更大的，就像以前用小水桶盛水，现在小水桶装不下了。我们用一个更大的桶。
JDK1.8融入了红黑树的机制，比较复杂。这里先介绍JDK1.7的扩展源代码，便于理解，再介绍JDK1.8的源代码。
//参数newCapacity是新数组的大小。
void resize(int newCapacity) {
Entry[] oldTable=表；//在展开之前引用条目数组
int old capacity=old table . length；
If(old capacity==maximum _ capacity){//如果扩展前的数组大小已达到最大值(2 ^ 30)
阈值=整数。MAX _ VALUE///修改int(2 ^ 31-1)的最大阈值，这样以后就不会扩大了。
返回；
}
Entry[] newTable=新条目[new capacity]；//初始化新的条目数组
transfer(newTable，inithashseedasneed(new capacity))；//将数组元素转移到新数组中
table=newTable
threshold=(int)math . min(new CAPACITY * load factor，MAXIMUM _ CAPACITY 1)；//修改阈值
}
void transfer(Entry[] newTable，boolean rehash) {
int new capacity=new table . length；
For (Entry K，V e: table) {//遍历数组
while(null！=e) {
条目K，V next=e.next
如果(再散列){
e.hash=null==e.key？0:哈希(e . key)；
}
int i=indexFor(e.hash，new capacity)；//重新计算数组中每个元素的索引位置
e . next=new table[I]；//标记下一个元素，加法就是链表头的加法。
new table[I]=e；//将元素放在链上
e=下一个；//访问下一个条目链上的元素
}
}
}通过方法我们可以看到，在JDK1.7中，首先创建一个新的大容量数组，然后依次重新计算原集合所有元素的索引，再重新赋值。如果数组中某个位置存在哈希冲突，则使用插入单个链表头的方法，相同位置的新元素总是放在链表头，这样与原来设置的链表相比，扩展后的链表可能是倒排链表。
我们来看看JDK1.8。
最终节点K，V [] resize() {
节点K，V[]old tab=table；
int oldCap=(oldTab==null)？0:old tab . length；//如果原数组为空，则长度赋为0。
int oldThr=threshold
int newCap，new thr=0；
If (oldCap 0) {//如果原始数组长度大于0
If (oldCap=MAXIMUM_CAPACITY) {//如果数组大小大于或等于最大值(2 ^ 30)
阈值=整数。MAX _ VALUE//用int(2 ^ 31-1)的阈值修改最大值，这样以后就不会扩大了。
返回oldTab
}
//原数组长度大于等于初始化长度16，如果原数组长度翻倍，也小于2的30次方。
else if((new cap=old cap 1)MAXIMUM _ CAPACITY
oldCap=DEFAULT _ INITIAL _ CAPACITY)
new thr=old thr 1；//门槛翻倍。
}
Else if (oldThr 0) //如果旧阈值大于0，则新容量将直接等于旧阈值。
newCap=oldThr
Else {//阈值等于0，oldCap也等于0(集合未初始化)
new cap=DEFAULT _ INITIAL _ CAPACITY；//数组长度初始化为16
new thr=(int)(DEFAULT _ LOAD _ FACTOR * DEFAULT _ INITIAL _ CAPACITY)；//阈值等于16*0.75=12
}
//计算新的上限阈值
if (newThr==0) {
float ft=(float)newCap * load factor；
new thr=(newCap MAXIMUM _ CAPACITY ft(float)MAXIMUM _ CAPACITY？
(int)ft:整数。MAX _ VALUE)；
}
threshold=newThr
@SuppressWarnings({rawtypes ， unchecked})
Node K，V [] newTab=(Node K，V[])new Node[newCap]；
table=newTab
if (oldTab！=null) {
//将每个存储桶移动到新的存储桶
for(int j=0；j oldCapj) {
节点K，V
if ((e=oldTab[j])！=null) {
old tab[j]=null；//元数据j位置设置为空，用于垃圾回收。
If (e.next==null)//数组没有下一个引用(不是链表)
new tab[e . hash(newCap-1)]=e；
Else if (e instanceof TreeNode)//红黑树
((TreeNode K，V )e)。split(this，newTab，j，old cap)；
else { //保持顺序
节点K，V loHead=null，loTail=null
节点K，V hiHead=null，hiTail=null
节点K，V接下来；
做{
next=e.next
//原始索引
if ((e.hash oldCap)==0) {
if (loTail==null)
loHead=e；
其他
lotail . next=e；
loTail=e；
}
//原始索引oldCap
否则{
if (hiTail==null)
hiHead=e；
其他
hitail . next=e；
hiTail=e；
}
} while ((e=next)！=null)；
//将原始索引放入桶中
如果(loTail！=null) {
loTail.next=null
new tab[j]=loHead；
}
//将原始索引oldCap放入bucket。
如果(hiTail！=null) {
hiTail.next=null
new tab[j old cap]=hiHead；
}
}
}
}
}
返回newTab
}这个方法分为两部分。首先计算新桶数组的容量newCap和新阈值newThr，然后将原集合的元素重新映射到新集合。
与JDK1.7相比，1.8采用2次方扩展(即长度增加一倍)。因此，元素的位置要么在原始位置，要么从原始位置移动2次幂。我们在扩展HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，我们只需要看看原来hash值新增加的位是1还是0就可以了。如果为0，则索引保持不变，如果为1，则索引变为“原始索引oldCap”。
1删除元素HashMap删除元素先找到桶的位置，然后如果是链表，遍历链表，找到要删除的元素后删除；如果是红黑树，也是树遍历。找到元素并删除后，进行平衡调整。注意，当红黑树的节点数小于6时，会转换成链表。
public V get(对象键){
节点K，V
return (e=getNode(hash(key)，key))==null？null:e . value；
}
最终节点K，V getNode(int hash，Object key) {
节点K，V[]tab；节点K，V优先，e；int n；K k
if ((tab=table)！=null (n=tab.length) 0
(first=tab[(n - 1) hash])！=null) {
//根据key计算的索引检查第一个索引
if (first.hash==hash //始终检查第一个节点
((k=first.key)==key (key！=null key.equals(k))))
先退；
//不是第一个节点
if ((e=first.next)！=null) {
If(树的第一个实例)//遍历树以查找元素
先返回((TreeNode K，V))。getTreeNode(hash，key)；
做{
//遍历链表以查找元素
如果(例如，哈希==哈希
((k=e.key)==key (key！=null key.equals(k))))
返回e；
} while ((e=e.next)！=null)；
}
}
返回null
}12求元素。通过键查找值。
首先，通过键找到计算索引和桶位置。首先，检查第一个节点。如果是，它将返回。如果没有，就遍历后面的链表或者红黑树。所有其他情况返回null。
public V get(对象键){
节点K，V
return (e=getNode(hash(key)，key))==null？null:e . value；
}
最终节点K，V getNode(int hash，Object key) {
节点K，V[]tab；节点K，V优先，e；int n；K k
if ((tab=table)！=null (n=tab.length) 0
(first=tab[(n - 1) hash])！=null) {
//根据key计算的索引检查第一个索引
if (first.hash==hash //始终检查第一个节点
((k=first.key)==key (key！=null key.equals(k))))
先退；
//不是第一个节点
if ((e=first.next)！=null) {
If(树的第一个实例)//遍历树以查找元素
先返回((TreeNode K，V))。getTreeNode(hash，key)；
做{
//遍历链表以查找元素
如果(例如，哈希==哈希
((k=e.key)==key (key！=null key.equals(k))))
返回e；
} while ((e=e.next)！=null)；
}
}
返回null
}摘要
基于JDK1.8的HashMap由数组链表红黑树组成。当链表长度超过8时，会自动转换为红黑树，当红黑树的节点数小于6时，会再次转换为链表。与早期版本的JDK HashMap相比，增加了新的红黑树作为底层数据结构，在数据量大、哈希碰撞多的情况下，可以大大增加检索效率。
允许键和值都为空。重复的关键字将被覆盖，并且允许重复的值。
非线程安全
无序(遍历HashMap得到的元素顺序不是插入顺序)
版权归作者所有：原创作品来自博主小二上九8，转载请联系作者取得转载授权，否则将追究法律责任。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。