简介：

都说理论是学习的基础，但是没有实际操作的理论都是别人说的，可信与否只有自己亲手实验了才知道，毕竟眼见为实。以前学习hashmap的时候都是网上各种看资料，讲解的都是一大堆的理论，但是很少有能实际操作让大家可以看到实际展示效果的，而且没有实现展示效果但凭一篇几千字上万字的文章没有自己动手操作想要理解透彻hashmap还是比较困难的，而用debug模式又会有很多的不必要流程会加在进去，需要提取到有效信息时需要跳过很多没必要关注的流程，所以今天来带大家看看怎么使用打印日志来分析hashmap源码，哪里不明白就在哪里打日志就完了。

为什么放弃debug而使用源码

原因

因为在使用源码的时候 调用hashMap构造函数 HashMap(int initialCapacity) 内部加入相应的断点，无论你的参数初始大小是多少，那么他最终构造该方法里第一次展示的都是11，在这个断电里会停留很多次才会执行到我们创建的方法，使用不是很方便

这是为什么呢，经过仔细分析后最终找到了调用这个方法的源头，因为hashmap是一容器，不只是你在用，很多框架包括jdk内部自身也有很多地方在使用，而jvm的类加载机制会优先加载jdk内部包的内容，所以调用这个方法也就不足为奇了,初始化为11的值方法在java.util.jar.Attributes类中调用的，见下面代码。

//调用栈的第三行 public Attributes() { this(11); } //调用栈的第二行 public Attributes(int size) { map = new HashMap<>(size);//size 11 }

解决方式

那么这个问题就无法解决了吗，肯定有的，因为博主使用的是IDEA IDEA的整个流程在断点处单击右键 codition栏中添加 initialCapacity==设置的容量，那么就会在满足当前条件的时候才会停下来了，如图 不过这种方法只是报提出了部分没用的值，但是并不能保证取到的就一定是自己调用的，因为还是有可能会有其他方法也调用了相同的值。

关于断点与源码的推荐

断点适合查看自定义代码走向一步步查看流程，对于使用比较复杂的通用工具类是不推荐使用的，因为我们这里要做的是研究hashmap内部的部分方法，对于这种的需求采用控制变量法是一个不错的方法，我们只关注我们的代码执行流程，那么复制一个自定义类是比较好的选择，无论是用日志还是断点自定义的源码操作都比较方便。

探讨问题：

关于hashmap的扩容决定因素时是取决于key的数量还是数组的占用数量，因为网上很多文章都是说的是取决于数组占用长度，也有文章说是当桶的占用数量小于64就只会扩容，大于64后就会取决于桶的占用长度，但是在查看过源码后总觉得代码逻辑不是这么实现的，关于链表上的元素新增元素是添加在链表的头部还是尾部这个问题的说法也不一致，查看源码后觉得是增加在尾部的，所以今天来用源码实际查看运行的效果。

先告诉大家结论，可以直接看最后的测试代码和运行结果：

1.hashmap中的数组扩容决定因子是key的数量而不是数组占用的数量。

2.map链表中新增元素的内容是加在链表尾部的，jdk1.7的据说时头部，没有测试过，博主这里使用的时jdk1.8。

源码提供：

MyHashMap

/* * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved. * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. */ package com.map; import java.io.IOException; import java.io.InvalidObjectException; import java.io.Serializable; import java.lang.reflect.ParameterizedType; import java.lang.reflect.Type; import java.util.*; import java.util.function.BiConsumer; import java.util.function.BiFunction; import java.util.function.Consumer; import java.util.function.Function; /** * Hash table based implementation of the <tt>Map</tt> interface. This * implementation provides all of the optional map operations, and permits * <tt>null</tt> values and the <tt>null</tt> key. (The <tt>MyHashMap</tt> * class is roughly equivalent to <tt>Hashtable</tt>, except that it is * unsynchronized and permits nulls.) This class makes no guarantees as to * the order of the map; in particular, it does not guarantee that the order * will remain constant over time. * * <p>This implementation provides constant-time performance for the basic * operations (<tt>get</tt> and <tt>put</tt>), assuming the hash function * disperses the elements properly among the buckets. Iteration over * collection views requires time proportional to the "capacity" of the * <tt>MyHashMap</tt> instance (the number of buckets) plus its size (the number * of key-value mappings). Thus, it's very important not to set the initial * capacity too high (or the load factor too low) if iteration performance is * important. * * <p>An instance of <tt>MyHashMap</tt> has two parameters that affect its * performance: <i>initial capacity</i> and <i>load factor</i>. The * <i>capacity</i> is the number of buckets in the hash table, and the initial * capacity is simply the capacity at the time the hash table is created. The * <i>load factor</i> is a measure of how full the hash table is allowed to * get before its capacity is automatically increased. When the number of * entries in the hash table exceeds the product of the load factor and the * current capacity, the hash table is <i>rehashed</i> (that is, internal data * structures are rebuilt) so that the hash table has approximately twice the * number of buckets. * * <p>As a general rule, the default load factor (.75) offers a good * tradeoff between time and space costs. Higher values decrease the * space overhead but increase the lookup cost (reflected in most of * the operations of the <tt>MyHashMap</tt> class, including * <tt>get</tt> and <tt>put</tt>). The expected number of entries in * the map and its load factor should be taken into account when * setting its initial capacity, so as to minimize the number of * rehash operations. If the initial capacity is greater than the * maximum number of entries divided by the load factor, no rehash * operations will ever occur. * * <p>If many mappings are to be stored in a <tt>MyHashMap</tt> * instance, creating it with a sufficiently large capacity will allow * the mappings to be stored more efficiently than letting it perform * automatic rehashing as needed to grow the table. Note that using * many keys with the same {@code hashCode()} is a sure way to slow * down performance of any hash table. To ameliorate impact, when keys * are {@link Comparable}, this class may use comparison order among * keys to help break ties. * * <p><strong>Note that this implementation is not synchronized.</strong> * If multiple threads access a hash map concurrently, and at least one of * the threads modifies the map structurally, it <i>must</i> be * synchronized externally. (A structural modification is any operation * that adds or deletes one or more mappings; merely changing the value * associated with a key that an instance already contains is not a * structural modification.) This is typically accomplished by * synchronizing on some object that naturally encapsulates the map. * <p> * If no such object exists, the map should be "wrapped" using the * {@link Collections#synchronizedMap Collections.synchronizedMap} * method. This is best done at creation time, to prevent accidental * unsynchronized access to the map:<pre> * Map m = Collections.synchronizedMap(new MyHashMap(...));</pre> * * <p>The iterators returned by all of this class's "collection view methods" * are <i>fail-fast</i>: if the map is structurally modified at any time after * the iterator is created, in any way except through the iterator's own * <tt>remove</tt> method, the iterator will throw a * {@link ConcurrentModificationException}. Thus, in the face of concurrent * modification, the iterator fails quickly and cleanly, rather than risking * arbitrary, non-deterministic behavior at an undetermined time in the * future. * * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed * as it is, generally speaking, impossible to make any hard guarantees in the * presence of unsynchronized concurrent modification. Fail-fast iterators * throw <tt>ConcurrentModificationException</tt> on a best-effort basis. * Therefore, it would be wrong to write a program that depended on this * exception for its correctness: <i>the fail-fast behavior of iterators * should be used only to detect bugs.</i> * * <p>This class is a member of the * <a href="{@docRoot}/../technotes/guides/collections/index.html"> * Java Collections Framework</a>. * * @param <K> the type of keys maintained by this map * @param <V> the type of mapped values * @author Doug Lea * @author Josh Bloch * @author Arthur van Hoff * @author Neal Gafter * @see Object#hashCode() * @see Collection * @see Map * @see TreeMap * @see Hashtable * @since 1.2 */ @SuppressWarnings("all") public class MyHashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable, Serializable { private static final long serialVersionUID = 362498820763181265L; transient Set<K> keySet; transient Collection<V> values; /* * Implementation notes. * * This map usually acts as a binned (bucketed) hash table, but * when bins get too large, they are transformed into bins of * TreeNodes, each structured similarly to those in * java.util.TreeMap. Most methods try to use normal bins, but * relay to TreeNode methods when applicable (simply by checking * instanceof a node). Bins of TreeNodes may be traversed and * used like any others, but additionally support faster lookup * when overpopulated. However, since the vast majority of bins in * normal use are not overpopulated, checking for existence of * tree bins may be delayed in the course of table methods. * * Tree bins (i.e., bins whose elements are all TreeNodes) are * ordered primarily by hashCode, but in the case of ties, if two * elements are of the same "class C implements Comparable<C>", * type then their compareTo method is used for ordering. (We * conservatively check generic types via reflection to validate * this -- see method comparableClassFor). The added complexity * of tree bins is worthwhile in providing worst-case O(log n) * operations when keys either have distinct hashes or are * orderable, Thus, performance degrades gracefully under * accidental or malicious usages in which hashCode() methods * return values that are poorly distributed, as well as those in * which many keys share a hashCode, so long as they are also * Comparable. (If neither of these apply, we may waste about a * factor of two in time and space compared to taking no * precautions. But the only known cases stem from poor user * programming practices that are already so slow that this makes * little difference.) * * Because TreeNodes are about twice the size of regular nodes, we * use them only when bins contain enough nodes to warrant use * (see TREEIFY_THRESHOLD). And when they become too small (due to * removal or resizing) they are converted back to plain bins. In * usages with well-distributed user hashCodes, tree bins are * rarely used. Ideally, under random hashCodes, the frequency of * nodes in bins follows a Poisson distribution * (http://en.wikipedia.org/wiki/Poisson_distribution) with a * parameter of about 0.5 on average for the default resizing * threshold of 0.75, although with a large variance because of * resizing granularity. Ignoring variance, the expected * occurrences of list size k are (exp(-0.5) * pow(0.5, k) / * factorial(k)). The first values are: * * 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 * more: less than 1 in ten million * * The root of a tree bin is normally its first node. However, * sometimes (currently only upon Iterator.remove), the root might * be elsewhere, but can be recovered following parent links * (method TreeNode.root()). * * All applicable internal methods accept a hash code as an * argument (as normally supplied from a public method), allowing * them to call each other without recomputing user hashCodes. * Most internal methods also accept a "tab" argument, that is * normally the current table, but may be a new or old one when * resizing or converting. * * When bin lists are treeified, split, or untreeified, we keep * them in the same relative access/traversal order (i.e., field * Node.next) to better preserve locality, and to slightly * simplify handling of splits and traversals that invoke * iterator.remove. When using comparators on insertion, to keep a * total ordering (or as close as is required here) across * rebalancings, we compare classes and identityHashCodes as * tie-breakers. * * The use and transitions among plain vs tree modes is * complicated by the existence of subclass LinkedHashMap. See * below for hook methods defined to be invoked upon insertion, * removal and access that allow LinkedHashMap internals to * otherwise remain independent of these mechanics. (This also * requires that a map instance be passed to some utility methods * that may create new nodes.) * * The concurrent-programming-like SSA-based coding style helps * avoid aliasing errors amid all of the twisty pointer operations. */ /** * The default initial capacity - MUST be a power of two. */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 /** * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two <= 1<<30. */ static final int MAXIMUM_CAPACITY = 1 << 30; /** * The load factor used when none specified in constructor. */ static final float DEFAULT_LOAD_FACTOR = 0.75f; /** * The bin count threshold for using a tree rather than list for a * bin. Bins are converted to trees when adding an element to a * bin with at least this many nodes. The value must be greater * than 2 and should be at least 8 to mesh with assumptions in * tree removal about conversion back to plain bins upon * shrinkage. */ static final int TREEIFY_THRESHOLD = 8; /** * The bin count threshold for untreeifying a (split) bin during a * resize operation. Should be less than TREEIFY_THRESHOLD, and at * most 6 to mesh with shrinkage detection under removal. */ static final int UNTREEIFY_THRESHOLD = 6; /** * The smallest table capacity for which bins may be treeified. * (Otherwise the table is resized if too many nodes in a bin.) * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts * between resizing and treeification thresholds. */ static final int MIN_TREEIFY_CAPACITY = 64; /** * Basic hash bin node, used for most entries. (See below for * TreeNode subclass, and in LinkedHashMap for its Entry subclass.) */ static class Node<K, V> implements Entry<K, V> { final int hash; final K key; V value; Node<K, V> next; Node(int hash, K key, V value, Node<K, 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; if (o instanceof Map.Entry) { Entry<?, ?> e = (Entry<?, ?>) o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } } /* ---------------- Static utilities -------------- */ /** * Computes key.hashCode() and spreads (XORs) higher bits of hash * to lower. Because the table uses power-of-two masking, sets of * hashes that vary only in bits above the current mask will * always collide. (Among known examples are sets of Float keys * holding consecutive whole numbers in small tables.) So we * apply a transform that spreads the impact of higher bits * downward. There is a tradeoff between speed, utility, and * quality of bit-spreading. Because many common sets of hashes * are already reasonably distributed (so don't benefit from * spreading), and because we use trees to handle large sets of * collisions in bins, we just XOR some shifted bits in the * cheapest possible way to reduce systematic lossage, as well as * to incorporate impact of the highest bits that would otherwise * never be used in index calculations because of table bounds. */ static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } /** * Returns x's Class if it is of the form "class C implements * Comparable<C>", else null. */ static Class<?> comparableClassFor(Object x) { if (x instanceof Comparable) { Class<?> c; Type[] ts, as; Type t; ParameterizedType p; if ((c = x.getClass()) == String.class) // bypass checks return c; if ((ts = c.getGenericInterfaces()) != null) { for (int i = 0; i < ts.length; ++i) { if (((t = ts[i]) instanceof ParameterizedType) && ((p = (ParameterizedType) t).getRawType() == Comparable.class) && (as = p.getActualTypeArguments()) != null && as.length == 1 && as[0] == c) // type arg is c return c; } } } return null; } /** * Returns k.compareTo(x) if x matches kc (k's screened comparable * class), else 0. */ @SuppressWarnings({"rawtypes", "unchecked"}) // for cast to Comparable static int compareComparables(Class<?> kc, Object k, Object x) { return (x == null || x.getClass() != kc ? 0 : ((Comparable) k).compareTo(x)); } /** * Returns a power of two size for the given target capacity. */ static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; } /* ---------------- Fields -------------- */ /** * The table, initialized on first use, and resized as * necessary. When allocated, length is always a power of two. * (We also tolerate length zero in some operations to allow * bootstrapping mechanics that are currently not needed.) */ transient Node<K, V>[] table; /** * Holds cached entrySet(). Note that AbstractMap fields are used * for keySet() and values(). */ transient Set<Entry<K, V>> entrySet; /** * The number of key-value mappings contained in this map. */ transient int size; /** * The number of times this HashMap has been structurally modified * Structural modifications are those that change the number of mappings in * the HashMap or otherwise modify its internal structure (e.g., * rehash). This field is used to make iterators on Collection-views of * the HashMap fail-fast. (See ConcurrentModificationException). */ transient int modCount; /** * The next size value at which to resize (capacity * load factor). * * @serial */ // (The javadoc description is true upon serialization. // Additionally, if the table array has not been allocated, this // field holds the initial array capacity, or zero signifying // DEFAULT_INITIAL_CAPACITY.) int threshold; /** * The load factor for the hash table. * * @serial */ final float loadFactor; /* ---------------- Public operations -------------- */ /** * Constructs an empty <tt>MyHashMap</tt> with the specified initial * capacity and load factor. * * @param initialCapacity the initial capacity * @param loadFactor the load factor * @throws IllegalArgumentException if the initial capacity is negative * or the load factor is nonpositive */ public MyHashMap(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); } /** * Constructs an empty <tt>MyHashMap</tt> with the specified initial * capacity and the default load factor (0.75). * * @param initialCapacity the initial capacity. * @throws IllegalArgumentException if the initial capacity is negative. */ public MyHashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } /** * Constructs an empty <tt>MyHashMap</tt> with the default initial capacity * (16) and the default load factor (0.75). */ public MyHashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } /** * Constructs a new <tt>MyHashMap</tt> with the same mappings as the * specified <tt>Map</tt>. The <tt>MyHashMap</tt> is created with * default load factor (0.75) and an initial capacity sufficient to * hold the mappings in the specified <tt>Map</tt>. * * @param m the map whose mappings are to be placed in this map * @throws NullPointerException if the specified map is null */ public MyHashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); } /** * Implements Map.putAll and Map constructor * * @param m the map * @param evict false when initially constructing this map, else * true (relayed to method afterNodeInsertion). */ final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { int s = m.size(); if (s > 0) { if (table == null) { // pre-size float 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) resize(); for (Entry<? extends K, ? extends V> e : m.entrySet()) { K key = e.getKey(); V value = e.getValue(); putVal(hash(key), key, value, false, evict); } } } /** * Returns the number of key-value mappings in this map. * * @return the number of key-value mappings in this map */ public int size() { return size; } /** * Returns <tt>true</tt> if this map contains no key-value mappings. * * @return <tt>true</tt> if this map contains no key-value mappings */ public boolean isEmpty() { return size == 0; } /** * Returns the value to which the specified key is mapped, * or {@code null} if this map contains no mapping for the key. * * <p>More formally, if this map contains a mapping from a key * {@code k} to a value {@code v} such that {@code (key==null ? k==null : * key.equals(k))}, then this method returns {@code v}; otherwise * it returns {@code null}. (There can be at most one such mapping.) * * <p>A return value of {@code null} does not <i>necessarily</i> * indicate that the map contains no mapping for the key; it's also * possible that the map explicitly maps the key to {@code null}. * The {@link #containsKey containsKey} operation may be used to * distinguish these two cases. * * @see #Object, Object) */ public V get(Object key) { Node<K, V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } /** * Implements Map.get and related methods * * @param hash hash for key * @param key the key * @return the node, or null if none */ final MyHashMap.Node<K, V> getNode(int hash, Object key) { MyHashMap.Node<K, V>[] tab; MyHashMap.Node<K, V> first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != 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 ((TreeNode<K, 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; } /** * Returns <tt>true</tt> if this map contains a mapping for the * specified key. * * @param key The key whose presence in this map is to be tested * @return <tt>true</tt> if this map contains a mapping for the specified * key. */ public boolean containsKey(Object key) { return getNode(hash(key), key) != null; } /** * Associates the specified value with the specified key in this map. * If the map previously contained a mapping for the key, the old * value is replaced. * * @param key key with which the specified value is to be associated * @param value value to be associated with the specified key * @return the previous value associated with <tt>key</tt>, or * <tt>null</tt> if there was no mapping for <tt>key</tt>. * (A <tt>null</tt> return can also indicate that the map * previously associated <tt>null</tt> with <tt>key</tt>.) */ public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } /** * Implements Map.put and related methods * * @param hash hash for key * @param key the key * @param value the value to put * @param onlyIfAbsent if true, don't change existing value * @param evict if false, the table is in creation mode. * @return previous value, or null if none */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K, V>[] tab; Node<K, V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) { //当第一次put时创建table使用 n = (tab = resize()).length; } int i1 = n - 1; i = i1 & hash; //1.根据hah值确定咋那个hash槽 //2.如果这个槽中没有链表则直接创建一个链表，并且唯一元素为当前的k-v //3.如果这个槽存在链表则直接把内容加在链表后 if ((p = tab[i]) == null) { //当第一个槽存入数据创建链表时使用 tab[i] = newNode(hash, key, value, null); } else { // System.out.println(p.key + "-->" + p.value); MyHashMap.Node<K, V> e; K k; //1.p表示数据会存放的链表 //2.k表示链表第一个元素的key //这一个方法仅表示当存入的key为已有的key的时候的情况 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //表示当链表太长已经转换成红黑树的时候 else if (p instanceof MyHashMap.TreeNode) e = ((MyHashMap.TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { //从第一个节点开始判断，当下一个节点为空的时候就把这个k-v数据节点的指定为最后一个节点的下一节点 //注：因为前面第一个判断中已经有判断如果说当前的key与链表中的唯一一个key相等的时候会直接跳过， // 不会执行到这里来了，所以这里默认的是这个key一定不会与链表的key相同 if ((e = p.next) == null) { 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)))) break; //这里的切换p时为了让临时变量指向他的下一个节点，继续判断下一节点是否有下一节点，轮询链表去判断值需要存入的key是否存在 p = e; } } // System.out.println(hash + "--" + key + "--" + i); // System.out.println("start:" + tab[i].key); if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); // System.out.println("end:" + tab[i].key); return oldValue; } } ++modCount; if (++size > threshold) { resize(); System.out.println(key + "扩容"); } afterNodeInsertion(evict); // System.out.println("key:" + key + " table。size:" + table.length); return null; } /** * Initializes or doubles table size. 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 Node<K, V>[] resize() { Node<K, 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 } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults newCap = 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"}) Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap]; table = newTab; if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K, 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) ((TreeNode<K, V>) e).split(this, newTab, j, oldCap); else { // preserve order Node<K, V> loHead = null, loTail = null; Node<K, V> hiHead = null, hiTail = null; Node<K, V> next; do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.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; } /** * Replaces all linked nodes in bin at index for given hash unless * table is too small, in which case resizes instead. */ final void treeifyBin(Node<K, V>[] tab, int hash) { int n, index; Node<K, V> e; if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); else if ((e = tab[index = (n - 1) & hash]) != null) { TreeNode<K, V> hd = null, tl = null; do { TreeNode<K, 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. * * @param m mappings to be stored in this map * @throws NullPointerException if the specified map is null */ public void putAll(Map<? extends K, ? extends V> m) { putMapEntries(m, true); } /** * Removes the mapping for the specified key from this map if present. * * @param key key whose mapping is to be removed from the map * @return the previous value associated with <tt>key</tt>, or * <tt>null</tt> if there was no mapping for <tt>key</tt>. * (A <tt>null</tt> return can also indicate that the map * previously associated <tt>null</tt> with <tt>key</tt>.) */ public V remove(Object key) { Node<K, V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; } /** * Implements Map.remove and related methods * * @param hash hash for key * @param key the key * @param value the value to match if matchValue, else ignored * @param matchValue if true only remove if value is equal * @param movable if false do not move other nodes while removing * @return the node, or null if none */ final Node<K, V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { Node<K, V>[] tab; Node<K, V> p; int n, index; if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) { Node<K, 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 = ((TreeNode<K, 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) ((TreeNode<K, V>) node).removeTreeNode(this, tab, movable); else if (node == p) tab[index] = node.next; else p.next = node.next; ++modCount; --size; afterNodeRemoval(node); return node; } } return null; } /** * Removes all of the mappings from this map. * The map will be empty after this call returns. */ public void clear() { Node<K, V>[] tab; modCount++; if ((tab = table) != null && size > 0) { size = 0; for (int i = 0; i < tab.length; ++i) tab[i] = null; } } /** * Returns <tt>true</tt> if this map maps one or more keys to the * specified value. * * @param value value whose presence in this map is to be tested * @return <tt>true</tt> if this map maps one or more keys to the * specified value */ public boolean containsValue(Object value) { Node<K, V>[] tab; V v; if ((tab = table) != null && size > 0) { for (int i = 0; i < tab.length; ++i) { for (Node<K, V> e = tab[i]; e != null; e = e.next) { if ((v = e.value) == value || (value != null && value.equals(v))) return true; } } } return false; } /** * Returns a {@link Set} view of the keys contained in this map. * The set is backed by the map, so changes to the map are * reflected in the set, and vice-versa. If the map is modified * while an iteration over the set is in progress (except through * the iterator's own <tt>remove</tt> operation), the results of * the iteration are undefined. The set supports element removal, * which removes the corresponding mapping from the map, via the * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> * operations. It does not support the <tt>add</tt> or <tt>addAll</tt> * operations. * * @return a set view of the keys contained in this map */ public Set<K> keySet() { Set<K> ks = keySet; if (ks == null) { ks = new KeySet(); keySet = ks; } return ks; } final class KeySet extends AbstractSet<K> { public final int size() { return size; } public final void clear() { MyHashMap.this.clear(); } public final Iterator<K> 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 Spliterator<K> spliterator() { return new KeySpliterator<>(MyHashMap.this, 0, -1, 0, 0); } public final void forEach(Consumer<? super K> action) { Node<K, V>[] tab; if (action == null) throw new NullPointerException(); if (size > 0 && (tab = table) != null) { int mc = modCount; for (int i = 0; i < tab.length; ++i) { for (Node<K, V> e = tab[i]; e != null; e = e.next) action.accept(e.key); } if (modCount != mc) throw new ConcurrentModificationException(); } } } /** * Returns a {@link Collection} view of the values contained in this map. * The collection is backed by the map, so changes to the map are * reflected in the collection, and vice-versa. If the map is * modified while an iteration over the collection is in progress * (except through the iterator's own <tt>remove</tt> operation), * the results of the iteration are undefined. The collection * supports element removal, which removes the corresponding * mapping from the map, via the <tt>Iterator.remove</tt>, * <tt>Collection.remove</tt>, <tt>removeAll</tt>, * <tt>retainAll</tt> and <tt>clear</tt> operations. It does not * support the <tt>add</tt> or <tt>addAll</tt> operations. * * @return a view of the values contained in this map */ public Collection<V> values() { Collection<V> vs = values; if (vs == null) { vs = new Values(); values = vs; } return vs; } final class Values extends AbstractCollection<V> { public final int size() { return size; } public final void clear() { MyHashMap.this.clear(); } public final Iterator<V> iterator() { return new ValueIterator(); } public final boolean contains(Object o) { return containsValue(o); } public final Spliterator<V> spliterator() { return new ValueSpliterator<>(MyHashMap.this, 0, -1, 0, 0); } public final void forEach(Consumer<? super V> action) { Node<K, V>[] tab; if (action == null) throw new NullPointerException(); if (size > 0 && (tab = table) != null) { int mc = modCount; for (int i = 0; i < tab.length; ++i) { for (Node<K, V> e = tab[i]; e != null; e = e.next) action.accept(e.value); } if (modCount != mc) throw new ConcurrentModificationException(); } } } /** * Returns a {@link Set} view of the mappings contained in this map. * The set is backed by the map, so changes to the map are * reflected in the set, and vice-versa. If the map is modified * while an iteration over the set is in progress (except through * the iterator's own <tt>remove</tt> operation, or through the * <tt>setValue</tt> operation on a map entry returned by the * iterator) the results of the iteration are undefined. The set * supports element removal, which removes the corresponding * mapping from the map, via the <tt>Iterator.remove</tt>, * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and * <tt>clear</tt> operations. It does not support the * <tt>add</tt> or <tt>addAll</tt> operations. * * @return a set view of the mappings contained in this map */ public Set<Entry<K, V>> entrySet() { Set<Entry<K, V>> es; return (es = entrySet) == null ? (entrySet = new EntrySet()) : es; } final class EntrySet extends AbstractSet<Entry<K, V>> { public final int size() { return size; } public final void clear() { MyHashMap.this.clear(); } public final Iterator<Entry<K, V>> iterator() { return new EntryIterator(); } public final boolean contains(Object o) { if (!(o instanceof Map.Entry)) return false; Entry<?, ?> e = (Entry<?, ?>) o; Object key = e.getKey(); Node<K, V> candidate = getNode(hash(key), key); return candidate != null && candidate.equals(e); } public final boolean remove(Object o) { if (o instanceof Map.Entry) { Entry<?, ?> e = (Entry<?, ?>) o; Object key = e.getKey(); Object value = e.getValue(); return removeNode(hash(key), key, value, true, true) != null; } return false; } public final Spliterator<Entry<K, V>> spliterator() { return new EntrySpliterator<>(MyHashMap.this, 0, -1, 0, 0); } public final void forEach(Consumer<? super Entry<K, V>> action) { Node<K, V>[] tab; if (action == null) throw new NullPointerException(); if (size > 0 && (tab = table) != null) { int mc = modCount; for (int i = 0; i < tab.length; ++i) { for (Node<K, V> e = tab[i]; e != null; e = e.next) action.accept(e); } if (modCount != mc) throw new ConcurrentModificationException(); } } } // Overrides of JDK8 Map extension methods @Override public V getOrDefault(Object key, V defaultValue) { Node<K, V> e; return (e = getNode(hash(key), key)) == null ? defaultValue : e.value; } @Override public V putIfAbsent(K key, V value) { return putVal(hash(key), key, value, true, true); } @Override public boolean remove(Object key, Object value) { return removeNode(hash(key), key, value, true, true) != null; } @Override public boolean replace(K key, V oldValue, V newValue) { Node<K, V> e; V v; if ((e = getNode(hash(key), key)) != null && ((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) { e.value = newValue; afterNodeAccess(e); return true; } return false; } @Override public V replace(K key, V value) { Node<K, V> e; if ((e = getNode(hash(key), key)) != null) { V oldValue = e.value; e.value = value; afterNodeAccess(e); return oldValue; } return null; } @Override public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) { if (mappingFunction == null) throw new NullPointerException(); int hash = hash(key); Node<K, V>[] tab; Node<K, V> first; int n, i; int binCount = 0; TreeNode<K, V> t = null; Node<K, 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 = (TreeNode<K, V>) first).getTreeNode(hash, key); else { Node<K, 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; } } V v = mappingFunction.apply(key); 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; ++size; afterNodeInsertion(true); return v; } public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) { if (remappingFunction == null) throw new NullPointerException(); Node<K, V> e; V oldValue; int hash = hash(key); if ((e = getNode(hash, key)) != null && (oldValue = e.value) != null) { V v = remappingFunction.apply(key, oldValue); if (v != null) { e.value = v; afterNodeAccess(e); return v; } else removeNode(hash, key, null, false, true); } return null; } @Override public V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) { if (remappingFunction == null) throw new NullPointerException(); int hash = hash(key); Node<K, V>[] tab; Node<K, V> first; int n, i; int binCount = 0; TreeNode<K, V> t = null; Node<K, 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 = (TreeNode<K, V>) first).getTreeNode(hash, key); else { Node<K, 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; V v = remappingFunction.apply(key, oldValue); if (old != null) { if (v != null) { old.value = v; afterNodeAccess(old); } else removeNode(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; ++size; afterNodeInsertion(true); } return v; } @Override public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) { if (value == null) throw new NullPointerException(); if (remappingFunction == null) throw new NullPointerException(); int hash = hash(key); Node<K, V>[] tab; Node<K, V> first; int n, i; int binCount = 0; TreeNode<K, V> t = null; Node<K, 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 = (TreeNode<K, V>) first).getTreeNode(hash, key); else { Node<K, 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) v = remappingFunction.apply(old.value, value); else v = value; if (v != null) { old.value = v; afterNodeAccess(old); } else removeNode(hash, key, null, false, true); return v; } if (value != null) { 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; } @Override public void forEach(BiConsumer<? super K, ? super V> action) { Node<K, V>[] tab; if (action == null) throw new NullPointerException(); if (size > 0 && (tab = table) != null) { int mc = modCount; for (int i = 0; i < tab.length; ++i) { for (Node<K, V> e = tab[i]; e != null; e = e.next) action.accept(e.key, e.value); } if (modCount != mc) throw new ConcurrentModificationException(); } } @Override public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) { Node<K, V>[] tab; if (function == null) throw new NullPointerException(); if (size > 0 && (tab = table) != null) { int mc = modCount; for (int i = 0; i < tab.length; ++i) { for (Node<K, V> e = tab[i]; e != null; e = e.next) { e.value = function.apply(e.key, e.value); } } if (modCount != mc) throw new ConcurrentModificationException(); } } /* ------------------------------------------------------------ */ // Cloning and serialization /** * Returns a shallow copy of this <tt>MyHashMap</tt> instance: the keys and * values themselves are not cloned. * * @return a shallow copy of this map */ @SuppressWarnings("unchecked") @Override public Object clone() { MyHashMap<K, V> result; try { result = (MyHashMap<K, V>) super.clone(); } catch (CloneNotSupportedException e) { // this shouldn't happen, since we are Cloneable throw new InternalError(e); } result.reinitialize(); result.putMapEntries(this, false); return result; } // These methods are also used when serializing HashSets final float loadFactor() { return loadFactor; } final int capacity() { return (table != null) ? table.length : (threshold > 0) ? threshold : DEFAULT_INITIAL_CAPACITY; } /** * Save the state of the <tt>MyHashMap</tt> instance to a stream (i.e., * serialize it). * * @serialData The <i>capacity</i> of the HashMap (the length of the * bucket array) is emitted (int), followed by the * <i>size</i> (an int, the number of key-value * mappings), followed by the key (Object) and value (Object) * for each key-value mapping. The key-value mappings are * emitted in no particular order. */ private void writeObject(java.io.ObjectOutputStream s) throws IOException { int buckets = capacity(); // Write out the threshold, loadfactor, and any hidden stuff s.defaultWriteObject(); s.writeInt(buckets); s.writeInt(size); internalWriteEntries(s); } /** * Reconstitute the {@code HashMap} instance from a stream (i.e., * deserialize it). */ private void readObject(java.io.ObjectInputStream s) throws IOException, ClassNotFoundException { // Read in the threshold (ignored), loadfactor, and any hidden stuff s.defaultReadObject(); reinitialize(); if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new InvalidObjectException("Illegal load factor: " + loadFactor); s.readInt(); // Read and ignore number of buckets int mappings = s.readInt(); // Read number of mappings (size) if (mappings < 0) throw new InvalidObjectException("Illegal mappings count: " + mappings); else if (mappings > 0) { // (if zero, use defaults) // Size the table using given load factor only if within // range of 0.25...4.0 float lf = Math.min(Math.max(0.25f, loadFactor), 4.0f); float fc = (float) mappings / lf + 1.0f; int cap = ((fc < DEFAULT_INITIAL_CAPACITY) ? DEFAULT_INITIAL_CAPACITY : (fc >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : tableSizeFor((int) fc)); float ft = (float) cap * lf; threshold = ((cap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY) ? (int) ft : Integer.MAX_VALUE); @SuppressWarnings({"rawtypes", "unchecked"}) Node<K, V>[] tab = (Node<K, V>[]) new Node[cap]; table = tab; // Read the keys and values, and put the mappings in the HashMap for (int i = 0; i < mappings; i++) { @SuppressWarnings("unchecked") K key = (K) s.readObject(); @SuppressWarnings("unchecked") V value = (V) s.readObject(); putVal(hash(key), key, value, false, false); } } } /* ------------------------------------------------------------ */ // iterators abstract class HashIterator { Node<K, V> next; // next entry to return Node<K, V> current; // current entry int expectedModCount; // for fast-fail int index; // current slot HashIterator() { expectedModCount = modCount; Node<K, V>[] t = table; current = next = null; index = 0; if (t != null && size > 0) { // advance to first entry do { } while (index < t.length && (next = t[index++]) == null); } } public final boolean hasNext() { return next != null; } final Node<K, V> nextNode() { Node<K, V>[] t; Node<K, V> e = next; if (modCount != expectedModCount) throw new ConcurrentModificationException(); if (e == null) throw new NoSuchElementException(); if ((next = (current = e).next) == null && (t = table) != null) { do { } while (index < t.length && (next = t[index++]) == null); } return e; } public final void remove() { Node<K, V> p = current; if (p == null) throw new IllegalStateException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); current = null; K key = p.key; removeNode(hash(key), key, null, false, false); expectedModCount = modCount; } } final class KeyIterator extends HashIterator implements Iterator<K> { public final K next() { return nextNode().key; } } final class ValueIterator extends HashIterator implements Iterator<V> { public final V next() { return nextNode().value; } } final class EntryIterator extends HashIterator implements Iterator<Entry<K, V>> { public final Entry<K, V> next() { return nextNode(); } } /* ------------------------------------------------------------ */ // spliterators static class HashMapSpliterator<K, V> { final MyHashMap<K, V> map; Node<K, V> current; // current node int index; // current index, modified on advance/split int fence; // one past last index int est; // size estimate int expectedModCount; // for comodification checks HashMapSpliterator(MyHashMap<K, V> m, int origin, int fence, int est, int expectedModCount) { this.map = m; this.index = origin; this.fence = fence; this.est = est; this.expectedModCount = expectedModCount; } final int getFence() { // initialize fence and size on first use int hi; if ((hi = fence) < 0) { MyHashMap<K, V> m = map; est = m.size; expectedModCount = m.modCount; Node<K, V>[] tab = m.table; hi = fence = (tab == null) ? 0 : tab.length; } return hi; } public final long estimateSize() { getFence(); // force init return (long) est; } } static final class KeySpliterator<K, V> extends HashMapSpliterator<K, V> implements Spliterator<K> { KeySpliterator(MyHashMap<K, V> m, int origin, int fence, int est, int expectedModCount) { super(m, origin, fence, est, expectedModCount); } public KeySpliterator<K, V> trySplit() { int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; return (lo >= mid || current != null) ? null : new KeySpliterator<>(map, lo, index = mid, est >>>= 1, expectedModCount); } public void forEachRemaining(Consumer<? super K> action) { int i, hi, mc; if (action == null) throw new NullPointerException(); MyHashMap<K, V> m = map; Node<K, V>[] tab = m.table; if ((hi = fence) < 0) { mc = expectedModCount = m.modCount; hi = fence = (tab == null) ? 0 : tab.length; } else mc = expectedModCount; if (tab != null && tab.length >= hi && (i = index) >= 0 && (i < (index = hi) || current != null)) { Node<K, V> p = current; current = null; do { if (p == null) p = tab[i++]; else { action.accept(p.key); p = p.next; } } while (p != null || i < hi); if (m.modCount != mc) throw new ConcurrentModificationException(); } } public boolean tryAdvance(Consumer<? super K> action) { int hi; if (action == null) throw new NullPointerException(); Node<K, V>[] tab = map.table; if (tab != null && tab.length >= (hi = getFence()) && index >= 0) { while (current != null || index < hi) { if (current == null) current = tab[index++]; else { K k = current.key; current = current.next; action.accept(k); if (map.modCount != expectedModCount) throw new ConcurrentModificationException(); return true; } } } return false; } public int characteristics() { return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) | Spliterator.DISTINCT; } } static final class ValueSpliterator<K, V> extends HashMapSpliterator<K, V> implements Spliterator<V> { ValueSpliterator(MyHashMap<K, V> m, int origin, int fence, int est, int expectedModCount) { super(m, origin, fence, est, expectedModCount); } public ValueSpliterator<K, V> trySplit() { int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; return (lo >= mid || current != null) ? null : new ValueSpliterator<>(map, lo, index = mid, est >>>= 1, expectedModCount); } public void forEachRemaining(Consumer<? super V> action) { int i, hi, mc; if (action == null) throw new NullPointerException(); MyHashMap<K, V> m = map; Node<K, V>[] tab = m.table; if ((hi = fence) < 0) { mc = expectedModCount = m.modCount; hi = fence = (tab == null) ? 0 : tab.length; } else mc = expectedModCount; if (tab != null && tab.length >= hi && (i = index) >= 0 && (i < (index = hi) || current != null)) { Node<K, V> p = current; current = null; do { if (p == null) p = tab[i++]; else { action.accept(p.value); p = p.next; } } while (p != null || i < hi); if (m.modCount != mc) throw new ConcurrentModificationException(); } } public boolean tryAdvance(Consumer<? super V> action) { int hi; if (action == null) throw new NullPointerException(); Node<K, V>[] tab = map.table; if (tab != null && tab.length >= (hi = getFence()) && index >= 0) { while (current != null || index < hi) { if (current == null) current = tab[index++]; else { V v = current.value; current = current.next; action.accept(v); if (map.modCount != expectedModCount) throw new ConcurrentModificationException(); return true; } } } return false; } public int characteristics() { return (fence < 0 || est == map.size ? Spliterator.SIZED : 0); } } static final class EntrySpliterator<K, V> extends HashMapSpliterator<K, V> implements Spliterator<Entry<K, V>> { EntrySpliterator(MyHashMap<K, V> m, int origin, int fence, int est, int expectedModCount) { super(m, origin, fence, est, expectedModCount); } public EntrySpliterator<K, V> trySplit() { int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; return (lo >= mid || current != null) ? null : new EntrySpliterator<>(map, lo, index = mid, est >>>= 1, expectedModCount); } public void forEachRemaining(Consumer<? super Entry<K, V>> action) { int i, hi, mc; if (action == null) throw new NullPointerException(); MyHashMap<K, V> m = map; Node<K, V>[] tab = m.table; if ((hi = fence) < 0) { mc = expectedModCount = m.modCount; hi = fence = (tab == null) ? 0 : tab.length; } else mc = expectedModCount; if (tab != null && tab.length >= hi && (i = index) >= 0 && (i < (index = hi) || current != null)) { Node<K, V> p = current; current = null; do { if (p == null) p = tab[i++]; else { action.accept(p); p = p.next; } } while (p != null || i < hi); if (m.modCount != mc) throw new ConcurrentModificationException(); } } public boolean tryAdvance(Consumer<? super Entry<K, V>> action) { int hi; if (action == null) throw new NullPointerException(); Node<K, V>[] tab = map.table; if (tab != null && tab.length >= (hi = getFence()) && index >= 0) { while (current != null || index < hi) { if (current == null) current = tab[index++]; else { Node<K, V> e = current; current = current.next; action.accept(e); if (map.modCount != expectedModCount) throw new ConcurrentModificationException(); return true; } } } return false; } public int characteristics() { return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) | Spliterator.DISTINCT; } } /* ------------------------------------------------------------ */ // LinkedHashMap support /* * The following package-protected methods are designed to be * overridden by LinkedHashMap, but not by any other subclass. * Nearly all other internal methods are also package-protected * but are declared final, so can be used by LinkedHashMap, view * classes, and HashSet. */ // Create a regular (non-tree) node Node<K, V> newNode(int hash, K key, V value, Node<K, V> next) { return new Node<>(hash, key, value, next); } // For conversion from TreeNodes to plain nodes Node<K, V> replacementNode(Node<K, V> p, Node<K, V> next) { return new Node<>(p.hash, p.key, p.value, next); } // Create a tree bin node TreeNode<K, V> newTreeNode(int hash, K key, V value, Node<K, V> next) { return new TreeNode<>(hash, key, value, next); } // For treeifyBin TreeNode<K, V> replacementTreeNode(Node<K, V> p, Node<K, V> next) { return new TreeNode<>(p.hash, p.key, p.value, next); } /** * Reset to initial default state. Called by clone and readObject. */ void reinitialize() { table = null; entrySet = null; keySet = null; values = null; modCount = 0; threshold = 0; size = 0; } // Callbacks to allow LinkedHashMap post-actions void afterNodeAccess(MyHashMap.Node<K, V> p) { } void afterNodeInsertion(boolean evict) { } void afterNodeRemoval(Node<K, V> p) { } // Called only from writeObject, to ensure compatible ordering. void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException { Node<K, V>[] tab; if (size > 0 && (tab = table) != null) { for (int i = 0; i < tab.length; ++i) { for (Node<K, V> e = tab[i]; e != null; e = e.next) { s.writeObject(e.key); s.writeObject(e.value); } } } } /* ------------------------------------------------------------ */ // Tree bins /** * Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn * extends Node) so can be used as extension of either regular or * linked node. */ static final class TreeNode<K, V> extends MyLinkedHashMap.Entry<K, V> { TreeNode<K, V> parent; // red-black tree links TreeNode<K, V> left; TreeNode<K, V> right; TreeNode<K, V> prev; // needed to unlink next upon deletion boolean red; TreeNode(int hash, K key, V val, Node<K, V> next) { super(hash, key, val, next); } /** * Returns root of tree containing this node. */ final TreeNode<K, V> root() { for (TreeNode<K, V> r = this, p; ; ) { if ((p = r.parent) == null) return r; r = p; } } /** * Ensures that the given root is the first node of its bin. */ static <K, V> void moveRootToFront(Node<K, V>[] tab, TreeNode<K, V> root) { int n; if (root != null && tab != null && (n = tab.length) > 0) { int index = (n - 1) & root.hash; TreeNode<K, V> first = (TreeNode<K, V>) tab[index]; if (root != first) { Node<K, V> rn; tab[index] = root; TreeNode<K, V> rp = root.prev; if ((rn = root.next) != null) ((TreeNode<K, V>) rn).prev = rp; if (rp != null) rp.next = rn; if (first != null) first.prev = root; root.next = first; root.prev = null; } assert checkInvariants(root); } } /** * Finds the node starting at root p with the given hash and key. * The kc argument caches comparableClassFor(key) upon first use * comparing keys. */ final TreeNode<K, V> find(int h, Object k, Class<?> kc) { TreeNode<K, V> p = this; do { int ph, dir; K pk; TreeNode<K, V> pl = p.left, pr = p.right, q; if ((ph = p.hash) > h) p = pl; else if (ph < h) p = pr; else if ((pk = p.key) == k || (k != null && k.equals(pk))) return p; else if (pl == null) p = pr; else if (pr == null) p = pl; else if ((kc != null || (kc = comparableClassFor(k)) != null) && (dir = compareComparables(kc, k, pk)) != 0) p = (dir < 0) ? pl : pr; else if ((q = pr.find(h, k, kc)) != null) return q; else p = pl; } while (p != null); return null; } /** * Calls find for root node. */ final TreeNode<K, V> getTreeNode(int h, Object k) { return ((parent != null) ? root() : this).find(h, k, null); } /** * Tie-breaking utility for ordering insertions when equal * hashCodes and non-comparable. We don't require a total * order, just a consistent insertion rule to maintain * equivalence across rebalancings. Tie-breaking further than * necessary simplifies testing a bit. */ static int tieBreakOrder(Object a, Object b) { int d; if (a == null || b == null || (d = a.getClass().getName(). compareTo(b.getClass().getName())) == 0) d = (System.identityHashCode(a) <= System.identityHashCode(b) ? -1 : 1); return d; } /** * Forms tree of the nodes linked from this node. * * @return root of tree */ final void treeify(Node<K, V>[] tab) { TreeNode<K, V> root = null; for (TreeNode<K, V> x = this, next; x != null; x = next) { next = (TreeNode<K, V>) x.next; x.left = x.right = null; if (root == null) { x.parent = null; x.red = false; root = x; } else { K k = x.key; int h = x.hash; Class<?> kc = null; for (TreeNode<K, V> p = root; ; ) { int dir, ph; K pk = p.key; if ((ph = p.hash) > h) dir = -1; else if (ph < h) dir = 1; else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0) dir = tieBreakOrder(k, pk); TreeNode<K, V> xp = p; if ((p = (dir <= 0) ? p.left : p.right) == null) { x.parent = xp; if (dir <= 0) xp.left = x; else xp.right = x; root = balanceInsertion(root, x); break; } } } } moveRootToFront(tab, root); } /** * Returns a list of non-TreeNodes replacing those linked from * this node. */ final Node<K, V> untreeify(MyHashMap<K, V> map) { Node<K, V> hd = null, tl = null; for (Node<K, V> q = this; q != null; q = q.next) { Node<K, V> p = map.replacementNode(q, null); if (tl == null) hd = p; else tl.next = p; tl = p; } return hd; } /** * Tree version of putVal. */ final TreeNode<K, V> putTreeVal(MyHashMap<K, V> map, Node<K, V>[] tab, int h, K k, V v) { Class<?> kc = null; boolean searched = false; TreeNode<K, V> root = (parent != null) ? root() : this; for (TreeNode<K, V> p = root; ; ) { int dir, ph; K pk; if ((ph = p.hash) > h) dir = -1; else if (ph < h) dir = 1; else if ((pk = p.key) == k || (k != null && k.equals(pk))) return p; else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0) { if (!searched) { TreeNode<K, V> q, ch; searched = true; if (((ch = p.left) != null && (q = ch.find(h, k, kc)) != null) || ((ch = p.right) != null && (q = ch.find(h, k, kc)) != null)) return q; } dir = tieBreakOrder(k, pk); } TreeNode<K, V> xp = p; if ((p = (dir <= 0) ? p.left : p.right) == null) { Node<K, V> xpn = xp.next; TreeNode<K, V> x = map.newTreeNode(h, k, v, xpn); if (dir <= 0) xp.left = x; else xp.right = x; xp.next = x; x.parent = x.prev = xp; if (xpn != null) ((TreeNode<K, V>) xpn).prev = x; moveRootToFront(tab, balanceInsertion(root, x)); return null; } } } /** * Removes the given node, that must be present before this call. * This is messier than typical red-black deletion code because we * cannot swap the contents of an interior node with a leaf * successor that is pinned by "next" pointers that are accessible * independently during traversal. So instead we swap the tree * linkages. If the current tree appears to have too few nodes, * the bin is converted back to a plain bin. (The test triggers * somewhere between 2 and 6 nodes, depending on tree structure). */ final void removeTreeNode(MyHashMap<K, V> map, Node<K, V>[] tab, boolean movable) { int n; if (tab == null || (n = tab.length) == 0) return; int index = (n - 1) & hash; TreeNode<K, V> first = (TreeNode<K, V>) tab[index], root = first, rl; TreeNode<K, V> succ = (TreeNode<K, V>) next, pred = prev; if (pred == null) tab[index] = first = succ; else pred.next = succ; if (succ != null) succ.prev = pred; if (first == null) return; if (root.parent != null) root = root.root(); if (root == null || root.right == null || (rl = root.left) == null || rl.left == null) { tab[index] = first.untreeify(map); // too small return; } TreeNode<K, V> p = this, pl = left, pr = right, replacement; if (pl != null && pr != null) { TreeNode<K, V> s = pr, sl; while ((sl = s.left) != null) // find successor s = sl; boolean c = s.red; s.red = p.red; p.red = c; // swap colors TreeNode<K, V> sr = s.right; TreeNode<K, V> pp = p.parent; if (s == pr) { // p was s's direct parent p.parent = s; s.right = p; } else { TreeNode<K, V> sp = s.parent; if ((p.parent = sp) != null) { if (s == sp.left) sp.left = p; else sp.right = p; } if ((s.right = pr) != null) pr.parent = s; } p.left = null; if ((p.right = sr) != null) sr.parent = p; if ((s.left = pl) != null) pl.parent = s; if ((s.parent = pp) == null) root = s; else if (p == pp.left) pp.left = s; else pp.right = s; if (sr != null) replacement = sr; else replacement = p; } else if (pl != null) replacement = pl; else if (pr != null) replacement = pr; else replacement = p; if (replacement != p) { TreeNode<K, V> pp = replacement.parent = p.parent; if (pp == null) root = replacement; else if (p == pp.left) pp.left = replacement; else pp.right = replacement; p.left = p.right = p.parent = null; } TreeNode<K, V> r = p.red ? root : balanceDeletion(root, replacement); if (replacement == p) { // detach TreeNode<K, V> pp = p.parent; p.parent = null; if (pp != null) { if (p == pp.left) pp.left = null; else if (p == pp.right) pp.right = null; } } if (movable) moveRootToFront(tab, r); } /** * Splits nodes in a tree bin into lower and upper tree bins, * or untreeifies if now too small. Called only from resize; * see above discussion about split bits and indices. * * @param map the map * @param tab the table for recording bin heads * @param index the index of the table being split * @param bit the bit of hash to split on */ final void split(MyHashMap<K, V> map, Node<K, V>[] tab, int index, int bit) { TreeNode<K, V> b = this; // Relink into lo and hi lists, preserving order TreeNode<K, V> loHead = null, loTail = null; TreeNode<K, V> hiHead = null, hiTail = null; int lc = 0, hc = 0; for (TreeNode<K, V> e = b, next; e != null; e = next) { next = (TreeNode<K, V>) e.next; e.next = null; if ((e.hash & bit) == 0) { if ((e.prev = loTail) == null) loHead = e; else loTail.next = e; loTail = e; ++lc; } else { if ((e.prev = hiTail) == null) hiHead = e; else hiTail.next = e; hiTail = e; ++hc; } } if (loHead != null) { if (lc <= UNTREEIFY_THRESHOLD) tab[index] = loHead.untreeify(map); else { tab[index] = loHead; if (hiHead != null) // (else is already treeified) loHead.treeify(tab); } } if (hiHead != null) { if (hc <= UNTREEIFY_THRESHOLD) tab[index + bit] = hiHead.untreeify(map); else { tab[index + bit] = hiHead; if (loHead != null) hiHead.treeify(tab); } } } /* ------------------------------------------------------------ */ // Red-black tree methods, all adapted from CLR static <K, V> TreeNode<K, V> rotateLeft(TreeNode<K, V> root, TreeNode<K, V> p) { TreeNode<K, V> r, pp, rl; if (p != null && (r = p.right) != null) { if ((rl = p.right = r.left) != null) rl.parent = p; if ((pp = r.parent = p.parent) == null) (root = r).red = false; else if (pp.left == p) pp.left = r; else pp.right = r; r.left = p; p.parent = r; } return root; } static <K, V> TreeNode<K, V> rotateRight(TreeNode<K, V> root, TreeNode<K, V> p) { TreeNode<K, V> l, pp, lr; if (p != null && (l = p.left) != null) { if ((lr = p.left = l.right) != null) lr.parent = p; if ((pp = l.parent = p.parent) == null) (root = l).red = false; else if (pp.right == p) pp.right = l; else pp.left = l; l.right = p; p.parent = l; } return root; } static <K, V> TreeNode<K, V> balanceInsertion(TreeNode<K, V> root, TreeNode<K, V> x) { x.red = true; for (TreeNode<K, V> xp, xpp, xppl, xppr; ; ) { if ((xp = x.parent) == null) { x.red = false; return x; } else if (!xp.red || (xpp = xp.parent) == null) return root; if (xp == (xppl = xpp.left)) { if ((xppr = xpp.right) != null && xppr.red) { xppr.red = false; xp.red = false; xpp.red = true; x = xpp; } else { if (x == xp.right) { root = rotateLeft(root, x = xp); xpp = (xp = x.parent) == null ? null : xp.parent; } if (xp != null) { xp.red = false; if (xpp != null) { xpp.red = true; root = rotateRight(root, xpp); } } } } else { if (xppl != null && xppl.red) { xppl.red = false; xp.red = false; xpp.red = true; x = xpp; } else { if (x == xp.left) { root = rotateRight(root, x = xp); xpp = (xp = x.parent) == null ? null : xp.parent; } if (xp != null) { xp.red = false; if (xpp != null) { xpp.red = true; root = rotateLeft(root, xpp); } } } } } } static <K, V> TreeNode<K, V> balanceDeletion(TreeNode<K, V> root, TreeNode<K, V> x) { for (TreeNode<K, V> xp, xpl, xpr; ; ) { if (x == null || x == root) return root; else if ((xp = x.parent) == null) { x.red = false; return x; } else if (x.red) { x.red = false; return root; } else if ((xpl = xp.left) == x) { if ((xpr = xp.right) != null && xpr.red) { xpr.red = false; xp.red = true; root = rotateLeft(root, xp); xpr = (xp = x.parent) == null ? null : xp.right; } if (xpr == null) x = xp; else { TreeNode<K, V> sl = xpr.left, sr = xpr.right; if ((sr == null || !sr.red) && (sl == null || !sl.red)) { xpr.red = true; x = xp; } else { if (sr == null || !sr.red) { if (sl != null) sl.red = false; xpr.red = true; root = rotateRight(root, xpr); xpr = (xp = x.parent) == null ? null : xp.right; } if (xpr != null) { xpr.red = (xp == null) ? false : xp.red; if ((sr = xpr.right) != null) sr.red = false; } if (xp != null) { xp.red = false; root = rotateLeft(root, xp); } x = root; } } } else { // symmetric if (xpl != null && xpl.red) { xpl.red = false; xp.red = true; root = rotateRight(root, xp); xpl = (xp = x.parent) == null ? null : xp.left; } if (xpl == null) x = xp; else { TreeNode<K, V> sl = xpl.left, sr = xpl.right; if ((sl == null || !sl.red) && (sr == null || !sr.red)) { xpl.red = true; x = xp; } else { if (sl == null || !sl.red) { if (sr != null) sr.red = false; xpl.red = true; root = rotateLeft(root, xpl); xpl = (xp = x.parent) == null ? null : xp.left; } if (xpl != null) { xpl.red = (xp == null) ? false : xp.red; if ((sl = xpl.left) != null) sl.red = false; } if (xp != null) { xp.red = false; root = rotateRight(root, xp); } x = root; } } } } } /** * Recursive invariant check */ static <K, V> boolean checkInvariants(TreeNode<K, V> t) { TreeNode<K, V> tp = t.parent, tl = t.left, tr = t.right, tb = t.prev, tn = (TreeNode<K, V>) t.next; if (tb != null && tb.next != t) return false; if (tn != null && tn.prev != t) return false; if (tp != null && t != tp.left && t != tp.right) return false; if (tl != null && (tl.parent != t || tl.hash > t.hash)) return false; if (tr != null && (tr.parent != t || tr.hash < t.hash)) return false; if (t.red && tl != null && tl.red && tr != null && tr.red) return false; if (tl != null && !checkInvariants(tl)) return false; if (tr != null && !checkInvariants(tr)) return false; return true; } } //用于查看map中当前数组长度 public int getSize() { return table.length; } //用于打印map中每个链表的内容 public void print() { for (int a = 0; a < table.length; a++) { System.out.print("第" + a + "个链表："); print(table[a]); System.out.println(); } } void print(Node<K, V> kvNode) { if (kvNode != null) { System.out.print(kvNode.key + " "); print(kvNode.next); } } }

MyLinkedHashMap

package com.map; /* * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved. * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. * * * * * * * * * * * * * * * * * * * * */ import java.util.*; import java.util.function.Consumer; import java.util.function.BiConsumer; import java.util.function.BiFunction; import java.io.IOException; /** * <p>Hash table and linked list implementation of the <tt>Map</tt> interface, * with predictable iteration order. This implementation differs from * <tt>HashMap</tt> in that it maintains a doubly-linked list running through * all of its entries. This linked list defines the iteration ordering, * which is normally the order in which keys were inserted into the map * (<i>insertion-order</i>). Note that insertion order is not affected * if a key is <i>re-inserted</i> into the map. (A key <tt>k</tt> is * reinserted into a map <tt>m</tt> if <tt>m.put(k, v)</tt> is invoked when * <tt>m.containsKey(k)</tt> would return <tt>true</tt> immediately prior to * the invocation.) * * <p>This implementation spares its clients from the unspecified, generally * chaotic ordering provided by {@link HashMap} (and {@link Hashtable}), * without incurring the increased cost associated with {@link TreeMap}. It * can be used to produce a copy of a map that has the same order as the * original, regardless of the original map's implementation: * <pre> * void foo(Map m) { * Map copy = new MyLinkedHashMap(m); * ... * } * </pre> * This technique is particularly useful if a module takes a map on input, * copies it, and later returns results whose order is determined by that of * the copy. (Clients generally appreciate having things returned in the same * order they were presented.) * * <p>A special {@link #MyLinkedHashMap(int, float, boolean) constructor} is * provided to create a linked hash map whose order of iteration is the order * in which its entries were last accessed, from least-recently accessed to * most-recently (<i>access-order</i>). This kind of map is well-suited to * building LRU caches. Invoking the {@code put}, {@code putIfAbsent}, * {@code get}, {@code getOrDefault}, {@code compute}, {@code computeIfAbsent}, * {@code computeIfPresent}, or {@code merge} methods results * in an access to the corresponding entry (assuming it exists after the * invocation completes). The {@code replace} methods only result in an access * of the entry if the value is replaced. The {@code putAll} method generates one * entry access for each mapping in the specified map, in the order that * key-value mappings are provided by the specified map's entry set iterator. * <i>No other methods generate entry accesses.</i> In particular, operations * on collection-views do <i>not</i> affect the order of iteration of the * backing map. * * <p>The {@link #removeEldestEntry(Map.Entry)} method may be overridden to * impose a policy for removing stale mappings automatically when new mappings * are added to the map. * * <p>This class provides all of the optional <tt>Map</tt> operations, and * permits null elements. Like <tt>HashMap</tt>, it provides constant-time * performance for the basic operations (<tt>add</tt>, <tt>contains</tt> and * <tt>remove</tt>), assuming the hash function disperses elements * properly among the buckets. Performance is likely to be just slightly * below that of <tt>HashMap</tt>, due to the added expense of maintaining the * linked list, with one exception: Iteration over the collection-views * of a <tt>MyLinkedHashMap</tt> requires time proportional to the <i>size</i> * of the map, regardless of its capacity. Iteration over a <tt>HashMap</tt> * is likely to be more expensive, requiring time proportional to its * <i>capacity</i>. * * <p>A linked hash map has two parameters that affect its performance: * <i>initial capacity</i> and <i>load factor</i>. They are defined precisely * as for <tt>HashMap</tt>. Note, however, that the penalty for choosing an * excessively high value for initial capacity is less severe for this class * than for <tt>HashMap</tt>, as iteration times for this class are unaffected * by capacity. * * <p><strong>Note that this implementation is not synchronized.</strong> * If multiple threads access a linked hash map concurrently, and at least * one of the threads modifies the map structurally, it <em>must</em> be * synchronized externally. This is typically accomplished by * synchronizing on some object that naturally encapsulates the map. * <p> * If no such object exists, the map should be "wrapped" using the * {@link Collections#synchronizedMap Collections.synchronizedMap} * method. This is best done at creation time, to prevent accidental * unsynchronized access to the map:<pre> * Map m = Collections.synchronizedMap(new MyLinkedHashMap(...));</pre> * <p> * A structural modification is any operation that adds or deletes one or more * mappings or, in the case of access-ordered linked hash maps, affects * iteration order. In insertion-ordered linked hash maps, merely changing * the value associated with a key that is already contained in the map is not * a structural modification. <strong>In access-ordered linked hash maps, * merely querying the map with <tt>get</tt> is a structural modification. * </strong>) * * <p>The iterators returned by the <tt>iterator</tt> method of the collections * returned by all of this class's collection view methods are * <em>fail-fast</em>: if the map is structurally modified at any time after * the iterator is created, in any way except through the iterator's own * <tt>remove</tt> method, the iterator will throw a {@link * ConcurrentModificationException}. Thus, in the face of concurrent * modification, the iterator fails quickly and cleanly, rather than risking * arbitrary, non-deterministic behavior at an undetermined time in the future. * * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed * as it is, generally speaking, impossible to make any hard guarantees in the * presence of unsynchronized concurrent modification. Fail-fast iterators * throw <tt>ConcurrentModificationException</tt> on a best-effort basis. * Therefore, it would be wrong to write a program that depended on this * exception for its correctness: <i>the fail-fast behavior of iterators * should be used only to detect bugs.</i> * * <p>The spliterators returned by the spliterator method of the collections * returned by all of this class's collection view methods are * <em><a href="Spliterator.html#binding">late-binding</a></em>, * <em>fail-fast</em>, and additionally report {@link Spliterator#ORDERED}. * * <p>This class is a member of the * <a href="{@docRoot}/../technotes/guides/collections/index.html"> * Java Collections Framework</a>. * * @param <K> the type of keys maintained by this map * @param <V> the type of mapped values * @author Josh Bloch * @implNote The spliterators returned by the spliterator method of the collections * returned by all of this class's collection view methods are created from * the iterators of the corresponding collections. * @see Object#hashCode() * @see Collection * @see Map * @see HashMap * @see TreeMap * @see Hashtable * @since 1.4 */ @SuppressWarnings("all") public class MyLinkedHashMap<K, V> extends MyHashMap<K, V> implements Map<K, V> { /* * Implementation note. A previous version of this class was * internally structured a little differently. Because superclass * HashMap now uses trees for some of its MyHashMap.Nodes, class * MyLinkedHashMap.Entry is now treated as intermediary MyHashMap.Node class * that can also be converted to tree form. The name of this * class, MyLinkedHashMap.Entry, is confusing in several ways in its * current context, but cannot be changed. Otherwise, even though * it is not exported outside this package, some existing source * code is known to have relied on a symbol resolution corner case * rule in calls to removeEldestEntry that suppressed compilation * errors due to ambiguous usages. So, we keep the name to * preserve unmodified compilability. * * The changes in MyHashMap.Node classes also require using two fields * (head, tail) rather than a pointer to a header MyHashMap.Node to maintain * the doubly-linked before/after list. This class also * previously used a different style of callback methods upon * access, insertion, and removal. */ /** * HashMap.Node subclass for normal MyLinkedHashMap entries. */ static class Entry<K, V> extends MyHashMap.Node<K, V> { Entry<K, V> before, after; Entry(int hash, K key, V value, MyHashMap.Node<K, V> next) { super(hash, key, value, next); } } private static final long serialVersionUID = 3801124242820219131L; /** * The head (eldest) of the doubly linked list. */ transient MyLinkedHashMap.Entry<K, V> head; /** * The tail (youngest) of the doubly linked list. */ transient MyLinkedHashMap.Entry<K, V> tail; /** * The iteration ordering method for this linked hash map: <tt>true</tt> * for access-order, <tt>false</tt> for insertion-order. * * @serial */ final boolean accessOrder; // internal utilities // link at the end of list private void linkNodeLast(MyLinkedHashMap.Entry<K, V> p) { MyLinkedHashMap.Entry<K, V> last = tail; tail = p; if (last == null) { head = p; } else { p.before = last; last.after = p; } } // apply src's links to dst private void transferLinks(MyLinkedHashMap.Entry<K, V> src, MyLinkedHashMap.Entry<K, V> dst) { MyLinkedHashMap.Entry<K, V> b = dst.before = src.before; MyLinkedHashMap.Entry<K, V> a = dst.after = src.after; if (b == null) head = dst; else b.after = dst; if (a == null) tail = dst; a.before = dst; } // overrides of HashMap hook methods void reinitialize() { super.reinitialize(); head = tail = null; } MyHashMap.Node<K, V> newNode(int hash, K key, V value, MyHashMap.Node<K, V> e) { MyLinkedHashMap.Entry<K, V> p = new MyLinkedHashMap.Entry<K, V>(hash, key, value, e); linkNodeLast(p); return p; } MyHashMap.Node<K, V> replacementNode(MyHashMap.Node<K, V> p, MyHashMap.Node<K, V> next) { MyLinkedHashMap.Entry<K, V> q = (MyLinkedHashMap.Entry<K, V>) p; MyLinkedHashMap.Entry<K, V> t = new MyLinkedHashMap.Entry<K, V>(q.hash, q.key, q.value, next); transferLinks(q, t); return t; } MyHashMap.TreeNode<K, V> newTreeNode(int hash, K key, V value, MyHashMap.Node<K, V> next) { MyHashMap.TreeNode<K, V> p = new MyHashMap.TreeNode<K, V>(hash, key, value, next); linkNodeLast(p); return p; } MyHashMap.TreeNode<K, V> replacementTreeNode(MyHashMap.Node<K, V> p, MyHashMap.Node<K, V> next) { MyLinkedHashMap.Entry<K, V> q = (MyLinkedHashMap.Entry<K, V>) p; MyHashMap.TreeNode<K, V> t = new MyHashMap.TreeNode<K, V>(q.hash, q.key, q.value, next); transferLinks(q, t); return t; } void afterNodeRemoval(MyHashMap.Node<K, V> e) { // unlink MyLinkedHashMap.Entry<K, V> p = (MyLinkedHashMap.Entry<K, V>) e, b = p.before, a = p.after; p.before = p.after = null; if (b == null) head = a; else b.after = a; if (a == null) tail = b; else a.before = b; } void afterNodeInsertion(boolean evict) { // possibly remove eldest MyLinkedHashMap.Entry<K, V> first; if (evict && (first = head) != null && removeEldestEntry(first)) { K key = first.key; removeNode(hash(key), key, null, false, true); } } void afterNodeAccess(MyHashMap.Node<K, V> e) { // move MyHashMap.Node to last MyLinkedHashMap.Entry<K, V> last; if (accessOrder && (last = tail) != e) { MyLinkedHashMap.Entry<K, V> p = (MyLinkedHashMap.Entry<K, V>) e, b = p.before, a = p.after; p.after = null; if (b == null) head = a; else b.after = a; if (a != null) a.before = b; else last = b; if (last == null) head = p; else { p.before = last; last.after = p; } tail = p; ++modCount; } } void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException { for (MyLinkedHashMap.Entry<K, V> e = head; e != null; e = e.after) { s.writeObject(e.key); s.writeObject(e.value); } } /** * Constructs an empty insertion-ordered <tt>MyLinkedHashMap</tt> instance * with the specified initial capacity and load factor. * * @param initialCapacity the initial capacity * @param loadFactor the load factor * @throws IllegalArgumentException if the initial capacity is negative * or the load factor is nonpositive */ public MyLinkedHashMap(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor); accessOrder = false; } /** * Constructs an empty insertion-ordered <tt>MyLinkedHashMap</tt> instance * with the specified initial capacity and a default load factor (0.75). * * @param initialCapacity the initial capacity * @throws IllegalArgumentException if the initial capacity is negative */ public MyLinkedHashMap(int initialCapacity) { super(initialCapacity); accessOrder = false; } /** * Constructs an empty insertion-ordered <tt>MyLinkedHashMap</tt> instance * with the default initial capacity (16) and load factor (0.75). */ public MyLinkedHashMap() { super(); accessOrder = false; } /** * Constructs an insertion-ordered <tt>MyLinkedHashMap</tt> instance with * the same mappings as the specified map. The <tt>MyLinkedHashMap</tt> * instance is created with a default load factor (0.75) and an initial * capacity sufficient to hold the mappings in the specified map. * * @param m the map whose mappings are to be placed in this map * @throws NullPointerException if the specified map is null */ public MyLinkedHashMap(Map<? extends K, ? extends V> m) { super(); accessOrder = false; putMapEntries(m, false); } /** * Constructs an empty <tt>MyLinkedHashMap</tt> instance with the * specified initial capacity, load factor and ordering mode. * * @param initialCapacity the initial capacity * @param loadFactor the load factor * @param accessOrder the ordering mode - <tt>true</tt> for * access-order, <tt>false</tt> for insertion-order * @throws IllegalArgumentException if the initial capacity is negative * or the load factor is nonpositive */ public MyLinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder; } /** * Returns <tt>true</tt> if this map maps one or more keys to the * specified value. * * @param value value whose presence in this map is to be tested * @return <tt>true</tt> if this map maps one or more keys to the * specified value */ public boolean containsValue(Object value) { for (MyLinkedHashMap.Entry<K, V> e = head; e != null; e = e.after) { V v = e.value; if (v == value || (value != null && value.equals(v))) return true; } return false; } /** * Returns the value to which the specified key is mapped, * or {@code null} if this map contains no mapping for the key. * * <p>More formally, if this map contains a mapping from a key * {@code k} to a value {@code v} such that {@code (key==null ? k==null : * key.equals(k))}, then this method returns {@code v}; otherwise * it returns {@code null}. (There can be at most one such mapping.) * * <p>A return value of {@code null} does not <i>necessarily</i> * indicate that the map contains no mapping for the key; it's also * possible that the map explicitly maps the key to {@code null}. * The {@link #containsKey containsKey} operation may be used to * distinguish these two cases. */ public V get(Object key) { MyHashMap.Node<K, V> e; if ((e = getNode(hash(key), key)) == null) return null; if (accessOrder) afterNodeAccess(e); return e.value; } /** * {@inheritDoc} */ public V getOrDefault(Object key, V defaultValue) { MyHashMap.Node<K, V> e; if ((e = getNode(hash(key), key)) == null) return defaultValue; if (accessOrder) afterNodeAccess(e); return e.value; } /** * {@inheritDoc} */ public void clear() { super.clear(); head = tail = null; } /** * Returns <tt>true</tt> if this map should remove its eldest entry. * This method is invoked by <tt>put</tt> and <tt>putAll</tt> after * inserting a new entry into the map. It provides the implementor * with the opportunity to remove the eldest entry each time a new one * is added. This is useful if the map represents a cache: it allows * the map to reduce memory consumption by deleting stale entries. * * <p>Sample use: this override will allow the map to grow up to 100 * entries and then delete the eldest entry each time a new entry is * added, maintaining a steady state of 100 entries. * <pre> * private static final int MAX_ENTRIES = 100; * * protected boolean removeEldestEntry(Map.Entry eldest) { * return size() &gt; MAX_ENTRIES; * } * </pre> * * <p>This method typically does not modify the map in any way, * instead allowing the map to modify itself as directed by its * return value. It <i>is</i> permitted for this method to modify * the map directly, but if it does so, it <i>must</i> return * <tt>false</tt> (indicating that the map should not attempt any * further modification). The effects of returning <tt>true</tt> * after modifying the map from within this method are unspecified. * * <p>This implementation merely returns <tt>false</tt> (so that this * map acts like a normal map - the eldest element is never removed). * * @param eldest The least recently inserted entry in the map, or if * this is an access-ordered map, the least recently accessed * entry. This is the entry that will be removed it this * method returns <tt>true</tt>. If the map was empty prior * to the <tt>put</tt> or <tt>putAll</tt> invocation resulting * in this invocation, this will be the entry that was just * inserted; in other words, if the map contains a single * entry, the eldest entry is also the newest. * @return <tt>true</tt> if the eldest entry should be removed * from the map; <tt>false</tt> if it should be retained. */ protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return false; } /** * Returns a {@link Set} view of the keys contained in this map. * The set is backed by the map, so changes to the map are * reflected in the set, and vice-versa. If the map is modified * while an iteration over the set is in progress (except through * the iterator's own <tt>remove</tt> operation), the results of * the iteration are undefined. The set supports element removal, * which removes the corresponding mapping from the map, via the * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> * operations. It does not support the <tt>add</tt> or <tt>addAll</tt> * operations. * Its {@link Spliterator} typically provides faster sequential * performance but much poorer parallel performance than that of * {@code HashMap}. * * @return a set view of the keys contained in this map */ public Set<K> keySet() { Set<K> ks = keySet; if (ks == null) { ks = new LinkedKeySet(); keySet = ks; } return ks; } final class LinkedKeySet extends AbstractSet<K> { public final int size() { return size; } public final void clear() { MyLinkedHashMap.this.clear(); } public final Iterator<K> iterator() { return new LinkedKeyIterator(); } 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 Spliterator<K> spliterator() { return Spliterators.spliterator(this, Spliterator.SIZED | Spliterator.ORDERED | Spliterator.DISTINCT); } public final void forEach(Consumer<? super K> action) { if (action == null) throw new NullPointerException(); int mc = modCount; for (MyLinkedHashMap.Entry<K, V> e = head; e != null; e = e.after) action.accept(e.key); if (modCount != mc) throw new ConcurrentModificationException(); } } /** * Returns a {@link Collection} view of the values contained in this map. * The collection is backed by the map, so changes to the map are * reflected in the collection, and vice-versa. If the map is * modified while an iteration over the collection is in progress * (except through the iterator's own <tt>remove</tt> operation), * the results of the iteration are undefined. The collection * supports element removal, which removes the corresponding * mapping from the map, via the <tt>Iterator.remove</tt>, * <tt>Collection.remove</tt>, <tt>removeAll</tt>, * <tt>retainAll</tt> and <tt>clear</tt> operations. It does not * support the <tt>add</tt> or <tt>addAll</tt> operations. * Its {@link Spliterator} typically provides faster sequential * performance but much poorer parallel performance than that of * {@code HashMap}. * * @return a view of the values contained in this map */ public Collection<V> values() { Collection<V> vs = values; if (vs == null) { vs = new LinkedValues(); values = vs; } return vs; } final class LinkedValues extends AbstractCollection<V> { public final int size() { return size; } public final void clear() { MyLinkedHashMap.this.clear(); } public final Iterator<V> iterator() { return new LinkedValueIterator(); } public final boolean contains(Object o) { return containsValue(o); } public final Spliterator<V> spliterator() { return Spliterators.spliterator(this, Spliterator.SIZED | Spliterator.ORDERED); } public final void forEach(Consumer<? super V> action) { if (action == null) throw new NullPointerException(); int mc = modCount; for (MyLinkedHashMap.Entry<K, V> e = head; e != null; e = e.after) action.accept(e.value); if (modCount != mc) throw new ConcurrentModificationException(); } } /** * Returns a {@link Set} view of the mappings contained in this map. * The set is backed by the map, so changes to the map are * reflected in the set, and vice-versa. If the map is modified * while an iteration over the set is in progress (except through * the iterator's own <tt>remove</tt> operation, or through the * <tt>setValue</tt> operation on a map entry returned by the * iterator) the results of the iteration are undefined. The set * supports element removal, which removes the corresponding * mapping from the map, via the <tt>Iterator.remove</tt>, * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and * <tt>clear</tt> operations. It does not support the * <tt>add</tt> or <tt>addAll</tt> operations. * Its {@link Spliterator} typically provides faster sequential * performance but much poorer parallel performance than that of * {@code HashMap}. * * @return a set view of the mappings contained in this map */ public Set<Map.Entry<K, V>> entrySet() { Set<Map.Entry<K, V>> es; return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es; } final class LinkedEntrySet extends AbstractSet<Map.Entry<K, V>> { public final int size() { return size; } public final void clear() { MyLinkedHashMap.this.clear(); } public final Iterator<Map.Entry<K, V>> iterator() { return new LinkedEntryIterator(); } public final boolean contains(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry<?, ?> e = (Map.Entry<?, ?>) o; Object key = e.getKey(); MyHashMap.Node<K, V> candidate = getNode(hash(key), key); return candidate != null && candidate.equals(e); } public final boolean remove(Object o) { if (o instanceof Map.Entry) { Map.Entry<?, ?> e = (Map.Entry<?, ?>) o; Object key = e.getKey(); Object value = e.getValue(); return removeNode(hash(key), key, value, true, true) != null; } return false; } public final Spliterator<Map.Entry<K, V>> spliterator() { return Spliterators.spliterator(this, Spliterator.SIZED | Spliterator.ORDERED | Spliterator.DISTINCT); } public final void forEach(Consumer<? super Map.Entry<K, V>> action) { if (action == null) throw new NullPointerException(); int mc = modCount; for (MyLinkedHashMap.Entry<K, V> e = head; e != null; e = e.after) action.accept(e); if (modCount != mc) throw new ConcurrentModificationException(); } } // Map overrides public void forEach(BiConsumer<? super K, ? super V> action) { if (action == null) throw new NullPointerException(); int mc = modCount; for (MyLinkedHashMap.Entry<K, V> e = head; e != null; e = e.after) action.accept(e.key, e.value); if (modCount != mc) throw new ConcurrentModificationException(); } public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) { if (function == null) throw new NullPointerException(); int mc = modCount; for (MyLinkedHashMap.Entry<K, V> e = head; e != null; e = e.after) e.value = function.apply(e.key, e.value); if (modCount != mc) throw new ConcurrentModificationException(); } // Iterators abstract class LinkedHashIterator { MyLinkedHashMap.Entry<K, V> next; MyLinkedHashMap.Entry<K, V> current; int expectedModCount; LinkedHashIterator() { next = head; expectedModCount = modCount; current = null; } public final boolean hasNext() { return next != null; } final MyLinkedHashMap.Entry<K, V> nextNode() { MyLinkedHashMap.Entry<K, V> e = next; if (modCount != expectedModCount) throw new ConcurrentModificationException(); if (e == null) throw new NoSuchElementException(); current = e; next = e.after; return e; } public final void remove() { MyHashMap.Node<K, V> p = current; if (p == null) throw new IllegalStateException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); current = null; K key = p.key; removeNode(hash(key), key, null, false, false); expectedModCount = modCount; } } final class LinkedKeyIterator extends LinkedHashIterator implements Iterator<K> { public final K next() { return nextNode().getKey(); } } final class LinkedValueIterator extends LinkedHashIterator implements Iterator<V> { public final V next() { return nextNode().value; } } final class LinkedEntryIterator extends LinkedHashIterator implements Iterator<Map.Entry<K, V>> { public final Map.Entry<K, V> next() { return nextNode(); } } public void test() { Node node = null; for (int a = 0; a < 10; a++) { Node node1 = new Node(a, a, a, node); node = node1; } while (node.next != null) { System.out.println(node.key); node = node.next; } afterNodeAccess(node); while (node.next != null) { System.out.println(node.key); node = node.next; } } }

因为java的类加载器存在双亲委派机制，如果说再写一个HashMap的话会优先加载原有的，自己写的如果在同一个包下是不会加载的且会报错，当然也可以放在不同的包下，但是因为名称相同，且里面有静态方法，稍微不注意就会出现包导入错误的情况，为了避免这些问题便于区分，写一个自己的map是比较保险的，而HashMap和LinkedHashMap之间有相互调用，所以两个都必须同时重写。

新增方法:

用于查看map中的数组长度和查看map中每个链表的内容

//用于查看map中当前数组长度 public int getSize() { return table.length; } //用于打印map中每个链表的内容 public void print() { for (int a = 0; a < table.length; a++) { System.out.print("第" + a + "个链表："); print(table[a]); System.out.println(); } } void print(Node<K, V> kvNode) { if (kvNode != null) { System.out.print(kvNode.key + " "); print(kvNode.next); } }

探索方法：

1.put方法

/** * Implements Map.put and related methods * * @param hash hash for key * @param key the key * @param value the value to put * @param onlyIfAbsent if true, don't change existing value * @param evict if false, the table is in creation mode. * @return previous value, or null if none */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K, V>[] tab; Node<K, V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) { //当第一次put时创建table使用 n = (tab = resize()).length; } int i1 = n - 1; i = i1 & hash; //1.根据hah值确定咋那个hash槽 //2.如果这个槽中没有链表则直接创建一个链表，并且唯一元素为当前的k-v //3.如果这个槽存在链表则直接把内容加在链表后 if ((p = tab[i]) == null) { //当第一个槽存入数据创建链表时使用 tab[i] = newNode(hash, key, value, null); } else { // System.out.println(p.key + "-->" + p.value); MyHashMap.Node<K, V> e; K k; //1.p表示数据会存放的链表 //2.k表示链表第一个元素的key //这一个方法仅表示当存入的key为已有的key的时候的情况 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //表示当链表太长已经转换成红黑树的时候 else if (p instanceof MyHashMap.TreeNode) e = ((MyHashMap.TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { //从第一个节点开始判断，当下一个节点为空的时候就把这个k-v数据节点的指定为最后一个节点的下一节点 //注：因为前面第一个判断中已经有判断如果说当前的key与链表中的唯一一个key相等的时候会直接跳过， // 不会执行到这里来了，所以这里默认的是这个key一定不会与链表的key相同 if ((e = p.next) == null) { 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)))) break; //这里的切换p时为了让临时变量指向他的下一个节点，继续判断下一节点是否有下一节点，轮询链表去判断值需要存入的key是否存在 p = e; } } // System.out.println(hash + "--" + key + "--" + i); // System.out.println("start:" + tab[i].key); if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); // System.out.println("end:" + tab[i].key); return oldValue; } } ++modCount; if (++size > threshold) { resize(); System.out.println(key + "扩容"); } afterNodeInsertion(evict); // System.out.println("key:" + key + " table。size:" + table.length); return null; }

这个方法里为当有一个键值对要存储的时候，需要确定存储在哪个链表，然后链表中判断是否存在这个key，替换新增扩容等方式，关键代码注释都已经标注。

2.扩容方法

/** * Initializes or doubles table size. 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 Node<K, V>[] resize() { Node<K, 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 } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults newCap = 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"}) Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap]; table = newTab; if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K, 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) ((TreeNode<K, V>) e).split(this, newTab, j, oldCap); else { // preserve order Node<K, V> loHead = null, loTail = null; Node<K, V> hiHead = null, hiTail = null; Node<K, V> next; do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.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; }

这个方法的原理比较简单，概括地说就是创建一个新的数组，把原有的map中的所有key值的hash值进行重新计算后写入到另外一个数组中去 修改形参指向地址就可以了。

3.get方法

/** * Implements Map.get and related methods * * @param hash hash for key * @param key the key * @return the node, or null if none */ final MyHashMap.Node<K, V> getNode(int hash, Object key) { MyHashMap.Node<K, V>[] tab; MyHashMap.Node<K, V> first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != 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 ((TreeNode<K, 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; }

get方法也比较简单，也只是根据key计算出hash值判断后到相应的链表去遍历链表的内容后取出相应的值。

4.转换红黑树方法

final void treeifyBin(Node<K, V>[] tab, int hash) {}

因为红黑树的触发条件需要链表长度达到8，手动改小了看不出效果，而要找8个都在统一链表的元素又比较困难所以不好使用实际数据展示效果，而且转换红黑树的方法并非hashmap中特有的，可以说是直接引用了红黑树数据结构的算法，建议查看红黑树数据结构及算法。

结果验证

1.当桶的数量小于64

public static void main(String[] args) { //经测试已知定义好一个数组长度为4的hashmap数组，a,a2,97三个key在根据计算会存入到同一个链表中去 MyHashMap map = new MyHashMap(4); map.put("a1", "a1"); map.put("a2", "a2"); map.put("a", "a1"); map.put(97, "a2"); map.put("a", "a3"); map.put(97, "a2"); map.put("a", "a3"); System.out.println("数组长度：" + map.getSize()); System.out.println("key的数量：" + map.size()); System.out.println("map的链表展示："); map.print(); }

运行结果

数组长度：8 key的数量：4 map的链表展示： 第0个链表：a1 第1个链表：a2 a 97 第2个链表： 第3个链表： 第4个链表： 第5个链表： 第6个链表： 第7个链表：

可以看到桶的数量设置初始化为4，当有四个key时，这个时候只占用了两个链表没达到4的0.75倍，但是还是扩容了。

2.当桶的数量大于64

public static void main(String[] args) { MyHashMap map = new MyHashMap(128); for (int a = 0; a < 94; a++) { map.put(a, a); } map.put("a97", "a2"); map.put("a", "a1"); map.put(97, "a2"); System.out.println("map的链表展示："); map.print(); System.out.println("数组长度：" + map.getSize()); System.out.println("key的数量：" + map.size()); } map的链表展示： 第0个链表：0 第1个链表：1 第2个链表：2 第3个链表：3 第4个链表：4 第5个链表：5 第6个链表：6 第7个链表：7 第8个链表：8 第9个链表：9 第10个链表：10 第11个链表：11 第12个链表：12 第13个链表：13 第14个链表：14 第15个链表：15 第16个链表：16 第17个链表：17 第18个链表：18 第19个链表：19 第20个链表：20 第21个链表：21 第22个链表：22 第23个链表：23 第24个链表：24 第25个链表：25 第26个链表：26 第27个链表：27 第28个链表：28 第29个链表：29 第30个链表：30 第31个链表：31 第32个链表：32 第33个链表：33 第34个链表：34 第35个链表：35 第36个链表：36 第37个链表：37 第38个链表：38 第39个链表：39 第40个链表：40 第41个链表：41 第42个链表：42 第43个链表：43 第44个链表：44 第45个链表：45 第46个链表：46 第47个链表：47 第48个链表：48 第49个链表：49 第50个链表：50 第51个链表：51 第52个链表：52 第53个链表：53 第54个链表：54 第55个链表：55 第56个链表：56 第57个链表：57 第58个链表：58 第59个链表：59 第60个链表：60 第61个链表：61 第62个链表：62 a97 第63个链表：63 第64个链表：64 第65个链表：65 第66个链表：66 第67个链表：67 第68个链表：68 第69个链表：69 第70个链表：70 第71个链表：71 第72个链表：72 第73个链表：73 第74个链表：74 第75个链表：75 第76个链表：76 第77个链表：77 第78个链表：78 第79个链表：79 第80个链表：80 第81个链表：81 第82个链表：82 第83个链表：83 第84个链表：84 第85个链表：85 第86个链表：86 第87个链表：87 第88个链表：88 第89个链表：89 第90个链表：90 第91个链表：91 第92个链表：92 第93个链表：93 第94个链表： 第95个链表： 第96个链表： 第97个链表：a 97 第98个链表： 第99个链表： 第100个链表： 第101个链表： 第102个链表： 第103个链表： 第104个链表： 第105个链表： 第106个链表： 第107个链表： 第108个链表： 第109个链表： 第110个链表： 第111个链表： 第112个链表： 第113个链表： 第114个链表： 第115个链表： 第116个链表： 第117个链表： 第118个链表： 第119个链表： 第120个链表： 第121个链表： 第122个链表： 第123个链表： 第124个链表： 第125个链表： 第126个链表： 第127个链表： 第128个链表： 第129个链表： 第130个链表： 第131个链表： 第132个链表： 第133个链表： 第134个链表： 第135个链表： 第136个链表： 第137个链表： 第138个链表： 第139个链表： 第140个链表： 第141个链表： 第142个链表： 第143个链表： 第144个链表： 第145个链表： 第146个链表： 第147个链表： 第148个链表： 第149个链表： 第150个链表： 第151个链表： 第152个链表： 第153个链表： 第154个链表： 第155个链表： 第156个链表： 第157个链表： 第158个链表： 第159个链表： 第160个链表： 第161个链表： 第162个链表： 第163个链表： 第164个链表： 第165个链表： 第166个链表： 第167个链表： 第168个链表： 第169个链表： 第170个链表： 第171个链表： 第172个链表： 第173个链表： 第174个链表： 第175个链表： 第176个链表： 第177个链表： 第178个链表： 第179个链表： 第180个链表： 第181个链表： 第182个链表： 第183个链表： 第184个链表： 第185个链表： 第186个链表： 第187个链表： 第188个链表： 第189个链表： 第190个链表： 第191个链表： 第192个链表： 第193个链表： 第194个链表： 第195个链表： 第196个链表： 第197个链表： 第198个链表： 第199个链表： 第200个链表： 第201个链表： 第202个链表： 第203个链表： 第204个链表： 第205个链表： 第206个链表： 第207个链表： 第208个链表： 第209个链表： 第210个链表： 第211个链表： 第212个链表： 第213个链表： 第214个链表： 第215个链表： 第216个链表： 第217个链表： 第218个链表： 第219个链表： 第220个链表： 第221个链表： 第222个链表： 第223个链表： 第224个链表： 第225个链表： 第226个链表： 第227个链表： 第228个链表： 第229个链表： 第230个链表： 第231个链表： 第232个链表： 第233个链表： 第234个链表： 第235个链表： 第236个链表： 第237个链表： 第238个链表： 第239个链表： 第240个链表： 第241个链表： 第242个链表： 第243个链表： 第244个链表： 第245个链表： 第246个链表： 第247个链表： 第248个链表： 第249个链表： 第250个链表： 第251个链表： 第252个链表： 第253个链表： 第254个链表： 第255个链表： 数组长度：256 key的数量：97

从运行结果可以看到这里设置初始长度为128，共计录入了97个key,但是序号64和序号97的链表中都有两个元素，因此被占用的桶只有95个小于128*0.75，但是还是扩容了。

结论：

探索结果： 从测试代码及最后的结果我们可以看到无论桶的数量大于64还是小于64，他的扩容因素都是取决于key的数量，而不是桶的占用树。 1. hashmap的数组长度是根据key的数量决定的，而不是根据已经占用的数组长度决定的，这样就有可能会存在很多数组长度远大于key数量的情况，感觉不是很合理，在这种情况下的话就类似于一个数组，不过索引是根据hash值确当的，不允许自己指定，有点在于删除不会修改其他索引数据的位置，效率会更快一些，不过感觉数组长度拉这么长不是很合理，有一点浪费空间，但是当key数量足够大的时候可以尽可能减少hash碰撞次数，各有利弊。 2.可以看到桶数量小于64时上面的第二个链表存入顺序为a2,a,7,a,97,a,但是到最后链表的第一个元素永远是存入的第一个元素a2，所以新增的元素是依此存在链表尾部的，据说jdk1.7之前时放在头部，因为没有1.7了就没去验证。

注：

此结果为本人测试结果，如果不当之处请大家指正，欢迎大家亲自测试参与讨论。

最后建议大家自己把代码复制到开发工具中运行一下，想要探索哪里就对哪里加日志，这种方式相对于看源码亲手操作过后更容易理解记忆，相对于debug模式有历史记录信息可以查看也比较明了，比较推荐大家使用这种方法。