staticclassEntry<K,V> implementsMap.Entry<K,V> { final K key; V value; //存储指向下一个Entry的引用,单链表结构 Entry<K,V> next; //对key的hashcode值进行hash运算后得到的值,存储在Entry,避免重复计算 int hash; /** * Creates new entry. */ Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; } }
/**这是一个神奇的函数,用了很多的异或,移位等运算 * 对key的hashcode进一步进行计算以及二进制位的调整等 * 来保证最终获取的存储位置尽量分布均匀 */ finalinthash(Object k){ int h = hashSeed; if (0 != h && k instanceof String) { return sun.misc.Hashing.stringHash32((String) k); }
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); }
以上hash函数计算出的值,通过indexFor进一步处理来获取实际的存储位置
1 2 3 4 5 6
/** * 返回数组下标 */ staticintindexFor(int h, int length){ return h & (length-1); }
/** * The default initial capacity - MUST be a power of two. * 默认容量,1向左移位4个,00000001变成00010000, * 也就是2的4次方为16,使用移位是因为移位是计算机基础运算,效率比加减乘除快。 */ staticfinalint 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. */ staticfinalint MAXIMUM_CAPACITY = 1 << 30;
/** * The load factor used when none specified in constructor. * 用于扩容的加载因子 */ staticfinalfloat 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. * 当桶的数量大于该值时,会把链表结构转换成红黑树结构 */ staticfinalint 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. * 当桶的节点数量小于该值时,会自动转换成链表结构,前天是当前结构为红黑树 */ staticfinalint 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. * 当hashmap中元素的数量大于该值时,桶的存储结构也会转换成红黑树 */ staticfinalint MIN_TREEIFY_CAPACITY = 64;
/** * Basic hash bin node, used for most entries. (See below for * TreeNode subclass, and in LinkedHashMap for its Entry subclass.) * 链表结构定义 */ staticclassNode<K,V> implementsMap.Entry<K,V> { finalint hash; final K key; V value; Node<K,V> next;
publicfinal V setValue(V newValue){ V oldValue = value; value = newValue; return oldValue; }
publicfinalbooleanequals(Object o){ if (o == this) returntrue; if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) returntrue; } returnfalse; } }
/* ---------------- 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修饰,表示不被序列化 */ transient Node<K,V>[] table;
/** * Holds cached entrySet(). Note that AbstractMap fields are used * for keySet() and values(). * 将数据转换成set的另一种存储形式,这个变量主要用于迭代功能 */ transient Set<Map.Entry<K,V>> entrySet;
/** * The number of key-value mappings contained in this map. * 元素数量,实际存储key-value键值对的数量 */ transientint 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). * 统计map的结构化修改次数 */ transientint 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 */ finalfloat loadFactor; /** * Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn * extends Node) so can be used as extension of either regular or * linked node. * -- 红黑树结构 */ staticfinalclassTreeNode<K,V> extendsLinkedHashMap.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); }
/** * 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. * 使用key的hashCode进行移位异或运算,尽量避免hash碰撞 * 如果在修改某个对象的hashCode方法时需要尽量保障唯一性, * 否则在使用map数据结构存储时会出现数据覆盖的问题 */ staticfinalinthash(Object key){ int h; /** * 1.首先获取key的hashCode值 * 2.将hashCode值的高16位参与运算 */ return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
/** * 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 #put(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 Node<K,V> getNode(int hash, Object key){ Node<K,V>[] tab; Node<K,V> first, e; int n; K k; /** * 只有当table不为空,且table长度大于0, * 且table索引位置(使用table.length - 1和hash值进行位与运算)的节点不为空 */ if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { /** * 2.检查first节点的hash值和key是否和入参的一样, * 如果一样则first即为目标节点,直接返回first节点 */ if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; /** * 3.如果first不是目标节点,并且first的next节点不为空则继续遍历 */ if ((e = first.next) != null) { if (first instanceof TreeNode) /** * 3.如果first不是目标节点,并且first的next节点不为空则继续遍历 */ return ((TreeNode<K,V>)first).getTreeNode(hash, key); do { /** * 5.执行链表节点的查找,向下遍历链表, 直至找到节点的key和入参的key相等时,返回该节点 */ if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } // 没有查询到数据 returnnull; }
/** * 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; } }
/** * 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.(初始化时使用false) * @return previous value, or null if none */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict){ /** * tab 哈希数组, * p 该哈希桶的首节点, * n hashMap的长度, * i 计算出的数组下标 */ Node<K,V>[] tab; Node<K,V> p; int n, i; /** * 1.使用懒加载的方式完成table的初始化(通过扩容完成:resize方法) * 2.如果table为空或者长度为0,则调用resize完成初始化 */ if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; /** * 通过hash值计算索引位置,如果计算出的该哈希桶的位置没有值, * 则把新插入的key-value放到此处,并且赋值给p(首节点) */ if ((p = tab[i = (n - 1) & hash]) == null) //如果p(首节点)为空,则在该索引位置新增一个节点 tab[i] = newNode(hash, key, value, null); else { /** * table索引位置不为空,及首节点不为空,则进行查找 */ // e 临时节点的作用, k 存放该当前节点的key Node<K,V> e; K k; /** * 第一种:插入的key-value的hash值,key都与当前节点的相等,e = p, * 则表示为首节点 */ if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; /** * 第二种:hash值不等于首节点,判断该p是否属于红黑树的节点 */ elseif (p instanceof TreeNode) /** * 为红黑树的节点,则在红黑树中进行添加, * 如果该节点已经存在,则返回该节点(不为null), * 该值很重要,用来判断put操作是否成功,如果添加成功返回null */ e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); /** * 第三种,hash值不等于首节点,不为红黑树的节点,则为链表的节点,使用binCount统计链表数 */ else { for (int binCount = 0; ; ++binCount) {// 遍历链表 /** * 如果找到尾部,则表明添加的key-value没有重复,在尾部进行添加 */ if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); // 判断是否转换成红黑树结构,减1,是由于循环从p的下一个节点开始 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } // 如果链表中有重复的key,e则为当前重复的节点,结束循环 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; // 将p指向下一个节点 } } /** * 如果存在重复key,则使用新值插入,并且返回旧值 */ if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } /** * 在没有重复值的情况下,完成以下操作 * 1.modCount + 1 * 2.实际长度size + 1 * 3.根据实际情况完成扩容 * 4.返回null,表示添加成功 */ ++modCount; if (++size > threshold) resize(); // 该方法目前未具体实现,在LinkedHashMap中有实现 afterNodeInsertion(evict); returnnull; }
/** * 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. * - 用于不可比较或者hashCode相同时进行比较的方法, * - 只是一个一致的插入规则,用来维护重定位的等价性。 */ staticinttieBreakOrder(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; }