环境：在AndroidStudio中查看Android-28中的HashMap源码

属性：Node[]table、threshold、loadFactor

在构造函数中可以看到下面的方法，是为了保证HashMap中的大小是2的幂数

图1

在图1中，分别对n左移并取或，是为了让n的二进制1最先出现的地方不断左移，最终实现n的二进制1最先出现的地方随后全是1，返回的是2的幂数。例子：cap=5,n的二进制是100，经过左移之后n的值为111，返回8。

图2

在图2中可以看出一个节点包含hash值、键、值及下一个节点。

其实现原理：HashMap中利用数组去存放Node即创建哈希表，键的hash值即是数组的index，如果在数组对应的位置没有发现Node则创建Node并在Node中存放键值，若存在Node,则比较key看是否相同，若相同则修改Node中的值，若不同则去看Node中的next,在下一个Node中去比较，不断循环直至找到key相同的Node或者在最后一个Node还未找到则创建一个新的Node,用来存放键值,并将其添加到最后一个节点之后，使新创建的Node成为最后一个节点。

LinkedHashMap是HashMap的子类，其实现原理和HashMap相同，区别在于LinkedHashMap的Node是LinkedHashMapEntry,比起HashMap的Node，LinkedHashMapEntry多保存了前一个节点和后一个节点，从而使得其存储是有序的；还有LinkedHashMap中比起HashMap，LinkedHashMap多保存了头部和尾部Node，我们可以从头部节点开始找到所有的节点，LinkedHashMap的遍历即是如此操作。所以说HashMap和LinkedHashMap的区别在于：HashMap的存放是无序的，其遍历得到的结果也是无序的；而LinkedHashMap的存放是有序的，其遍历得到的结果也是有序的。（这里的有序、无序针对的是存入的顺序来说的）

问题1:为什么HashMap的长度是2的幂数？

为了实现key的hash值即为数组的index，我们通常是hash%length。在执行效率方面，位运算肯定效率比取余的效率要高。为了提高效率，所以源码中采用了位运算，感觉有些用空间换时间。只要HashMap的长度始终是2的幂数，则hash&(length-1)==hash%length。

问题2:loadFactor(加载因子)的作用？

源码中默认的存放Node的数组length为16，loadFactor = 0.75f，loadFactor的作用是用来确定HashMap的当前的最大容量即最多可以存放length*loadFactor个Node(键值对)。属性threshold用来保存当前HashMap最大存放Node的数量即threshold = length * loadFactor。我们在使用时，一旦put到HashMap中的键值对的size大于threshold，就会对HashMap进行扩容即将哈希表的长度增加一倍，创建新的哈希表，同时将旧的哈希表中的Node重新计算其在新的哈希表中的index,并将其存放在新的哈希表中。所以loadFactor的作用就是用来确定HashMap中可以存放的键值对的大小。

问题3:在什么情况下会使用到红黑树？

当HashMap中数组中的某一index对应的链表的长度超过7个，并且整个数组的长度不小于64时才开始在数组的最后一个index对应的最开始的Node开始遍历链表，将链表中的Node替换成TreeNode，替换完成后在将TreeNode变成红黑树。

参考文章：Hashmap为什么容量是2的幂次，什么是负载因子 - 隆曦的博客 - CSDN博客