手机开发网站工具,通辽住房和城乡建设厅网站,家庭千兆网络组建方案,外贸网站商城类描述
基于Hash表的Map接口实现。此实现提供了所有的可选的map操作#xff0c;并且避免了null值和null键。#xff08;HashMap类大体上等价于Hashtable,除了它是非同步的和禁止null#xff09;。此类不保证map的顺序。特别是#xff0c;不保证随着时间的变化顺序保持不变…类描述
基于Hash表的Map接口实现。此实现提供了所有的可选的map操作并且避免了null值和null键。HashMap类大体上等价于Hashtable,除了它是非同步的和禁止null。此类不保证map的顺序。特别是不保证随着时间的变化顺序保持不变。
假设hash功能将元素完全在bucket之中打散对于基本操作get和put此实现提供了常量时间的性能。在集合视图上进行迭代要求的时间与HashMap实例的“容量”(bucket的数量)加上它的大小key-value映射的数量成正比。因此如果迭代性能比较重要不要设置初始容量太高或者负载因子太低是非常重要的。
一个HashMap实例有两个参数影响它的性能初始容量和负载因子。容量是在哈希表中bucket的数量并且初始容量就是hash表创建时的容量。负载因子是衡量hash表在容量自动增加之前允许其达到多满的指标。当hash表中条目的数量超过当前容量和负载因子的乘积hash表重新rehash重新hash也就是说内部数据结构被重建所以hash表大约有两倍的bucket数量。
一般情况下默认的负载因子0.75在时间和空间消耗之间有很好的平衡。较高的值降低了空间负载但是增加了查询消耗在大多数的HashMap类的操作上都会影响包括get和put。当设置初始容量时应该考虑map中期望的条目数量和它的负载因子从而最小化重hash操作的数量。如果初始容量大于条目最大值数量除以负载因子不会有重hash操作发生。
如果许多映射已经在HashMap实例中存储使用足够大的容量创建它将允许比在随着table的增长所需让他执行自动化重刷更加高效的映射存储。注意使用许多相同的hashcode()的key肯定会降低任何hash表的性能。为减轻影响当key是Comparable的时类可以使用键之间的比较顺序来打破并列。
注意此实现不是同步的。 如果多个线程并发访问hash表至少有一个线程修改了map结构他必须在外部同步。一个结构化的修改可以是添加或者删除一个或者更多映射的任意操作仅仅修改已经在实例中存在的key的关联值不是结构修改。这通常是通过一些自然封装了map的对象上同步来完成的。如果没有这样的对象存在此map应该使用Collections.synchronizedMap方法封装。最好在创建时完成避免意外的对map的访问
Map m Collections.synchronizedMap(new HashMap(...));所有类的集合视图方法返回的迭代器是快速失败的如果在创建迭代器之后在任何时间结构被修改使用除了迭代器自己的remove方法的任何方法迭代器将抛出ConcurrentModificationException。这样在面对并发修改迭代器很快和干净地失败而不是冒着在未来任意时间段任意不确定行为的风险。
注意迭代器快速失败的行为是无法保证的通常来说存在不同步的并发修改时不可能作出任何硬保证。快速失败尽最大努力抛出ConcurrentModificationException。因此依赖这个异常写一个程序保证正确性是错误的迭代器的快速失败行为应该仅用于检测bug。
此类是Java集合框架成员。
实现注意事项
这个map通常扮演的是一个带有槽位的hash表但是当槽位太大时他们将被转为TreeNode的槽位每一个结构类似于java.util.TreeMap。大多数方法使用普通的槽位但在适时时转换为TreeNode方法仅仅通过instanceof一个节点检查。TreeNode的槽位就想其他任意节点遍历和使用但是当槽位过多时支持更快速的查找。但是因为大多数在正常使用的槽位没有过多使用因此在使用表方法的过程中对tree槽位的检查可能存在延迟。
tree槽位即所有的元素是TreeNode的槽位主要是按照hashCode排序但是在tie的情况下如果两个元素有相同的“class C implements Comparable”然后使用他们的compareTo方法排序我们通过反射检查泛型类型来进行验证–可以看方法comparableClassFor。当键具有不同的哈希值或可排序时树槽位增加的复杂性值得提供最差情况下O(log n)的操作。因此当hashCode()方法意外或恶意使用时性能会优雅地下降比如返回的值分布不均匀或者许多键共享一个哈希码只要它们是可比较的。如果两者都不适用与不采取预防措施相比我们可能会浪费大约2倍的时间和空间。但唯一已知的案例来自于糟糕的用户编程实践这些实践已经非常缓慢以至于没有什么区别。
因为TreeNode大概是常规节点的两倍我们只有在槽位足够多的节点时才使用请查看TREEIFY_THRESHOLD。当他们变得比较小时由于移除或者resize他们会被转换成普通的槽位。分布较好的用户hashCode在使用中tree binstree的槽位是很少使用的。理想情况下在随机hashCode下在槽位中节点的频率遵循泊松Poisson分布在默认的重新设置大小阈值为0.75时参数平均为0.5尽管由于调整粒度的不同方差很大。忽略方差k列表大小的期望出现次数是exp(-0.5) * pow(0.5, k) / factorial(k)第一个值是 0: 0.60653066 1: 0.30326533 2: 0.07581633 3: 0.01263606 4: 0.00157952 5: 0.00015795 6: 0.00001316 7: 0.00000094 8: 0.00000006 更多: 小于千万分之一
tree槽位的根节点通常是他的第一个节点。但是有时目前仅在Iteraotr.remove上执行根可以在其他地方但可以在父连接之后回复方法TreeNode.root()。
所有适当的内部方法接收一个hash code作为参数通常由公共方法提供允许他们互相调用无需重新计算用户hashCode。大多数内部方法也接受“tab”参数即当前的table当重新整理大小或者转换时可能是新的也有可能是老的。
当槽位已经变为tree分隔非tree的情况下我们保留他们相同的相对访问/遍历顺序即字段Node.next以便更好的保持局部性并略微简化调用对Iterator.remove的拆分和遍历的处理。当在插入使用比较器时为了在重新平衡时保持总的排序尽可能接近我们比较类和identityHashCodes作为决定因素。
由于子类LinkedHashMap的存在普通模式和树模式之间的使用和转换变得复杂。下面是定义在插入、删除和访问时调用的挂钩方法这些方法允许LinkedHashMap内部保持独立于这些机制。(这也需要将一个map实例传递给一些可以创建新节点的工具方法。)
类似于基于ssa的并发编程风格有助于避免所有弯曲指针操作中的混叠错误。
静态变量关于容量设计的字段
/**
* 默认的初始容量必须是2的幂
*/
static final int DEFAULT_INITIAL_CAPACITY 1 4; // aka 16 // 也就是16
/**
* 最大值容量如果任意一个带参数的构造器隐式指定则使用此值必须是2的幂
*/
static final int MAXIMUM_CAPACITY 1 30;
/**
* 当在构造器中没有指定时使用的负载因子
*/
static final float DEFAULT_LOAD_FACTOR 0.75f;
/**
* 使用树而不是列表的bin数量阈值。当元素添加到一个槽位时至少这些节点bins才会转为树。
* 该值必须大于2且至少为8以符合tree移除时关于收缩后转换为普通bins的假设。
*/
static final int TREEIFY_THRESHOLD 8;
/**
* 在resize期间非树化一个bin的bin数量阈值。
* 应该小于TREEIFY_THRESHOLD至多为6与移除操作下收缩检测配合。
*/
static final int UNTREEIFY_THRESHOLD 6;
/**
* 哪个bin可能被树化的最小table容量。
* 否则如果一个bin中太多节点table将resize
* 应该至少4 * TREEIFY_THRESHOLD来避免resize和树化阈值之间的冲突。
*/
static final int MIN_TREEIFY_CAPACITY 64;内部类-节点 /*** 基本的哈希bin节点用于大多数条目(看下面了解* TreeNode子类, 和LinkedHashMap的Entry子类)*/static class NodeK,V implements Map.EntryK,V {final int hash;final K key;V value;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;}public final K getKey() { return key; }public final V getValue() { return value; }public final String toString() { return key value; }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;return o instanceof Map.Entry?, ? e Objects.equals(key, e.getKey()) Objects.equals(value, e.getValue());}}静态工具-内部方法 /*** 计算key.hashCode()并将其hash的高位与地位对齐XOR方式. * 因为table使用了二幂码所以在当前掩码只有几bit变化的hash集总是冲突。* (在已知的示例中一组Float键在小表中保持连续的整数。) * 所以我们提供了一个转换将高比特的影响向下扩散。在比特传播的速度实用和质量之间进行权衡。 * 因为许多常用的hash集已经合理分布不会从传播中获益, * 并且因为我们在bin中使用了tree来处理大的冲突集, 我们只是使用最廉价的方式对一些偏移bit进行异或来减少系统损失, 并结合了高位的影响否则由于表边界的原因在索引计算中高位不会被使用。*/static final int hash(Object key) {int h;return (key null) ? 0 : (h key.hashCode()) ^ (h 16);}/*** 如果x是class C implements* ComparableC格式返回x的Class否则返回null。*/static Class? comparableClassFor(Object x) {if (x instanceof Comparable) {Class? c; Type[] ts, as; ParameterizedType p;if ((c x.getClass()) String.class) // bypass checksreturn c;if ((ts c.getGenericInterfaces()) ! null) {for (Type t : ts) {if ((t instanceof ParameterizedType) ((p (ParameterizedType) t).getRawType() Comparable.class) (as p.getActualTypeArguments()) ! null as.length 1 as[0] c) // type arg is creturn c;}}}return null;}/*** Returns k.compareTo(x) if x matches kc (ks screened comparable* class), else 0.* 如果x匹配kc则返回k.compareTo(x)(k是筛选过的可比较类),否则返回0.*/SuppressWarnings({rawtypes,unchecked}) // for cast to Comparablestatic int compareComparables(Class? kc, Object k, Object x) {return (x null || x.getClass() ! kc ? 0 :((Comparable)k).compareTo(x));}/*** 根据给定目标的容量返回2的幂大小往上ceil进位5变为8*/static final int tableSizeFor(int cap) {int n -1 Integer.numberOfLeadingZeros(cap - 1);return (n 0) ? 1 : (n MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n 1;}内部字段 /*** 在第一次使用时初始化当必要时resize。 当分配时长度一直是2的幂。* (我们也容许在一些启动机制并不需要的操作中长度为0)。*/transient NodeK,V[] table;/*** 持有缓存的entrySet(). 注意AbstractMap字段用于keySet()和values().*/transient SetMap.EntryK,V entrySet;/*** 在此map中包含的key-value映射的数量。*/transient int size;/*** HashMap已经被结构化修改的次数的数量。* 结构化修改就是那些HashMap中改变映射的数量或者他的内部结构的修改(比如,rehash)。* 此字段用于使在HashMap的集合视图快速失败(请查看ConcurrentModificationException)。*/transient int modCount;/*** 要进行resize(capacity * load factor)的阈值.* serial*/int threshold;/*** hash表的负载因子* serial*/final float loadFactor;公共方法 /*** 构造一个带有指定的初始容量和负载因子的空的HashMap* param initialCapacity 初始容量* param loadFactor 负载因子* throws IllegalArgumentException 如果初始容量是负数或者负载因子是非正数*/public HashMap(int initialCapacity, float loadFactor) {if (initialCapacity 0)throw new IllegalArgumentException(Illegal initial capacity: initialCapacity);if (initialCapacity MAXIMUM_CAPACITY)initialCapacity MAXIMUM_CAPACITY;if (loadFactor 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException(Illegal load factor: loadFactor);this.loadFactor loadFactor;this.threshold tableSizeFor(initialCapacity);}/*** 构造一个带有指定初始容量并且默认的负载因子0.75的空的HashMap。* param initialCapacity 初始容量.* throws IllegalArgumentException 如果初始容量是负数.*/public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);}/*** Constructs an empty {code HashMap} with the default initial capacity* (16) and the default load factor (0.75).*/public HashMap() {this.loadFactor DEFAULT_LOAD_FACTOR; // all other fields defaulted}/*** 构造一个与指定的Map相同的映射的HashMap。HashMap使用默认的负载因子创建。HashMap使用默认的负载因子创建0.75并且初始容量满足指定Map的映射。** param m 将映射放置到此map的map* throws NullPointerException 如果指定的map为空*/public HashMap(Map? extends K, ? extends V m) {this.loadFactor DEFAULT_LOAD_FACTOR;putMapEntries(m, false);}/*** 实现Map.putAll和Map构造器* param m the map* param evict 当初始化构造此map时为false其他则为true(与方法afterNodeInsertion相关).*/final void putMapEntries(Map? extends K, ? extends V m, boolean evict) {int s m.size();if (s 0) {if (table null) { // pre-sizefloat ft ((float)s / loadFactor) 1.0F;int t ((ft (float)MAXIMUM_CAPACITY) ?(int)ft : MAXIMUM_CAPACITY);if (t threshold)threshold tableSizeFor(t);} else {// 由于linked-list桶的限制我们不能一次全部扩展但是可以通过现在比以前的重复加倍// 减少重新扩容的工作量。while (s threshold table.length MAXIMUM_CAPACITY)resize();}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);}}}/*** 返回此map中key-value映射的数量* return 此map中key-value映射的数量*/public int size() {return size;}/*** 如果此map没有包含key-value映射返回true* return 如果此map没有包含key-value映射返回true*/public boolean isEmpty() {return size 0;}/*** 返回指定key映射的值如果map没有包含此key的映射则返回null。** 正式来说, 如果此映射中包含键k到值v的映射以至于keynull ? knull :* key.equals(k)然后此方法返回v否则返回null. (最多只有一个这样的映射.)* null的返回值并不是表示映射中不包含此key的映射它也可能此映射显性地将此key映射为null。* containKey操作可以用于识别这两种情况。* see #put(Object, Object)*/public V get(Object key) {NodeK,V e;return (e getNode(key)) null ? null : e.value;}/*** 实现Map.get和相关方法。* param key the key* return the node, or null if none*/final NodeK,V getNode(Object key) {NodeK,V[] tab; NodeK,V first, e; int n, hash; K k;if ((tab table) ! null (n tab.length) 0 (first tab[(n - 1) (hash hash(key))]) ! null) {if (first.hash hash // always check first node((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;}/*** 如果此映射包含指定key的映射则返回true。* param key 在此map中测试是否存在的key* return 如果此映射包含指定key的映射则返回true。* key.*/public boolean containsKey(Object key) {return getNode(key) ! null;}/*** 在此map中使用指定的key关联指定的值。如果此map先前包含此key的值则老值被替换。* param key 要与指定的value关联的key* param value 要与指定的key关联的value* return 此前与此key关联的value如果没有key的映射则返回null。如果返回null也可能表示此前关联了null。*/public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}/*** 实现Map.put和关联方法。* param hash key的hash* param key the key* param value 要放入的value* param onlyIfAbsent 如果是true不会修改存在的值* param evict 如果是falsetable在创建中* return 先前的值如果没有则返回null*/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)n (tab resize()).length;if ((p tab[i (n - 1) hash]) null)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))))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);if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))break;p e;}}if (e ! null) { // existing mapping for keyV oldValue e.value;if (!onlyIfAbsent || oldValue null)e.value value;afterNodeAccess(e);return oldValue;}}modCount;if (size threshold)resize();afterNodeInsertion(evict);return null;}/*** 初始化或者翻倍table大小。If null, allocates in* accord with initial capacity target held in field threshold.* Otherwise, because we are using power-of-two expansion, the* elements from each bin must either stay at same index, or move* with a power of two offset in the new table.** return the 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) {threshold Integer.MAX_VALUE;return oldTab;}// 新容量翻倍阈值翻倍else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY)newThr oldThr 1; // double threshold}// 老容量小于0阈值大于0则新容量等于老阈值else if (oldThr 0) // initial capacity was placed in thresholdnewCap oldThr;else { // zero initial threshold signifies using defaultsnewCap DEFAULT_INITIAL_CAPACITY;newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}// 重新计算阈值if (newThr 0) {float 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) {oldTab[j] null;if (e.next null)newTab[e.hash (newCap - 1)] e;else if (e instanceof TreeNode)((TreeNodeK,V)e).split(this, newTab, j, oldCap);else { // preserve order// 将此链表分为2个链表要么在原位置要么原位置oldCap,//其实e.nextnull里面的重新放置也可以使用此方法判断//https://segmentfault.com/a/1190000015812438地址有详细介绍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;}/*** 将所给定的hash的索引的bin中的链表节点替换*/final void treeifyBin(NodeK,V[] tab, int hash) {int n, index; NodeK,V e;// 如果小于最小树化大小则resizeif (tab null || (n tab.length) MIN_TREEIFY_CAPACITY)resize();else if ((e tab[index (n - 1) hash]) ! null) {TreeNodeK,V hd null, tl null;do {// 创建tree节点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);}}/*** Copies all of the mappings from the specified map to this map.* These mappings will replace any mappings that this map had for* any of the keys currently in the specified map.* 将指定的map的所有映射复制到此map。这些映射将替换在此map中有的在并且在指定map中已经存在的任何映射。* param m 在此map中将要存储的映射* throws NullPointerException if the specified map is null*/public void putAll(Map? extends K, ? extends V m) {putMapEntries(m, true);}/*** 如果指定的key存在的话从此map中移除映射。* param key 从此map中将要移除映射的key* return the previous value associated with {code key}, or* {code null} if there was no mapping for {code key}.* (A {code null} return can also indicate that the map* previously associated {code null} with {code key}.)*/public V remove(Object key) {NodeK,V e;return (e removeNode(hash(key), key, null, false, true)) null ?null : e.value;}/*** 实现Map.remove和相关方法。* param hash key的hash* param key the key* param value 如果matchValue等于true则用于匹配的值否则忽略* param matchValue 如果为true只有value相等才移除。* param movable 如果为false移除时不能移除其他节点。* return the node, or null if none*/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) {NodeK,V node null, e; K k; V v;if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))node p;else 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);}}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;elsep.next node.next;modCount;--size;afterNodeRemoval(node);return node;}}return null;}/*** 移除此表的所有映射。在此调用返回后map将是空的。*/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;}}/*** 如果map映射一个或者多个key到指定的值则返回true。* param value 在此map中测试是否存在的值* return 如果map映射一个或者多个key到指定的值则返回true* */public boolean containsValue(Object value) {NodeK,V[] tab; V v;if ((tab table) ! null size 0) {for (NodeK,V e : tab) {for (; e ! null; e e.next) {if ((v e.value) value ||(value ! null value.equals(v)))return true;}}}return false;}/*** 返回此map中包含的key集合视图。集合是通过map来支持的所以map的修改是反应到set反之亦然。* 如果在集合在迭代的过程中除了迭代器本身的移除操作map被修改那么结果是未定义的。* 此set支持元素移除其移除响应的map的映射通过Iterator.remove,Set.remove,removeAll,retainAll,clear操作。他不支持add或者addAll操作。* return 包含在此map中的key集合视图*/public SetK keySet() {SetK ks keySet;if (ks null) {ks new KeySet();keySet ks;}return ks;}/*** 准备Collection#toArray(Object[])实现的数组。* 如果提供的数组小于map的大小分配一个新的数组。* 如果提供的数组大于map的大小null将写在size大小的索引上。* param 传入到toArray()方法的一个原始数组。* param T 数组元素类型。* return 一个准备从toArray()方法填充和返回的数组。*/SuppressWarnings(unchecked)final T T[] prepareArray(T[] a) {int size this.size;if (a.length size) {return (T[]) java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);}if (a.length size) {a[size] null;}return a;}/*** 使用此map的key填充数组并返回它。此方法假设输入的数组是足够大来填充所有的key。使用prepareArray(Object[])来确认此事。* param a 一个要填充的数组* param T 数组元素的类型* return 提供的数组*/T T[] keysToArray(T[] a) {Object[] r a;NodeK,V[] tab;int idx 0;if (size 0 (tab table) ! null) {for (NodeK,V e : tab) {for (; e ! null; e e.next) {r[idx] e.key;}}}return a;}/*** 使用map的值填充到一个数组并返回它。此方法假设输入的数组足够大来满足所有的值。使用prepareArrayObject[])来确认此事。* param a 一个要填充的数组* param T 数组元素的类型* return 提供的数组*/T T[] valuesToArray(T[] a) {Object[] r a;NodeK,V[] tab;int idx 0;if (size 0 (tab table) ! null) {for (NodeK,V e : tab) {for (; e ! null; e e.next) {r[idx] e.value;}}}return a;}// 专门存放KeySet视图的内部类。final class KeySet extends AbstractSetK {public final int size() { return size; }public final void clear() { HashMap.this.clear(); }public final IteratorK iterator() { return new KeyIterator(); }public final boolean contains(Object o) { return containsKey(o); }public final boolean remove(Object key) {return removeNode(hash(key), key, null, false, true) ! null;}public final SpliteratorK spliterator() {return new KeySpliterator(HashMap.this, 0, -1, 0, 0);}public Object[] toArray() {return keysToArray(new Object[size]);}public T T[] toArray(T[] a) {return keysToArray(prepareArray(a));}public final void forEach(Consumer? super K action) {NodeK,V[] tab;if (action null)throw new NullPointerException();if (size 0 (tab table) ! null) {int mc modCount;for (NodeK,V e : tab) {for (; e ! null; e e.next)action.accept(e.key);}if (modCount ! mc)throw new ConcurrentModificationException();}}}/*** 返回在此map中包含的value的Collection视图。此集合是依据此map的所以对map的修改会反应到此集合中反之依然。* 如果当此集合在迭代过程中map被修改除了通过迭代器本身remove操作迭代的结果是不确定的。* 集合支持元素移除也会移除相应的map映射通过Iterator.remove,Set.remove,removeAll,retainAll,clear操作。他不支持add或者addAll操作。* return 一个在此map中包含的值的视图*/public CollectionV values() {CollectionV vs values;if (vs null) {vs new Values();values vs;}return vs;}// 专门存放value值的内部类final class Values extends AbstractCollectionV {public final int size() { return size; }public final void clear() { HashMap.this.clear(); }public final IteratorV iterator() { return new ValueIterator(); }public final boolean contains(Object o) { return containsValue(o); }public final SpliteratorV spliterator() {return new ValueSpliterator(HashMap.this, 0, -1, 0, 0);}public Object[] toArray() {return valuesToArray(new Object[size]);}public T T[] toArray(T[] a) {return valuesToArray(prepareArray(a));}public final void forEach(Consumer? super V action) {NodeK,V[] tab;if (action null)throw new NullPointerException();if (size 0 (tab table) ! null) {int mc modCount;for (NodeK,V e : tab) {for (; e ! null; e e.next)action.accept(e.value);}if (modCount ! mc)throw new ConcurrentModificationException();}}}/*** 返回一个在此map中包含的映射视图。* 此集合通过map支持所以对图的修改会反应到set反之依然。* 如果在set迭代处理的过程中map被修改除了迭代器自身的remove操作或者通过迭代器返回的map条目上的setValue操作。迭代的结果是不确定的。* 集合支持元素移除也会移除相应的map映射通过Iterator.remove,Set.remove,removeAll,retainAll,clear操作。他不支持add或者addAll操作。* return 一个此map中包含的映射的set视图。*/public SetMap.EntryK,V entrySet() {SetMap.EntryK,V es;return (es entrySet) null ? (entrySet new EntrySet()) : es;}// 专门存放EntrySet的方法final class EntrySet extends AbstractSetMap.EntryK,V {public final int size() { return size; }public final void clear() { HashMap.this.clear(); }public final IteratorMap.EntryK,V iterator() {return new EntryIterator();}public final boolean contains(Object o) {if (!(o instanceof Map.Entry?, ? e))return false;Object key e.getKey();NodeK,V candidate getNode(key);return candidate ! null candidate.equals(e);}public final boolean remove(Object o) {if (o instanceof Map.Entry?, ? e) {Object key e.getKey();Object value e.getValue();return removeNode(hash(key), key, value, true, true) ! null;}return false;}public final SpliteratorMap.EntryK,V spliterator() {return new EntrySpliterator(HashMap.this, 0, -1, 0, 0);}public final void forEach(Consumer? super Map.EntryK,V action) {NodeK,V[] tab;if (action null)throw new NullPointerException();if (size 0 (tab table) ! null) {int mc modCount;for (NodeK,V e : tab) {for (; e ! null; e e.next)action.accept(e);}if (modCount ! mc)throw new ConcurrentModificationException();}}}JDK8 Map扩展方法的重写 // 如果通过key没获取到值则使用defaultValueOverridepublic V getOrDefault(Object key, V defaultValue) {NodeK,V e;return (e getNode(key)) null ? defaultValue : e.value;}// 如果不存在才会putOverridepublic V putIfAbsent(K key, V value) {return putVal(hash(key), key, value, true, true);}// 移除key并且value等于此时key所对应的valueOverridepublic boolean remove(Object key, Object value) {return removeNode(hash(key), key, value, true, true) ! null;}// 新值替换老值// 1.必须通过key查询到Node否则返回true查询不到并不会替换// 2.查询到的Node的value必须和老值相等Overridepublic boolean replace(K key, V oldValue, V newValue) {NodeK,V e; V v;if ((e getNode(key)) ! null ((v e.value) oldValue || (v ! null v.equals(oldValue)))) {e.value newValue;afterNodeAccess(e);return true;}return false;}// 新值替换老值// 1.必须通过key查询到Node否则返回true查询不到并不会替换// 2.不会检查查询到的Node的valueOverridepublic V replace(K key, V value) {NodeK,V e;if ((e getNode(key)) ! null) {V oldValue e.value;e.value value;afterNodeAccess(e);return oldValue;}return null;}/*** 如果此方法检测在计算期间映射函数修改此map此方法将尽力抛出一个ConcurrentModificationException。* throws ConcurrentModificationException 如果它检测到映射函数修改此map*/// 如果key查询不到Node或者Node的值为空则通过mappingFunction函数和key进行计算,如果存在则直接返回老值// 将计算出来的value与key一起存储到MapOverridepublic V computeIfAbsent(K key,Function? super K, ? extends V mappingFunction) {if (mappingFunction null)throw new NullPointerException();int hash hash(key);NodeK,V[] tab; NodeK,V first; int n, i;int binCount 0;TreeNodeK,V t null;NodeK,V old null;if (size threshold || (tab table) null ||(n tab.length) 0)n (tab resize()).length;if ((first tab[i (n - 1) hash]) ! null) {if (first instanceof TreeNode)old (t (TreeNodeK,V)first).getTreeNode(hash, key);else {NodeK,V e first; K k;do {if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) {old e;break;}binCount;} while ((e e.next) ! null);}V oldValue;if (old ! null (oldValue old.value) ! null) {afterNodeAccess(old);return oldValue;}}int mc modCount;V v mappingFunction.apply(key);if (mc ! modCount) { throw new ConcurrentModificationException(); }if (v null) {return null;} else if (old ! null) {old.value v;afterNodeAccess(old);return v;}else if (t ! null)t.putTreeVal(this, tab, hash, key, v);else {tab[i] newNode(hash, key, v, first);if (binCount TREEIFY_THRESHOLD - 1)treeifyBin(tab, hash);}modCount mc 1;size;afterNodeInsertion(true);return v;}/*** 如果此方法检测在计算期间映射函数修改此map此方法将尽力抛出一个ConcurrentModificationException。* throws ConcurrentModificationException 如果它检测到映射函数修改此map*/// 如果存在则通过remappingFunction将key和value重算并替换老值并返回新值// 不存在返回nullOverridepublic V computeIfPresent(K key,BiFunction? super K, ? super V, ? extends V remappingFunction) {if (remappingFunction null)throw new NullPointerException();NodeK,V e; V oldValue;if ((e getNode(key)) ! null (oldValue e.value) ! null) {int mc modCount;V v remappingFunction.apply(key, oldValue);if (mc ! modCount) { throw new ConcurrentModificationException(); }if (v ! null) {e.value v;afterNodeAccess(e);return v;}else {int hash hash(key);removeNode(hash, key, null, false, true);}}return null;}/*** 如果此方法检测在计算期间映射函数修改此map此方法将尽力抛出一个ConcurrentModificationException。* throws ConcurrentModificationException 如果它检测到映射函数修改此map*/// 通过key查询node不管是否存在则通过remappingFunction生成新值存在则替换不存在则新增Overridepublic V compute(K key,BiFunction? super K, ? super V, ? extends V remappingFunction) {if (remappingFunction null)throw new NullPointerException();int hash hash(key);NodeK,V[] tab; NodeK,V first; int n, i;int binCount 0;TreeNodeK,V t null;NodeK,V old null;if (size threshold || (tab table) null ||(n tab.length) 0)n (tab resize()).length;if ((first tab[i (n - 1) hash]) ! null) {if (first instanceof TreeNode)old (t (TreeNodeK,V)first).getTreeNode(hash, key);else {NodeK,V e first; K k;do {if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) {old e;break;}binCount;} while ((e e.next) ! null);}}V oldValue (old null) ? null : old.value;int mc modCount;V v remappingFunction.apply(key, oldValue);if (mc ! modCount) { throw new ConcurrentModificationException(); }if (old ! null) {if (v ! null) {old.value v;afterNodeAccess(old);}elseremoveNode(hash, key, null, false, true);}else if (v ! null) {if (t ! null)t.putTreeVal(this, tab, hash, key, v);else {tab[i] newNode(hash, key, v, first);if (binCount TREEIFY_THRESHOLD - 1)treeifyBin(tab, hash);}modCount mc 1;size;afterNodeInsertion(true);}return v;}/*** 如果此方法检测在计算期间映射函数修改此map此方法将尽力抛出一个ConcurrentModificationException。* throws ConcurrentModificationException 如果它检测到映射函数修改此map*/// 通过key查询是否存在node不存在则将keyvalue存储如果存在则将value和oldValue生成newValue与key一起存储。Overridepublic V merge(K key, V value,BiFunction? super V, ? super V, ? extends V remappingFunction) {if (value null || remappingFunction null)throw new NullPointerException();int hash hash(key);NodeK,V[] tab; NodeK,V first; int n, i;int binCount 0;TreeNodeK,V t null;NodeK,V old null;if (size threshold || (tab table) null ||(n tab.length) 0)n (tab resize()).length;if ((first tab[i (n - 1) hash]) ! null) {if (first instanceof TreeNode)old (t (TreeNodeK,V)first).getTreeNode(hash, key);else {NodeK,V e first; K k;do {if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) {old e;break;}binCount;} while ((e e.next) ! null);}}if (old ! null) {V v;if (old.value ! null) {int mc modCount;v remappingFunction.apply(old.value, value);if (mc ! modCount) {throw new ConcurrentModificationException();}} else {v value;}if (v ! null) {old.value v;afterNodeAccess(old);}elseremoveNode(hash, key, null, false, true);return v;} else {if (t ! null)t.putTreeVal(this, tab, hash, key, value);else {tab[i] newNode(hash, key, value, first);if (binCount TREEIFY_THRESHOLD - 1)treeifyBin(tab, hash);}modCount;size;afterNodeInsertion(true);return value;}}//循环处理keyvalueOverridepublic void forEach(BiConsumer? super K, ? super V action) {NodeK,V[] tab;if (action null)throw new NullPointerException();if (size 0 (tab table) ! null) {int mc modCount;for (NodeK,V e : tab) {for (; e ! null; e e.next)action.accept(e.key, e.value);}if (modCount ! mc)throw new ConcurrentModificationException();}}// key值不变替换value值public void replaceAll(BiFunction? super K, ? super V, ? extends V function) {NodeK,V[] tab;if (function null)throw new NullPointerException();if (size 0 (tab table) ! null) {int mc modCount;for (NodeK,V e : tab) {for (; e ! null; e e.next) {e.value function.apply(e.key, e.value);}}if (modCount ! mc)throw new ConcurrentModificationException();}}
