数据结构
JDK1.8的HashMap采纳数组+单链表+红黑树的数据结构，数组和链表存储的是一个个Node对象，红黑树存储的是TreeNode对象
Node
static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; }TreeNode
static final class TreeNode<K,V> extends LinkedHashMap.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); } final TreeNode<K,V> root() { for (TreeNode<K,V> r = this, p;;) { if ((p = r.parent) == null) return r; r = p; } } }罕用办法
罕用API
V get(Object key); //取得指定key的值V put(K key, V value); //增加key-value对void putAll(Map<? extends K, ? extends V> m); //将指定Map中的key-value对复制到此Map中V remove(Object key); //删除该key-valueboolean containsKey(Object key); //判断是否存在该key的key-value对；是则返回trueboolean containsValue(Object value); //判断是否存在该value的key-value对；是则返回true Set<K> keySet(); //独自抽取key序列，将所有key生成一个SetCollection<V> values(); //独自value序列，将所有value生成一个Collectionvoid clear(); // 革除HashMap中的所有key-value对int size(); // 返回HashMap中所有key-value对的数量boolean isEmpty(); // 判断HashMap是否为空,size == 0时示意为空 应用
public class HashMapTest { public static void main(String[] args) { /** * 1. 申明1个 HashMap的对象 */ Map<String, Integer> map = new HashMap<String, Integer>(); /** * 2. 向HashMap增加数据（放入键-值对） */ map.put("Java", 1); map.put("HashMap", 2); map.put("List",3); map.put("set",4); /** * 3. 获取 HashMap 的某个数据 */ System.out.println("" + map.get("HashMap")); /** * 4. 遍历HashMap共有3种办法：别离针对Entry或key或value * 步骤1：取得Entry或key或value的汇合 * 步骤2：遍历，应用for循环或迭代器Iterator */ // 办法1：取得Entry的Set汇合再遍历 // 取得Entry的Set汇合 Set<Map.Entry<String, Integer>> entrySet = map.entrySet(); // 通过for循环遍历 for(Map.Entry<String, Integer> entry : entrySet){ System.out.print(entry.getKey()); System.out.println(entry.getValue()); } // 通过迭代器遍历 // 先取得Entry的Iterator，再循环遍历 Iterator iter1 = entrySet.iterator(); while (iter1.hasNext()) { // 遍历时，需先获取entry，再别离获取key、value Map.Entry entry = (Map.Entry) iter1.next(); System.out.print((String) entry.getKey()); System.out.println((Integer) entry.getValue()); } // 办法2：取得key的Set汇合再遍历 Set<String> keySet = map.keySet(); // 通过for循环 for(String key : keySet){ System.out.print(key); System.out.println(map.get(key)); } // 通过迭代器遍历 // 先取得key的Iterator，再循环遍历 Iterator iter2 = keySet.iterator(); String key = null; while (iter2.hasNext()) { // 遍历时，需先获取key，再获取value key = (String)iter2.next(); System.out.print(key); System.out.println(map.get(key)); } // 办法3：取得value的汇合再遍历 Collection valueSet = map.values(); // 取得values的Iterator，再循环遍历 Iterator iter3 = valueSet.iterator(); while (iter3.hasNext()) { System.out.println(iter3.next()); } }}对于遍历形式，举荐应用针对 key-value对（Entry）的形式：效率高
- 对于遍历keySet,valueSet，本质上遍历了2次：
第1次，for/iterator迭代器遍历;
第2次 从HashMap中取出key的value操作 - 对于遍历entrySet，本质遍历了1次for/iterator迭代器遍历，Entry曾经存储了key和 value
源码剖析
次要属性
//默认容量static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;//最大容量static final int MAXIMUM_CAPACITY = 1 << 30;//加载因子static final float DEFAULT_LOAD_FACTOR = 0.75f;//扩容阈值 = 容量 x 加载因子，当哈希表的大小 ≥ 扩容阈值时，就会扩容哈希表int threshold//存储数据的Node类型数组，长度=2的幂transient Node<K,V>[] table;//HashMap中存储的键值对的数量transient int size// 链表的树化阈值，即链表转成红黑树的阈值，当Node链表长度>该值时，则将链表转换成红黑树static final int TREEIFY_THRESHOLD = 8; // 链表的还原阈值，即红黑树转为链表的阈值，当在扩容时，HashMap的数据存储地位会从新计算，在从新计算存储地位后，当红黑树内TreeNode数量 < 6时，则将 红黑树转换成链表static final int UNTREEIFY_THRESHOLD = 6;// 最小链表树化容量阈值，即 当Node数组长度 > 该值时，才容许树形化链表，否则则间接扩容，而不是树形化static final int MIN_TREEIFY_CAPACITY = 64;构造方法
//加载因子，容量可指定 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); } //加载因子等于默认值，容量可指定 public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } //默认构造函数，加载因子，容量等于默认值 public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } //可传入一个map的构造函数 public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }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) { Node<K,V>[] tab; Node<K,V> p; int n, i; //1. 若Node数组为空，则通过resize()初始化数组 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //2.计算key寄存Node数组中的数组下标，判断这个数组下标Node数组上是否有Node存在 //2.1若不存在，则在该地位新建一个Node节点 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null) //2.2若存在 else { Node<K,V> e; K k; //2.1.1判断key是否与数组上的Node外面的key是否雷同，是则用新的value值替换旧的value值 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //2.1.2若不雷同，判断以后Node是红黑树，则在树中插入或更新键值对 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); //2.1.3若不雷同，判断以后Node是链表，则在链表中插入或更新键值对 else { //遍历以该Node为头结点的链表,判断该key是否已存在 for (int binCount = 0; ; ++binCount) { //若该key不存在，则将key-value增加到Node数组中,这里采纳尾插法 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已存在，则用新value替换旧value if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; // 插入胜利后，判断理论存在的键值对数量size > 最大容量threshold if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }putTreeVal()
//向红黑树插入或更新数据（键值对），遍历红黑树判断该节点的key是否与传入key雷同，雷同则新value笼罩旧value，不雷同则插入 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; } } }resize()办法
final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; //扩容前Node数组 int oldCap = (oldTab == null) ? 0 : oldTab.length; //扩容前Node数组长度 int oldThr = threshold; //扩容前Node数组阈值 int newCap, newThr = 0; //Node数组长度大于0,非初始化数组 if (oldCap > 0) { //扩容前Node数组容量超过最大值，不扩容 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } //没有超过最大值，数组长度扩容为原来的2倍 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } //Node数组长度=0,初始化数组 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) { // 遍历旧数组，从新计算每个Node在新数组的数组下标，应用尾插法将旧数组中的Node转移到新数组 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; 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; }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; //计算key寄存Node数组中的数组下标，判断这个数组下标Node数组上是否有Node存在 if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { //1.在Node数组中找key相等的Node if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; //2.在红黑树中找key相等的Node if ((e = first.next) != null) { if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); //3.在链表中找key相等的Node do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }源码总结
1.JDK1.8的HashMap采纳数组+单链表+红黑树的数据结构，数组和链表存储的是一个个Node对象，红黑树存储的是TreeNode对象
2.增加key-value时会依据key值计算出对应的hash值，再依据hash值计算出对应的数组下标，判断这个数组在这个下标中是否有Node存在：
若没有，则在该地位新建一个Node节点
若有则判断这个Node是属于链表还是属于红黑树，而后别离遍历链表或红黑树，判断是否有雷同的key，如果有则用新value替换旧value，如果没有就将Node增加到链表或红黑树，留神这里的链表插入采纳尾插法
3.在将Node插入到链表时：
会进行是否红黑树树化的判断，链表长度 >= 桶的树化阈值=8，则将链表转换成红黑树
会进行是否须要扩容的判断，当Node的数量，或者说key-value的数量大于扩容阈值 = 以后容量 x 加载因子，新建一个数组，容量时是数组的2倍，将旧entry数组上的entry数据转移到newtable中，让以后的数组指向新数组从而实现扩容。
4.hashmap1.8与hashmap1.7的区别：
1.数据结构不同
2.与1.7中hashmap的扩容机制不同：
a.hashmap1.8中的扩容后Node的地位是数组的原地位/原地位+旧容b.量，hashmap1.7则是原来地位
b.扩容时，hashmap1.8采纳尾插法将数据转移到新数组中，hashmap1.7采纳头插法