public class HashMap extends AbstractMap implements Map , Cloneable, Serializable { private static final long serialVersionUID = 362498820763181265L; ... }复制代码
/** * 默认的初始化容量，必须是2的幂次方 */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 /** * 最大容量，如果构造函数隐式地指定了一个更高的初始容量， * 那么就默认使用此最大容量。也必须是2的幂次方 */ static final int MAXIMUM_CAPACITY = 1 << 30; /** * 加载因子，默认是0.75，也可以由构造函数指定 * 它代表的意思是如果当前添加的元素个数除以当前容量大于等于加载因子， * 那么容量扩容为当前容量的2倍 */ static final float DEFAULT_LOAD_FACTOR = 0.75f; /** * 当链表存储数据的个数大于等于8的时候，链表就会转换成红黑树 * 因为红黑树比链表的查找效率要高（红黑树属于特殊的搜索二叉树） */ static final int TREEIFY_THRESHOLD = 8; /** * 当红黑树中存储的数据个数小于等于6的时候，红黑树就会自动转换成链表了。 */ static final int UNTREEIFY_THRESHOLD = 6; /** * 存储Node 数据的底层数组，第一次使用需要初始化，存储的数据个数达到阀值的时候要扩容 * 它的容量要是2的幂次方 */ transient Node [] table;复制代码
Node内部类
/** * HashMap中的内部类，用来存储key和value的。 */ static class Node implements Map.Entry { final int hash; final K key; V value; Node next; Node(int hash, K key, V value, Node 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; } ... }复制代码
四个构造函数
/** * 指定初始化容量和加载因子 * * @param initialCapacity 初始化容量 * @param loadFactor 加载因子 */ public HashMap(int initialCapacity, float loadFactor) { //初始容量小于0，抛出异常 if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); //如果传入的初始化容量大于默认的最大容量，就把默认的最大容量作为初始化容量 if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; //如果加载因子小于等于0或者为空，抛出异常 if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); } /** * 仅指定初始化容量 * * @param initialCapacity 初始化容量. */ public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } /** * 使用默认的初始化容量 16 和默认的加载因子 0.75 */ public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } /** * 传入一个hashMap对象 * */ public HashMap(Map m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }复制代码
putMapEntries分析
/** * 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 m, boolean evict) { //获取传入的map的大小 int s = m.size(); if (s > 0) { //判断数组是否为null,如果为null,就根据传入map的大小，来计算出数组的大小 if (table == null) { // pre-size //计算存储Node 数组的大小 float ft = ((float)s / loadFactor) + 1.0F; int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY); if (t > threshold) //根据t来算出数组所需的最终容量，因为数组容量必须是2的幂次方，所以不能直接用t threshold = tableSizeFor(t); } else if (s > threshold) //初始化数组或者把数组扩容为原来的两倍 resize(); //遍历传入的map，把里面的数据取出，在存入当前hashMap中 for (Map.Entry e : m.entrySet()) { K key = e.getKey(); V value = e.getValue(); putVal(hash(key), key, value, false, evict); } } }复制代码
put方法解析
/** * 将键值对存储，如果之前存储过此键的值，那么用新的值替换掉原来的值 * * @param key 键 * @param value 值 * @return 返回和这个键关联的之前的一个值或者null */ public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } /** * * @param hash 根据key生成的哈希值 * @param key 键 * @param value 存储的值 * @param onlyIfAbsent * @param evict * @return 返回之前存储的值，或者null */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node [] tab; Node p; int n, i; //如果数组为null或者数组长度为0，初始化数组 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //如果数组中i的位置之前没有存储过数据（当前位置为null），就直接创建一个Node对象，存储在当前位置 //i = (n - 1) & hash 说明Node对象在数组中存储的位置是根据数组的大小和key的哈希值确定的 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); //否则就是数组当前位置之前存储过数据 else { Node e; K k; //如果之前存储的数据的key和哈希值和将要存储的数据的key和哈希值相同，说明是同一个key //那么就把之前的value替换成新的value就可以了 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //如果不是相同的key,并且当前已存储的节点是一个树节点，那么这个位置的数据是用红黑树存储的 //将新的数据存储到红黑树当中去就可以了 else if (p instanceof TreeNode) e = ((TreeNode )p).putTreeVal(this, tab, hash, key, value); //否则就存储到当前位置的链表数据结构中 else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { //把新的节点存储为当前节点的后驱节点 p.next = newNode(hash, key, value, null); //如果存储新的节点后，链表存储的数据个数大于等于8，那么将链表转换成红黑树 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指向它的后驱，接着循环 p = e; } } //当前haspMap中已经存在和包含此key的Node对象，就把旧的值替换成新的值就可以了 if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; //如果当前存储的元素个数大于数组容量，进行扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }复制代码
get方法解析
/** * 返回和key映射的value, */ public V get(Object key) { Node e; //根据key的key生成的哈希值获取对应的Node对象，再根据Node对象获取对应的value return (e = getNode(hash(key), key)) == null ? null : e.value; } /** * 根据key和hash获取对应的Node对象 * * @param hash hash for key * @param key the key * @return the node, or null if none */ final Node getNode(int hash, Object key) { Node [] tab; Node first, e; int n; K k; //根据哈希值获取数组中对应位置存储的Node数据 if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { //如果这个数据和要找的key相等，就返回 if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; //否则就是哈希值相同，key不相同，在红黑树中或者链表中查找 if ((e = first.next) != null) { if (first instanceof TreeNode) //在红黑树中查找 return ((TreeNode )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; }复制代码