关键字：get，put，红黑树，自动扩容，数组，链表

在看完spring之后才知道HashMap使用的有多频繁，spring两个特性，面向切面编程，面向内存编程(并不，是控制反转）。

控制反转就是将类初始化，储存在内存中，以HashMap的形式。

底层原理

hashMap中get是如何实现的？

怎么样通过get直接找到值？程序运行就3件事，循环/分叉/按顺序，

先猜一下，key应该是有一个单独存储的空间，循环key找到要get的那个key，然后怎么拿到值？（这是MySQL索引的原理，MySQL用到的B+tree也是一种平衡二叉树）

并不是！key没有独立空间。

先计算key的hash

tab[hash]直接拿到HashMap中这个hash下标的值

链表就是遍历所有键值对，用==或equals来比对键，然后拿值；看上去挺粗暴的。

当然其中还有很多非空，长度的判断，还有是否红黑树的判断。

一些小问题

数组是怎么查询的？

数组可以随机访问，这是数组的一大特点，它不需要从0数起；因为数组是先申请一块连续空间（所以数组定长），所以储存空间是连续的，tab[3]就直接访问第4个值，而不需要遍历前面的几个值。

为什么用链表？

链表可以申请不连续的空间，通过一个指针按顺序将这些空间串起来。数组是定长的，链表不是。链表的检索能力偏弱（只能遍历），作为弥补，它在动态调整上会更容易。这也是为什么要用红黑树的原因，为了查询快。

集合也是可变的，为什么不用集合？

ArrayList底层由数组实现；集合中的数组默认是10的容量，在调用add方法时如果容量已满，会将数组的容量扩大1.5倍的容量。

其他的所有储存方式也只不过是数组和链表的组合和变化。

红黑树

hashMap有两种储存方式，一种是链表，数据多了就会转红黑树。

红黑树怎么查询呢？看这个结构就是要做2分查找了，确实数据多了比for循环快很多很多。

这看上去应该是有序的，key是怎么排序的？字符串是通过ASCII码比较大小。

为什么要叫红黑？不是为了好看，还是有意义的。为了确保树的平衡

1.根节点是黑的。

2.叶子节点也是黑的（指的是NIL/null）。

3.红色节点不能连续，父节点/子节点都必须是黑的。

4.从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。（这个很神奇，数一下还是真的）

5.新加入到红黑树的节点为红色节点。（如果加到红色节点下就需要调整了）

每个节点都只能有两个子节点（因为是二叉树）。

hashMap中put是如何实现的？

先计算key的hash值，找到tab[hash]的值，

链表就没什么好说的，遍历链表，key存在就覆盖值，不存在就新增；主要说红黑树的put。

这个红黑树树的结构要保持平衡（是一种平衡二叉树），子节点高度要一致。

所有put还是需要技巧的，不能随便插入；

如果插入的数据导致树不符合上面的规则，就会开始变色和旋转；

直到调整到符合上面的规则，符合规则后树又刚好平衡了。

参考关于红黑树(R-B tree)原理，看这篇如何

等我看完算法导论再来自己说说。

自动扩容

什么时候扩容？

负载因子默认是0.75，就是容量达到3/4的时候会扩容。

扩容多少？

扩大一倍。

怎么样扩容？

原来是新建一个更大的数组，在转移过去。同时hash算法也会发生变化，因为开始只能最大生成15的值，扩容之后可以生成到31。

相关hash算法估计和nginx负载均衡用的hash类似，hash（key）%16，这样他永远不会超过16。

怪不得网易的面试官会问我数组怎么扩容？数组怎么能扩容，幸好机制的我还是猜到了这个方法。

一些构不成问题的疑问

扩容是只扩容数组，所以链表和红黑树里数据多少都不会触发扩容？

并不！是键值对的个数触发的。也就是tab[0]的红黑树里有12个数据，tab数组其他位置下一个数据也没有，也会触发扩容。

这样的机制下，红黑树出现的几率不高啊！（链表值大于8个转红黑树，低了还会变回链表）

如果红黑树里数据很多，扩容之后更新hash算法，分散了数据后，又达到扩容要求，那就要连续扩容了?

好像也不会，触发扩容的那个值所在的位置一定没有hash冲突。所以不会连续触发扩容。

考虑到扩容时红黑树也要重组，扩容是个比较消耗资源的操作。

hash是什么?

散列，把任意长度的字符经过hash算法都能生成相同长度的输出。hashMap中应该是把key散列成数字，这样就可以组成数组下标。

hashmap和hashtable

//todo

treeMap怎么排序？

//todo