一篇文章搞清楚HashMap和TreeMap的内部结构 _HashMap

一、HashMap1、基于哈希表的 Map 接口的实现。
此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。
【一篇文章搞清楚HashMap和TreeMap的内部结构】2、HashMap 的实例有两个参数影响其性能：初始容量和加载因子。
容量是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。
加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。
按照key关键字的哈希值和buckets数组的长度取模查找桶的位置，如果key的哈希值相同，Hash冲突（也就是指向了同一个桶）则每次新添加的作为头节点，而最先添加的在表尾。

文章插图

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) 。