一个网站如何做seo优化,卖书网站开发的背景,WordPress设置会话有效时间,仿站吧HashMap 是 Map 接口中基于哈希表的非同步实现, 自身也可以自动扩容。使用时可以通过 key 快速定位到对应的 value。key 和 value 同时可以都为 null。
1 HashMap 的结构定义
JDK1.8 对 HashMap 进行了比较大的优化, 底层实现由之前的 “数组 链表” 改为 “数组 链表 红黑…HashMap 是 Map 接口中基于哈希表的非同步实现, 自身也可以自动扩容。使用时可以通过 key 快速定位到对应的 value。key 和 value 同时可以都为 null。
1 HashMap 的结构定义
JDK1.8 对 HashMap 进行了比较大的优化, 底层实现由之前的 “数组 链表” 改为 “数组 链表 红黑树”。 在链表的长度大于等于 8 并且数组的长度大于等于 64 时, 将对应的链表转为红黑树 (本文不涉及红黑树部分的分析, 涉及到时, 只会提一下, 然后跳过)。
首先数组是整个数据的存储真正实体, 数组中的存储的数据是链表或者红黑树, 当链表的长度达到了条件, 就变成了红黑树, 大体的情况如下:
1.1 数组的定义
public class HashMapK,V {transient NodeK,V[] table;
}从上面的代码就是 HashMap 中数据存储的地方: 数组。 数组存储的数据类型为 Node, 这个 Node 是链表的定义。 而 红黑树的定义是继承了 Node, 所以通过向上转型的方式, 就能通过一个 Node 的类型表示链表和红黑树。
1.2 链表的定义
public class HashMapK,V {/*** 链表定义* Map.Entry 行为接口, 定义了一堆操作方法, 比如 getValue, setValue 等*/static class NodeK,V implements Map.EntryK,V {// 当前节点的 hash 值final int hash;// 当前节点的 keyfinal K key;// 当前节点的 valueV value;// 下一个节点, 这个属性决定了 Node 为链表NodeK,V next;Node(int hash, K key, V value, NodeK,V next) {this.hash hash;this.key key;this.value value;this.next next;}/*** 计算当前节点 hashCode*/public final int hashCode() {// Objects.hashCode 本质就是调用对象的 o.hashCode()// 当前节点的 hashCode 值 等于 key 的 hashCode 异或 value 的 hashCode 值return Objects.hashCode(key) ^ Objects.hashCode(value);}/*** 节点比较*/public final boolean equals(Object o) {if (o this)return true;// 都是 Map.Entry 节点if (o instanceof Map.Entry) {Map.Entry?,? e (Map.Entry?,?)o;// Objects.equals 会先比较一下 2 者的内存地址, 一样直接返回 true// 不一样, 调用 key.equals(e.getKey) 进行比较if (Objects.equals(key, e.getKey()) Objects.equals(value, e.getValue()))return true;}return false;}}
}1.3 红黑树的定义 public class HashMapK, V {// 继承了 LinkedHashMap.Entry, Entry 继承了 HashMap.Node 所以 TreeNode 具有 链表的特点/** * 红黑树的定义* LinkedHashMap.Entry 继承了 HashMap.Node 节点, 所以 TreeNode 是 Node 的子类, 也具备链表的特点*/ static final class TreeNodeK,V extends LinkedHashMap.EntryK,V {/*** 红黑树的根节点*/TreeNodeK,V parent;/*** 当前节点的左节点*/TreeNodeK,V left;/*** 当前节点的右节点*/TreeNodeK,V right;/*** 删除后需要解决连接的节点*/TreeNodeK,V prev; /*** 是否为红色节点*/boolean red;// ... 后面 省略 红黑树的操作}
}2 HashMap 中的几个重要属性
public class HashMapK,V {transient NodeK,V[] table;transient int size;transient int modCount;final float loadFactor;private int threshold;static final int DEFAULT_INITIAL_CAPACITY 1 4;static final int MAXIMUM_CAPACITY 1 30;static final int TREEIFY_THRESHOLD 8;static final int UNTREEIFY_THRESHOLD 6;static final int MIN_TREEIFY_CAPACITY 64;
}2.1 table
transient NodeK,V[] table;HashMap 中存储数据的数组
2.2 size
transient int size;HashMap 中已经存储的数据个数
2.3 modCount
transient int modCount;HashMap 已经被修改了多少次, 用于支撑 fail-fast 机制
2.4 loadFactor
final float loadFactor;负载因子: 默认等于 DEFAULT_LOAD_FACTOR 0.75f; 作用: 一般情况都是在容器满了才会进行扩容, 但是在 HashMap 中, 数据量达到了数组的长度 * 负载因子的值, 就会进行扩容了。 原因: HashMap 在数组中插入一个数据, 是先通过一个 hash 方法转换为一个 hash 值, 通过这个 hash 值计算得到存储在数组的位置, 通过 hash 计算, 就可能存在 hash 冲突。 数据越密集, 冲突的可能性越大, 所以 HashMap 中的数组是不会完成存满的, 通过空留一部分, 减少冲突等。
负载因子默认值为 0.75 的原因: 太大冲突可能性变大, 太小浪费了空间, 同时会导致数组扩容等耗时操作。 所以 0.75 应该是一个经验值的估算, 或者是因为 HashMap的数组长度为 2^n, 乘以 0.75, 能获得一个整数。
2.5 threshold
private int threshold;当前数组的阈值, 即数组实际应该放多少数据
2.6 几个常量
// 1 左移多少位, 就是相当于 2 的 多少次方, 这里就是 2^4 16
static final int DEFAULT_INITIAL_CAPACITY 1 4;声明 HashMap, 不指定容量时, 默认为 16。
// 2^30
static final int MAXIMUM_CAPACITY 1 30;HashMap 最大容量, 容量必须是 2 的 n 次方, 涉及到通过 key 的 hash 值定位到数组的位置中的一个配合。 HashMap 中数组的容量设定为 2 的 n 次方具体有 2 个作用:
第一, 得到了 key 对应的 hash 后, 如何通过 hash 定位到数组中的哪一个位置呢?
最简单的方式就是取模了吧, 通过 hash 值模于当前数组的长度, 得到的就是当前 hash 对应的数组位置。 但是取模的效率不太好, 那么有什么好的优化方式吗?
在数学上, a, b 都是正整数的情况下, a % b, 在 b 是 2 的 n 次方下, a % b a (b - 1)。 位运算比正常的算术运算快, 那么将 HashMap 的容量设置为 2 的 n 次方, 就可以通过与运算达到取模的效果。 所以 HashMap 中的数组容量必须为 2 的 n 次方。
第二个作用在后面会分析。
static final int TREEIFY_THRESHOLD 8;HashMap 中链表变为红黑树的长度配置, 链表长度达到了 8 满足了链表变为红黑树的条件之一。
static final int UNTREEIFY_THRESHOLD 6;HashMap 中红黑树重新变为链表的长度配置, 红黑树的节点个数达到了 6, 满足了红黑树变为链表的条件之一。
static final int MIN_TREEIFY_CAPACITY 64;HashMap 中链表变为红黑树的的另外一个条件, 当前数组的长度达到了 64。
3 HashMap 的构造方法
3.1 无参的构造函数 public HashMap() {// 设置负载因子为 0.75this.loadFactor DEFAULT_LOAD_FACTOR;
}3.2 指定初始容量 (和负载因子) 的构造函数
public HashMap(int initialCapacity) {// 调用到自身的指定容量 和负载因子的构造函数, 传入的负载因子为默认值 0.75this(initialCapacity, DEFAULT_LOAD_FACTOR);
}/** * 指定 初始容量 和 负载因子 */
public HashMap(int initialCapacity, float loadFactor) {// 指定的容量小于 0, 格式不正确if (initialCapacity 0)throw new IllegalArgumentException(Illegal initial capacity: initialCapacity);// 指定的容量超过了最大容量, 设置为支持的最大容量值if (initialCapacity MAXIMUM_CAPACITY)initialCapacity MAXIMUM_CAPACITY;// 格式不正确 NaN: Not-a-Number, isNaN(arg) arg 不是数字, 返回trueif (loadFactor 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException(Illegal load factor: loadFactor); // 负载因子直接等于输入的值this.loadFactor loadFactor;// tableSizeFor 这个方法会对输入的值, 转换为第一个大于或等于输入值的 2 的 n 次方的数, 比如: 输入 3 得到 4, 输入 4 得到 4, 输入 5 得到 8// 因为 HashMap 的容量需要是 2 的 n 次方, 通过 tableSizeFor 将用户输入的不是 2 的 n 次方的数, 进行修正// threshold 这个属性上面说过是用来存储 HashMap 的实际容量 (声明的数组容量 * 负载因子), 但是这里直接赋值的是 2 的 n 次方, 错了吗?// 实际上没错的, threshold 就是用来存储实际的容量的, 这里只是把计算出来的容量临时存在这个变量, 在第一次进行存放数据时, 进行修正为实际容量的this.threshold tableSizeFor(initialCapacity);}/*** 计算数组容量*/
static final int tableSizeFor(int cap) {// 此次减 1 的原因: 让后面的处理结果变为 n 是第一个大于等于 cap 的 2 的 n 次方的数// 如果这里不减 1 的话, 刚好传进来的数是 2 的 n 次方, 经过下面几步的处理会变成 2 的 n1 次方的数int n cap - 1;n | n 1;n | n 2;n | n 4;n | n 8;n | n 16;// 做一个容错 如果 cap 是一个小于等于 0 的数, 经过上面的处理, n 将会变成一个负数return (n 0) ? 1 : (n MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n 1;
}
3.3 给定一个 Map 的构造函数
public HashMap(Map? extends K, ? extends V m) {// 负载因子 0.75this.loadFactor DEFAULT_LOAD_FACTOR;putMapEntries(m, false);
}/*** 放入数据* param m 数据* param evict 这个参数主用是在插入节点后, 做调整用的, 在 HashMap 中不具备任何作用, 构造参数中直接使用 false, 其他的情况使用 true 即可, 基于 HashMap 实现的 LinkedHashMap 才需要使用到这个参数*/
final void putMapEntries(Map? extends K, ? extends V m, boolean evict) {// 获取需要传入的 Map 的数据个数int s m.size();// 大于 0 的话, 才出来if (s 0) {// 当前存放数据的 table 为空, 表示为初始化if (table null) {// 计算出来需要的容量 长度 / 赋值因子 1float ft ((float)s / loadFactor) 1.0F;// 限制最大的容量 为 2^ 30int t ((ft (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);// 计算出来的当前需要的容量 实际的容量, 进行新容量的计算if (t threshold)// 计算存储数据的数组的容量threshold tableSizeFor(t);} else if (s threshold)// 当前存入的数据量直接大于当前阈值, 进行重新扩容// 扩容方法在下面的添加数据讲解resize();// 遍历 Map, 将里面的数据逐个迁移到当前的 Map 中for (Map.Entry? extends K, ? extends V e : m.entrySet()) {K key e.getKey();V value e.getValue();// 添加数据的在下面的添加数据讲解putVal(hash(key), key, value, false, evict);}}
}4 HashMap 的操作方法
4.1 添加数据
public class HashMapK, V {public V put(K key, V value) {// 1. 计算 key 的 hash 值// 2. 调用 putVal 进行数据的新增return putVal(hash(key), key, value, false, true);}/*** key 计算出 hash 值*/static final int hash(Object key) {int h;// 对象的 hashCode ^ 对象的 hashCode 16// 将 hashCode 的高 16 位与 hashCode 进行异或运算, 主要是为了在 table 的 length 较小的时候, 让高位也参与运算, 减少 hash 冲突, 并且不会有太大的开销// 这里做了一个容错, 如果 key 为 0, 那么计算出来的 hash 值为 0, 也就是 HashMap 直接 key 为 0 的情况, 但是只能存一个 key 为 null 的数据, // 后面的 key 为 null, 计算出来的 hash 都是 0, 会把旧值覆盖(默认情况)return (key null) ? 0 : (h key.hashCode()) ^ (h 16);}/*** 存值* hash 存的 key 的hash值* key 对象的 key* value 存的值* onlyIfAbsent 存入的数据已在 HashMap 中存在, 是否有新的 value 替代旧的 value, false 进行修改, true 不修改* evict 这个值用于 LinkedHashMap, 在HashMap 中没有作用*/final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {NodeK,V[] tab; NodeK,V p; int n, i;// 数组为空 或者 数组的长度为 0, 进行扩容if ((tab table) null || (n tab.length) 0)n (tab resize()).length;// HashMap 对象的位置是通过 (数组的长度 - 1) hash, 也就是 hash % (2 ^ n - 1) 的形式// 存储的位置为空, 直接将 hash, key, value 封装为新的 Node 节点, 放到指定的位置if ((p tab[i (n - 1) hash]) null)tab[i] newNode(hash, key, value, null); else {// 存储的位置已经有数据了NodeK,V e; K k;// 需要放入的位置的第一个节点 的 hash 和 key 一样, 取到这个节点if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))e p;else if (p instanceof TreeNode)// 调用红黑树 进行处理e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value); else {for (int binCount 0; ; binCount) {// 对应的位置不是红黑树, 那么就是链表了, 从链表的第一个节点开始遍历到尾部// 下一个节点为空, 直接将当前的节点放到尾部if ((e p.next) null) {p.next newNode(hash, key, value, null);// 当前的容量已经达到了 8个, 转为红黑树, binCount 从 0 开始遍历的if (binCount TREEIFY_THRESHOLD - 1)// 这个方法后面treeifyBin(tab, hash);break; }// 链表中有一个节点的 hash 和 key 和要插入的一样, 取到这个节点, 停止遍历链表if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) break;// p p 的下一个节点, 判断下一个节点p e }}// e 不为空, 表示在数组当前的位置的链表或红黑树中存在一个 key 值和 hash 值和当前要存入的数据一样。if (e ! null) {// 获取旧值V oldValue e.value;// 旧值为 null 或者入参的 onlyIfAbsent 为 false, 新值替换旧值if (!onlyIfAbsent || oldValue null)e.value value;// 在 HashMap 中这个是空方法 afterNodeAccess(e);return oldValue;}// 修改次数 1, 用于支持 fast-fail 机制modCount;// 当前存储的数据个数达到了阈值, 进行扩容if (size threshold)resize();} // HashMap 的这个方法没有实现afterNodeInsertion(evict);return null;}/*** 重新扩容*/final NodeK,V[] resize() {// 获取当前数组的引用NodeK,V[] oldTab table;// 当前的容量int oldCap (oldTab null) ? 0 : oldTab.length;// 当前的阈值int oldThr threshold;// 新的容量, 新的阈值int newCap, newThr 0;// 当前的容量不为0, 也就是有数据存在了if (oldCap 0) {// 当前的容量已经达到最大了, 直接不进行操作if (oldCap MAXIMUM_CAPACITY) {// 直接将阈值设为 int 的最大值// 实际的数组长度依旧为 2^30, 一般情况阈值 threshold 实际数组的长度 * 负载因子, 负载因子一般都是小于 1 大于 0 的数, 所以 threshold 数组的实际长度// 决定数组是否扩容的则是由 threshold 是否小于当前的数据个数 size, 所以数组的容量还未完全用完了, 就扩容了,// 现在的情况是, 旧的数组的容量已经达到了设定的最大容量了, 无法继续扩了, 所以将 threshold 直接设置为 int 的最大值 数组的长度, 这样可以继续利用原本因负载因子而无法使用到的空间threshold Integer.MAX_VALUE;return oldTab;// 新容量的值 旧数组的容量 * 2// 新的容量 最大容量 旧的容量 初始默认的容量(16), 这种情况下设置新的负载 旧的 * 2// 那么就存在旧的容量为 2, 4, 8 三种情况, 没有走到下面的 newThr old 1, 那么新的阈值为 0 // oldCap DEFAULT_INITIAL_CAPACITY, 新的阈值什么不是无条件的等于旧的阈值的 2 倍// 而是只有在 oldCap DEFAULT_INITIAL_CAPACITY, 新的阈值才会是旧阈值的 2 倍// 而如果 oldCap 为 2, 4, 8, 则新的阈值为 0, 需要到下面的新的阈值 0 的判断进行处理, 具体的分析看下面的备注 1} else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY)newThr oldThr 1;} else if (oldThr 0)// 当旧的阈值大于 0, 设置新的容量 阈值// 能够走到这一步的情况有: // 1. 我们初始时, 只指定了容量, 然后第一次往里面加数据// 2. 初始时, 只传递了一个 Map, 然后第一次把 Map 里面的数据放到当前 HashMap 时// 新的容量 当前的阈值 threshold, 因为在声明 HashMap 时, 会临时将容量存储到 threshold, 直接赋值过来就是需要的容量了newCap oldThr;else { // 当我们创建时, 没有指定容量时, 在第一次放数据, 会走这一步// 这里将需要的容量的设置为默认值 16, 新的阈值为 16 * 0.75newCap DEFAULT_INITIAL_CAPACITY;newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}// 新的阈值为 0 if (newThr 0) {// 一般情况下阈值 新容量 * 0.75, 如果数组的容量达到了最大容量, 则直接设置为 int 的最大值// 这里新的阈值为 0, 能够走到这一步的情况有:// 1. 我们初始时, 只指定了容量, 然后第一次往里面加数据// 2. 初始时, 只传递了一个 Map, 然后第一次把 Map 里面的数据放到当前 HashMap 时// 3. 扩容时, 旧的容量为 2/4/8 中的一个, 那么 newThr 也是 0, 需要结合上面的扩容的 oldCap DEFAULT_INITIAL_CAPACITY 进行分析// 计算理论的阈值 新的容量 * 负载因子float ft (float)newCap * loadFactor;// 新的容量 最大值 理论的阈值 最大值 ? 新的阈值 计算出来的阈值 : 新的阈值 int 的最大值// 这里个人感觉有点问题, 具体看下面的 备注 2newThr (newCap MAXIMUM_CAPACITY ft (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);}// 设置新的阈值threshold newThr;// 声明新的数组, 用于存储数据NodeK,V[] newTab (NodeK,V[])new Node[newCap];// HashMap 中的数组引用修改为新声明的数组table newTab;// 数组 重新赋值if (oldTab ! null) {// 遍历旧数组的每一项for (int j 0; j oldCap; j) {NodeK,V e;// 获取到当前数组的第 j 个元素if ((e oldTab[j]) ! null) {第 j 个元素不为 null, 表示有数据, 需要进行迁移// 旧数组的 j 位置的值设置为空, 方便垃圾回收oldTab[j] null;if (e.next null)// 如果 e.next 为空, 则代表旧数组的该位置只有 1 个节点, 那么把这个节点直接放到新数组里面, 就行了// 通过 (节点 的 hash 值 新容量 -1 ) 取到新的位置newTab[e.hash (newCap - 1)] e;else if (e instanceof TreeNode)// 原本的这个节点为树节点, 调用 TreeNode 的 split 进行处理((TreeNodeK,V)e).split(this, newTab, j, oldCap);else {// 到了这一步, 说明当前位置存储的是一个 链表, 同时链表的数据存在 2 个以上// 声明了2 个链表, lo 链表, hi 链表, 这 4 个指针, 分别指向了 2 个链表的头和尾 // 其中的 lo 可以理解为 low, 地位链表, hi 为 hight, 高维链表, // 新的数组的容量是是原来的2倍, 那么 原来的一倍 可以理解为 low, 扩充出来的为 hight// 原本在同一个链表上的节点, 转移到扩容后的数组式, 只可能会被分配到 2 个位置, 和原来一样的位置 或者原来的位置 oldCap 的位置, 看下面的备注 3 // lo 链表存放的是节点位置不需要修改的节点, hi 就是存储位置变为 原来位置 oldCap 的节点NodeK,V loHead null, loTail null;NodeK,V hiHead null, hiTail null;NodeK,V next;do {// 遍历 j 位置上的链表// 临时保存下一个节点next e.next;// 当前节点的 hash 值 与上旧的容量值等于 0, 那么可以确定这个节点在新数组的位置和原来的一样// 先将其放到低维的链表, 后面在把低维的链表放到新数组的对应位置if ((e.hash oldCap) 0) {if (loTail null)// 如果loTail为空, 代表该节点为第一个节点loHead e;else// 否则将节点添加在链表的尾部loTail.next e; // 重新设置尾结点loTail e;} else { // 不等于 0, 表示这个节点需要存放到新的位置, 先放到高维链表if (hiTail null)// 作用同上面hiHead e;elsehiTail.next e;hiTail e;}} while ((e next) ! null);if (loTail ! null) {// 设置数组的 j 位置为 lo 链表loTail.next null;newTab[j] loHead;}if (hiTail ! null) {// 设置数组的 j oldCap 为 hi链表hiTail.next null;newTab[j oldCap] hiHead;}} }}}// 返回新数组return newTab;}/*** 将指定的位置转为树* 在 putVal 时, 如果发现链表的长度大于 8 了, 就会调用这个方法, 将链表变为链表*/final void treeifyBin(NodeK,V[] tab, int hash) {int n, index; NodeK,V e;// 注意这里: 数组为空, 或者长度还不够 64, 进行扩容, 不进行转换操作// 所以链表转为红黑树的还有一个大前提: 当前 HashMap 中存储数据的数组的长度要大于 64, 而不是链表的长度大于 8 就树化if (tab null || (n tab.length) MIN_TREEIFY_CAPACITY)resize();// 需要处理的位置的链表不为 nullelse if ((e tab[index (n - 1) hash]) ! null) {TreeNodeK,V hd null, tl null;do {// 因为 TreeNode 继承了 Node, 所以 TreeNode 也可以当做链表使用// 将 Node 转为 TreeNode// 然后将下面拼接成一个以 TreeNode 为类型的链表TreeNodeK,V p replacementTreeNode(e, null);if (tl null)// 树的根节点hd p;else {// 按照链表的格式, 改变节点的指向, p.prev tl;tl.next p;}tl p;} while ((e e.next) ! null);// 重新将当前节点头结点设置为树的根节点if ((tab[index] hd) ! null)// 转为树hd.treeify(tab);}}
}4.1.1 备注 1
在 resize 方法中, 旧数组已有数据了, 但是在进行扩容时, 容量默认是 2 倍扩展, 但是阈值只有在 oldCap DEFAULT_INITIAL_CAPACITY 时才会进行 2 倍扩展, 否则是为新的容量 * 负载因子。 原因: 为了在容量少的情况下, 尽可能的利用数组的空间, 不造成浪费。
假设我们在初始时, 指定了容量为 2, 那么在初始后容量值为 2, 阈值为 2 * 0.75 1。
第一次扩容:
旧的容量新的容量旧的阈值经过运算新的阈值旧阈值 12412新容量 × 0.752413
第一次扩容:
旧的容量新的容量旧的阈值经过运算新的阈值旧阈值 14824新容量 × 0.754836
第三次扩容
旧的容量新的容量旧的阈值经过运算新的阈值旧阈值 181648新容量 × 0.75816612
第四次扩容
旧的容量新的容量旧的阈值经过运算新的阈值旧阈值 11632816新容量 × 0.7516321224
通过上面可以发现: 在旧容量 16 之间变化时, 通过新容量 × 负载因子, 阈值会大一些, 可以更充分的利用数组的空间, 在第四次扩容时, 新容量为 32 时, 旧的阈值为 12, 这时 12 1 等于 32 * 0.75, 所以 2 者后续的计算是一样的, 通过位运算比较快。
可以简单理解为: 阈值一直都是等于当前的容量 * 负载因子, 在旧容量为 2, 4, 8 按照上面的方式计算。 到了就容量 16 时, 可以通过位运算达到同样的计算效果, 使用位运算更快
4.1.2 备注 2 final NodeK,V[] resize() {NodeK,V[] oldTab table;int oldCap (oldTab null) ? 0 : oldTab.length;int oldThr threshold;int newCap, newThr 0;if (oldCap 0) {if (oldCap MAXIMUM_CAPACITY) {threshold Integer.MAX_VALUE;return oldTab;// 步骤 1 } else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY)newThr oldThr 1;} else if (oldThr 0)// 省略else { // 省略}if (newThr 0) {// 步骤 2float ft (float)newCap * loadFactor;// 步骤 3newThr (newCap MAXIMUM_CAPACITY ft (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);}// 设置新的阈值threshold newThr;
}上面的阈值的计算一般情况下是没问题的, 但是在容量从 2^29 到最大值 2^30 扩容时, 按照上面的步骤 走到步骤 1 时, 容量变为原来的 2 倍, newCap MAXIMUM_CAPACITY, 这时 newCap MAXIMUM_CAPACITY, 不满足条件, 所以 newThr 还是 0到了步骤 2 时, 计算出来的 ft newCap * loadFactor, loadFactory 一般都是大于 0, 小于 1 的数, 所以 ft newCap MAXIMUM_CAPACITY, 既 ft MAXIMUM_CAPACITY到了步骤 3 时, new MAXIMUM_CAPACITY MAXIMUM_CAPACITY 为 false, false true false经过步骤 3 后, newThr 直接变为 int.max_value, 正常应该是 newCap * loadFactor, 下次扩容时, 到达上面的旧容量 MAXIMUM_CAPACITY, 再把阈值修改为 int.max_value 上面的分析都是基于负载因子大于 0, 小于 1 的情况的分析, 如果用户将负载因子设置为大于 1 的情况, 可能导致步骤 2 计算出来的 ft 为 负数。 所以可以将上面的步骤 1 修改为 MAXIMUM_CAPACITY 或者步骤 3 修改为 MAXIMUM_CAPACITY
4.1.3 备注 3
(e.hash oldCap) 0 可以判断节点在新数组的位置和旧数组的是否一样, 很巧妙的利用了数组的长度为 2 的 n 次方这个特性。 也就是 HashMap 中数组的容量是 2 的 n 次方的第二个作用。
能达到这样的效果的必须知道: oldCap 是 2 ^ n, newCap 是 在 oldCap 的基础 * 2, 也就是 newCap 是 2 ^ (n 1)2 ^ n 在二进制的表示为 1 n 个 0 , 2 ^ (n 1) 二进制表示 1 ( n 1 ) 个 02 ^ n - 1 在二进制的表示为 n 个 1, 那么 2 ^ (n 1) 就是 n 1 个 1(2 ^ n - 1) hash, 我们只需要取 hash 的从右到左的 1 到 n 位就行了, 因为 2 ^ n - 1 前面都是 0, 上都是 0 我们假设有个节点 A, 其 现在在数组中的 index 位置, 现在 oldCap 是 16, 既 2^4, 16 - 1 15, 二进制表示为 00000000 00000000 00000000 00001111
这时候 index hash (16 - 1), index 的值自然就是只和 hash 值的低 4 位有关, 我们假设它为 abcd
oldCap 扩大了一倍, 当前节点的的位置 index 的计算公式 (32-1) hash, 和 hash 值的低 5 位有关, hash 的低 5 位的值无外乎下面两种情况: 0abcd 或者 1abcd
0abcd index, 而 1abcd 0abcd 10000 0abcd oldCap index oldCap, 从这里可以知道容量扩大了一倍, 那么新的 index 是有规律的, 要么不变, 要么就是 index oldCap
新旧 index 是否一致就体现在 hash 值的第 5 位, 那么第 5 位怎么知道呢 32 的 2^n 的二进制形式 1 5 个 0, 那么 hash oldCap 就能知道 hash 的第 5 位是 0 或者 1 了, 既 hash oldCap 0, hash 的第 5 位为 0, hash oldCap 不等于 0, hash 的第 5 位为 1。
最终可以通过 hash oldCap 得到 hash oldCap 0 当前节点在数组的位置不用变hash oldCap ! 0 当前节点在新数组的 index oldCap 的位置 4.2 其他添加数据的方式 直接添加一个 Map 的 putAll(MapK, V map);添加一个元素, 如果对应的位置已经有数据了, 则不添加 putIfAbsent(K key, V value) 4.3 获取数据
public class HashMapK, V {/** * 通过 key 获取 value, 如果节点为 null, 返回 nulL*/public V get(Object key) {NodeK,V e;return (e getNode(hash(key), key)) null ? null : e.value;}/*** 通过 key 的 hash 值和 key 值获取 value 值*/final NodeK,V getNode(int hash, Object key) {NodeK,V[] tab; NodeK,V first, e; int n; K k;// 数组不为空, 长度大于 0, 链表的第一个节点 不为 nullif ((tab table) ! null (n tab.length) 0 (first tab[(n - 1) hash]) ! null) {// 第一个节点的 hash 值和传入的 hash 值一样, key 值也一样, 第一个节点符合条件了, 直接返回if (first.hash hash ((k first.key) key || (key ! null key.equals(k))))return first;// 链表有下一个节点 if ((e first.next) ! null) {// 树节点, 转换为树节点进行处理if (first instanceof TreeNode)return ((TreeNodeK,V)first).getTreeNode(hash, key);do {// 遍历 链表的其他节点,if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))return e;} while ((e e.next) ! null);}}return null;}
}4.4 删除数据
public class HashMapK, V {/*** 直接通过 key删除*/public V remove(Object key) {NodeK,V e;return (e removeNode(hash(key), key, null, false, true)) null ? null : e.value;}/*** 删除节点* matchValue : 为 true, 找到了节点, 还会比较他们的值, 值相同才会删除* movable : 针对红黑树起作用, 为 false, 节点删除了, 不改变其他节点的位置*/final NodeK,V removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {// 数组不为 null, 长度大于 0, 同时定位到的位置不为 nullif ((tab table) ! null (n tab.length) 0 (p tab[index (n - 1) hash]) ! null) {NodeK,V node null, e; K k; V v;// 链表的第一个节点符合了条件if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))node p;// 链表的下一个节点不为nullelse if ((e p.next) ! null) { // 节点为 树节点if (p instanceof TreeNode)node ((TreeNodeK,V)p).getTreeNode(hash, key);else {// 遍历链表do {// 寻找找到符合条件if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) {node e;break;}p e;} while ((e e.next) ! null);} }// 找到了需要删除的节点, 如果设置了需要检查值, 后面会对其值的内存地址和 equals 进行比较 if (node ! null (!matchValue || (v node.value) value || (value ! null value.equals(v)))) {if (node instanceof TreeNode)// 调用红黑树的删除节点的方法((TreeNodeK,V)node).removeTreeNode(this, tab, movable);else if (node p)// 把链表的头部直接指向了下一个节点tab[index] node.next;else// p 在上面的链表的遍历中, 变成需要删除的节点的前一个节点了// p 的下一个节点指向需要删除节点的下一个节点p.next node.next;modCount;--size;// 空方法afterNodeRemoval(node);return node; }}}
}上面只是通过 key 进行删除数据的, 同样还有一个通过 key 和 value 值都相同的情况进行删除的方法。
4.5 修改数据
public class HashMapK, V {public boolean replace(K key, V oldValue, V newValue) {NodeK,V e; V v;// 通过 getNode 获取到对应的节点, 节点的值等于入参的 oldValueif ((e getNode(hash(key), key)) ! null ((v e.value) oldValue || (v ! null v.equals(oldValue)))) {// 替换节点的 value 值等于入参的新 valuee.value newValue;afterNodeAccess(e);return true;}return false;}
}5 HashMap 的补充 HashMap 同样是线程不安全的, 如果需要线程安全, 同样可以通过 Collections.synchronizedMap() 获取到一个线程安全的实现类。HashMap 支持 fail-fast 机制HashMap 的序列化也是自定义的HashMap 内部提供了许多迭代器: KeyIterator, ValueIterator, EntryIterator, 方便各种遍历需求HashMap 的线程不安全, 猜测时, 同时有 2 个线程判断到需要扩容了, 然后同时进行扩容, 期间就可能造成闭合的链路。 6 红黑树相关的内容 清晰理解红黑树的演变—红黑的含义 红黑树的前身教你初步了解红黑树 红黑树的节点插入红黑树之删除节点 红黑树的节点删除红黑树原理以及插入、删除算法 附图例说明 里面的增删图片不错 7 参考
Java集合: HashMap详解 (JDK 1.8) 深入理解HashMap(四): 关键源码逐行分析之resize扩容
