大气手机网站模板免费下载,军事网站模板下载,优惠活动制作网站,内网建站软件前言 之前读过一些类的源码#xff0c;近来发现都忘了#xff0c;再读一遍整理记录一下。这次读的是 JDK 11 的代码#xff0c;贴上来的源码会去掉大部分的注释, 也会加上一些自己的理解。 Map 接口 这里提一下 Map 接口与1.8相比 Map接口又新增了几个方法#xff1a; … 前言 之前读过一些类的源码近来发现都忘了再读一遍整理记录一下。这次读的是 JDK 11 的代码贴上来的源码会去掉大部分的注释, 也会加上一些自己的理解。 Map 接口 这里提一下 Map 接口与1.8相比 Map接口又新增了几个方法 这些方法都是包私有的static方法of()方法分别返回包含 0 - 9 个键值对的不可修改的MapofEntries()方法返回包含从给定的entries总提取出来的键值对的不可修改的* Map不会包含给定的entriesentry()方法返回包含键值对的不可修改的 Entry不允许 null 作为 key 或 valuecopyOf()返回一个不可修改的包含给定 Map 的 entries 的 Map 调用了ofEntries()方法.数据结构 HashMap 是如何存储键值对的呢? HashMap 有一个属性 table: transient NodeK,V[] table; table 是一个 Node 的数组, 在首次使用和需要 resize 时进行初始化; 这个数组的长度始终是2的幂, 初始化时是0, 因此能够使用位运算来代替模运算. HashMap的实现是装箱的(binned, bucketed), 一个 bucket 是 table 数组中的一个元素, 而 bucket 中的元素称为 bin . 来看一下 Node , 很显然是一个单向链表: static class NodeK,V implements Map.EntryK,V {final int hash;final K key;V value;NodeK,V next;...
} 当然, 我们都知道 bucket 的结构是会在链表和红黑树之间相互转换的: // 转换成红黑树
if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);// 转换成链表结构
if (lc UNTREEIFY_THRESHOLD)tab[index] loHead.untreeify(map); 注意在 treeifyBin() 方法中: // table 为 null 或者 capacity 小于 MIN_TREEIFY_CAPACITY 会执行 resize() 而不是转换成树结构
if (tab null || (n tab.length) MIN_TREEIFY_CAPACITY)resize(); TreeNode 的结构和 TreeMap 相似, 并且实现了 tree 版本的一些方法: static final class TreeNodeK,V extends LinkedHashMap.EntryK,V {TreeNodeK,V parent; // red-black tree linksTreeNodeK,V left;TreeNodeK,V right;TreeNodeK,V prev; // needed to unlink next upon deletionboolean red;...
} initialCapacity 和 loadFactor 先看一下 HashMap 的4个构造器可以发现3个重要的 int thresholdinitialCapacity 和 loadFactor 其中 threshold 和 loadFactor 是 HashMap 的私有属性。 HashMap 的 javadoc 中有相关的解释 capacityHashMap 的哈希表中桶的数量initial capacity 哈希表创建时桶的数量load factor 在 capacity 自动增加(resize())之前哈希表允许的填满程度threshold下一次执行resize()时 size 的值 (capacity * load factor)如果表没有初始化存放的是表的长度为0时表的长度将会是 DEFAULT_INITIAL_CAPACITY 。 注意: 构造器中的 initialCapacity 参数并不是 table 的实际长度, 而是期望达到的值, 实际值一般会大于等于给定的值. initialCapacity 会经过tableSizeFor() 方法, 得到一个不大于 MAXIMUM_CAPACITY 的足够大的2的幂, 来作为table的实际长度: static final int tableSizeFor(int cap) {int n -1 Integer.numberOfLeadingZeros(cap - 1);return (n 0) ? 1 : (n MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n 1;
} loadFactor 的默认值是 0.75f static final float DEFAULT_LOAD_FACTOR 0.75f; initialCapacity 的默认值是16 static final int DEFAULT_INITIAL_CAPACITY 1 4; // aka 16 capacity 的最大值是1073741824 static final int MAXIMUM_CAPACITY 1 30; 在 new 一个 HasMap 时应该根据 mapping 数量尽量给出 initialCapacity , 减少表容量自增的次数 . putMapEntries() 方法给出了一种计算 initialCapacity 的方法: float ft ((float)s / loadFactor) 1.0F;
int t ((ft (float)MAXIMUM_CAPACITY) ?(int)ft : MAXIMUM_CAPACITY);
if (t threshold)threshold tableSizeFor(t); 这段代码里的 t 就是 capacity . hash() 方法 hash() 是 HashMap 用来计算 key 的 hash 值的方法, 这个方法并不是直接返回 key 的 hashCode() 方法的返回值, 而是将 hashCode 的高位移到低位后 再与原值异或. static final int hash(Object key) {int h;return (key null) ? 0 : (h key.hashCode()) ^ (h 16);
} 因为 HashMap 用 hash (table.length-1)代替了 模运算 , 如果直接使用 hashCode() 的返回值的话, 只有hash code的低位(如果 table.length 是2的n次方, 只有最低的 n - 1 位)会参加运算, 高位即使发生变化也会产生碰撞. 而 hash() 方法把 hashCode 的高位与低位异或, 相当于高位也参加了运算, 能够减少碰撞. 举个例子: 假设 table.length - 1 的 值为 0000 0111, 有两个hash code : 0001 0101 和 0000 0101. 这两个hash code 分别与 table.length - 1 做与运算之后的结果是一样的: 0000 0101; 将这两个hash code 的高位和低位异或之后分别得到: 0001 0100、 0000 0101, 此时再分别与 table.length - 1 做与运算的结果是 0000 0100 和 0000 0101, 不再碰撞了. resize() resize() 方法负责初始化或扩容 table. 如果 table 为 null 初始化 table 为 一个长度为 threshold 或 DEFAULT_INITIAL_CAPACITY的表; 否则将 table 的长度加倍, 旧 table 中的元素要么呆在原来的 index 要么以2的幂为偏移量在新 table中移动: 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) {// 旧 table 的容量已经达到最大, 不扩容, 返回旧表threshold Integer.MAX_VALUE;return oldTab;}else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY)// 将旧容量加倍作为新表容量, 如果新表容量没达到容量最大值, 并且旧容量大于等于默认容量, threshold 加倍newThr oldThr 1; // double threshold}else if (oldThr 0) // initial capacity was placed in threshold// 旧的threshold 不为 0 , 旧 threshold 作为新表的容量newCap oldThr;else { // zero initial threshold signifies using defaults// 旧 threshold 为 0 , 用 DEFAULT_INITIAL_CAPACITY 作为新容量, 用默认值计算新 thresholdnewCap DEFAULT_INITIAL_CAPACITY;newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}if (newThr 0) {// 之前没有计算过新 threshold , 计算 thresholdfloat ft (float)newCap * loadFactor;newThr (newCap MAXIMUM_CAPACITY ft (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold newThr;SuppressWarnings({rawtypes,unchecked})// 创建新表数组, 更新表引用NodeK,V[] newTab (NodeK,V[])new Node[newCap];table newTab;if (oldTab ! null) {// 将旧表中的元素移动到新表for (int j 0; j oldCap; j) {// 遍历旧表NodeK,V e;if ((e oldTab[j]) ! null) {// 帮助 GColdTab[j] null;if (e.next null)// 这个桶里只有一个元素, 此处用位运算代替了模运算newTab[e.hash (newCap - 1)] e;else if (e instanceof TreeNode)// 如果这个 bucket 的结构是树, 将这个 bucket 中的元素分为高低两部分((e.hash bit) 0 就分在低的部分, bit 是 oldCap), 低的部分留在原位, 高的部分放到 newTab[j oldCap]; 如果某一部分的元素个数小于 UNTREEIFY_THRESHOLD 将这一部分转换成链表形式, 否则就形成新的树结构((TreeNodeK,V)e).split(this, newTab, j, oldCap);else { // preserve order// 将普通结构的 bucket 中的元素分为高低两部分, 低的部分留在原位, 高的部分放到 newTab[j oldCap]NodeK,V loHead null, loTail null;NodeK,V hiHead null, hiTail null;NodeK,V next;do {next e.next;if ((e.hash oldCap) 0) {if (loTail null)loHead e;elseloTail.next e;loTail e;}else {if (hiTail null)hiHead e;elsehiTail.next e;hiTail e;}} while ((e next) ! null);if (loTail ! null) {loTail.next null;newTab[j] loHead;}if (hiTail ! null) {hiTail.next null;newTab[j oldCap] hiHead;}}}}}return newTab;
} 举个例子解释一下高低两部分的划分: 扩容前 table.length 是 0000 1000 记为 oldCap , table.length - 1 是 0000 0111 记为 oldN;扩容后 table.length 是 0001 0000 记为 newCap, table.length - 1 为 0000 1111 记为 newN;有两个Node, hash ( hash() 方法得到的值)分别为 0000 1101 和 0000 0101 记为 n1 和 n2; 在扩容前, n1 和 n2 显然是在一个 bucket 里的, 但在扩容后 n1 newN 和 n2 newN 的值分别是 0000 1101 和 0000 0101, 这是需要划分成两部分, 并且把属于高部分的 bin 移动到新的 bucket 里的原因. 扩容后, hash 中只会有最低的4位参加 index 的计算, 因此可以用第4位来判断属于高部分还是低部分, 也就可以用 (hash oldCap) 0 来作为属于低部分的依据了. 查找 查找方法只有 get() 和 getOrDefault() 两个, 都是调用了 getNode()方法: public V get(Object key) {NodeK,V e;return (e getNode(hash(key), key)) null ? null : e.value;
}Override
public V getOrDefault(Object key, V defaultValue) {NodeK,V e;return (e getNode(hash(key), key)) null ? defaultValue : e.value;
} getNode() 方法 final NodeK,V getNode(int hash, Object key) {NodeK,V[] tab; NodeK,V first, e; int n; K k;if ((tab table) ! null (n tab.length) 0 (first tab[(n - 1) hash]) ! null) {// table 已经被初始化且 table 的长度不为 0 且 对应的 bucket 里有 binif (first.hash hash // always check first node((k first.key) key || (key ! null key.equals(k))))// 第一个节点的 key 和 给定的 key 相同return first;if ((e first.next) ! null) {// bucket 中还有下一个 binif (first instanceof TreeNode)// 是树结构的 bucket, 调用树版本的 getNode 方法return ((TreeNodeK,V)first).getTreeNode(hash, key);do {// 在普通的链表中查找 keyif (e.hash hash ((k e.key) key || (key ! null key.equals(k))))return e;} while ((e e.next) ! null);}}return null;
} 遍历 可以通过entrySet()、keySet()、values()分别获得 EntrySet、KeySet()和Values对象, 他们的迭代器都是HashIterator的子类. fast-fail 和 modCount HashMap 不是线程安全的, 并且实现了 fast-fail 机制. 当一个迭代器被创建的时候(或者迭代器自身的 remove() 方法被调用), 会记录当前的 modCount 作为期待中的 modCount, 并在操作中先检查当前 modCount 是不是和旧的 modCount 相同, 不同则会抛出ConcurrentModificationException. 任何结构修改(新增或删除节点)都会改变 modCount 的值. 新增和更新 1.8 之前有4个方法和构造器能够往 HashMap 中添加键值对: 以一个Map为参数的构造器、put()、putAll()、putIfAbsent(), public HashMap(Map? extends K, ? extends V m) {this.loadFactor DEFAULT_LOAD_FACTOR;putMapEntries(m, false);
}public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}public void putAll(Map? extends K, ? extends V m) {putMapEntries(m, true);
}Override
public V putIfAbsent(K key, V value) {return putVal(hash(key), key, value, true, true);
} 他们分别调用了putMapEntries()和putVal(). 这两个方法中有一个参数 evict , 仅当初始化时(构造器中)为 false. putVal() 方法 来看一下putVal() 方法: final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {NodeK,V[] tab; NodeK,V p; int n, i;if ((tab table) null || (n tab.length) 0)// table 未被初始化或者长度为 0 时, 执行 resize()n (tab resize()).length;if ((p tab[i (n - 1) hash]) null)// 对应的 bucket 里没有元素, 新建一个普通 Node 放到这个位置tab[i] newNode(hash, key, value, null);else {NodeK,V e; K k;if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))// 第一个节点的 key 和 给定的 key 相同e p;else if (p instanceof TreeNode)// 树结构, 调用树版本的 putVal, 如果树结构中存在 key, 将会返回相应的 TreeNode, 否则返回 nulle ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value);else {for (int binCount 0; ; binCount) {if ((e p.next) null) {// 在链表中没有找到 key, 新建一个节点放到链表末尾p.next newNode(hash, key, value, null);if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1st// 当前桶转换成树结构treeifyBin(tab, hash);break;}if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))// key 相同 breakbreak;p e;}}if (e ! null) { // existing mapping for key// key 在 map 中存在V oldValue e.value;if (!onlyIfAbsent || oldValue null)// 覆盖旧值e.value value;afterNodeAccess(e);return oldValue;}}// key 之前在 map 中不存在, 发生了结构变化, modCount 增加 1modCount;if (size threshold)// 扩容resize();afterNodeInsertion(evict);return null;
} HashMap 提供了三个回调方法: void afterNodeAccess(NodeK,V p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(NodeK,V p) { } putMapEntries() 方法 putMapEntries()方法就简单多了 final void putMapEntries(Map? extends K, ? extends V m, boolean evict) {int s m.size();if (s 0) {if (table null) { // pre-size// table 还没有初始化, 计算出 thresholdfloat ft ((float)s / loadFactor) 1.0F;int t ((ft (float)MAXIMUM_CAPACITY) ?(int)ft : MAXIMUM_CAPACITY);if (t threshold)threshold tableSizeFor(t);}else if (s threshold)// s 超过了 threshold, 扩容resize();for (Map.Entry? extends K, ? extends V e : m.entrySet()) {// 调用 putVal() 方法, 将键值对放进 mapK key e.getKey();V value e.getValue();putVal(hash(key), key, value, false, evict);}}
} 删除 删除元素有三个方法, 还有 EntrySet 和 KeySet 的 remove 和 clear 方法: public V remove(Object key) {NodeK,V e;return (e removeNode(hash(key), key, null, false, true)) null ?null : e.value;
}Override
public boolean remove(Object key, Object value) {return removeNode(hash(key), key, value, true, true) ! null;
}public void clear() {NodeK,V[] tab;modCount;if ((tab table) ! null size 0) {size 0;for (int i 0; i tab.length; i)tab[i] null;}
} removeNode() 方法 removeNode() 方法有5个参数, 说明一下其中两个: matchValue 为 true 时, 只在 value 符合的情况下删除;movable 为 false 时, 删除时不移动其他节点, 只给树版本的删除使用. final NodeK,V removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) {NodeK,V[] tab; NodeK,V p; int n, index;if ((tab table) ! null (n tab.length) 0 (p tab[index (n - 1) hash]) ! null) {// table 已经被初始化且 table 的长度不为 0 且 对应的 bucket 里有 binNodeK,V node null, e; K k; V v;if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))// 第一个的 key 和给定的 key 相同node p;else if ((e p.next) ! null) {// bucket 中有不止一个 binif (p instanceof TreeNode)// 树结构, 调用树版本的 getNodenode ((TreeNodeK,V)p).getTreeNode(hash, key);else {// 在普通的 bucket 中查找 nodedo {if (e.hash hash ((k e.key) key ||(key ! null key.equals(k)))) {node e;break;}p e;} while ((e e.next) ! null);}}if (node ! null (!matchValue || (v node.value) value ||(value ! null value.equals(v)))) {// 找到了 node , 并且符合删除条件if (node instanceof TreeNode)// 树结构, 调用树版本的 removeNode , 如果节点过少, 会转换成链表结构((TreeNodeK,V)node).removeTreeNode(this, tab, movable);else if (node p)// node 是链表的第一个元素tab[index] node.next;else// 不是第一个元素p.next node.next;// 结构变化 modCount 1modCount;--size;afterNodeRemoval(node);return node;}}return null;
} 总结 HashMap 是一个基于哈希表的装箱了的 Map 的实现; 它的数据结构是一个桶的数组, 桶的结构可能是单向链表或者红黑树, 大部分是链表.table 的容量是2的幂, 因此可以用更高效的位运算替代模运算.HashMap 使用的 hash 值, 并不是 key 的 hashCode()方法所返回的值, 详细还是看上面吧.一个普通桶中的 bin 的数量超过 TREEIFY_THRESHOLD, 并且 table 的容量大于 MIN_TREEIFY_CAPACITY, 这个桶会被转换成树结构; 如果 bin 数量大于TREEIFY_THRESHOLD , 但 table 容量小于 MIN_TREEIFY_CAPACITY, 会进行扩容.每次扩容新 table 的容量是老 table 的 2 倍.扩容时, 会将原来下标为 index 的桶里的 bin 分为高低两个部分, 高的部分放到 newTab[index oldCap] 上, 低的部分放在原位; 如果某部分的 bin 的个数小于 UNTREEIFY_THRESHOLD 树结构将会转换成链表结构. 转自https://www.cnblogs.com/FJH1994/p/10227048.html 转载于:https://www.cnblogs.com/hujunzheng/p/10231097.html
