广州做网站的网络公司,网站上的视频上传怎么做,长春网站建设电话咨询,网站的总体方案HashMap 调研 前言JDK1.8之前拉链法: JDK1.8之后JDK1.7 VS JDK1.8 比较优化了一下问题: HashMap的put方法的具体流程?HashMap的扩容resize操作怎么实现的? 前言
在Java中#xff0c;保存数据有两种比较简单的数据结构:数组和链表。
数组的特点是:寻址容易#xff0c;插入… HashMap 调研 前言JDK1.8之前拉链法: JDK1.8之后JDK1.7 VS JDK1.8 比较优化了一下问题: HashMap的put方法的具体流程?HashMap的扩容resize操作怎么实现的? 前言
在Java中保存数据有两种比较简单的数据结构:数组和链表。
数组的特点是:寻址容易插入和删除 困难; 链表的特点是:寻址困难但插入和删除容易;
所以我们将数组和链表结合在一起发挥两者各 自的优势使用一种叫做拉链法的方式可以解决哈希冲突 。 JDK1.8之前
JDK1.8之前采用的是拉链法。
拉链法: 将链表和数组相结合。也就是说创建一个链表数组数组中每一格就是一个链表。若遇到哈希冲突则将冲突的值加到链表中即可。 JDK1.8之后
相比于之前的版本jdk1.8在解决哈希冲突时有了较大的变化当链表长度大于阈值(默认为8)时将 链表转化为红黑树以减少搜索时间。 JDK1.7 VS JDK1.8 比较
优化了一下问题:
resize 扩容优化引入了红黑树目的是避免单条链表过长而影响查询效率解决了多线程死循环问题但仍是非线程安全的多线程时可能会造成数据丢失问题。
HashMap的put方法的具体流程? public class HashMapDemoK, V extends HashMapK, V {// 默认初始容量 - 必须是 2 的幂。static final int DEFAULT_INITIAL_CAPACITY 1 4; // aka 16// 如果任一带有参数的构造函数隐式指定更高的值则使用最大容量。必须是 2 的幂 130。static final int MAXIMUM_CAPACITY 1 30;// 初始因子static final float DEFAULT_LOAD_FACTOR 0.75f;// 使用树而不是箱列表的箱计数阈值。当将元素添加到至少具有这么多节点的 bin 时bin 会转换为树。该值必须大于2并且至少应为8以便与树木移除中有关收缩后转换回普通箱的假设相吻合。static final int TREEIFY_THRESHOLD 8;// 在调整大小操作期间对分割bin 进行树形化的 bin 计数阈值。应小于 TREEIFY_THRESHOLD且最多 6 个网格以便在移除时进行收缩检测。static final int UNTREEIFY_THRESHOLD 6;// bin 可以树化的最小表容量。 初始数量否则如果 bin 中的节点太多则表的大小将被调整。应至少为 4的倍数以避免调整大小和树化阈值之间的冲突。static final int MIN_TREEIFY_CAPACITY 64;transient HashMapDemo.NodeK, V[] table;transient SetEntryK, V entrySet;transient int size;transient int modCount;int threshold;// 创建一个节点Node类 作为链表使用static class NodeK, V implements Map.EntryK, V {// hash值final int hash;// keyfinal K key;// 对应的值V value;// 子节点HashMapDemo.NodeK, V next;Node(int hash, K key, V value, HashMapDemo.NodeK, V next) {this.hash hash;this.key key;this.value value;this.next next;}// get setpublic final K getKey() {return key;}public final V getValue() {return value;}public final String toString() {return key value;}// 计算规则 节点上的key 进行hashCode 计算异或 hashCode 值public final int hashCode() {return Objects.hashCode(key) ^ Objects.hashCode(value);}public final V setValue(V newValue) {V oldValue value;value newValue;return oldValue;}public final boolean equals(Object o) {if (o this)return true;if (o instanceof Map.Entry) {Map.Entry?, ? e (Map.Entry?, ?) o;if (Objects.equals(key, e.getKey()) Objects.equals(value, e.getValue()))return true;}return false;}}// 定义一个 hash 方法 通过hashCode 得到一个长度 位运算 h 高低16bitstatic final int hash(Object key) {int h;// key.hashCode()) ^ (h 16) hashcode 和 自己hashcode 位运算异或return (key null) ? 0 : (h key.hashCode()) ^ (h 16);}// put方法Overridepublic V put(K key, V value) {return super.put(key, value);}V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {HashMapDemo.NodeK, V[] tab;HashMapDemo.NodeK, V p;int n;int i;// 初始化表大小或将表大小加倍。如果为空则根据阈值字段中保存的初始容量目标进行分配if ((tab table) null || (n tab.length) 0) {// 步骤1:tab为空则创建 table未初始化或者长度为0进行扩容n (tab resize()).length;}// 计算下标是否为空 通过hash算法 得到 p (n - 1) hash 确定元素存放在哪个桶中if ((p tab[i (n - 1) hash]) null) {// 为空找不到放到桶里面tab[i] newNode(hash, key, value, null);}// 桶里面存在类else {HashMapDemo.NodeK, V e;K k;// 步骤3:节点key存在直接覆盖value比较桶中第一个元素(数组中的结点)的hash值相等key相等if (p.hash hash ((k p.key) key || (key ! null key.equals(k)))) {// 直接覆盖值e p;}// 步骤4:判断该链为红黑树 hash值不相等即key不相等;为红黑树结点 如果当前元素类型为TreeNode表示为红黑树putTreeVal返回待存放的node e可能为空else if (p instanceof TreeNode) {// 放入树中e ((TreeNodeK, V) p).putTreeVal(this, tab, hash, key, value);}// 步骤5 不是树就是链表else {// 循环for (int binCount 0; ; binCount) {// 为空最后一个节点if ((e p.next) null) {// 在链表最末插入Node结点p.next newNode(hash, key, value, null);判断链表的长度是否达到转化红黑树的临界值临界值为8// TREEIFY_THRESHOLD 属性 8 前面定义类if (binCount TREEIFY_THRESHOLD - 1)// 链表结构转树形结构treeifyBin(tab, hash);break;}// 判断链表中结点的key值与插入的元素的key值是否相等if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) {// 相等跳出循环break;}// 用于遍历桶中的链表与前面的e p.next组合可以遍历链表p e;}}// 判断当前的key已经存在的情况下再来一个相同的hash值、key值时返回新来的val ue这个值if (e ! null) {// 记录e的valueV oldValue e.value;// onlyIfAbsent为false或者旧值为nullif (!onlyIfAbsent || oldValue null) {// 用新值替换旧值e.value value;}// 访问后回调afterNodeAccess(e);// 返回旧值return oldValue;}}// 结构性修改modCount;// 步骤6:超过最大容量就扩容 实际大小大于阈值则扩容if (size threshold) {// 插入后回调resize();}// node 节点插入afterNodeInsertion(evict);return null;}
}判断键值对数组table[i]是否为空或为null否则执行resize()进行扩容; 根据键值key计算hash值得到插入的数组索引i如果table[i]null直接新建节点添加转向6如果table[i]不为空转向3; 判断table[i]的首个元素是否和key一样如果相同直接覆盖value否则转向4这里的相同指的是hashCode以及equals; 判断table[i] 是否为treeNode即table[i] 是否是红黑树如果是红黑树则直接在树中插入键值 对否则转向5; 遍历table[i]判断链表长度是否大于8大于8的话把链表转换为红黑树在红黑树中执行插入操 作否则进行链表的插入操作;遍历过程中若发现key已经存在直接覆盖value即可; 插入成功后判断实际存在的键值对数量size是否超多了 大容量threshold如果超过进行扩容。 HashMap的扩容resize操作怎么实现的?
