电商网站在线支付怎么做,手机版网站建设报价,开展农业信息网站建设工作总结,美食网站设计的代码前言#xff1a;本文基于JDK8
一、HashMap
1.1、hash方法
hash方法是map中的基石#xff0c;后续很多操作都依赖hash方法#xff1b; 下面是 jdk 7 中 hash方法#xff0c;注意hashSeed 这个扰动因子#xff0c;该值随机#xff0c;所以同一个 key 每次调用hash方法后…前言本文基于JDK8
一、HashMap
1.1、hash方法
hash方法是map中的基石后续很多操作都依赖hash方法 下面是 jdk 7 中 hash方法注意hashSeed 这个扰动因子该值随机所以同一个 key 每次调用hash方法后得到的hash值都不一样。 该值存在就是为了增加随机性避免链表过长性能急剧下降jdk 8 中 hash方法移除了扰动因子因为底层数据结构链表过长的情况下会进行转换为红黑树来提升性能 // jdk 7
final int hash(Object k) {int h hashSeed; // 扰动因子if (0 ! h k instanceof String) {return sun.misc.Hashing.stringHash32((String) k);}h ^ k.hashCode();// 扰动因子 参与 hash 计算// This function ensures that hashCodes that differ only by// constant multiples at each bit position have a bounded// number of collisions (approximately 8 at default load factor).h ^ (h 20) ^ (h 12);return h ^ (h 7) ^ (h 4);
}1.2、put方法 1.3、putVal方法
其中( n - 1 ) hash是对 hash % nn 是 2 的幂次方的性能优化。 HashMap数组长度都是2的幂次方就是为了方便上述操作提高处理效率。 注意上图中操作数组位置 i 空闲时直接存入节点多线程情况下会导致元素丢失所以putVal方法线程不安全。 上图提到了采用拉链法解决hash冲突下面来看下具体内容 链表尾插法 JDK 7 时采用的是头插法即下一个冲突的键值对会放在上一个键值对的前面。扩容的时候就有可能导致出现环形链表造成死循环。 注意链表转化为红黑树阈值TREEIFY_THRESHOLD 为 8 TREEIFY_THRESHOLD - 1的值为 7 为何减1 插入新节点时binCount表示插入前的链表长度。 例如 插入第8个节点时插入前链表长度为7binCount7满足条件7 7触发树化。 插入完成后链表实际长度为8此时已超过阈值需转换为红黑树。 jdk 7 拉链法只有链表并无红黑树处理逻辑。 1.4、方法treeifyBin
数组长度小于64时采用扩容数组来减少hash冲突否则转换为红黑树 1.5、扩容resize 重点关注迁移数组链表红黑树同理不再赘述中元素 之所以可以达到迁移前后数组位置的上述变化奥秘就在于 数组长度为2的 n 次幂key 的 hash 值固定 1.6、get方法 1.7、getNode方法 1.8、节点
1.8.1、Node 1.8.2、TreeNode LinkedHashMap.Entry在HashMap.Node基础上扩展了before和after指针形成双向链表以维护插入/访问顺序。而TreeNode继承它后天然具备了维护双向链表的能力。这种设计允许在树化链表转红黑树和反树化红黑树转链表时快速重构链表结构避免重新遍历节点。 1.9、小节
JDK1.8 HashMap 结构为数组链表/红黑树数组长度为2的 n 次幂方便用位运算快速计算数组下标链表转换为红黑树前提2个 链表长度达到8个数组长度达到64 数组扩容后链表元素红黑树一样分为2个链表 一个链表位置在新老数组中下标一样另外一个位置为旧数组位置 旧数组长度计算时通过hash值 与旧数组长度进行位与操作来区分这种优化依赖hash值稳定不变和数组长度为2的n次幂
二、LinkedHashMap
LinkedHashMap 继承了HashMap增加了元素的顺序控制
插入顺序访问顺序 头部最老尾部最年轻 2.1、HashMap 对LinkedHashMap支持
HashMap 中添加了一系列钩子方法来支持LinkedHashMap。 2.2、get方法 2.3、afterNodeAccess方法
开启访问顺序控制时将访问节点移动到链表尾部迭代访问LinkedHashMap时后输出的元素最近被访问过 2.4、removeEldestEntry方法
是否移除最老元素当访问顺序标识开启同时覆写此方法如下图注释即可实现简易版LRU(Least Recently Used最近最少使用) 通过 LinkedHashMap实现LRU
// 自定义 LinkedHashMap限制最大容量并开启淘汰逻辑
public class LRUCacheK,V extends LinkedHashMapK,V {private final int maxCapacity;public LRUCache(int maxCapacity) {super(maxCapacity, 0.75f, true); // accessOrdertrue 维护访问顺序this.maxCapacity maxCapacity;}Overrideprotected boolean removeEldestEntry(Map.EntryK,V eldest) {return size() maxCapacity; // 超过容量时移除最久未访问的节点}
}2.5、afterNodeInsertion方法
LRU中移除最老元素就是此方法做的。 该钩子方法在HashMap中putVal方法结束前会调用 其中的removeNode方法是HashMap中的方法该方法结束前会调用钩子方法afterNodeRemoval详见2.6小节。 2.6、afterNodeRemoval方法
双向链表删除节点 三、ConcurrentHashMap
相对于 HashMapConcurrentHashMap 就是线程安全的 map其中利用了锁分段的思想大大提高了并发的效率。 ConcurrentHashMap中与HashMap中一致的内容不再赘述。 1.8 版本舍弃了 1.7中的 segment使用了 synchronized 和 CAS 无锁操作来保证 ConcurrentHashMap 的线程安全。
为什么不用 ReentrantLock 而是 synchronzied 呢 实际上synchronzied 做了很多的优化包括偏向锁、轻量级锁、重量级锁synchronized 相较于 ReentrantLock 的性能其实差不多。 3.1、hash方法
ConcurrentHashMap 中hash方法名变为spread与HashMap相比增加了将hash值变为正数严谨点非负数的操作。 hash值为非负数是为了配合3.2小节中的辅助节点。 key 不允许为 null所以这里没有必要判空 3.2、节点
ConcurrentHashMap 中5种节点分为两类
数据节点hash值为非负数通过方法spread计算 Node链表节点TreeNode红黑树节点 辅助节点不存放数据hash值固定且均为负数 TreeBin用于指向红黑树根节点hash值为-2ForwardingNode数组扩容时使用hash值为-1ReservationNode占位节点hash值为-3方法computeIfAbsent 和 compute中使用该节点。
3.2.1、Node 3.2.2、TreeNode 3.2.3、TreeBin
该节点hash值固定为TREEBIN -2 3.2.4、ForwardingNode
注意构造方法中MOVED是该节点的hash值固定为 -1成员变量nextTable就是扩容过程中用于指向新的数组位置。 3.2.5、ReservationNode
注意构造方法中RESERVED是该节点的hash值固定为 -3 该节点使用详见3.6小节 3.3、put方法 为啥不允许key 、value 为null ? 多线程环境下的歧义性问题 HashMap中允许当get(key) 返回null 时单线程情况下 通过containskey(key) 可以确认key是否存在即 key 不存在所以value返回null 或key存在value就是null ConcurrentHashMap中不允许它是面向多线程的当get(key) 返回null 时 通过containskey(key) 无法确认key一开始是否存在 线程A执行get(key) 返回null线程B执行put(key)设置key null或者删除了key线程A执行containskey(key) 返回啥问题来了key一开始不存在(对于A就应该返回false)后面被B设置了实际返回true或者一开始存在对于A就应该返回truevalue就是null后面被B删除了实际返回false这key一开始到底存不存在已经产生歧义了。 为了避免歧义ConcurrentHashMap直接禁止key、value为null的情况。 3.4、putVal方法
注意比HashMap中的putVal方法多了的循环是为了配合CAS操作。 CAS 一般都会伴随自旋操作具体细节参阅 自旋、CLH、AQS浅析; 拉链法解决hash冲突链表尾插法插入链表长度超过8尝试转换为红黑树或者红黑树插入 链表尝试转换为红黑树时和HashMap一致数组长度小于64时首选扩容否则转换。 解决冲突时使用内置锁synchronized锁的对象时数组 i 位置的节点锁的粒度就是1个节点。 jdk 7 使用 ReentrantLock锁的对象是segment包含数组相邻位置多个节点。为了避免浪费空间去为每一个数组桶关联一个锁对象所以使用数组桶中第一个元素作为一把锁。 注意下图判断链表和红黑树的判断方法 hash 值下图变量fh0 是链表因为红黑树的根节点被节点TreeBinhash值固定为 -2指着。 3.5、get方法 注意上图红黑树查找时如遇到数组正在扩容时会先找到ForwardingNode节点通过ForwardingNode找到扩容后的新数组在新数组中查找(类似递归了)。 3.6、computeIfAbsent方法 我们只关注key不存在的情况数组对应位置记为 i 元素为null线程A、B同时执行此逻辑 新建占位节点ReservationNode记为 r, 通过CAS操作将占位节点设置设置到 数组i;既然CAS就会有失败的可能所以外侧通过循环来自旋CAS成功了占位节点就会设置到数组 i 位置后续就可以break退出循环CAS失败了进入下次循环注意下次循环进来后不会再次进入CAS逻辑了 CAS失败意味着数组位置 i 元素图示f null因为被别的线程设置了 下次循环会进入图示下方的同步代码块此处加锁的对象是f; 此处加锁应该没有疑问就是防止链表修改并发产生错误 问题来了占位节点r 作用域就在else if这个代码块每个线程执行时创建的r都不同为啥对r加锁 加锁一定有并发场景问题是此处r 会有其它线程来争抢吗 回到上面CAS失败的情况假设线程A CAS失败线程B CAS成功 线程B CAS成功意味着线程B之前对自己创建的r加锁成功了 线程A 会进入下次循环走到图示下方的同步代码块 此时线程B还在图示上方同步块中执行那线程A此时读到的对象是f就是线程B创建的r了即f r;线程A无法加锁成功进入阻塞状态因为占位节点r时临时节点最终会被线程B替换为真正的节点Node; 综上占位节点ReservationNode 和真正的节点替换作为一个原子操作是不可以分开的所以此处必须对占位节点ReservationNode 进行加锁。
四、TreeMap
TreeMap可以保持元素的自然顺序所以使用时需要提供排序器或将key实现排序接口。 4.1、树节点Entry
TreeMap中的Tree是红黑树时间复杂度O(log n); 4.2、put方法 4.3、get方法 4.4、getEntry方法
