【Java】HashMap相关知识
1 HashMap特点
- HashMap是一个散列表（数组+链表），它存储的内容是键值对（key-value）；
- HashMap继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口;
- HashMap 的实现不是同步的，这意味着它不是线程安全的。它的key、value都可以为null。此外，HashMap中的映射不是有序的。
2 HashMap原理
2.1 基本原理
HashMap是一个散列表，是一个数组和链表的结合体。首先会声明一个下标范围比较大的数组来存储元素，数组存储的元素是一个Entry类，这个类包括三个数据域：key(键)，value(值)以及next(指向下一个Entry)。例如有一个键值对A进来，通过计算其key的hashcode得到下标为0，则该A键值对被封装到Entry对象里后会存入到下标为0的数组中；第二个键值对B进来，通过计算其key的hashcode得到的下标还是0，则B键值对也会被封装到Entry对象中然后存入数组下标为0的地方，不过之前存了一个A，所以此时将采用链表形式，而且是采用头插法，即Entry(B).next=Entry(A).
hashMap结构示意图如下：
图2.1 hashMap结构示意图
3 hashMap相关问答
- 问：为什么要用hashMap
（1） hashMap可以接受null键值和值；
（2）HashMap底层是用数组加链表的结构存储数据的，存储和查找都很快；
（3）因为hashMap是非Synchronized的，所以hashMap很快；
（4）hashMap是以键值对的方式存储数据的，操作方便。
- 问：你知道HashMap的工作原理么？
HashMap使用put(key，value)的方式将值存储到HashMap中，使用get(key)从HashMap中获取对象。当我们使用put(key，value)时，首先会对key调用hashcode方法，通过返回的hashcode值进行hash计算找到bucket位置来存储Entry对象。当两个对象的hashcode值一致，则可能发生碰撞，这时，需要通过equals()方法来对这两个key对象的进行比较，如果相等，则覆盖；如果不相等，则再bucket这个位置以链表（LinkedList）形式存储，而且这里采用的是头插法。当使用get（key）方法获取对象时，首先会对key值进行hashcode计算，通过得到的hashcode值来定位bucket位置，然后通过equals方法比较key，如果相等则取出该key对应的值。
put方法和get方法中比较key如下：
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
...
}
- 问：如果hashMap的大小超过了负载因子定义的容量怎么办？
简便回答：HashMap默认的负载因子为0.75，即如果HashMap容量超过原来定义的容量的75%，则HashMap将自动扩充约为原来的两倍大小。
详细回答：HashMap在初始化对象时，用户可以指定一个容量大小和一个负载因子，如果用户没有指定容量大小和负载因子，则系统会默认容量大小为16，负载因子为0.75。此时还会设置一个阈值，即当HashMap存储的数量达到这个阈值时，HashMap就需要扩容。阈值计算方法是：容量*负载因子，即默认情况下，存储的数据达到HashMap容量的75%时，就会创建原来HashMap大小的两倍的bucket数组。
- 问：HashMap中hash函数是怎么实现的？
将hashcode的值的高16位与hashcode值进行异或，得到的值再与（n-1）进行与运算：（n-1）&(h^(h>>>16))
图3.1 hash函数实现图解
- 问：HashMap中如何减少碰撞发生？
- 扰动函数，促使元素位置分布均匀，减少碰撞几率。扰动函数：（n-1）&(h^(h>>>16))。
- 使用final对象，并且采用合适的equals()和hashCode()方法，可以减少碰撞的发生，提高效率。
- 问：拉链法导致的链表过深问题为什么不用二叉查找树代替，而选择红黑树？为什么不一直用红黑树？
之所以选择红黑树是为了解决二叉查找树的缺陷，二叉查找树在特殊情况下会变成一条线性结构，会造成层次过深，遍历查找会非常慢。而红黑树通过左旋、右旋及变色等操作来保持平衡，引入红黑树就是为了查找数据快，解决层次过深问题。但红黑树为保持平衡，是需要付出代价的，所以只有当链表长度大于8时才使用红黑树，如果链表长度较短，使用红黑树反而会使效率降低。
- 问：你对红黑树的见解？（红黑树的特性？）
- 红黑树的节点都是黑色或者红色
- 根节点一定是黑色
- 叶子节点NIL一定是黑色
- 从任一节点出发到它所有的叶子节点的路径上，其黑色节点都相同
- 红色节点的两个子节点都为黑色
