今天聊聊 HashMap 和 TreeMap 的内部结构，图文并茂才容易理解

HashMap中的桶的个数就是下图中的0- n的数组的长度，存储第一个entry的位置叫桶（bucket）而桶中只能存一个值也就是链表的头节点，链表的每个节点就是添加的一个值（HashMap内部类Entry的实例Entry有哪些属性之后在详说）。

也可以这样理解，一个entry 类型的存储链表的数组。数组的索引位置就是一个个桶的索引地址。

从上图我们可以发现哈希表是由数组+链表组成的，一个长度为16的数组中，每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢。

一般情况是通过hash(key)%len获得，也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中，12%16=12、28%16=12、108%16=12、140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。

HashMap 总结

1、HashMap 是链式数组（存储链表的数组）实现查询速度可以，而且能快速的获取key对应的value；

2、查询速度的影响因素有 容量和负载因子，容量大负载因子小查询速度快但浪费空间，反之则相反；

3、数组的index值是（key 关键字， hashcode为key的哈希值， len 数组的大小）：hashcode%len的值来确定，如果容量大负载因子小则index相同（index相同也就是指向了同一个桶）的概率小，链表长度小则查询速度快，反之index相同的概率大链表比较长查询速度慢。

4、对于HashMap以及其子类来说，他们是采用hash算法来决定集合中元素的存储位置，当初始化HashMap的时候系统会创建一个长度为capacity的Entry数组，这个数组里可以存储元素的位置称为桶（bucket）,每一个桶都有其指定索引，系统可以根据索引快速访问该桶中存储的元素。

5、无论何时HashMap 中的每个桶都只存储一个元素（Entry 对象）。由于Entry对象可以包含一个引用变量用于指向下一个Entry，因此可能出现HashMap 的桶（bucket）中只有一个Entry,但这个Entry指向另一个Entry 这样就形成了一个Entry 链。

6、通过上面的源码发现HashMap在底层将key_value对当成一个整体进行处理（Entry 对象）这个整体就是一个Entry对象，当系统决定存储HashMap中的key_value对时，完全没有考虑Entry中的value，而仅仅是根据key的hash值来决定每个Entry的存储位置。

注意点

JDK1.8中使用一个Node数组来存储数据，但这个Node可能是链表结构，也可能是红黑树结构如果插入的key的hashcode相同，那么这些key也会被定位到Node数组的同一个格子里。

如果同一个格子里的key不超过8个，使用链表结构存储。如果超过了8个，那么会调用treeifyBin函数，将链表转换为红黑树。

那么即使hashcode完全相同，由于红黑树的特点，查找某个特定元素，也只需要O(log n)的开销。

也就是说put/get的操作的时间复杂度最差只有O(log n)。

需要注意：key的对象，必须正确的实现了Compare接口

二、TreeMap

1、红黑树是一种近似平衡的二叉查找树，它能够确保任何一个节点的左右子树的高度差不会超过二者中较低那个的一倍。具体来说，红黑树是满足如下条件的二叉查找树（binary search tree）：

1. 每个节点要么是红色，要么是黑色。
   
2. 根节点必须是黑色
   
3. 红色节点不能连续（也即是，红色节点的孩子和父亲都不能是红色）。
   
4. 对于每个节点，从该点至null（树尾端）的任何路径，都含有相同个数的黑色节点。