为什么用HashMap

  • HashMap是一个散列桶（数组和链表），它存储的内容是键值对(key-value)映射
  • HashMap采用了数组和链表的数据结构，能在查询和修改方便继承了数组的线性查找和链表的寻址修改
  • HashMap是非synchronized，所以HashMap很快
  • HashMap可以接受null键和值，而Hashtable则不能（原因就是equlas()方法需要对象，因为HashMap是后出的API经过处理才可以）

HashMap 底层原理

HashMap 实现 Map 接口，非线程安全的，区别于 ConcurrentHashMap。允许使用 null 值和 null 键, 不保证映射的顺序. 底层数据结构是一个 “数组 + 链表 + 红黑树 “
put():

  1. 根据 key 计算得到 key.hash = (h = k.hashCode()) ^ (h >>> 16)；
  2. 根据 key.hash 计算得到桶数组的索引 index = key.hash & (table.length - 1)，这样就找到该 key 的存放位置了：
    ① 如果该位置没有数据，用该数据新生成一个节点保存新数据，返回 null；
    ② 如果该位置有数据是一个红黑树，那么执行相应的插入 / 更新操作
    ③ 如果该位置有数据是一个链表，分两种情况一是该链表没有这个节点，另一个是该链表上有这个节点，注意这里判断的依据是 key.hash 是否一样： 如果该链表没有这个节点，那么采用尾插法新增节点保存新数据，返回 null； 如果该链表已经有这个节点了，那么找到該节点并更新新数据，返回老数据。
    3. 更新 size 和阈值
    扩容机制
    扩容时机：
    1）当链表长度大于 8 的时候并且数组的长度小于 64 时优先进行扩容
    2） 当元素个数大于阈值时，进行扩容。
    怎么扩容：
    调用 resize（）方法方法，
    1. 首先进行异常情况的判断，如是否需要初始化，二是若当前容量 > 最大值则不扩容，
    2. 然后根据新容量（是就容量的 2 倍、）新建数组，将旧数组上的数据（键值对）转移到新的数组中，这里包括：（遍历旧数组的每个元素，重新计算每个数据在数组中的存放位置。（原位置或者原位置 + 旧容量），将旧数组上的每个数据逐个转移到新数组中，这里采用的是尾插法。）
    3. 新数组 table 引用到 HashMap 的 table 属性上
    4. 最后重新设置扩容阙值，此时哈希表 table = 扩容后（2 倍）& 转移了旧数据的新 table

Hashmap是不是有序的

就比如问你HashMap是不是有序的？

你回答不是有序的。那面试官就会可能继续问你，有没有有序的Map实现类呢？

你如果这个时候说不知道的话，那这块问题就到此结束了。如果你说有TreeMap和LinkedHashMap。

那么面试官接下来就可能会问你，TreeMap和LinkedHashMap是如何保证它的顺序的？

如果你回答不上来，那么到此为止。如果你说TreeMap是通过实现SortMap接口，能够把它保存的键值对根据key排序，基于红黑树，从而保证TreeMap中所有键值对处于有序状态。LinkedHashMap则是通过插入排序（就是你put的时候的顺序是什么，取出来的时候就是什么样子）和访问排序（改变排序把访问过的放到底部）让键值有序。

那么面试官还会继续问你，你觉得它们两个哪个的有序实现比较好？

HashMap 与 HashTable 有什么区别？

  1. 线程安全： HashMap 是非线程安全的，HashTable 是线程安全的；HashTable 内部的方法基本都经过 synchronized 修饰。（如果你要保证线程安全的话就使用 ConcurrentHashMap 吧！）；
  2. 效率： 因为线程安全的问题，HashMap 要比 HashTable 效率高一点。另外，HashTable 基本被淘汰，不要在代码中使用它；
  3. 对Null key 和Null value的支持： HashMap 中，null 可以作为键，这样的键只有一个，可以有一个或多个键所对应的值为 null。但是在 HashTable 中 put 进的键值只要有一个 null，直接抛NullPointerException。
  4. 初始容量大小和每次扩充容量大小的不同 ： ①创建时如果不指定容量初始值，Hashtable 默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。HashMap 默认的初始化大小为16。之后每次扩充，容量变为原来的2倍。②创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为2的幂次方大小。也就是说 HashMap 总是使用2的幂作为哈希表的大小，后面会介绍到为什么是2的幂次方。
  5. 底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。

  6. 推荐使用：在 Hashtable 的类注释可以看到，Hashtable 是保留类不建议使用，推荐在单线程环境下使用 HashMap 替代，如果需要多线程使用则用 ConcurrentHashMap 替代。

    HashMap 和 ConcurrentHashMap 的区别

  7. ConcurrentHashMap对整个桶数组进行了分割分段(Segment)，然后在每一个分段上都用lock锁进行保护，相对于HashTable的synchronized锁的粒度更精细了一些，并发性能更好，而HashMap没有锁机制，不是线程安全的。（JDK1.8之后ConcurrentHashMap启用了一种全新的方式实现,利用CAS算法。）

  8. HashMap的键值对允许有null，但是ConCurrentHashMap都不允许。

HashMap、TreeMap、LinkedHashMap 三者有啥相同点，有啥不同点

答：相同点：
1. 三者在特定的情况下，都会使用红黑树；
2. 底层的 hash 算法相同；
3. 在迭代的过程中，如果 Map 的数据结构被改动，都会报
ConcurrentModificationException 的错误。

不同点：
1. HashMap 数据结构以数组为主，查询非常快，TreeMap 数据结构以红黑树为主，利用了红
黑树左小右大的特点，可以实现 key 的排序，LinkedHashMap 在 HashMap 的基础上增加
了链表的结构，实现了插入顺序访问和最少访问删除两种策略;
2. 由于三种 Map 底层数据结构的差别，导致了三者的使用场景的不同，TreeMap 适合需要根
据 key 进行排序的场景，LinkedHashMap 适合按照插入顺序访问，或需要删除最少访问元
素的场景，剩余场景我们使用 HashMap 即可，我们工作中大部分场景基本都在使用
HashMap；
3. 由于三种 map 的底层数据结构的不同，导致上层包装的 api 略有差别。

为什么HashMap中String、Integer这样的包装类适合作为K？

答：String、Integer等包装类的特性能够保证Hash值的不可更改性和计算准确性，能够有效的减少Hash碰撞的几率

  1. 都是final类型，即不可变性，保证key的不可更改性，不会存在获取hash值不同的情况
  2. 内部已重写了equals()、hashCode()等方法，遵守了HashMap内部的规范（不清楚可以去上面看看putValue的过程），不容易出现Hash值计算错误的情况；

能否使用任何类作为 Map 的 key？

可以使用任何类作为 Map 的 key，然而在使用之前，需要考虑以下几点：

  • 如果类重写了 equals() 方法，也应该重写 hashCode() 方法。
  • 类的所有实例需要遵循与 equals() 和 hashCode() 相关的规则。
  • 如果一个类没有使用 equals()，不应该在 hashCode() 中使用它。
  • 用户自定义 Key 类最佳实践是使之为不可变的，这样 hashCode() 值可以被缓存起来，拥有更好的性能。不可变的类也可以确保 hashCode() 和 equals() 在未来不会改变，这样就会解决与可变相关的问题了。

如果使用Object作为HashMap的Key，应该怎么办呢？

答：重写hashCode()和equals()方法

  1. 重写**hashCode()**是因为需要计算存储数据的存储位置，需要注意不要试图从散列码计算中排除掉一个对象的关键部分来提高性能，这样虽然能更快但可能会导致更多的Hash碰撞；
  2. 重写**equals()**方法，需要遵守自反性、对称性、传递性、一致性以及对于任何非null的引用值x，x.equals(null)必须返回false的这几个特性，目的是为了保证key在哈希表中的唯一性；

如何决定使用 HashMap 还是 TreeMap？

对于在Map中插入、删除和定位元素这类操作，HashMap是最好的选择。然而，假如你需要对一个有序的key集合进行遍历，TreeMap是更好的选择。基于你的collection的大小，也许向HashMap中添加元素会更快，将map换为TreeMap进行有序key的遍历。

散列表是New HashMap()的时候创建的，还是什么时候创建的？

散列表是懒加载机制，只有在第一次put数据的时候才创建（JDK1.8，JDK1.7是直接加载散列表）

为啥我们重写equals方法的时候需要重写hashCode方法呢？

因为在java中，所有的对象都是继承于Object类。Ojbect类中有两个方法equals、hashCode，这两个方法都是用来比较两个对象是否相等的。
在未重写equals方法我们是继承了object的equals方法，那里的 equals是比较两个对象的内存地址，显然我们new了2个对象内存地址肯定不一样
比如发生Hash冲突的时候，我们去get，他就是根据key去hash然后计算出index，找到了2，那我怎么找到具体的”电脑“还是”脑电“呢？
equals！是的，所以如果我们对equals方法进行了重写，建议一定要对hashCode方法重写，以保证相同的对象返回相同的hash值，不同的对象返回不同的hash值。

另外一个版本

因为在java中，所有的对象都是继承于Object类。Ojbect类中有两个方法equals、hashCode，这两个方法都是用来比较两个对象是否相等的。

在未重写equals方法我们是继承了object的equals方法，那里的 equals是比较两个对象的内存地址，显然我们new了2个对象内存地址肯定不一样

  • 对于值对象，==比较的是两个对象的值
  • 对于引用对象，比较的是两个对象的地址

大家是否还记得我说的HashMap是通过key的hashCode去寻找index的，那index一样就形成链表了，也就是说”帅丙“和”丙帅“的index都可能是2，在一个链表上的。

我们去get的时候，他就是根据key去hash然后计算出index，找到了2，那我怎么找到具体的”帅丙“还是”丙帅“呢？

equals！是的，所以如果我们对equals方法进行了重写，建议一定要对hashCode方法重写，以保证相同的对象返回相同的hash值，不同的对象返回不同的hash值。

不然一个链表的对象，你哪里知道你要找的是哪个，到时候发现hashCode都一样，这不是完犊子嘛。

1.8还采用了红黑树，讲讲红黑树的特性，为什么人家一定要用红黑树而不是AVL、B树之类的？

之所以选择红黑树是为了解决二叉查找树的缺陷，二叉查找树在特殊情况下会变成一条线性结构（这就跟原来使用链表结构一样了，造成很深的问题），遍历查找会非常慢。

而红黑树在插入新数据后可能需要通过左旋，右旋、变色这些操作来保持平衡，引入红黑树就是为了查找数据快，解决链表查询深度的问题，我们知道红黑树属于平衡二叉树，但是为了保持“平衡”是需要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少，所以当长度大于8的时候，会使用红黑树，如果链表长度很短的话，根本不需要引入红黑树，引入反而会慢。

https://www.yuque.com/docs/share/2bbf43ac-0592-46dc-9e3e-9bd220248e30?# 《红黑树的特性》

拉链法导致的链表过深问题为什么不用二叉查找树代替，而选择红黑树？为什么不一直使用红黑树

之所以选择红黑树是为了解决二叉查找树的缺陷，二叉查找树在特殊情况下会变成一条线性结构（这就跟原来使用链表结构一样了，造成很深的问题），遍历查找会非常慢

而红黑树在插入新数据后可能需要通过左旋，右旋、变色这些操作来保持平衡，引入红黑树就是为了查找数据快，解决链表查询深度的问题，我们知道红黑树属于平衡二叉树，但是为了保持 “平衡” 是需要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少，所以当长度大于 8 的时候，会使用红黑树，如果链表长度很短的话，根本不需要引入红黑树，引入反而会慢。

说说你对红黑树的见解

· 每个节点非红即黑
· 根节点总是黑色的
· 如果节点是红色的，则它的子节点必须是黑色的（反之不一定）
· 每个叶子节点都是黑色的空节点（NIL 节点）
从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）

当两个对象的 hashCode 相同会发生什么

因为 hashCode 相同，不一定就是相等的（equals 方法比较），所以两个对象所在数组的下标相同，”碰撞” 就此发生。又因为 HashMap 使用链表存储对象，这个 Node 会存储到链表中。

HashMap 在 put 时，如果数组中已经有了这个 key，我不想把 value 覆盖怎么办？取值时，如果得到的 value 是空时，想返回默认值怎么办？

答：如果数组有了 key，但不想覆盖 value ，可以选择 putIfAbsent 方法，这个方法有个内置变 量 onlyIfAbsent ， 内 置 是 true ， 就 不 会 覆 盖 ， 我 们 平 时 使 用 的 put 方 法 ， 内 置onlyIfAbsent 为 false，是允许覆盖的。
取值时，如果为空，想返回默认值，可以使用 getOrDefault 方法，方法第一参数为 key，第二个参数为你想返回的默认值，如 map.getOrDefault(“2”,“0”)，当 map 中没有 key 为 2的值时，会默认返回 0，而不是空。

通过以下代码进行删除，是否可行？

HashMap map = Maps.newHashMap();
map.put(“1”,”1”);
map.put(“2”,”2”);
map.forEach((s, s2) -> map.remove(“1”));

答：不行，会报错误 ConcurrentModificationException，原因如下图：
image.png