来源
Java建设者
责编
Carol
封图
CSDN下载自视觉中国
（如果你没有时间细抠本文，可以直接看HashMap概述，能让你对HashMap有个大致的了解）
HashMap是Map接口的实现，HashMap允许空的key-value键值对，HashMap被认为是Hashtable的增强版，HashMap是一个非线程安全的容器，如果想构造线程安全的Map考虑使用ConcurrentHashMap。HashMap是无序的，因为HashMap无法保证内部存储的键值对的有序性。
HashMap的底层数据结构是数组+链表的集合体，数组在HashMap中又被称为桶(bucket)。遍历HashMap需要的时间损耗为HashMap实例桶的数量+(key-value映射)的数量。因此，如果遍历元素很重要的话，不要把初始容量设置的太高或者负载因子设置的太低。
HashMap实例有两个很重要的因素，初始容量和负载因子，初始容量指的就是hash表桶的数量，负载因子是一种衡量哈希表填充程度的标准，当哈希表中存在足够数量的entry，以至于超过了负载因子和当前容量，这个哈希表会进行rehash操作，内部的数据结构重新rebuilt。
注意HashMap不是线程安全的，如果多个线程同时影响了HashMap，并且至少一个线程修改了HashMap的结构，那么必须对HashMap进行同步操作。可以使用Collections.synchronizedMap(newHashMap)来创建一个线程安全的Map。
HashMap会导致除了迭代器本身的remove外，外部remove方法都可能会导致fail-fast机制，因此尽量要用迭代器自己的remove方法。如果在迭代器创建的过程中修改了map的结构，就会抛出ConcurrentModificationException异常。
下面就来聊一聊HashMap的细节问题。我们还是从面试题入手来分析HashMap。
HashMap和HashTable的区别
我们上面介绍了一下HashMap，现在来介绍一下HashTable。
相同点
HashMap和HashTable都是基于哈希表实现的，其内部每个元素都是key-value键值对，HashMap和HashTable都实现了Map、Cloneable、Serializable接口。
不同点
父类不同：HashMap继承了AbstractMap类，而HashTable继承了Dictionary类
空值不同：HashMap允许空的key和value值，HashTable不允许空的key和value值。HashMap会把Nullkey当做普通的key对待。不允许nullkey重复。
线程安全性：HashMap不是线程安全的，如果多个外部操作同时修改HashMap的数据结构比如add或者是delete，必须进行同步操作，仅仅对key或者value的修改不是改变数据结构的操作。可以选择构造线程安全的Map比如Collections.synchronizedMap或者是ConcurrentHashMap。而HashTable本身就是线程安全的容器。性能方面：虽然HashMap和HashTable都是基于单链表的，但是HashMap进行put或者get操作，可以达到常数时间的性能；而HashTable的put和get操作都是加了synchronized锁的，所以效率很差。
初始容量不同：HashTable的初始长度是11，之后每次扩充容量变为之前的2n+1（n为上一次的长度）而HashMap的初始长度为16，之后每次扩充变为原来的两倍。创建时，如果给定了容量初始值，那么HashTable会直接使用你给定的大小，而HashMap会将其扩充为2的幂次方大小。
HashMap和HashSet的区别
也经常会问到HashMap和HashSet的区别
HashSet继承于AbstractSet接口，实现了Set、Cloneable,、java.io.Serializable接口。HashSet不允许集合中出现重复的值。HashSet底层其实就是HashMap，所有对HashSet的操作其实就是对HashMap的操作。所以HashSet也不保证集合的顺序。
HashMap底层结构
要了解一个类，先要了解这个类的结构，先来看一下HashMap的结构：
最主要的三个类(接口)就是HashMap,AbstractMap和Map了，HashMap我们上面已经在概述中简单介绍了一下，下面来介绍一下AbstractMap。
AbstractMap类
这个抽象类是Map接口的骨干实现，以求最大化的减少实现类的工作量。为了实现不可修改的map，程序员仅需要继承这个类并且提供entrySet方法的实现即可。它将会返回一组map映射的某一段。通常，返回的集合将在AbstractSet之上实现。这个set不应该支持add或者remove方法，并且它的迭代器也不支持remove方法。
为了实现可修改的map，程序员必须额外重写这个类的put方法(否则就会抛出UnsupportedOperationException)，并且entrySet.iterator()返回的iterator必须实现remove()方法。
Map接口
Map接口定义了key-value键值对的标准。一个对象支持key-value存储。Map不能包含重复的key，每个键最多映射一个值。这个接口代替了Dictionary类，Dictionary是一个抽象类而不是接口。
Map接口提供了三个集合的构造器，它允许将map的内容视为一组键，值集合或一组键值映射。map的顺序定义为map映射集合上的迭代器返回其元素的顺序。一些map实现，像是TreeMap类，保证了map的有序性；其他的实现，像是HashMap，则没有保证。
重要内部类和接口
Node接口
Node节点是用来存储HashMap的一个个实例，它实现了Map.Entry接口，我们先来看一下Map中的内部接口Entry接口的定义
Map.Entry
//一个map的entry链，这个Map.entrySet()方法返回一个集合的视图，包含类中的元素，//这个唯一的方式是从集合的视图进行迭代，获取一个map的entry链。这些Map.Entry链只在//迭代期间有效。interfaceEntryK,V{KgetKey();VgetValue();VsetValue(Vvalue);booleanequals(Objecto);inthashCode();}
Node节点会存储四个属性，hash值，key，value，指向下一个Node节点的引用
//hash值finalinthash;//键finalKkey;//值Vvalue;//指向下一个Node节点的Node类型NodeK,Vnext;
因为Map.Entry是一条条entry链连接在一起的，所以Node节点也是一条条entry链。构造一个新的HashMap实例的时候，会把这四个属性值分为传入
Node(inthash,Kkey,Vvalue,NodeK,Vnext){this.hash=hash;this.key=key;this.value=value;this.next=next;}
实现了Map.Entry接口所以必须实现其中的方法，所以Node节点中也包括上面的五个方法
KeySet内部类
keySet类继承于AbstractSet抽象类，它是由HashMap中的keyset()方法来创建KeySet实例的，旨在对HashMap中的key键进行操作，看一个代码示例
图中把「1,2,3」这三个key放在了HashMap中，然后使用lambda表达式循环遍历key值，可以看到，map.keySet()其实是返回了一个Set接口，KeySet()是在Map接口中进行定义的，不过是被HashMap进行了实现操作，来看一下源码就明白了
//返回一个set视图，这个视图中包含了map中的key。publicSetKkeySet(){////keySet指向的是AbstractMap中的keysetSetKks=keySet;if(ks==null){//如果ks为空，就创建一个KeySet对象//并对ks赋值。ks=newKeySet();keySet=ks;}returnks;}
所以KeySet类中都是对Map中的Key进行操作的：
Values内部类
Values类的创建其实是和KeySet类很相似，不过KeySet旨在对Map中的键进行操作，Values旨在对key-value键值对中的value值进行使用，看一下代码示例：
循环遍历Map中的values值，看一下values()方法最终创建的是什么：
publicCollectionVvalues(){//values其实是AbstractMap中的valuesCollectionVvs=values;if(vs==null){vs=newValues();values=vs;}returnvs;}
所有的values其实都存储在AbstractMap中，而Values类其实也是实现了Map中的Values接口，看一下对values的操作都有哪些方法
其实是和key的操作差不多
EntrySet内部类
上面提到了HashMap中分别有对key、value进行操作的，其实还有对key-value键值对进行操作的内部类，它就是EntrySet，来看一下EntrySet的创建过程：
点进去entrySet()会发现这个方法也是在Map接口中定义的，HashMap对它进行了重写
//返回一个set视图，此视图包含了map中的key-value键值对publicSetMap.EntryK,VentrySet(){SetMap.EntryK,Ves;return(es=entrySet)==null?(entrySet=newEntrySet()):es;}
如果es为空创建一个新的EntrySet实例，EntrySet主要包括了对key-value键值对映射的方法，如下
HashMap1.7的底层结构
JDK1.7中，HashMap采用位桶+链表的实现，即使用链表来处理冲突，同一hash值的链表都存储在一个数组中。但是当位于一个桶中的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低。它的数据结构如下
HashMap大致结构
HashMap底层数据结构就是一个Entry数组，Entry是HashMap的基本组成单元，每个Entry中包含一个key-value键值对。
transientEntryK,V[]table=(EntryK,V[])EMPTY_TABLE;
而每个Entry中包含「hash,key,value」属性，它是HashMap的一个内部类
staticclassEntryK,VimplementsMap.EntryK,V{finalKkey;Vvalue;EntryK,Vnext;inthash;Entry(inth,Kk,Vv,EntryK,Vn){value=v;next=n;key=k;hash=h;}...}
所以，HashMap的整体结构就像下面这样
HashMap1.8的底层结构
与JDK1.7相比，1.8在底层结构方面做了一些改变，当每个桶中元素大于8的时候，会转变为红黑树，目的就是优化查询效率，JDK1.8重写了resize()方法。
HashMap重要属性
「初始容量」
HashMap的默认初始容量是由DEFAULT_INITIAL_CAPACITY属性管理的。
staticfinalintDEFAULT_INITIAL_CAPACITY=14;
HashMap的默认初始容量是14=16，是一个左移操作，它相当于是
「最大容量」
HashMap的最大容量是
staticfinalintMAXIMUM_CAPACITY=;
这里是不是有个疑问？int占用四个字节，按说最大容量应该是左移31位，为什么HashMap最大容量是左移30位呢？因为在数值计算中，最高位也就是最左位的位是代表着符号为，0-正数，1-负数，容量不可能是负数，所以HashMap最高位只能移位到2^30次幂。
「默认负载因子」
HashMap的默认负载因子是
staticfinalfloatDEFAULT_LOAD_FACTOR=0.75f;
float类型所以用.f为单位，负载因子是和扩容机制有关，这里大致提一下，后面会细说。扩容机制的原则是当HashMap中存储的数量HashMap容量*负载因子时，就会把HashMap的容量扩大为原来的二倍。
HashMap的第一次扩容就在DEFAULT_INITIAL_CAPACITY*DEFAULT_LOAD_FACTOR=12时进行。
「树化阈值」
HashMap的树化阈值是
staticfinalintTREEIFY_THRESHOLD=8;
在进行添加元素时，当一个桶中存储元素的数量8时，会自动转换为红黑树（JDK1.8特性）。
「链表阈值」
HashMap的链表阈值是
staticfinalintUNTREEIFY_THRESHOLD=6;
在进行删除元素时，如果一个桶中存储元素数量6后，会自动转换为链表
「扩容临界值」
staticfinalintMIN_TREEIFY_CAPACITY=64;
这个值表示的是当桶数组容量小于该值时，优先进行扩容，而不是树化
「节点数组」
HashMap中的节点数组就是Entry数组，它代表的就是HashMap中「数组+链表」数据结构中的数组。
transientNodeK,V[]table;
Node数组在第一次使用的时候进行初始化操作，在必要的时候进行resize，resize后数组的长度扩容为原来的二倍。
「键值对数量」
在HashMap中，使用size来表示HashMap中键值对的数量。
「修改次数」
在HashMap中，使用modCount来表示修改次数，主要用于做并发修改HashMap时的快速失败-fail-fast机制。
「扩容阈值」
在HashMap中，使用threshold表示扩容的阈值，也就是初始容量*负载因子的值。
threshold涉及到一个扩容的阈值问题，这个问题是由tableSizeFor源码解决的。我们先看一下它的源码再来解释
staticfinalinttableSizeFor(intcap){intn=cap-1;n
=n1;n
=n2;n
=n4;n
=n8;n
=n16;return(n0)?1:(n=MAXIMUM_CAPACITY)?MAXIMUM_CAPACITY:n+1;}
代码中涉及一个运算符
=，它表示的是按位或，啥意思呢？你一定知道「a+=b的意思是a=a+b」，那么同理：a
=b就是a=a
b，也就是双方都转换为二进制，来进行与操作。如下图所示
我们上面采用了一个比较大的数字进行扩容，由上图可知2^29次方的数组经过一系列的或操作后，会算出来结果是2^30次方。
所以扩容后的数组长度是原来的2倍。
「负载因子」
loadFactor表示负载因子，它表示的是HashMap中的密集程度。
HashMap构造函数
在HashMap源码中，有四种构造函数，分别来介绍一下
带有初始容量initialCapacity和负载因子loadFactor的构造函数publicHashMap(intinitialCapacity,floatloadFactor){if(initialCapacity0)thrownewIllegalArgumentException(Illegalinitialcapacity:+initialCapacity);if(initialCapacityMAXIMUM_CAPACITY)initialCapacity=MAXIMUM_CAPACITY;if(loadFactor=0
Float.isNaN(loadFactor))thrownewIllegalArgumentException(Illegalloadfactor:+loadFactor);this.loadFactor=loadFactor;//扩容的阈值this.threshold=tableSizeFor(initialCapacity);}
初始容量不能为负，所以当传递初始容量0的时候，会直接抛出IllegalArgumentException异常。如果传递进来的初始容量最大容量时，初始容量=最大容量。负载因子也不能小于0。然后进行数组的扩容，这个扩容机制也非常重要，我们后面进行探讨
只带有initialCapacity的构造函数publicHashMap(intinitialCapacity){this(initialCapacity,DEFAULT_LOAD_FACTOR);}
最终也会调用到上面的构造函数，不过这个默认的负载因子就是HashMap的默认负载因子也就是0.75f
无参数的构造函数publicHashMap(){this.loadFactor=DEFAULT_LOAD_FACTOR;}
默认的负载因子也就是0.75f
带有map的构造函数publicHashMap(Map?extendsK,?extendsVm){this.loadFactor=DEFAULT_LOAD_FACTOR;putMapEntries(m,false);}
带有Map的构造函数，会直接把外部元素批量放入HashMap中。
讲一讲HashMapput的全过程
我记得刚毕业一年去北京面试，一家公司问我HashMapput过程的时候，我支支吾吾答不上来，后面痛下决心好好整。以JDK1.8为基准进行分析，后面也是。先贴出整段代码，后面会逐行进行分析。
finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent,booleanevict){NodeK,V[]tab;NodeK,Vp;intn,i;//如果table为null或者没有为table分配内存，就resize一次if((tab=table)==null
(n=tab.length)==0)n=(tab=resize()).length;//指定hash值节点为空则直接插入，这个(n-1)hash才是表中真正的哈希if((p=tab[i=(n-1)hash])==null)tab=newNode(hash,key,value,null);//如果不为空else{NodeK,Ve;Kk;//计算表中的这个真正的哈希值与要插入的key.hash相比if(p.hash==hash((k=p.key)==key
(key!=nullkey.equals(k))))e=p;//若不同的话，并且当前节点已经在TreeNode上了elseif(pinstanceofTreeNode)//采用红黑树存储方式e=((TreeNodeK,V)p).putTreeVal(this,tab,hash,key,value);//key.hash不同并且也不再TreeNode上，在链表上找到p.next==nullelse{for(intbinCount=0;;++binCount){if((e=p.next)==null){//在表尾插入p.next=newNode(hash,key,value,null);//新增节点后如果节点个数到达阈值，则进入treeifyBin()进行再次判断if(binCount=TREEIFY_THRESHOLD-1)//-1for1sttreeifyBin(tab,hash);break;}//如果找到了同hash、key的节点，那么直接退出循环if(e.hash==hash((k=e.key)==key
(key!=nullkey.equals(k))))break;//更新p指向下一节点p=e;}}//map中含有旧值，返回旧值if(e!=null){//existingmappingforkeyVoldValue=e.value;if(!onlyIfAbsent
oldValue==null)e.value=value;afterNodeAccess(e);returnoldValue;}}//map调整次数+1++modCount;//键值对的数量达到阈值，需要扩容if(++sizethreshold)resize();afterNodeInsertion(evict);returnnull;}
首先看一下putVal方法，这个方法是final的，如果你自已定义HashMap继承的话，是不允许你自己重写put方法的，然后这个方法涉及五个参数
hash-put放在桶中的位置，在put之前，会进行hash函数的计算。key-参数的key值value-参数的value值onlyIfAbsent-是否改变已经存在的值，也就是是否进行value值的替换标志evict-是否是刚创建HashMap的标志在调用到putVal方法时，首先会进行hash函数计算应该插入的位置
publicVput(Kkey,Vvalue){returnputVal(hash(key),key,value,false,true);}
哈希函数的源码如下
staticfinalinthash(Objectkey){inth;return(key==null)?0:(h=key.hashCode())^(h16);}
首先先来理解一下hash函数的计算规则
Hash函数
hash函数会根据你传递的key值进行计算，首先计算key的hashCode值，然后再对hashcode进行无符号右移操作，最后再和hashCode进行异或^操作。
:无符号右移操作，它指的是「无符号右移，也叫逻辑右移，即若该数为正，则高位补0，而若该数为负数，则右移后高位同样补0」，也就是不管是正数还是负数，右移都会在空缺位补0。
在得到hash值后，就会进行put过程。
首先会判断HashMap中的Node数组是否为null，如果第一次创建HashMap并进行第一次插入元素，首先会进行数组的resize，也就是重新分配，这里还涉及到一个resize()扩容机制源码分析，我们后面会介绍。扩容完毕后，会计算出HashMap的存放位置，通过使用「(n-1)hash」进行计算得出。
然后会把这个位置作为数组的下标作为存放元素的位置。如果不为空，那么计算表中的这个真正的哈希值与要插入的key.hash相比。如果哈希值相同，key-value不一样，再判断是否是树的实例，如果是的话，那么就把它插入到树上。如果不是，就执行尾插法在entry链尾进行插入。
会根据桶中元素的数量判断是链表还是红黑树。然后判断键值对数量是否大于阈值，大于的话则进行扩容。
扩容机制
在Java中，数组的长度是固定的，这意味着数组只能存储固定量的数据。但在开发的过程中，很多时候我们无法知道该建多大的数组合适。好在HashMap是一种自动扩容的数据结构，在这种基于变长的数据结构中，扩容机制是非常重要的。
在HashMap中，阈值大小为桶数组长度与负载因子的乘积。当HashMap中的键值对数量超过阈值时，进行扩容。HashMap中的扩容机制是由resize()方法来实现的，下面我们就来一次认识下。（贴出中文注释，便于复制）
finalNodeK,V[]resize(){NodeK,V[]oldTab=table;//存储oldtable的大小intoldCap=(oldTab==null)?0:oldTab.length;//存储扩容阈值intoldThr=threshold;intnewCap,newThr=0;if(oldCap0){//如果oldtable数据已达最大，那么threshold也被设置成最大if(oldCap=MAXIMUM_CAPACITY){threshold=Integer.MAX_VALUE;returnoldTab;}//左移扩大二倍,elseif((newCap=oldCap1)MAXIMUM_CAPACITYoldCap=DEFAULT_INITIAL_CAPACITY)//扩容成原来二倍newThr=oldThr1;//doublethreshold}//如果oldThr!0elseif(oldThr0)//initialcapacitywasplacedinthresholdnewCap=oldThr;//如果oldtable=0并且存储的阈值=0else{//zeroinitialthresholdsignifiesusingdefaultsnewCap=DEFAULT_INITIAL_CAPACITY;newThr=(int)(DEFAULT_LOAD_FACTOR*DEFAULT_INITIAL_CAPACITY);}//如果扩充阈值为0if(newThr==0){//扩容阈值为初始容量*负载因子floatft=(float)newCap*loadFactor;newThr=(newCapMAXIMUM_CAPACITYft(float)MAXIMUM_CAPACITY?(int)ft:Integer.MAX_VALUE);}//重新给负载因子赋值threshold=newThr;//获取扩容后的数组
SuppressWarnings({rawtypes,unchecked})NodeK,V[]newTab=(NodeK,V[])newNode[newCap];table=newTab;//如果第一次进行table初始化不会走下面的代码//扩容之后需要重新把节点放在新扩容的数组中if(oldTab!=null){for(intj=0;joldCap;++j){NodeK,Ve;if((e=oldTab[j])!=null){oldTab[j]=null;if(e.next==null)newTab[e.hash(newCap-1)]=e;elseif(einstanceofTreeNode)//重新映射时，需要对红黑树进行拆分((TreeNodeK,V)e).split(this,newTab,j,oldCap);else{//preserveorderNodeK,VloHead=null,loTail=null;NodeK,VhiHead=null,hiTail=null;NodeK,Vnext;//遍历链表，并将链表节点按原顺序进行分组do{next=e.next;if((e.hasholdCap)==0){if(loTail==null)loHead=e;elseloTail.next=e;loTail=e;}else{if(hiTail==null)hiHead=e;elsehiTail.next=e;hiTail=e;}}while((e=next)!=null);//将分组后的链表映射到新桶中if(loTail!=null){loTail.next=null;newTab[j]=loHead;}if(hiTail!=null){hiTail.next=null;newTab[j+oldCap]=hiHead;}}}}}returnnewTab;}扩容机制源码比较长，我们耐心点进行拆分
我们以if...elseif...else逻辑进行拆分，上面代码主要做了这几个事情
判断HashMap中的数组的长度，也就是(NodeK,V[])oldTab.length()，再判断数组的长度是否比最大的的长度也就是2^30次幂要大，大的话直接取最大长度，否则利用位运算扩容为原来的两倍
如果数组长度不大于0，再判断扩容阈值threshold是否大于0，也就是看有无外部指定的扩容阈值，若有则使用，这里需要说明一下threshold何时是oldThr0，因为oldThr=threshold，这里其实比较的就是threshold，因为HashMap中的每个构造方法都会调用HashMap(initCapacity,loadFactor)这个构造方法，所以如果没有外部指定initialCapacity，初始容量使用的就是16，然后根据this.threshold=tableSizeFor(initialCapacity);求得threshold的值。
否则，直接使用默认的初始容量和扩容阈值，走else的逻辑是在table刚刚初始化的时候。
然后会判断newThr是否为0，笔者在刚开始研究时发现newThr=(int)(DEFAULT_LOAD_FACTOR*DEFAULT_INITIAL_CAPACITY);一直以为这是常量做乘法，怎么会为0，其实不是这部分的问题，在于上面逻辑判断中的扩容操作，可能会导致位溢出。
导致位溢出的示例：oldCap=2^28次幂，threshold2的三次方整数次幂。在进入到floatft=(float)newCap*loadFactor;这个方法是2^28*2^(3+n)会直接2^31次幂，导致全部归零。
「在扩容后需要把节点放在新扩容的数组中，这里也涉及到三个步骤」
循环桶中的每个Node节点，判断Node是否为空，为空直接返回，不为空则遍历桶数组，并将键值对映射到新的桶数组中。如果不为空，再判断是否是树形结构，如果是树形结构则按照树形结构进行拆分，拆分方法在split方法中。如果不是树形结构，则遍历链表，并将链表节点按原顺序进行分组。
讲一讲get方法全过程
我们上面讲了HashMap中的put方法全过程，下面我们来看一下get方法的过程，
publicVget(Objectkey){NodeK,Ve;return(e=getNode(hash(key),key))==null?null:e.value;}finalNodeK,VgetNode(inthash,Objectkey){NodeK,V[]tab;NodeK,Vfirst,e;intn;Kk;//找到真实的元素位置if((tab=table)!=null(n=tab.length)0(first=tab[(n-1)hash])!=null){//总是会check一下第一个元素if(first.hash==hash//alwayscheckfirstnode((k=first.key)==key
(key!=nullkey.equals(k))))returnfirst;//如果不是第一个元素，并且下一个元素不是空的if((e=first.next)!=null){//判断是否属于TreeNode，如果是TreeNode实例，直接从TreeNode.getTreeNode取if(firstinstanceofTreeNode)return((TreeNodeK,V)first).getTreeNode(hash,key);//如果还不是TreeNode实例，就直接循环数组元素，直到找到指定元素位置do{if(e.hash==hash((k=e.key)==key
(key!=nullkey.equals(k))))returne;}while((e=e.next)!=null);}}returnnull;}
来简单介绍下吧，首先会检查table中的元素是否为空，然后根据hash算出指定key的位置。然后检查链表的第一个元素是否为空，如果不为空，是否匹配，如果匹配，直接返回这条记录；如果匹配，再判断下一个元素的值是否为null，为空直接返回，如果不为空，再判断是否是TreeNode实例，如果是TreeNode实例，则直接使用TreeNode.getTreeNode取出元素，否则执行循环，直到下一个元素为null位置。
getNode方法有一个比较重要的过程就是「(n-1)hash」，这段代码是确定需要查找的桶的位置的，那么，为什么要(n-1)hash呢？
n就是HashMap中桶的数量，这句话的意思也就是说(n-1)hash就是(桶的容量-1)hash
//为什么HashMap的检索位置是(table.size-1)hashpublicstaticvoidmain(String[]args){MapString,Objectmap=newHashMap();//debug得知1的hash值算出来是49map.put(1,cxuan);//debug得知1的hash值算出来是50map.put(2,cxuan);//debug得知1的hash值算出来是51map.put(3,cxuan);}
那么每次算完之后的(n-1)hash，依次为
也就是「tab[(n-1)hash]」算出的具体位置。
HashMap的遍历方式
HashMap的遍历，也是一个使用频次特别高的操作
HashMap遍历的基类是HashIterator，它是一个Hash迭代器，它是一个HashMap内部的抽象类，它的构造比较简单，只有三种方法，「hasNext、remove和nextNode」方法，其中nextNode方法是由三种迭代器实现的
这三种迭代器就就是
KeyIterator，对key进行遍历ValueIterator，对value进行遍历EntryIterator，对Entry链进行遍历虽然说看着迭代器比较多，但其实他们的遍历顺序都是一样的，构造也非常简单，都是使用HashIterator中的nextNode方法进行遍历
finalclassKeyIteratorextendsHashIteratorimplementsIteratorK{publicfinalKnext(){returnnextNode().key;}}finalclassValueIteratorextendsHashIteratorimplementsIteratorV{publicfinalVnext(){returnnextNode().value;}}finalclassEntryIteratorextendsHashIteratorimplementsIteratorMap.EntryK,V{publicfinalMap.EntryK,Vnext(){returnnextNode();}}
HashIterator中的遍历方式
abstractclassHashIterator{NodeK,Vnext;//下一个entry节点NodeK,Vcurrent;//当前entry节点intexpectedModCount;//fail-fast的判断标识intindex;//当前槽HashIterator(){expectedModCount=modCount;NodeK,V[]t=table;current=next=null;index=0;if(t!=nullsize0){//advancetofirstentrydo{}while(indext.length(next=t[index++])==null);}}publicfinalbooleanhasNext(){returnnext!=null;}finalNodeK,VnextNode(){NodeK,V[]t;NodeK,Ve=next;if(modCount!=expectedModCount)thrownewConcurrentModificationException();if(e==null)thrownewNoSuchElementException();if((next=(current=e).next)==null(t=table)!=null){do{}while(indext.length(next=t[index++])==null);}returne;}publicfinalvoidremove(){...}}
next和current分别表示下一个Node节点和当前的Node节点，HashIterator在初始化时会遍历所有的节点。下面我们用图来表示一下他们的遍历顺序
你会发现nextNode()方法的遍历方式和HashIterator的遍历方式一样，只不过判断条件不一样，构造HashIterator的时候判断条件是有没有链表，桶是否为null，而遍历nextNode的判断条件变为下一个node节点是不是null，并且桶是不是为null。
HashMap中的移除方法
HashMap中的移除方法也比较简单了，源码如下
publicVremove(Objectkey){NodeK,Ve;return(e=removeNode(hash(key),key,null,false,true))==null?null:e.value;}finalNodeK,VremoveNode(inthash,Objectkey,Objectvalue,booleanmatchValue,booleanmovable){NodeK,V[]tab;NodeK,Vp;intn,index;if((tab=table)!=null(n=tab.length)0(p=tab[index=(n-1)hash])!=null){NodeK,Vnode=null,e;Kk;Vv;if(p.hash==hash((k=p.key)==key
(key!=nullkey.equals(k))))node=p;elseif((e=p.next)!=null){if(pinstanceofTreeNode)node=((TreeNodeK,V)p).getTreeNode(hash,key);else{do{if(e.hash==hash((k=e.key)==key
(key!=nullkey.equals(k)))){node=e;break;}p=e;}while((e=e.next)!=null);}}if(node!=null(!matchValue
(v=node.value)==value
(value!=nullvalue.equals(v)))){if(nodeinstanceofTreeNode)((TreeNodeK,V)node).removeTreeNode(this,tab,movable);elseif(node==p)tab[index]=node.next;elsep.next=node.next;++modCount;--size;afterNodeRemoval(node);returnnode;}}returnnull;}
remove方法有很多，最终都会调用到removeNode方法，只不过传递的参数值不同，我们拿remove(object)来演示一下。
首先会通过hash来找到对应的bucket，然后通过遍历链表，找到键值相等的节点，然后把对应的节点进行删除。
关于HashMap的面试题
HashMap的数据结构
JDK1.7中，HashMap采用位桶+链表的实现，即使用链表来处理冲突，同一hash值的链表都存储在一个数组中。但是当位于一个桶中的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低。
所以，与JDK1.7相比，JDK1.8在底层结构方面做了一些改变，当每个桶中元素大于8的时候，会转变为红黑树，目的就是优化查询效率。
HashMap的put过程
大致过程如下，首先会使用hash方法计算对象的哈希码，根据哈希码来确定在bucket中存放的位置，如果bucket中没有Node节点则直接进行put，如果对应bucket已经有Node节点，会对链表长度进行分析，判断长度是否大于8，如果链表长度小于8，在JDK1.7前会使用头插法，在JDK1.8之后更改为尾插法。如果链表长度大于8会进行树化操作，把链表转换为红黑树，在红黑树上进行存储。
HashMap为啥线程不安全
HashMap不是一个线程安全的容器，不安全性体现在多线程并发对HashMap进行put操作上。如果有两个线程A和B，首先A希望插入一个键值对到HashMap中，在决定好桶的位置进行put时，此时A的时间片正好用完了，轮到B运行，B运行后执行和A一样的操作，只不过B成功把键值对插入进去了。如果A和B插入的位置（桶）是一样的，那么线程A继续执行后就会覆盖B的记录，造成了数据不一致问题。
还有一点在于HashMap在扩容时，因resize方法会形成环，造成死循环，导致CPU飙高。
HashMap是如何处理哈希碰撞的
HashMap底层是使用位桶+链表实现的，位桶决定元素的插入位置，位桶是由hash方法决定的，当多个元素的hash计算得到相同的哈希值后，HashMap会把多个Node元素都放在对应的位桶中，形成链表，这种处理哈希碰撞的方式被称为链地址法。
其他处理hash碰撞的方式还有「开放地址法、rehash方法、建立一个公共溢出区」这几种方法。
HashMap是如何get元素的
首先会检查table中的元素是否为空，然后根据hash算出指定key的位置。然后检查链表的第一个元素是否为空，如果不为空，是否匹配，如果匹配，直接返回这条记录；如果匹配，再判断下一个元素的值是否为null，为空直接返回，如果不为空，再判断是否是TreeNode实例，如果是TreeNode实例，则直接使用TreeNode.getTreeNode取出元素，否则执行循环，直到下一个元素为null位置。
HashMap和HashTable有什么区别
见上
HashMap和HashSet的区别
见上
HashMap是如何扩容的
HashMap中有两个非常重要的变量，一个是loadFactor，一个是threshold，loadFactor表示的就是负载因子，threshold表示的是下一次要扩容的阈值，当threshold=loadFactor*数组长度时，数组长度扩大位原来的两倍，来重新调整map的大小，并将原来的对象放入新的bucket数组中。
HashMap的长度为什么是2的幂次方
这道题我想了几天，之前和群里小伙伴们探讨每日一题的时候，问他们为什么length%hash==(n-1)hash，它们说相等的前提是length的长度2的幂次方，然后我回了一句难道length还能不是2的幂次方吗？其实是我没有搞懂因果关系，因为HashMap的长度是2的幂次方，所以使用余数来判断在桶中的下标。如果length的长度不是2的幂次方，小伙伴们可以举个例子来试试。
例如长度为9时候，3(9-1)=0，2(9-1)=0，都在0上，碰撞了；
这样会增大HashMap碰撞的几率。
HashMap线程安全的实现有哪些
因为HashMap不是一个线程安全的容器，所以并发场景下推荐使用ConcurrentHashMap，或者使用线程安全的HashMap，使用Collections包下的线程安全的容器，比如说
Collections.synchronizedMap(newHashMap());
还可以使用HashTable，它也是线程安全的容器，基于key-value存储，经常用HashMap和HashTable做比较就是因为HashTable的数据结构和HashMap相同。
上面效率最高的就是ConcurrentHashMap。
文章并没有叙述太多关于红黑树的构造、包含添加、删除、树化等过程，一方面是自己能力还达不到，一方面是关于红黑树的描述太过于占据篇幅，红黑树又是很大的一部分内容，所以会考虑放在后续的红黑树进行讲解。