一文搞定面试中HashMap相关问题

　　面试官：简单聊聊你理解的HashMap基本概念HashMap是基于哈希表的Map接口的，非同步实现的，以键值对存储数据的集合容器。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。数据结构在JDK7中，由数组链表组成在JDK8中，由数组链表红黑树组成。其中链表则是主要为了解决哈希冲突而存在的。当链表过长，则会严重影响HashMap的性能，jdk8做了进一步的优化，引入了红黑树，链表和红黑树在达到一定条件会进行转换，其中链表的时间复杂度是O（n），红黑树时间复杂度是O（logn）影响HashMap性能的重要参数初始容量capacity：创建哈希表（数组）时桶的数量，默认为16。如果太少，很容易触发扩容，如果太多，遍历哈希表会比较慢。负载因子loadFactor：哈希表在其容量自动增加之前可以达到多满的一种尺度，默认为0。75阈值threshold。阈值容量负载因子。默认12。当元素数量超过阈值时便会触发扩容单向链表转换为红黑树的时候会先变化为双向链表最终转换为红黑树，双向链表跟红黑树是共存的。红黑树的root节点不一定跟table〔i〕也就是链表的头节点是同一个，三者同步是靠MoveRootToFront实现的。
　　而HashIterator。remove（）会在调用removeNode的时候movablefalse。面试官：为啥hashmap中链表的个数默认设为8个时，转红黑树？
　　是因为泊松分布
　　源码中的注释：
　　大概的意思是：理想情况下，使用随机的哈希码，容器中节点分布在hash桶中的频率遵循泊松分布，按照泊松分布的计算公式计算出了桶中元素个数和概率的对照表，可以看到链表中元素个数为8时的概率已经非常小，小于千万分之一概率，所以在选择链表元素个数时，把长度8作为转化的默认转红黑树的阈值。面试官：默认加载因子是多少？为什么是0。75，不是0。6或者0。8？
　　当存储的所有节点数（160。7512）时，就会触发扩容。默认负载因子（0。75）在时间和空间成本上提供了很好的折衷。
　　较高的值会降低空间开销，但提高查找成本（体现在大多数的HashMap类的操作，包括get和put）。设置初始大小时，应该考虑预计的entry数在map及其负载系数，并且尽量减少rehash操作的次数。如果初始容量大于最大条目数除以负载因子，rehash操作将不会发生。
　　当桶中元素到达8个的时候，概率已经变得非常小，也就是说用0。75作为加载因子，每个碰撞位置的链表长度超过个是几乎不可能的。面试官：HashMap的底层数组长度为何总是2的n次方
　　HashMap根据用户传入的初始化容量，利用无符号右移和按位或运算等方式计算出第一个大于该数的2的幂。使数据分布均匀，减少碰撞当length为2的n次方时，h（length1）hlength，因为位运算直接对内存数据进行操作，不需要转成十进制，在速度、效率上比直接取模要快得多面试官：说说jdk8中HashMap链表和红黑树的转化条件
　　在数组同位置的元素个数又达到了8个（代码是7，从0开始，及第8个开始判断是否转化成红黑树），且数组的长度还小于64的时候，则会扩容数组
　　，或者当前存入数据大于阈值threshold即发生扩容。
　　且如果数组的长度大于等于64的话，才会将该节点的链表转换成树。如果当前数组的长度小于64，那么会选择先进行数组扩容，而不是转换为红黑树，以减少搜索时间。
　　在扩容完成之后，如果某个节点的是树，同时现在该节点的个数又小于等于6个了，则会将该树转为链表。
　　面试官：简单讲讲jdk8中put和get方法
　　put方法：
　　上图流程的边界条件过多，下面是精简的总结：判断Hashmap是否为空，为空就扩容，不为空计算出key的hash值，定位到对应的数组索引
　　如果此处数组是空的，则调用resize进行初始化；如果哈希冲突了，且key不存在，向链表后面追加元素（尾插法）如果冲突了，且key已经存在，就覆盖掉
　　向后追加时注意，优先以链表的形式存放，在数组同位置的元素个数又达到了8个（代码是7，从0开始，及第8个开始判断是否转化成红黑树），且数组的长度还小于64的时候，则会扩容数组，或者当前存入数据大于阈值threshold即发生扩容。如果数组的长度大于等于64的话，才会将该节点的链表转换成树。在扩容完成之后，如果某个节点的是树，同时现在该节点的个数又小于等于6个了，则会将该树转为链表。
　　源码摘录：publicVput（Kkey，Vvalue）｛对key的hashCode（）做hashreturnputVal（hash（key），key，value，false，true）；｝finalVputVal（inthash，Kkey，Vvalue，booleanonlyIfAbsent，booleanevict）｛NodeK，V〔〕NodeK，Vp；intn，i；步骤1：tab为空则创建if（（tabtable）null（ntab。length）0）n（tabresize（））。步骤2：计算index，并对null做处理if（（ptab〔i（n1）hash〕）null）tab〔i〕newNode（hash，key，value，null）；else｛NodeK，Ve；Kk；步骤3：节点key存在，直接覆盖valueif（p。hashhash（（kp。key）key（key！nullkey。equals（k））））步骤4：判断该链为红黑树elseif（pinstanceofTreeNode）e（（TreeNodeK，V）p）。putTreeVal（this，tab，hash，key，value）；步骤5：该链为链表else｛for（intbinCount0；；binCount）｛if（（ep。next）null）｛p。nextnewNode（hash，key，value，null）；链表长度大于8转换为红黑树进行处理if（binCountTREEIFYTHRESHOLD1）1for1sttreeifyBin（tab，hash）；｝key已经存在直接覆盖valueif（e。hashhash（（ke。key）key（key！nullkey。equals（k））））｝｝if（e！null）｛existingmappingforkeyVoldValuee。if（！onlyIfAbsentoldValuenull）e。afterNodeAccess（e）；returnoldV｝｝modC步骤6：超过最大容量就扩容if（sizethreshold）resize（）；afterNodeInsertion（evict）；｝第31行treeifyBin方法部分代码finalvoidtreeifyBin（NodeK，V〔〕tab，inthash）｛intn，NodeK，Ve；staticfinalintMINTREEIFYCAPACITY64；如果大于8但是数组容量小于64，就进行扩容if（tabnull（ntab。length）MINTREEIFYCAPACITY）resize（）；｝
　　get方法：
　　HashMap的get方法就是计算出要获取元素的hash值，去对应位置获取即可。面试官：简单说说Jdk7和Jdk8的put方法区别是什么？解决哈希冲突时，JDK7只使用链表，JDK8使用链表红黑树，当满足一定条件，链表会转换为红黑树。链表插入元素时，JDK7使用头插法插入元素，但在多线程的环境下，扩容时会造成环形链或数据丢失，出现死循环。在transfer函数中，jdk7中HashMap的transfer函数如下：voidtransfer（Entry〔〕newTable，booleanrehash）｛
　　intnewCapacitynewTable。
　　for（EntryK，Ve：table）｛
　　while（null！e）｛
　　EntryK，Vnexte。
　　if（rehash）｛
　　e。hashnulle。key？0：hash（e。key）；
　　｝
　　intiindexFor（e。hash，newCapacity）；
　　e。nextnewTable〔i〕；
　　newTable〔i〕e；
　　
　　｝
　　｝
　　｝总结下该函数的主要作用：在对table进行扩容到newTable后，需要将原来数据转移到newTable中，注意1012行代码，这里可以看出在转移元素的过程中，使用的是头插法，也就是链表的顺序会翻转，这里也是形成死循环的关键点因此，JDK8使用尾插法插入元素，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了，但JDK8的HashMap仍然是线程不安全的，在多线程环境下，会发生数据覆盖的情况，导致数据不一致
　　jdk8putVal（）方法中，。。。if（（ptab〔i（n1）hash〕）null）tab〔i〕newNode（hash，key，value，null）；else。。。
　　如果没有hash碰撞则会直接插入元素。如果线程A和线程B同时进行put操作，刚好这两条不同的数据hash值一样，并且该位置数据为null，所以这线程A、B都会进入tab中。
　　假设一种情况，线程A进入后还未进行数据插入时挂起，而线程B正常执行，从而正常插入数据，然后线程A获取CPU时间片，此时线程A不用再进行hash判断了，这时候会出现一种情况：线程A会把线程B插入的数据给覆盖，发生线程不安全。此处感兴趣的可以见这篇文章〔HashMap线程不安全的体现〕（https：www。cnblogs。comdeveloperchanp10450908。html）面试官：当两个对象的hashCode相同会发生什么？
　　因为hashCode相同，不一定就是相等的（equals方法比较），所以两个对象所在数组的下标相同，碰撞就此发生。又因为HashMap使用链表存储对象，这个Node会存储到链表中面试官：如何解决hash冲突？Hashmap解决hash冲突，使用的是链地址法，即数组链表的形式来解决。put方法执行首先判断table〔i〕位置，如果为空就直接插入，不为空判断和当前值是否相等，相等就覆盖，如果不相等的话，判断是否是红黑树节点，如果不是，就从table〔i〕位置开始遍历链表，相等覆盖，不相等插入。扰动函数可以减少碰撞原理是如果两个不相等的对象返回不同的hashcode的话，那么碰撞的几率就会小些。这就意味着存链表结构减小，这样取值的话就不会频繁调用equal方法，从而提高HashMap的性能（扰动即Hash方法内部的算法实现，目的是让不同对象返回不同hashcode）。使用不可变的、声明作final对象，并且采用合适的equals（）和hashCode（）方法，将会减少碰撞的发生不可变性使得能够缓存不同键的hashcode，这将提高整个获取对象的速度，使用String、Integer这样的wrapper类作为键是非常好的选择。面试官：你还知道哪些hash算法？
　　Hash函数是指把一个大范围映射到一个小范围，目的往往是为了节省空间，使得数据容易保存。
　　比较出名的有MurmurHash、MD4、MD5等等。面试官：你知道hash的实现吗？为什么要这样实现？
　　JDK1。8中，它是先算出正常的哈希值，然后通过hashCode（）的高16位异或运算实现的：（hk。hashCode（））（h16），主要是从速度，功效和质量来考虑的，减少系统的开销，也不会造成因为高位没有参与下标的计算，从而引起的碰撞。面试官：jdk8中，刚刚你说的hashmap在解决hash冲突的时候，选择先用链表，再转红黑树，为什么不直接用红黑树？
　　因为红黑树需要进行左旋，右旋，变色这些操作来保持平衡，而单链表不需要。
　　当数组同位置的元素小于8个的时候，此时做查询操作，链表结构已经能保证查询性能，红黑树也不会带来明显的查询时间上的优势，反而会增加空间负担。
　　当数组同位置的元素大于等于8个的时候，红黑树搜索时间复杂度是O（logn），而链表是O（n），此时需要红黑树来加快查询速度，但是新增节点的效率变慢了。
　　但如果一开始就用红黑树结构，元素太少，新增效率又比较慢，无疑这是浪费性能的。如果不用红黑树，用二叉查找树可以么？
　　但是二叉查找树在特殊情况下会变成一条线性结构（这就跟原来使用链表结构一样了，造成很深的问题），遍历查找会非常慢面试官：一般用什么作为HashMap的key？
　　一般用Integer、String这种不可变类当HashMap当key，而且String最为常用。因为字符串是不可变的，所以在它创建的时候hashcode就被缓存了，不需要重新计算。这就是HashMap中的键往往都使用字符串的原因。因为获取对象的时候要用到equals（）和hashCode（）方法，那么键对象正确的重写这两个方法是非常重要的，这些类已经很规范的重写了hashCode（）以及equals（）方法。
　　用可变类当HashMap的key有什么问题？
　　hashcode可能发生改变，导致put进去的值，无法get出。如下所示HashMapListString，ObjectchangeMapnewHashMap（）；ListStringlistnewArrayList（）；list。add（hello）；ObjectobjectValuenewObject（）；changeMap。put（list，objectValue）；System。out。println（changeMap。get（list））；list。add（helloworld）；hashcode发生了改变System。out。println（changeMap。get（list））；
　　输出值如下java。lang。Object74a14482null面试官：HashMap如何扩容？何时进行扩容？HashMap使用的是懒加载，构造完HashMap对象后，只要不进行put方法插入元素，HashMap并不会去初始化或者扩容table。
　　首次调用put方法时，HashMap如果发现table为空然后调用resize方法进行初始化。
　　jdk7：
　　Hashmap在容量超过负载因子所定义的容量之后，就会扩容。Java里的数组是无法自动扩容的，方法是将Hashmap的大小扩大为原来数组的两倍，并将原来的对象放入新的数组中。
　　那扩容的具体步骤是什么？让我们看看源码。
　　先来看下JDK7的代码：voidresize（intnewCapacity）｛Entry〔〕oldT引用扩容前的Entry数组intoldCapacityoldTable。if（oldCapacityMAXIMUMCAPACITY）｛扩容前的数组大小如果已经达到最大（230）了thresholdInteger。MAXVALUE；修改阈值为int的最大值（2311），这样以后就不会扩容了｝Entry〔〕newTablenewEntry〔newCapacity〕；transfer（newTable）；将数据转移到新的Entry数组里tablenewTthreshold（int）（newCapacityloadFactor）；｝
　　这里就是使用一个容量更大的数组来代替已有的容量小的数组，transfer（）方法将原有Entry数组的元素拷贝到新的Entry数组里。voidtransfer（Entry〔〕newTable）｛Entry〔〕intnewCapacitynewTable。for（intj0；jsrc。j）｛EntryK，Vesrc〔j〕；if（e！null）｛src〔j〕释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）do｛EntryK，Vnexte。intiindexFor（e。hash，newCapacity）；重新计算每个元素在数组中的位置e。nextnewTable〔i〕；newTable〔i〕e；｝while（e！null）；｝｝｝
　　newTable〔i〕的引用赋给了e。next，也就是使用了单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置；这样先放在一个索引上的元素终会被放到Entry链的尾部（如果发生了hash冲突的话）。
　　我们继续看下JDK8的resize源码：finalNodeK，V〔〕resize（）｛NodeK，V〔〕oldTintoldCap（oldTabnull）？0：oldTab。intoldTintnewCap，newThr0；if（oldCap0）｛超过最大值就不再扩充了，就只好随你碰撞去吧if（oldCapMAXIMUMCAPACITY）｛thresholdInteger。MAXVALUE；returnoldT｝没超过最大值，就扩充为原来的2倍elseif（（newCapoldCap1）MAXIMUMCAPACITYoldCapDEFAULTINITIALCAPACITY）newThroldThr1；doublethreshold｝elseif（oldThr0）初始容量设置为阈值newCapoldTelse｛zeroinitialthresholdsignifiesusingdefaultsnewCapDEFAULTINITIALCAPACITY；newThr（int）（DEFAULTLOADFACTORDEFAULTINITIALCAPACITY）；｝计算新的resize上限if（newThr0）｛floatft（float）newCaploadFnewThr（newCapMAXIMUMCAPACITYft（float）MAXIMUMCAPACITY？（int）ft：Integer。MAXVALUE）；｝thresholdnewTSuppressWarnings（｛rawtypes，unchecked｝）NodeK，V〔〕newTab（NodeK，V〔〕）newNode〔newCap〕；tablenewTif（oldTab！null）｛把每个bucket都移动到新的buckets中for（intj0；joldCj）｛NodeK，Ve；if（（eoldTab〔j〕）！null）｛oldTab〔j〕if（e。nextnull）newTab〔e。hash（newCap1）〕e；elseif（einstanceofTreeNode）（（TreeNodeK，V）e）。split（this，newTab，j，oldCap）；else｛链表优化重hash的代码块NodeK，VloHeadnull，loTNodeK，VhiHeadnull，hiTNodeK，Vdo｛nexte。if（（e。hasholdCap）0）｛if（loTailnull）loHelseloTail。loT｝原索引oldCapelse｛if（hiTailnull）hiHelsehiTail。hiT｝｝while（（enext）！null）；原索引放到bucket里if（loTail！null）｛loTail。newTab〔j〕loH｝原索引oldCap放到bucket里if（hiTail！null）｛hiTail。newTab〔joldCap〕hiHresize之后，元素的位置在原来的位置，或者原来的位置oldCap（原来哈希表的长度）。这边先不展开讲，后续提到这块｝｝｝｝｝returnnewT｝
　　当添加完元素后，如果HashMap发现size（元素总数）大于threshold（阈值），则会调用resize方法进行扩容，然后把扩容后的数组放到新的数组中去。
　　若threshold（阈值）不为空，table的首次初始化大小为阈值，否则初始化为缺省值大小16。
　　当table需要扩容时，扩容后的table大小变为原来的两倍，接下来就是进行扩容后table的调整：
　　假设扩容前的table大小为2的N次方，有put方法可知，元素的table索引为其hash值的后N位确定
　　那么扩容后的table大小即为2的N1次方，则其中元素的table索引为其hash值的后N1位确定，比原来多了一位
　　因此，table中的元素只有两种情况：元素hash值第N1位为0：不需要进行位置调整元素hash值第N1位为1：调整至原索引的两倍位置
　　在resize方法中，第45行的判断即用于确定元素hashi值第N1位是否为0：若为0，则使用loHead与loTail，将元素移至新table的原索引处若不为0，则使用hiHead与hiHead，将元素移至新table的两倍索引处
　　JDK8做了两处优化：JDK7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置（头插法）。JDK8不会倒置，使用尾插法。不需要像JDK7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成原索引oldCap。面试官：jdk8中的扩容为什么逻辑判断更简单
　　元素在重新计算hash之后，因为n变为2倍，那么n1的mask范围在高位多1bit（红色），因此新的index就会发生这样的变化：
　　因此，我们在扩充HashMap的时候，不需要像JDK7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成原索引oldCap由于hashmap的索引是根据哈希值的后N位决定的，由于初始数组容量是16（2416），所以是哈希码后4位决定索引位置（即当前元素要存到数组的哪个位置）。
　　而扩容是以2的次方扩容的（每次乘以2的次方倍），所以相当于n1高位1（这里是第5位01），同时索引值变成哈希值后N1位（这里是第一次扩容，所以是后5位）。
　　这样原先的哈希码仍然可以用作索引值。
　　这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，
　　因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK8新增的优化点。面试官：HashMap为什么不用跳表替换红黑树呢？
　　跳表是以空间换时间的数据结构，红黑树树不需要额外的空间
　　同时HashMap的Entry并没有内在的排序关系，所以也无法使用跳表，因为跳表本身要求要存在排序关系
　　对于hashmap的增删改查使用都很频繁，红黑树的特点就是相对来说各种性能比较均衡，稳定面试官：HashMap是如何实现FailFast的？
　　HashMap做的增删改都会引发modCount值的变化，跟版本控制功能类似，可以理解成version，在特定的操作下需要对version进行检查，适用于FaiFast机制。
　　在java的集合类中存在一种FailFast的错误检测机制，当多个线程对同一集合的内容进行操作时，可能就会产生此类异常。比如当A通过iterator去遍历某集合的过程中，其他线程修改了此集合，此时会抛出ConcurrentModificationException异常。此类机制就是通过modCount实现的，在迭代器初始化时，会赋值expectedModCount，在迭代过程中判断modCount和expectedModCount是否一致。面试官：HashMap，HashTable，ConcurrentHash的共同点和区别
　　HashMap底层由链表数组红黑树实现可以存储null键和null值线性不安全初始容量为16，扩容每次都是2的n次幂加载因子为0。75，当Map中元素总数超过Entry数组的0。75，触发扩容操作。并发情况下，HashMap进行put操作会引起死循环，导致CPU利用率接近100HashMap是对Map接口的实现
　　HashTableHashTable的底层也是由链表数组红黑树实现。无论key还是value都不能为null它是线性安全的，使用了synchronized关键字。HashTable实现了Map接口和Dictionary抽象类Hashtable初始容量为11性能比较低
　　ConcurrentHashMapConcurrentHashMap的底层是数组链表红黑树不能存储null键和值ConcurrentHashMap是线程安全的ConcurrentHashMap使用锁分段技术确保线性安全JDK8为何又放弃分段锁，是因为多个分段锁浪费内存空间，竞争同一个锁的概率非常小，分段锁反而会造成效率低。面试官：简单说说jdk8对HashMap的优化
　　最后在总结一下jdk7jdk8的优化：数组链表改成了数组链表红黑树链表的插入方式从头插法改成了尾插法扩容的时候7需要对原数组中的元素进行重新hash定位在新数组的位置，8采用更简单的判断逻辑，位置不变或索引旧容量大小；在插入时，7先判断是否需要扩容，再插入；而8先进行插入，插入完成再判断是否需要扩容；
　　HashMap相关问题在Java面试中是一个非常重要的一块知识，其实笔者一直都想对这部分的作个整理总结，但苦于没有空闲的时间，希望对需要的朋友有所帮助。
　　本篇文章到这里就结束啦，很感谢靓仔你能看到最后，如果觉得文章对你有帮助，别忘记关注我！
　　计算机内功、JAVA源码、职业成长、项目实战、面试相关资料等更多精彩文章在公众号小牛呼噜噜