前言

1.HashMap

线程不安全

2.Hashtable

线程安全，使用synchronized实现

3.ConcurrentHashMap

线程安全，使用CAS+synchronized实现

4.Collections.synchronizedMap()

线程安全，使用synchronized实现

HashMap

get

public V get(Object key) { HashMap.Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } final HashMap.Node<K,V> getNode(int hash, Object key) { HashMap.Node<K,V>[] tab; HashMap.Node<K,V> first, e; int n; K k; /** * (n - 1) & hash可以计算出key在table的哪个位置 * table数组不为空 且 table长度大于0 且 table数组该位置（first）不为空 */ if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { /** * 若first的头结点为寻找的key */ if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; /** * 若first后面还有结点 */ if ((e = first.next) != null) { /** * 若first为TreeNode，即这是一颗红黑数 */ if (first instanceof HashMap.TreeNode) return ((HashMap.TreeNode<K,V>)first).getTreeNode(hash, key); /** * 若first为Node，即这是一个链表 */ do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }

put

public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i; /** * 若table数组为空 或 table长度为0，则进行初始化 */ if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; /** * 若table数组中i位置为空，直接新建结点赋值给该数组i位置 */ if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); /** * 若table数组中该位置不为空 */ else { HashMap.Node<K,V> e; K k; /** * 若要插入的键值对的key为table数组i位置的头结点 */ if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; /** * 若要插入的key不是table数组i位置的头结点并且这是一颗红黑数，调用putTreeVal插入键值对 */ else if (p instanceof HashMap.TreeNode) e = ((HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); /** * 若要插入的key不是table数组i位置的头结点并且这是一个链表 */ else { for (int binCount = 0; ; ++binCount) { /** * 最后一个结点 */ if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); /** * 若链表的元素个数大于等于TREEIFY_THRESHOLD，链表转为红黑树 */ if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } /** * 要插入的key已存在，为某一个链表某元素的key */ 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; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } /** * 若table数组中i位置为空 */ ++modCount; /** * 若size大于threshold，则进行扩容 */ if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }

resize

final Node<K,V>[] resize() { /** * 原来的table数组 */ Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; /** * 原来的table数组不为空 */ if (oldCap > 0) { /** * 若oldCap的扩容已达上限 */ if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } /** * 若table数组的扩容正常，扩为原来长度的两倍 */ else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } /** * 原来的table数组为空，new HashMap的时候指定了initialCapacity */ else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; /** * 原来的table数组为空，new HashMap的时候什么也没指定 */ else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } /** * 指定threshold */ 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; /** * 若原来的table数组不为空 */ 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; /** * 若数组该位置为一个红黑树，调用split函数进行扩容 */ else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); /** * 若数组该位置为一个链表 */ else { // preserve order /** * 确定数组位置使用e.hash & oldCap的方法， * 由于数组长度扩充了一倍，则要使用e.hash & newCap的方法， * 由于newCap比oldCap多一位且该位置为1， * oldCap该位置为0，所以e.hash & newCap仅有两种情况，一种为0，一种不为0 * 对应于loHead链表和hiHead链表 */ 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; }

remove

public V remove(Object key) { Node<K,V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; } 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; /** * table数组不为空 且 table数组长度大于0 且 table数组该位置不为空 */ 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); } } /** * node为根据key查找到的，若该结点不为空，则进行移除操作 */ 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; }

扩容（resize）时机

第一次插入键值对size>threshold某一链表长度大于等于8 且 table数组长度小于64

链表转为红黑数时机

某一链表长度大于等于8 且 table数组长度大于等于64

红黑树转为链表时机

扩容之后元素重新分配，红黑树结点个数小于等于6个则转为链表