©2020-2024 ioDraw All rights reserved,
Privacy Policy
HashMap是面试中最常被问到的问题，被问到的概率基本是99%，关于HashMap的知识点很多，这里做个总结，如果没有提及版本，默认为jdk1.8.
1.HashMap的数据结构？
底层是数组+单链表实现。数组的每个元素是个单链表，在jdk1.8中，当数组长度大于等于64且链表长度超过 8 时，链表转换为红黑树。
2.为什么采用这种结构来存储元素呢？
数组的特点：查询效率高，插入，删除效率低。
链表的特点：查询效率低，插入，删除效率高。
在HashMap底层使用数组加（链表或红黑树）的结构完美的解决了数组和链表的问题，使得查询和插入，删除的效率都很高。
3.HashMap 的工作原理？
HashMap 底层是 hash 数组和单向链表实现，数组中的每个元素都是链表，由 Node 内部类（实现 Map.Entry接口）实现，HashMap
通过 put & get 方法存储和获取。
存储对象时，将 K/V 键值传给 put() 方法：
1）调用 hash(K) 方法计算 K 的 hash 值，然后结合数组长度，计算得数组下标。
2）如果下标对应的元素在 HashMap 中不存在，则执行插入，若存在，则发生碰撞。
3）发生碰撞时，如果两个K的 equals 返回 true，则更新键值对；否则插入链表的尾部或者红黑树中。（JDK 1.7 之前使用头插法、JDK 1.8
使用尾插法）。
4）调整数组大小，当容器中的元素个数大于总容量*负载因子时，容器会进行2倍扩容，默认总容量是16，负载因子是0.75。
获取对象时，将 K 传给 get() 方法：
1）调用 hash(K) 方法并结合数组长度，获取该键值所在链表的数组下标。
2）顺序遍历链表，equals()方法查找相同 Node 链表中 K 值对应的 V 值。
4.HashMap的扩容机制？
扩容时机：
HashMap使用的是懒加载，构造完HashMap对象后，只要不进行put 方法插入元素之前，HashMap并不会去初始化或者扩容table。
当首次调用put方法时，HashMap会发现table为空然后调用resize方法进行初始化，当添加完元素后，如果HashMap发现size（元素总数）大于threshold（阈值），则会调用resize方法进行扩容。
扩容过程：
若threshold（阈值）不为空，table的首次初始化大小为阈值，否则初始化为缺省值大小16，默认的负载因子大小为0.75，即扩容阈值为12。
当map填满了12个bucket时候，就会触发扩容，扩容后的table大小变为原来的两倍。
5.当两个key的 hashCode 相同会发生什么？
因为 hashCode 相同，所以两个key所在数组的下标相同，哈希冲突就此发生。
6.hash冲突带来的影响？
hash冲突一旦发生，那么就要将新的键值对追加到链表尾部。
hash冲突一旦严重，那么链表就会更长，或者让红黑树变得更加复杂。查询元素的时间成本就会上升。
7.那到底为啥会产生hash冲突啊？
1）HashMap容量太小。容量小，碰撞的概率就高了。
2）hashcode方法有问题，导致冲突概率高。
3）hash算法不够好。算法不合理也容易导致元素在hash桶中分配不均。
8.那你知道其他解决哈希冲突的方法吗？
线性探测法。ThreadLocal中的ThreadLocalMap解决Hash冲突的方式就并非链表的方式，而是采用线性探测法。
它的基本原理就是根据初始key的hashcode值确定元素在table数组中的位置，如果发现这个位置上已经有其他key值的元素被占用，则利用固定的算法寻找一定步长的下个位置，依次判断，直至找到能够存放的位置。
9.你知道HashMap的哈希函数怎么设计的吗？为什么这样设计？
hash函数是先拿到通过key 的hashcode，是32位的int值，然后让hashcode的高16位和低16位进行异或操作。
hash函数也叫扰动函数，这么设计有二点原因：
1）一定要尽可能降低hash碰撞，越分散越好；
2）算法一定要尽可能高效，因为这是高频操作, 因此采用位运算；
10.HashMap中bucket的下标是怎么计算的？
首先以key的hashcode为参数，通过hash函数，计算出一个hash 值，就是一个int 类型整数。然后将 table 的容量与 hash 值做“与
”运算，得到哈希 table 的 bucket 下标。
static final int hash(Object key) { int h; return (key == null) ? 0 : (h =
key.hashCode()) ^ (h >>> 16); }
11.hash函数不能直接用key的hashcode吗？
因为key.hashCode()函数调用的是key键值类型自带的哈希函数，返回int型散列值。int值范围大概为负21亿~正21亿之间。
以HashMap默认的初始16为例，定位数组下标，需要用之前需要对数组的长度取模运算，得到的余数才能用来访问数组下标。源码中模运算就是把散列值和数组长度-1做一个"与"操作，“与”操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问。
就算hashcode分布的再松散，要是只取最后几位的话，碰撞也会很严重。
所以不直接使用hashcode而是让hashcode的高16位和低16位进行异或操作，就是起一个扰动的作用，为了让更大程度的降低hash碰撞的概率。
12.你刚刚提到了红黑树，为啥要用红黑树？
为了避免链表过长导致的性能问题。
13.一直使用红黑树不行吗，为啥还要用链表？
红黑树查询快，插入慢。链表插入快，查询慢。
尽管转为树使得查找的速度更快，但是在节点数比较小的时候，二者查找的效率差距微乎其微，如果直接使用红黑树会占用更多的内存。
14.那为啥链表过长用红黑树，不用其它的AVL树呢？
红黑树和AVL树都是常用的平衡二叉搜索树，但AVL树比红黑树更为严格。
因为红黑树完成平衡所需要的的旋转次数比AVL树更少。所以它提供了比AVL树更快的插入和删除操作。
AVL树比Red Black Trees提供更快的查找，因为它们的平衡更为严格。
红黑树适合在大多数语言库中使用，而AVL树适合用于需要更快检索的数据库中。
15.你说说红黑树的特点？
1）每个节点非红即黑
2）根节点总是黑色的
3）如果节点是红色的，则它的子节点必须是黑色的（反之不一定）
4）每个叶子节点都是黑色的空节点（NIL节点）
5）从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）
16.你刚刚提到负载因子，那负载因子为啥选择0.75
负载因子的作用是为了设置一个合适的临界值用来让HashMap进行扩容，选择0.75作为负载因子是为了充分利用空间并且尽最大可能避免hash冲突。
负载因子如果选择1，则意味着HashMap满了才触发扩容，然而这样意味着能用小的容量存储更多的元素，但是容量小也意味着hash冲突的概率会更高（pis：hash算法会对Hash桶长度作取模运算来定位元素在hash桶的位置，hash桶长度一旦过短，那么取模后碰撞的概率就越高）。
负载因子如果选择0.5，虽然减少了Hash冲突的概率，但也容易造成空间上的浪费。
其次HashMap要求每次扩容后的容量是2的n次幂，如果选择0.75，那么每次扩容后新的容量*0.75永远都是个整数。
所以选择0.75是基于时间和空间上相互权衡的结果。
17.那HashMap默认初始容量为啥是16？
HashMap作为一种数据结构，元素在put的过程中需要进行hash运算，目的是计算出该元素存放在hashMap中的具体位置。
hash运算的过程其实就是以目标元素的Key的hashcode作参数进行hash运算得到一个整数，再对Map的容量进行取模，取模后的结果就是元素在hashMap数组里的位置。
而对Map容量取模的运算过程中，JDK的工程师为了提升取模效率，使用位运算代替了取模运算，这就要求Map的容量必须是2的n次方幂。
作为默认容量，太大和太小都不合适，所以16就作为一个比较合适的经验值被采用了。
18.HashMap如何保证容量始终是2的n次幂的？
为了保证任何情况下Map的容量都是2的n次幂，HashMap在两个地方都做了限制。
首先，创建HashMap时如果没有定制初始容量，则使用16作为初始容量。
其次，如果用户制定了初始容量，且初始容量恰好是2的n次幂，则使用这个容量。否则HashMap会计算出比该数大的第一个2的n次幂作为初始容量。
另外，在扩容的时候，通过2倍的形式进行扩容，保证了容量始终是2的n次幂。
19.HashMap是线程安全的吗？
不是，在多线程的情况下，1.7的HashMap会出现死循环、数据丢失，数据重复问题。在1.8不会出现链表死循环问题。
1）数据丢失(也叫数据覆盖)：
多线程插入两个hash值相同的key时，判断出哈希桶对应的位置为null， 那么两个线程都在同一时刻去创建entry，势必导致其中一个数据丢失。
2）数据重复：
如果有两个线程同时发现自己都key不存在，而这两个线程的key实际是相同的，在向链表中写入的时候第一线程将e设置为了自己的Entry，而第二个线程执行到了e.next，此时拿到的是最后一个节点，依然会将自己持有是数据插入到链表中，这样就出现了数据重复。
2）链表死循环：
HashMap扩容时，会将元素转移到新的哈希桶里面，其次会采用头插法将原始的链表结点放到新的链表里面，所以会对链表做一次翻转处理，如果多个线程对这个链表做翻转处理就容易导致循环链表的产生。
20.为啥扩容时会翻转链表？
因为HashMap默认采用链表头插入解决hash冲突，hashmap扩容时会从头遍历链表节点，然后插入到新的链表中，由于遍历时是从头开始遍历，而插入时是从头插入，所以会翻转链表。
21.那如果要实现线程安全，怎么办？
可以使用Hashtable,Collections.synchronizedMap,ConcurrentHashMap。
22.jdk7的HashMap为什么采用头插法？
HashMap的开发者认为后面被插入的对象，被查找的可能性更大，而链表查找元素从头遍历，所以采用头插法往往能够提升查找效率。
23.jdk8相比之前的版本，解决了HashMap哪些线程安全问题？
jdk8的HashMap在处理hash冲突时，采用尾插法代替头插法，扩容时避免了翻转链表的发生，也就是解决了循环链表的问题。
24.HashMap是如何处理K为null的？
1）HashMap 中，是允许 key、value 都为 null 的，且 key 为 null 只存一份，多次存储会将旧 value 值覆盖。
2）key 为 null 的存储位置，都统一放在下标为0的 bucket，即：table[0]位置的链表。
25.链表转化为红黑树的阈值为啥是8呢？
如果
hashCode的分布离散良好的话，那么红黑树是很少会被用到的，因为各个值都均匀分布，很少出现链表很长的情况。在理想情况下，链表长度符合泊松分布，各个长度的命中概率依次递减，当长度为8的时候，概率概率仅为十万分之6，这么小的概率，HashMap的红黑树转换几乎不会发生。
26.红黑树什么时候退化为链表?
为6的时候退转为链表。中间有个差值7可以防止链表和树之间频繁的转换。假设一下，如果设计成链表个数超过8则链表转换成树结构，链表个数小于8则树结构转换成链表，如果一个HashMap不停的插入、删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低。
27.你一般用什么作为HashMap的key?
一般用Integer、String这种不可变类当HashMap当key，而且String最为常用。
因为字符串是不可变的，所以在它创建的时候hashcode就被缓存了，不需要重新计算。这就使得字符串很适合作为Map中的键，字符串的处理速度要快过其它的键对象。这就是HashMap中的键往往都使用字符串。
因为获取对象的时候要用到equals()和hashCode()方法，那么键对象正确的重写这两个方法是非常重要的,这些类已经很规范的覆写了hashCode()以及equals()方法。
28.如果让你实现一个自定义的class作为HashMap的key该如何实现？
重写hashcode和equals方法
29.那重写hashcode和equals要注意啥？
1）两个对象相等，hashcode一定相等
2）两个对象不等，hashcode不一定不等
3）hashcode相等，两个对象不一定相等
4）hashcode不等，两个对象一定不等
30.除了链表尾插和红黑树，HashMap在jdk1.8和jdk1.7还有哪些差异？
1）JDK1.7是先扩容后插入，jdk1.8是先插入后扩容。
2）JDK1.7扩容需要重新hash来定位每个元素在桶中的位置，jdk1.8不需要。
31.为什么1.8不用重新hash就能定位新数据的位置呢?
因为1.8中HashMap每次扩容都是2的倍数，计算位置的时候是和数组的长度-1做与操作，那么影响位置的数据只有最高的一位。
如果最高位是0，那么rehash之后还是在原来的位置index；如果是1，那么rehash之后的位置是原来的位置 + 扩容前的数组容量，即index +
oldCap。
所以扩容之后，存在两种情况，一种情况下，key的位置不变，另外一种情况，key的位置往后移动了原先数组长度的位置。
这种方案明显要比把一个个的key重新寻址要快，效率要高，这就是HashMap在JDK1.8中的rehash算法优化。
32.如果我创建一个HashMap，构造器传入1000，那HashMap的实际初始容量是多少？
实际初始容量是1024，因为1000并不是2的n次幂，HashMap会自动计算出一个比1000大但是满足2的n次幂的值作为实际初始容量。