1.HashMap

简介

• HashMap是开发过程汇总最常用的集合之一。使用与存储key-value键值对的集合， 每一个键值对也叫做Entry,这些Entry分散的存储在一个数组中 这个数组就是HashMap的主干。

• HashMap每一个元素的初始值都是null

API

• Put方法

当调用HashMap.put(“a1” , 0)，的时候， java通过一个hash函数来确定这个Entry需要插入的位置 index.

index = hahs(“a1”)

但是，因为hashmap的长度是有限的， 当插入更多的Entry的时候， index会出现冲突， HashMap的解决方法的是使用 链表 的方式来解决，每一个entry通过next指针指向它的下一个Entry下一个节点。HashMap的作者认为， 后插入的元素， 被查找的可能性要大于先插入的元素， 所以， HashMap使用的头插入的方式实现链表。

• GET方法

HashMap对key进行hash计算

index = hash(“a1”);

由于hash的冲突。 同一个位置，会出现多个Entry， 这个时候， 就会顺着链表的头节点， 一个一个向下查找

HashMap中的hash算法

HashMap是如何均匀分布hash函数的呢？

HashMap通过位运算的方式实现。

index = HashCode( key ) & (length - 1);

HashMap的默认长度使16；每次扩容的长度是2的幂次方

下面我们以值为“book”的Key来演示整个过程：

1.计算book的hashcode，结果为十进制的3029737，二进制的101110001110101110 1001。

2.假定HashMap长度是默认的16，计算Length-1的结果为十进制的15，二进制的1111。

3.把以上两个结果做与运算，101110001110101110 1001 & 1111 = 1001，十进制是9，所以 index=9。

可以说，Hash算法最终得到的index结果，完全取决于Key的Hashcode值的最后几位。

那么为什HashMap默认长度是16呢

假如HashMap的默认长度是10的话：

单独看这个结果，表面上并没有问题。我们再来尝试一个新的HashCode 101110001110101110 1011 ：

让我们再换一个HashCode 101110001110101110 1111 试试 ：

是的，虽然HashCode的倒数第二第三位从0变成了1，但是运算的结果都是1001。也就是说，当HashMap长度为10的时候，有些index结果的出现几率会更大，而有些index结果永远不会出现（比如0111）！

这样，显然不符合Hash算法均匀分布的原则。

反观长度16或者其他2的幂，Length-1的值是所有二进制位全为1，这种情况下，index的结果等同于HashCode后几位的值。只要输入的HashCode本身分布均匀，Hash算法的结果就是均匀的。