HashMap是高级java工程师必须精通的集合容器，其重要性几乎等同于Volatile在并发编程中的重要性（可见性和有序性）。本文通过图文源码的详细讲解，深入剖析了HashMap的重要核心知识，易读易学易懂。建议收藏起来，多了解总是好的，以防面试被问到。我是Mike，教授BAT一线架构技术10多年。本文重点：HashMap的数据结构，HashMap的核心成员，HashMapd的Node数组，HashMap的数据存储，HashMap的哈希函数，哈希冲突：链式哈希表，HashMap的get方法:hash函数，HashMap的put方法，为什么slot数一定要用2^n？HashMap的数据结构首先我们从数据结构的角度来看：HashMap是：数组+链表+红黑树的数据结构（JDK1.问题：*底层具体存储的是什么数据?这种存储方式有什么优点?*默认初始容量(数组默认大小):16,2的整数次幂staticfinalintDEFAULT_INITIAL_CAPACITY=1<<4;最大容量staticfinalintMAXIMUM_CAPACITY=1<<30;defaultloadfactorstaticfinalfloatDEFAULT_LOAD_FACTOR=0.75f;loadfactor用来衡量HashMap的丰满度，也就是当map集合存储的数据达到当前数组大小的75%时，需要展开链表到红黑树边界staticfinalintTREEIFY_THRESHOLD=8;红黑树移出链表边界staticfinalintUNTREEIFY_THRESHOLD=6;哈希桶数组transientNode[]table;实际存储的元素个数transientintsize;当map中的数据大于这个阈值时，会扩容intthresholdthreshold=table.length*loadFactor2.Nodearray从源码可以看出，HashMap类中有一个很重要的字段，它就是Node[]表，也就是hashbucket数组，很明显就是一个Node数组。staticclassNodeimplementsMap.Entry{finalinthash;//用来确定数字组搜索位置finalKkey;V值；Nodenext;//链表的下一个节点节点Node(inthash,Kkey,Vvalue,Nodenext){this.hash=hash;this.key=键；this.value=值；这个.下一个=下一个；}publicfinalKgetKey(){返回密钥；}publicfinalVgetValue(){返回值；}publicfinalStringtoString(){returnkey+"="+value;}publicfinalinthashCode(){returnObjects.hashCode(key)^Objects.hashCode(value);}publicfinalVsetValue(VnewValue){VoldValue=value;价值=新价值；返回旧值；}publicfinalbooleanequals(Objecto){if(o==this)returntrue;if(oinstanceofMap.Entry){Map.Entrye=(Map.Entry)o;如果(Objects.equals(key,e.getKey())&&Objects.equals(value,e.getValue()))返回真；}返回假；}}Node是HashMap的内部类，实现了Map.Entry接口。本质上是一种映射（键值对）HashMap数据存储1.哈希表存储HashMap使用哈希表来存储数据。哈希表（Hashtable，也叫哈希表）是一种根据键值（Keyvalue）直接访问的数据结构。只要要查找的值是key，就可以找到对应的值。哈希表实际上是数组的扩展，由数组演化而来。可以说没有数组就没有哈希表。2.哈希函数哈希表中的元素是由哈希函数决定的。以数据元素的关键字Key为参数，通过一定的函数关系（称为哈希函数）计算出的值就是该元素的存储地址。表示为：Addr=H(key)，如下图所示：哈希表中哈希函数的设计非常重要，这也是构建哈希表过程中的关键问题之一。3、核心问题在构建哈希表之前，主要需要解决两个问题：1）构造一个合适的哈希函数，均匀性H（key）的值均匀分布在哈希表中2）冲突处理冲突：在哈希表中，不同的键值对应同一个存储位置。4.哈希冲突：链式哈希表哈希表为了解决冲突可以使用地址法和链式地址法来解决问题。Java中的HashMap使用链地址方式。链地址法，简单来说就是数组和链表的组合，如下图所示：HashMap的哈希函数/***重新计算哈希值*/staticfinalinthash(Objectkey){诠释h;//h=key.hashCode()是第一步获取hashCode值//h^(h>>>16)是第二步高位参与运算return(key==null)?0:(h=key.hashCode())^(h>>>16);}//计算arrayslot(n-1)&hash对key进行hashCode运算得到一个32位的int值h，然后使用h异或h>>>16位。在JDK1.8的实现中，优化了高位运算的算法，通过hashCode()的低16位的高16位异或来实现：(h=k.hashCode())^（h>>>16）。这样做的好处是可以将hashcode的高位值和低位值混合进行异或运算，混合后将高位信息加入到低位信息中，从而使高位的-订单信息被伪装保存。这意味着哈希的高16位也参与了下标的计算。掺杂的元素越多，生成的哈希值的随机性就会增加，哈希碰撞就会减少。备注：-^XOR：不同为1，相同为0->>>：无符号右移：向右加0-&运算：两位同时为“1”，结果为“1”，否则就是0h&(table.length-1)得到对象的存储位置，HashMap底层数组的长度永远是2的n次方。为什么槽数一定要用2^n1。为了使哈希后的结果更加统一，如果槽数不是16，而是17，则槽计算公式变为：(17–1)&hash由上可知，计算结果将是非常相似，hashcode在参与&运算后会被更多的0位屏蔽掉。计算结果只剩下0和16两种，这对hashmap来说是一场灾难。2.等价于长度取模当长度始终为2的n次方时，h&(length-1)运算等价于取长度的模数，即h%length，但&比%更高效。位运算比算术运算更高效，因为算术运算仍然转换为位运算。最终目的是为了让散列结果更均匀，减少散列冲突，提高hashmap的运行效率。分析HashMap的put方法：finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent,booleanevict){Node[]tab;节点p;诠释n,我;//当当前对象的数组为null或者数组长度为0时，需要对数组进行初始化if((tab=table)==null||(n=tab.length)==0){n=(tab=resize()).length;}//使用hash和数组长度减一的值得到散乱的数组下标，表示当前key会根据计算存放在这个位置。如果这个位置没有值，那么直接新建一个k-v节点进行存储//其中长度n是2的幂if((p=tab[i=(n-1)&hash])==null){tab[i]=newNode(哈希,键,值,null);}//如果走到else这一步，说明key索引的数组内容已经存在，也就是发生了碰撞//这时候就需要更复杂的方法来处理碰撞，比如链表和树else{Nodee;Kk;//节点key存在，直接覆盖valueif(p.hash==hash&&((k=p.key)==key||(key!=null&&key.equals(k)))){e=p;}//判断链是红黑树elseif(pinstanceofTreeNode){//其中this表示当前HashMap，tab是map中的数组e=((TreeNode)p).putTreeVal(this,tab,hash,key,value);}else{//判断该链为链表for(intbinCount=0;;++binCount){//如果当前碰撞的节点没有后续节点，则直接新建一个节点追加if((e=p.next)==null){p.next=newNode(hash,key,value,null);//TREEIFY_THRESHOLD=8//从0开始，如果到7就说明满了8，这时候需要转//重新判断是否扩容或者切换到红黑树if(binCount>=TREEIFY_THRESHOLD-1)//-1对于第一个treeifyBin(tab,hash);休息;}//在碰撞节点中找出key完全相同的节点，然后用新节点替换旧节点if(e.hash==hash&&((k=e.key)==key||(key!=null&&key.equals(k))))中断；p=e;}}//此时e为碰撞保存的节点，即旧节点if(e!=null){//keyVoldValue=e.value;//onlyIfAbsent是该方法的调用参数，表示是否替换已有值，//这个值在默认put方法中为false，所以旧值会被新值替换if(!onlyIfAbsent||oldValue==null)e.价值=价值；//允许LinkedHashMap后操作的回调afterNodeAccess(e);返回旧值；}}//mapchangeoperationcounter//比如map内容增减或者rehash等结构变化，会直接导致map的外部并发//迭代导致fail-fast问题，这个值是比较的基础++modCount;//size是map包含的k-v的个数//expandif(++size>threshold)if(++size>threshold)exceedsthemaximumcapacity);//回调以允许LinkedHashMap后操作afterNodeInsertion(evict);returnnull;}HashMap的put方法执行过程如下：①判断键值对数组table[i]是否为空或null，否则执行resize()展开；②根据键值key计算哈希值得到插入的数组索引i，如果table[i]==null，直接新建节点添加；③判断table[i]的第一个元素是否和key相同，如果相同直接覆盖value；④判断table[i]是否为treeNode，即table[i]是否为红黑树，如果是红黑树，直接向树中插入键值对；⑤遍历table[i]，判断链表长度是否大于8。如果大于8，将链表转为红黑树，在红黑树中进行插入操作，否则执行链表的插入操作；如果在遍历过程中发现key已经存在，则直接覆盖value即可；⑥插入成功后，判断实际键值对数量size是否超过最大容量阈值，如果超越，展开HashMap总结一下HashMap的底层结构？基于Map接口的实现，数组+链表的结构，JDK1.8增加了红黑树，链表长度>8变为红黑树，<6变为链表.如果两个对象的哈希码相同会发生什么？Hash冲突，HashMap通过链表来解决Hash冲突，HashMap中equals()和hashCode()的作用是什么？在添加和获取HashMap时，需要通过key的hashCode()进行hash()，然后计算下标(n-1&hash)，从而获取到你要找的相同位置。当发生冲突（collision）时，使用key.equals()方法在链表或树中找到对应的节点。HashMap什么时候扩容？当put元素达到容量乘以加载因子时，是否默认实现16*0.75hash？h=key.hashCode())^(h>>>16)，hashCode进行16位无符号右移，然后按位异或得到这个key的哈希值，因为哈希表的容量是2目前元素的hashCode()往往低位相同，会造成冲突（collisions），所以1.8之后做了一个移位操作：右移元素的hashCode()与自身是result在16位独占或HashMap线程安全之后？HashMap读写效率更高，但是由于是异步的，即读写等操作没有锁保护，在多线程场景下不安全，容易出现数据不一致的情况。推荐使用。以上就是HashMap的介绍。本文视频版讲解详尽，可私信获取。---END--作者简介：mikechen，十余年BAT架构经验，资深技术专家，曾就职于阿里、淘宝、百度。欢迎关注我的个人公众号：mikechen的互联网架构，十余年BAT架构经验！在公众号菜单栏对话框中回复【架构】关键字，即可查看我原创的300+BAT架构技术系列文章和1000+大厂面试问答合集。
