HashMap集合

HashMap基于哈希表的Map接口实现，是以key-value存储形式存在，主要用于存放键对值。HashMap的实现是不同步的，这就意味着不是线程安全的。

JDK1.8之前的HashMap由数组加链表组成，数组是HashMap的主题，链表则是用来解决哈希冲突（两个对象调用的hashCode方法计算的哈希码值一致导致计算的数组索引值相同）而存在的冲突。

JDK1.8之后当同一个索引位置的节点在新增后达到9个（阈值8）：如果此时数组长度大于等于64，则会触发链表节点转红黑树节点；而如果数组长度小于64，则不会触发链表转红黑树，而是会进行扩容，因为此时的数据量还比较小。

特点：

存取无序的

键和值位置都可以是null，但是键位置只能是一个null

键位置是唯一的，底层数据结构控制键

JDK1.8之前数据结构是：链表+数组；JDK1.8之后链表+数组+红黑树

JDK1.8之后当同一个索引位置的节点在新增后达到9个（阈值8）：如果此时数组长度大于等于64，则会触发链表节点转红黑树节点

//创建HashMap集合对象
        HashMap hm = new HashMap<>();
        hm.put("柳岩", 18);
        hm.put("杨幂", 28);
        hm.put("刘德华", 40);
        hm.put("柳岩", 20);

1.HashMap hm = new HashMap<>();

当创建HashMap集合对象的时候，在jdk8前，构造方法中创建一个- 一个长度是16的EntryI table用来存储键值对数据的。在jdk8以后不是在HashMap的构造方法底层创建数组了，是在第一次调用put方法时创建的数组，Node[] table用来存储键值对数据的。

2.假设向哈希表中存储柳岩- 18数据,根据柳岩调用String类中重写之后的hashCode0方法计算出值,然后结合数组长度采用某种算法计算出向Node数组中存储数据的空间的索引值。如果计算出的索引空间没有数据,则直接将柳岩18存储到数组中。举例: i算出的索引是3

面试题:哈希表底层采用何种算法计算hash值?还有哪些算法可以计算出hash值?

底层采用的key的hashCode方法的值结合数组长度进行无符号右移(>>>)。按位异或(^)。按位与(&)计算出索引。还可以采用：平方取中法，取余数，伪随机数法。10%8--2  11%8---》3其他计算方式相率比较低，而位运算效率要高。

3.向哈希表中存储数据刘德华40.假设刘德华计算出的hashCode方法结合数组长度计算出的索引值也是3.那么此时数组空间不是null,此时底层会比较柳岩和刘德华的hash值是否-致，如果不-致, 则在此空间上划出一个节点来存储键值对数据.40这种方式称为拉链法。

4.假设向哈希表中存储数据柳岩20,那么首先根据柳岩调用hashCode方法结合数组长度计算出索引肯定3。此时比较后存储的数据柳岩和已经存在的数据的hash值是否相等，如果hash值相等， 此时发生哈希碰撞。那么底层会调用柳岩所属类String中的equals方法比较两个内容是否相等：

相等：则将后添加的数据的value覆盖之前的value

不相等：那么继续向下和其他的数据的key进行比较,如果都不相等,则划出一个节点存储数据

如果节点长度即链表长度大于阈值8井且数组长度大于64则进行将链表变为红黑树

1.面试题：当两个对象的hashCode相等时会怎么样？

会产生哈希碰撞，若key值内容相同则替换旧的value，不然连接到链表后面，链表长度超过阈值8就转换为红黑树存储

2.面试题：何时发生哈希碰撞和什么是哈希碰撞？如何解决哈希碰撞

只要两个元素的key计算的哈希值相同就会发生哈希碰撞，jdk8前使用链表解决哈希碰撞。jdk8之后使用链表+红黑树

3.面试题：如果两个键的hashcode相同，如何存储键对值？

hashcode相同，通过equals比较内容是否相同

相同：则新的value覆盖之前的value

不相同：则将新的键值对添加到哈希表中

4.在不断的添加数据的过程中，会社驾到扩容的问题，当超出临界值（且要存放的位置非空），扩容，默认的扩容方式：扩容为原来容量的2倍，并将原来的数据复制过来。

5.通过上述描述，当位于一个链表中的元素较多，即hash值相等但是内容下相等的元素较多的、时，通过key值以此查找的效率较低。而JDK1.8中，哈希表存储采用数组+链表+红黑树实现，当链表长度超过8是且当前数组的长度>64时，将链表转换为红黑树，这样大大减少了查找时间。jdk8在哈希表中引入红黑树的原因只是为了查找效率更高。
JDK1.8之后链表+数组+红黑树

 6.为什么链表转红黑树的阈值是8？

平时在进行方案设计时，必须考虑的两个很重要的因素是：时间和空间。对于 HashMap也是同样的道理，简单来说，阈值为8是在时间和空间上权衡的结果。
红黑树节点大小约为链表节点的2倍，在节点太少时，红黑树的查找性能优势并不明显，付出2倍空间的代价作者觉得不值得。
理想情况下，使用随机的哈希码，节点分布在 hash 桶中的频率遵循泊松分布，按照泊松分布的公式计算，链表中节点个数为8时的概率为0.00000006，这个概率足够低了，并且到8个节点时，红黑树的性能优势也会开始展现出来，因此8是一个较合理的数字。

继承关系如图所示：

说明：

Cloneable空接口，表示可以克隆，创建并返回HashMap对象的一个副本

Serializable序列化接口。属于标记性接口。HashMap对象可以被序列化和反序列化

AbstractMap父类提供了Map实现接口。以最大限度的实现此接口所需的工作

HashMap构造一个带指定出事容量和默认加载因子的空HashMap

为什么必须是2的n次幂

当向HashMap添加一个元素的时候，需要根据key的hash值，去确定其在数组中的具体位置。HashMap为了存取高效，要尽量减少碰撞，就是尽量把数据分配均匀，每个链表长度大致相同，这个实现就在把数据存在那个链表中的算法，算法实际上就是取模。计算机中直接求余效率不如位移运算，所以源码中做了优化，使用hash&(length-1),而实际上hash%(length-1)的前提是length是2的n次幂

 如果输入值不是2的幂会怎样？

static final int tableSizeFor(int cap) {
    int n = cap - 1;  //首先-1，防止cap本身就是2的N次方
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;  //不断的进行无符号右移操作，将低位全变为1，最后在+1，称为2的N次方
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

3.默认的负载因子，默认值是0.75

final float loadFactor;

loadFaxtor加载因子，是用来衡量HashMap满的程度，表示HashMap的枢密程度，影响hash操作到同意数组位置的概率，计算HashMap的实时加载因子的方法为：size/capacity size为元素个数。loadFactor太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会分散。loadFactor的默认值为0.75是官方给出的一个比较好的临界值。

这个也是在时间和空间上权衡的结果。如果值较高，例如1，此时会减少空间开销，但是 hash冲突的概率会增大，增加查找成本；而如果值较低，例如 0.5 ，此时 hash冲突会降低，但是有一半的空间会被浪费，所以折衷考虑 0.75 似乎是一个合理的值。达到0.75 进行扩容