关于java:9-hashMap

hashMap
非线程平安，
hash 抵触采纳拉链法解决，1.8 中引入红黑树解决链表过长的问题
初始大小 16，扩容为 2 的幂次（求地位的时候速度快），如果给出初始，会用比你给的略微大一点的 2 的幂次
多线程操作导致死循环问题次要起因在于并发下的 Rehash 会造成元素之间会造成一个循环链表？

四个构造方法
1. 将负载因子变量设为默认值 0.75（默认状况下，HashMap 初始容量是 16，默认的负载因子(0.75) 在工夫和空间老本之间提供了很好的衡量。更高的值缩小了空间开销，但减少了查找老本）
2. 传入初始容量 + 将负载因子设为默认值
3. 传入初始容量和负载因子，hashMap 里没有字段保留初始容量，构造方法将阈值设为比初始容量大的 2 的幂，当初始化桶数组时，设初始容量 = 阈值
4. 将另一个 Map 中的映射拷贝一份到本人的存储构造中来

查找：先依据(n – 1)& hash 定位桶，而后对链表或红黑树进行查找
HashMap 中桶数组的大小 length 总是 2 的幂，此时，(n – 1) & hash 等价于对 length 取余。但取余的计算效率没有位运算高，

此时的 hash 是通过位运算从新计算 hash
图中的 hash 是由键的 hashCode 产生。计算余数时，因为 n 比拟小，hash 只有低 4 位参加了计算，高位的计算能够认为是有效的。这样导致了计算结果只与低位信息无关，高位数据没发挥作用。为了解决这个缺点，咱们能够上图中的 hash 高 4 位数据与低 4 位数据进行异或运算，即 hash ^ (hash >>> 4)。通过这种形式，让高位数据与低位数据进行异或，以此加大低位信息的随机性，变相的让高位数据参加到计算中。

遍历时程序是稳固的，然而和插入程序不一样

插入
当桶数组 table 为空时，通过扩容的形式初始化 table
查找要插入的键值对是否曾经存在，存在的话依据条件判断是否用新值替换旧值
如果不存在，则将键值对链入链表中，并依据链表长度决定是否将链表转为红黑树
判断键值对数量是否大于阈值，大于的话则进行扩容操作

扩容
每次扩成原来的两倍
计算新桶数组的容量 newCap 和新阈值 newThr
依据计算出的 newCap 创立新的桶数组，桶数组 table 也是在这里进行初始化的
将键值对节点从新映射到新的桶数组里。如果节点是 TreeNode 类型，则须要拆分红黑树。如果是一般节点，则节点按原程序进行分组。

键值对节点从新映射的过程
对于树形节点，需先拆分红黑树再映射。对于链表类型节点，则需先对链表进行分组，而后再映射。
如果是 16 个桶的 map，每个 hash 值依据后四位分在 16 个桶里。当桶的数量裁减到 32 后，每个 hash 依据后 5 位分在 32 个桶里，所以原来一个桶的元素，只会进入固定的两个新桶而且绝对地位不变。
1.7 为了防碰撞，hash 时退出随机种子以减少 hash 的随机性，扩容过程中会依据容量判断是否须要从新生成随机种子。1.8 因为加了红黑树不怕碰撞了，所以不加随机种子，扩容时不须要从新 hash，效率更高。

树化要满足两个条件：
链表长度大于等于 TREEIFY_THRESHOLD
桶数组容量大于等于 MIN_TREEIFY_CAPACITY

树节点比照
HashMap 在设计之初，并没有思考到当前会引入红黑树进行优化。所以并没有像 TreeMap 那样，要求键类实现 comparable 接口或提供相应的比拟器。但因为树化过程须要比拟两个键对象的大小，在键类没有实现 comparable 接口的状况下，怎么比拟键与键之间的大小了就成了一个辣手的问题。为了解决这个问题，HashMap 是做了三步解决，确保能够比拟出两个键的大小，如下：
比拟键与键之间 hash 的大小，如果 hash 雷同，持续往下比拟
检测键类是否实现了 Comparable 接口，如果实现调用 compareTo 办法进行比拟
如果仍未比拟出大小，就须要进行仲裁了，仲裁办法为 tieBreakOrder（大家本人看源码吧）
tie break 是网球术语，能够了解为加时赛的意思，起这个名字还是挺有意思的。
通过下面三次比拟，最终就能够比拟出孰大孰小。比拟出大小后就能够结构红黑树了。

红黑树拆分
在将一般链表转成红黑树时，HashMap 通过两个额定的援用 next 和 prev 保留了原链表的节点程序。这样再对红黑树进行从新映射时，齐全能够依照映射链表的形式进行。新链表如果太长，再进行一次树化。

被 transient 所润饰 table 变量
如果大家仔细浏览 HashMap 的源码，会发现桶数组 table 被申明为 transient。transient 示意易变的意思，在 Java 中，被该关键字润饰的变量不会被默认的序列化机制序列化。咱们再回到源码中，思考一个问题：桶数组 table 是 HashMap 底层重要的数据结构，不序列化的话，他人还怎么还原呢？

这里简略阐明一下吧，HashMap 并没有应用默认的序列化机制，而是通过实现 readObject/writeObject 两个办法自定义了序列化的内容。这样做是有起因的，试问一句，HashMap 中存储的内容是什么？不用说，大家也晓得是键值对。所以只有咱们把键值对序列化了，咱们就能够依据键值对数据重建 HashMap。有的敌人可能会想，序列化 table 不是能够一步到位，前面间接还原不就行了吗？这样一想，倒也是正当。但序列化 talbe 存在着两个问题：

table 少数状况下是无奈被存满的，序列化未应用的局部，节约空间
同一个键值对在不同 JVM 下，所处的桶地位可能是不同的，在不同的 JVM 下反序列化 table 可能会产生谬误。
以上两个问题中，第一个问题比拟好了解，第二个问题解释一下。HashMap 的 get/put/remove 等办法第一步就是依据 hash 找到键所在的桶地位，但如果键没有覆写 hashCode 办法，计算 hash 时最终调用 Object 中的 hashCode 办法。但 Object 中的 hashCode 办法是 native 型的，不同的 JVM 下，可能会有不同的实现，产生的 hash 可能也是不一样的。也就是说同一个键在不同平台下可能会产生不同的 hash，此时再对在同一个 table 持续操作，就会呈现问题。

综上所述，大家应该能明确 HashMap 不序列化 table 的起因了。