Java源码分析之HashMap

成员变量

//默认的初始容量，空间必须为2的幂 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 //最大容量 static final int MAXIMUM_CAPACITY = 1 << 30; //默认的加载因子,这里解释一下加载因子，在map被创建后，就有了一个容量，在put键值对时，会首先算key的hashcode，然后根据hash值来装进“桶”，加载因子的取值范围是(0,1]，加载因子乘初始容量，就是能装的最大值，举个例子，加入初始容量是16，初始加载因子是0.75，0.75*16=12，现在如果16个桶中已经装了12个，当再来一个，并且该对应的值还没有被装进通，那么容量就会扩大，变成原来的2倍，加载因子有什么用呢，就是平衡时间和空间，假如值太小了，那么在没有装几个的时候，就会扩容，对空间要求比较高，当值太大的时候，冲突会增加的比较多，所以装的也就更多，对时间要求比较高，所以折中是比较好的选择 static final float DEFAULT_LOAD_FACTOR = 0.75f; int threshold; final float loadFactor;

构造方法

public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); } //返回2的幂 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; } public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }

Node< K, V>

//通过这个类，来保存键值对 static class Node<K,V> implements Map.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; } //键值对的hash值是将key，value的hash值异或起来 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) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } }

基本的方法

put方法

public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } //onlyIfAbsent如果为真时，如果原map中已经存在了key值的对，那么不改变原来的对 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) n = (tab = resize()).length; //如果该桶内为空，直接装入 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; //如果存在了和要装入key值相同的对 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //如果是TreeNode，插入 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { //遍历链表，准备插入 for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); //如果长度大于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 = e; } } //当已经存在key时 if (e != null) { // existing mapping for key V oldValue = e.value; //如果oldValue为空，或者onlyIfAbsent 为false，则覆盖 if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; //是否需要扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; } 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(); //全部put进去，这也给我们了一个遍历map的模板 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { K key = e.getKey(); V value = e.getValue(); putVal(hash(key), key, value, false, evict); } } } public void putAll(Map<? extends K, ? extends V> m){ putMapEntries(m, true); }

get方法

public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; 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; } //是否包含key public boolean containsKey(Object key) { return getNode(hash(key), key) != null; } //查找是否存在value，从全部中找 O(n) 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; }

remove方法

public V remove(Object key) { Node<K,V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; } //移除key和value都相等的数，注意，倒数第二个参数是true public boolean remove(Object key, Object value) { return removeNode(hash(key), key, value, true, true) != null; } //matchValue表示删除时候，是否需要value也相等，movable表示是否可以移动 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); } } //找到了，并且看是否需要value也相等，并判断value是否相等 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; }

size() 与 isEmpty()

public int size() { return size; } public boolean isEmpty() { return size == 0; }

clear()

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; } }

keySet()

//keySet是继承自AbstractSet public Set<K> keySet() { Set<K> ks = keySet; if (ks == null) { ks = new KeySet(); keySet = ks; } return ks; } //居然叫values，不叫valuesSet，神奇 public Collection<V> values() { Collection<V> vs = values; if (vs == null) { vs = new Values(); values = vs; } return vs; } //entrySet，可以用来遍历 public Set<Map.Entry<K,V>> entrySet() { Set<Map.Entry<K,V>> es; return (es = entrySet) == null ? (entrySet = new EntrySet()) : es; }

replace方法

//先取到Node，再改变，返回旧的值 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; } //有旧值的替换 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; }

modCount

是为了检测多线程中，是否被其他线程修改，虽然如此，但依旧不是线程安全的

除了这些，还有迭代器这些，先不说了，另外，里面有红黑树的实现，可以改日好好研究一下