HashMap
16， 0.75
为什么能快速查找？
put操作放入key时
- 获取key的hash值。
- 在原始hash值的基础上再次获取hash值。
- 二次hash值与容量取模运算%capacity。获得桶下标。
- 根据桶下标，存入数据。
- get(key)时，能直接定位到桶下标。
- 问题：当同一个下标存在多个元素，查找依旧变成O(n)。
底层数据结构
为什么用红黑树？
- 用来避免DoS攻击，防止链表超长时性能下降，树化应当是偶然情况。
- hash表的查找，更新的时间复杂度O(1)，红黑树的查找更新时间复杂度是O(log2n)
- hash值如果足够随机，则在hash表内按泊松分布，在负载因子0.75情况下，长度超过8的链表概率是亿分之6，选择8为了树化概率更小。
为什么不直接树化？
树的TreeNode占用的内存比普通Node大，而且少量数据并不会有什么性能提升。
为什么树化阈值为8？
红黑树是一种异常情况下才转化成树。一般只有恶意攻击时才会出现。选择8为了树化概率更小。
什么时候树化？
- 链表长度超过数化阈值8
- 数组长度>=64
什么时候退化链表？
- 当扩容时如果拆分树时，树元素个数<=6则会退化链表。
- remove树节点时，移除之前检查，若root，root.left，root.right，root.left.left有一个null，也会退化链表。
索引计算过程？
索引==求模运算（二次hash值%capacity）
- 求模运算：97%16=1
- 位与运算：二次hash值&(capacity-1)=1；前提被除数是2的N次方。
为什么用二次hash值？
二次hash为了综合高位数据，让哈希分布均匀。
数组容量为什么是2的n次幂？
- 计算索引时，如果是2的N次幂可以使用位于运算代替取模，效率更高；
- 扩容时hash&oldCap==0元素留着不动，否则新位置=旧位置+oldCap；
2的n次幂造成的问题？
- 当大部分数据都是偶数时，造成数据只存储在偶数下标。
- 2的n次幂是为了性能更优，
- 想要更好的hash分布性应该采用容量为质数或者不是2的n次方。
put流程,1.7与1.8不同?
- HashMap懒惰创建数组，首次使用才创建数组。
- 计算索引
- 如果桶下标没人占用，创建Node占位返回
- 如果桶下标被人占用
- 已经是TreeNode走红黑树的添加或更新逻辑。
- 是普通Node，走链表的添加或更新逻辑，如果链表长度超过树化阈值，走树化逻辑
- 返回前检查容量是否超过阈值，一旦超过进行扩容。
- 不同点：
- 链表插入节点：1.7头插法，1.8尾插法。
- 1.7大于等于阈值且没有空位时才扩容，而1.8是大于阈值就扩容。
- 1.8扩容计算Node索引时会优化。
加载因子默认为什么0.75？
- 在空间占用和查询时间之间较好的权衡。
- 大于这个值，空间节省了，但是链表长度会比较长影响性能。
- 小于这个值，冲突减少了，但是扩容频繁，空间占用多。
多线程下的HashMap
- 1.8数据丢失现象。多个线程同时进入newNode 方法，并赋值到同一个位置。
- 1.7循环死链现象。扩容操作中，
- 多线程操作时，线程的临时变量e和next会记录链表位置。此时发送线程上下文切换，本来已经转换的元素再次转换造成死链。
key的要求
- HashMap的key可以为null,但Map的其他实现则不然。
- 作为key的对象，必然实现hashCode和equals，并且key的内容不能修改。改变后计算得到的hashCode不一样
hashCode为什么每次乘31？
目的：达到较为均匀的散列效果，每个字符串的hashCode
而且31能够优化为2的n次幂减一。
|