HashMap略解

Java面试突击
1.HashMap略解

日常工作开发中，我们经常会使用HashMap这种数据结构，进行一定的逻辑处理，很多时候我们只是会使用，而不知其所以然

用一个示例来说明：
我们创建一个一个map集合

HashMap map = new HashMap(); 
map.put("Hash1","Map1");
map.put("Hash2","Map2");

实际上的底层存储逻辑类似下面这样：

[<>,<>,,,......]

所以我们可以看到，HashMap的底层数据结构是数组。

但是当我们对某一元素进行取模时，可能会存在两个不同的Key返回相同的hashCode，此时，会将这个数据放在数组的同一位置处，这将会使其变为一个链表结构的数据。

链接：https://www.pdai.tech/md/interview/x-interview.html

哈希表有两种实现方式，一种开放地址方式(Open addressing)，另一种是冲突链表方式(Separate chaining with linked lists)。Java7 HashMap采用的是冲突链表方式。

根据 Java7 HashMap 的介绍，我们知道，查找的时候，根据 hash 值我们能够快速定位到数组的具体下标，但是之后的话，需要顺着链表一个个比较下去才能找到我们需要的，时间复杂度取决于链表的长度，为 O(n)。 为了降低这部分的开销，在 Java8 中，当链表中的元素达到了 8 个时，会将链表转换为红黑树，在这些位置进行查找的时候可以降低时间复杂度为 O(logN)。

简而言之：1.7基于哈希表实现，1.8基于数组+链表+红黑树。

结合HashMap底层数据结构，当这个数组满了之后，他就会自动进行扩容，编程一个更大的数组，一般来说是进行2倍扩容。
在扩容时，对原有数据会进行rehash,对所有的数组数据重新判断二进制结果是否多出一个bit的1，如果没有，那么就是原来的index，如果多了出来，那么就是index+oldCap，并不是粗鲁的在原来的数组后面继续添加1倍的长度。

本文仅仅简单介绍了HashMap的一般考察点，至于详细的rehash，请查阅官方资料。