图片来源网络，如有侵权，请联系删除
Map
Map是一种键值对数据对象，不能包含重复的键，每个键只能映射一个值。
Map接口提供了三种接口视图：键集合、值集合和键-值集合。
Map实例的顺序定义为map集合视图返回元素的迭代器的顺序。在一些map的实现中，比如TreeMap就可以保证他们的顺序，而HashMap则是无序的。
了解map对象，主要从他的四个方面进行：
- 增加：put/putAll/putIfAbsent/merge
- 删除：remove/clear
- 查询：get/isEmpty/size/values/keyset
- 修改：replace
下面将会对他的三个实现类进行介绍
HashMap
-
HashMap的定义
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {} -
hashmap数据存储原理
- transient Node<K,V>[] table 数据存储列表，对table的每个元素i而言，table[i]作为链表的根节点，在链表的数量少于TREEIFY_THRESHOLD时，还是保持单链表形式，否则将会转变为一个红黑树。
- transient Set<Map.Entry<K,V» entrySet 缓存cached entrySet()，用于keySet() and values()
- int threshold 扩容阀值，初始阀值是DEFAULT_INITIAL_CAPACITY=16
- static final float DEFAULT_LOAD_FACTOR = 0.75f 默认加载因子，当size>容量×DEFAULT_LOAD_FACTOR时进行扩容，扩容后，新容量为旧容量的2倍。
-
增加元素put函数的实现原理
//添加元素，HashMap允许添加null值作为key和value 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; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) //如果当前tab[i]是一个红黑树，则按照红黑树的规则增加元素 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); 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; } } 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; } -
扩容resize() 在当size>容量×DEFAULT_LOAD_FACTOR时进行扩容，扩容后，新容量为旧容量的2倍。好处在于，一个bin中的链表/红黑树元素可以按照hash后的值分为高位与低位两组，分别设置到table[i]和table[i+oldCap]就行了。
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;
//重点在这里，这就是为什么容量需要设置为2倍的原因了。 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; } -
红黑树平衡
//查找插入的位置 final TreeNode<K,V> putTreeVal(HashMap<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; } } }//插入时的平衡策略 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) { //父节点与uncle节点都是红色的，则把它们都设为黑色，祖父节点设为红色， 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; } } } } } -
总结
- 非线程安全
- 无序
- 允许为null的key和value
- 在table[i]的size大于8时，而整个hashmap的容量小于64时，扩容；否则树化
- 底层为哈希桶结构，每个桶可能为链表，也可能为红黑树
TreeMap
- 底层数据结构分析
- private transient Entry<K,V> root 红黑树的根节点
-
增加元素put函数的实现原理
public V put(K key, V value) { Entry<K,V> t = root; if (t == null) { compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null); size = 1; modCount++; return null; } int cmp; Entry<K,V> parent; // split comparator and comparable paths Comparator<? super K> cpr = comparator; if (cpr != null) { do { //查找插入的位置 parent = t; cmp = cpr.compare(key, t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return t.setValue(value); } while (t != null); } else { if (key == null) //key值不能为null throw new NullPointerException(); @SuppressWarnings("unchecked") Comparable<? super K> k = (Comparable<? super K>) key; do { parent = t; //查找插入的位置 cmp = k.compareTo(t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return t.setValue(value); } while (t != null); } Entry<K,V> e = new Entry<>(key, value, parent); if (cmp < 0) parent.left = e; else parent.right = e; //红黑树调整 fixAfterInsertion(e); size++; modCount++; return null; } -
remove同理 先查找需要删除的节点，然后做红黑树的平衡调整
- 总结
- key不能为null
- 非线程安全
- 底层为红黑树结构
- 迭代器按插入顺序返回
Hashtable
- 底层数据结构分析
- transient Entry<?,?>[] table 以哈希桶的方式存储数据，发生碰撞时，把新添加元素插入到桶的根节点
-
put函数分析
public synchronized V put(K key, V value) { // Make sure the value is not null if (value == null) { throw new NullPointerException(); }
// Makes sure the key is not already in the hashtable. Entry<?,?> tab[] = table; int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; @SuppressWarnings("unchecked") //哈希桶的根节点 Entry<K,V> entry = (Entry<K,V>)tab[index]; for(; entry != null ; entry = entry.next) { if ((entry.hash == hash) && entry.key.equals(key)) { V old = entry.value; entry.value = value; return old; } } addEntry(hash, key, value, index); return null; }private void addEntry(int hash, K key, V value, int index) { modCount++;
Entry<?,?> tab[] = table; if (count >= threshold) { // Rehash the table if the threshold is exceeded rehash(); tab = table; hash = key.hashCode(); index = (hash & 0x7FFFFFFF) % tab.length; } // Creates the new entry. @SuppressWarnings("unchecked") Entry<K,V> e = (Entry<K,V>) tab[index]; //新插入节点作为根节点 tab[index] = new Entry<>(hash, key, value, e); count++; }
LinkedHashMap
LinkedHashMap与HashMap不同的地方在于，LinkedHashMap的所有节点都是双向链表，记录了节点的插入顺序。他的应用场景就是LRU（least-recently-use）缓存。
-
插入节点
//插入节点 void afterNodeInsertion(boolean evict) { // possibly remove eldest LinkedHashMap.Entry<K,V> first; if (evict && (first = head) != null && removeEldestEntry(first)) { K key = first.key; removeNode(hash(key), key, null, false, true); } }
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { return false; }
#当removeEldestEntry按照一定策略返回true时，及可以删除最近没有使用的节点
-
获取value
public V get(Object key) { Node<K,V> e; if ((e = getNode(hash(key), key)) == null) return null; if (accessOrder) //重新设置为最近使用 afterNodeAccess(e); return e.value; }
void afterNodeAccess(Node<K,V> e) { // move node to last LinkedHashMap.Entry<K,V> last; if (accessOrder && (last = tail) != e) { LinkedHashMap.Entry<K,V> p = (LinkedHashMap.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; } }
-
总结
- 双向链表
- 最近使用的放到链表的最后
- 增加节点，可以按照一定的策略删除最少使用节点
- 其他的同
Hashmap
WeakHashMap
记录的是对象的引用，当对象被gc后，对应的节点会从WeakHashMap中移除。
IdentityHashMap
- 底层数据结构
- transient Object[] table 数组的方式存储键(偶数位)与值(奇数位)，发生冲突时，采用公开地址法进行处理
-
增加元素put
public V put(K key, V value) { final Object k = maskNull(key);
retryAfterResize: for (;;) { final Object[] tab = table; final int len = tab.length; int i = hash(k, len); // for (Object item; (item = tab[i]) != null; i = nextKeyIndex(i, len)) { if (item == k) { @SuppressWarnings("unchecked") V oldValue = (V) tab[i + 1]; tab[i + 1] = value; return oldValue; } } final int s = size + 1; // Use optimized form of 3 * s. // Next capacity is len, 2 * current capacity. // 扩容按原容量的2倍进行，确保table中留有空位 if (s + (s << 1) > len && resize(len)) continue retryAfterResize; modCount++; tab[i] = k; tab[i + 1] = value; size = s; return null; } } private static int hash(Object x, int length) { int h = System.identityHashCode(x); // Multiply by -127, and left-shift to use least bit as part of hash return ((h << 1) - (h << 8)) & (length - 1); } //偏移两位，实际值只是偏移了一位，因为奇数位保存的是值 private static int nextKeyIndex(int i, int len) { return (i + 2 < len ? i + 2 : 0); } -
获取元素
public V get(Object key) { Object k = maskNull(key); Object[] tab = table; int len = tab.length; int i = hash(k, len); while (true) { Object item = tab[i]; if (item == k) return (V) tab[i + 1]; if (item == null) return null; i = nextKeyIndex(i, len); } }
-
扩容
private boolean resize(int newCapacity) { // assert (newCapacity & -newCapacity) == newCapacity; // power of 2 //新容量为原容量的2倍 int newLength = newCapacity * 2;
Object[] oldTable = table; int oldLength = oldTable.length; if (oldLength == 2 * MAXIMUM_CAPACITY) { // can't expand any further if (size == MAXIMUM_CAPACITY - 1) throw new IllegalStateException("Capacity exhausted."); return false; } if (oldLength >= newLength) return false; Object[] newTable = new Object[newLength]; for (int j = 0; j < oldLength; j += 2) { Object key = oldTable[j]; if (key != null) { Object value = oldTable[j+1]; oldTable[j] = null; oldTable[j+1] = null; int i = hash(key, newLength); while (newTable[i] != null) i = nextKeyIndex(i, newLength); newTable[i] = key; newTable[i + 1] = value; } } table = newTable; return true; }
总结
| – | 存储结构 | 线程安全 | 扩容策略 | 冲突算法 | 其他特性 |
|---|---|---|---|---|---|
| HashMap | 哈希桶+单链表/红黑树 | 否 | 原容量两倍 | 哈希链 | - |
| Hashtable | 哈希桶+单链表 | 是 | 原容量两倍 | 哈希链 | - |
| TreeMap | 红黑树 | 否 | 无须扩容 | - | 顺序 |
| WeakHashMap | 哈希桶+单链表 | 是 | 原容量两倍 | 哈希链 | 引用回收 |
| IdentityHashMap | 数组 | 否 | 原容量两倍 | 开放地址法 | - |
| LinkedHashMap | 哈希桶+单链表/红黑树 | 否 | 原容量两倍 | 哈希链 | 双向链表，顺序，LRU |