转载

HashMap基础及相关面试题

HashMap的实现采用了除留余数法形式的哈希函数和链地址法解决哈希地址冲突的方案。
这样就涉及到两种基本的数据结构：数组和链表。数组的索引就是对应的哈希地址，存放的是链表的头结
点，链表存放的是哈希地址冲突的不同记录。
当链表中的节点个数超过阈值8时会转化为红黑树以提高查询效率。
复制代码

2.HashMap原理

HashMap通过key的hashcode经hash()处理得到hash值，然后通过 (n - 1) & hash 判断当前元素存放的
位置（这里的 n 指的是数组的 长度），进而存储和获取对象。
复制代码

3.HashMap的工作原理

a.存储对象：put(k,v)
  1.对key的hashcode进行hash()操作得到hash值，然后用 (n - 1) & hash计算bucket中的index索引值，
  2.若k的hash值在bucket中不存在，直接放在bucket里面，
  3.若存在，发生碰撞：
    i.若两者equal返回true，说明节点已经存在了，就更新键值对；
    ii.若两者equal返回false,插入链表尾部或红黑树中,
  4.如果增加后的个数大于阈值（loadfactor*current capacity，load factor默认0.75），
  就要resize扩容。
  
b.获取对象：get(k)
  1.对key的hashcode进行hash()操作得到hash值，然后用 (n - 1) & hash计算bucket中的index索引值，
  2.若发生碰撞，用k.equal()方法去链表中查找相应节点，返回v值。
复制代码

相关面试题

1.HashMap中hash函数怎么是是实现的？为什么要这样实现？

JDK1.8中，通过hashcode()的高16位异或低16位实现的(h = k.hashCode()) ^ (h >>> 16)，
主要是为了减少系统的开销，也不会造成因为高位没有参与下标的计算而导致的碰撞。

--为什么要使用异或？
-保证了对象的 hashCode 的 32 位值只要有一位发生改变，整个 hash()返回值就会改变。
尽可能的减少碰撞。
复制代码

2.HashMap如何解决冲突？

3.为什么 HashMap 中 String、Integer 这样的包装类适合作为 key 键？

1.由于这些包装类都是final类型，具有不可变性，
保证了key的不可更改性，不会出现放入和获取时哈希值不同的情况。
2.因为它们的内部已重写了hashcode(),equal()方法，不容易出现hash值的计算错误，
有效减少了发生hash碰撞的几率。
复制代码

4.Jdk1.8中满足什么条件后将链表转化成红黑树？又什么时候转回来？

1.先判断该链表内节点个数是否大于等于8，再判断总节点数是否大于64（最小红黑树容量），
若小于继续扩容，大于就转成红黑树。
2.当节点个数小于等于6时就会转回链表。
3.这样做是为了中间有个7可以防止链表和数频繁转换。
复制代码

5.为什么会引入红黑树做查询优化呢？

当key为自定义的对象时，可能会采用了不好的hash算法，导致HashMap中key的冲突率极高，
但为了保证HashMap高效的查询效率，引入了红黑树来优化查询。
复制代码

6.为什么把8作为阈值？ *

一般情况下用不着红黑数，因为树节点所占空间是普通节点的两倍，只有在节点
太多，红黑树占空间大这一劣势不太明显的时候，才会舍弃链表，使用红黑树。
由于链表中的节点遵循泊松分布，根据统计，链表中节点数是8的概率已经接近千分之一，这时哈希表的容量很大，造成链表的性能很差的情况下，才会使用红黑树，来提高性能。
通过概率统计所得，这个值是综合查询成本和新增元素成本得出的最好的一个值。
复制代码

详情： JDK1.8以后的hashmap为什么在链表长度为8的时候变为红黑树

7.HashMap的长度为什么是2的倍数？

由于 hash%n 当n为2的倍数时，就可以将%n转化为&(n-1)以提高效率了。
复制代码

8.HashMap 和 Hashtable 的区别

1.线程是否安全：HashMap不安全，HashTable线程安全，因为它经过synchronized 修饰
2.效率：HashMap效率高些。
3.对Null key和Null value是否支持：
    HashMap支持Null key（最多只有一个），可以有多个Null value。HashTable不支持Null。
4.初始容量大小和每次扩容大小：
    HashMap默认初始容量为16，每次扩容到原来的2倍，而HashTable初始容量为11，扩充为原来的2n+1。
    另外，若给定了初始容量，HashTable会直接用，而HashMap会先扩成2的幂次方大小。
5.底层数据结构：
    HashTable还是数组+链表，HashMap增加了红黑树。
复制代码

9.HashMap在1.7/1.8的变化

Hash1.7 和1.8 最大的不同在于1.8 采用了“数组+链表+红黑树”的数据结构，在链表长度超过8时，把链
表转化成红黑树来解决HashMap 因链表变长而查询变慢的问题；
其次在hash 取下标时将1.7 的9次扰动（5次按位与和4次位运算）改为2次（一次按位与和一次位运算）
1.7 的底层节点为Entry，1.8 为node ，但是本质一样，都是Map.Entry 的实现；
还有就是在存取数据时添加了关于树结构的遍历更新与添加操作，并采用了尾插法来避免环形链表的产生。
复制代码

原文 https://juejin.im/post/5e70398a518825493f6d0121

正文到此结束