JAVA集合之Map ＞＞HashMap/Hashtable/TreeMap/LinkedHashMap结构

Map 是一种键-值对（key-value）集合，键不可以重复，值可以重复。常见的实现类有：HashMap、Hashtable、TreeMap、LinkedHashMap等。

HashMap&Hashtable

HashMap：数据结构为哈希表，允许使用 null 值和 null 键，线程不同步。Hashtable与HashMap差不多，但是线程同步的，且不可以存入null键null值。

JDK1.7的Hashmap 结构是，数组+链表的形式进行存储的。存入时通过KEY的hashCode % capacity（数组的容量），找到数组位置，每个数组位置保存的都是一个链表结构，用于存储一个或多个对象。

JDK1.8后Hashmap结构进行优化，数组+链表+红黑树。当链表长度达到一定阈值时，链表结构会变为红黑树（当链表阈值长度=8时，会进入红黑树判断：当数组长度<64时，会优先扩容，当数组长度>= 64时才转红黑树），红黑树的优点在于，平衡链表结构的算法，提升查询性能。具体参考：红黑树算法。

JDK1.8为了避免多线程数据冲突及死锁的做了优化（去除了rehash），使用了高低位运算，来迁移数据，低位，直接迁移到原来的位置，高位，迁移到扩容后的位置（i + 原来Hashmap 数组的大小）。

JDK1.8对HashMap Get或Put寻址取模算法（hashCode % capacity）进行了优化，将其改为了hash & (length-1) 这种二进制的位运算进行判断，计算结果等同于取模算法，但是效率高于它。这种运算需要保证length-1的二进制码都为1，才能将元素均匀的分布到数组下标中，所以在hashmap底层代码内，规定了数组的容量必须是2的指数次幂（因为只有2的指数次幂 -1的二进制编码才全部为1），才能保证保存对象不会发生数组越界。具体参考：HashMap 底层源码。

hash碰撞

上面介绍了如何找到对应的下标进行保存对象，但是在操作多个对象时，是有可能在计算后得到相同的数组下标，也就是我们的hash碰撞，这个时候hashmap就会把相同下标的对象以链表的方式进行存储，当链表的长度达到一定的阈值（默认8）时，就会改用红黑树就行保存，红黑树的优点在于，平衡链表结构的算法，提升查询性能。链表查询的时间复杂度为O(n),红黑树的时间复杂的为O(logn)。

加载因子为0.75的作用

Hash存储对象，并不能保证利用率是100%（每个数组下标都能存放数据），所以为了每个对象能均匀散列在数组中，设置了加载因子为0.75（如，HashMap 的初始化容量是16，载因子为0.5，那么当HashMap中有16*0.5=8个元素时，HashMap 就会进行扩容）。0.75是选择了时间，与空间之间选择平衡。如果大于0.75，利用率高了，但是HashMap发生hash碰撞的几率就会变高，hash碰撞就会导致我们的链表或红黑树节点深度更深，所以性能会相对下降。如果小于0.75 ，那么我们的空间的利用率也就会变的更低。所以 hashMap 建议为默认的 0.75 在时间与空间之间的平衡选择。

参考源码：

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {/*** The default initial capacity - MUST be a power of two.* 翻译：默认初始容量-必须是2的幂*/static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16/*** 最大容量 1<<30.*/static final int MAXIMUM_CAPACITY = 1 << 30;/*** The load factor used when none specified in constructor.* 加载因子默认0.75*/static final float DEFAULT_LOAD_FACTOR = 0.75f;/*** 链表转成红黑树的阈值：当链表长度 > 该值时*/static final int TREEIFY_THRESHOLD = 8;/*** 红黑树转为链表的阈值（当原有的红黑树内数量 < 6时，则将红黑树转换成链表）*/static final int UNTREEIFY_THRESHOLD = 6;/*** 最小树形化容量阈值：当哈希表中数组的容量>该值时+链表长度>TREEIFY_THRESHOLD则链表转红黑树*/static final int MIN_TREEIFY_CAPACITY = 64;/*** 记录HashMap的结构修改次数*/transient int modCount;/*** The number of key-value mappings contained in this map.*/transient int size;/*** The next size value at which to resize (capacity * load factor).* 翻译: 记录当map存储了多少个数组元素时开始扩容 (capacity * load factor)*/int threshold;/*** Constructs an empty <tt>HashMap</tt> with the default initial capacity* (16) and the default load factor (0.75).*/public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;// 第一次操作，先初始化容量 16 if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// 通过hash获取数组元素，如果为空则将元素插入到当前位置if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {Node<K,V> e; K k;// 如果key相同，则e=p ,下面代码中会通过 e 将新元素覆盖掉就旧元素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);// 如果链表大小>=TREEIFY_THRESHOLD 则进入扩容或转红黑树逻辑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 keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);    //使用LinkHashMap时会进行回调的方法return oldValue;}}++modCount;//当map存储的数组个数大于 threshold（capacity * load factor） 开始扩容if (++size > threshold)resize(); //扩容代码不贴，可以自行源码中参考   afterNodeInsertion(evict); //使用LinkHashMap时会进行回调的方法return null;}/*** 扩容或转红黑树方法逻辑*/final void treeifyBin(Node<K,V>[] tab, int hash) {int n, index; Node<K,V> e;// 数组长度如果小于 MIN_TREEIFY_CAPACITY 则进行扩容if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)resize();// 转为红黑树else if ((e = tab[index = (n - 1) & hash]) != null) {TreeNode<K,V> hd = null, tl = null;do {TreeNode<K,V> p = replacementTreeNode(e, null);if (tl == null)hd = p;else {p.prev = tl;tl.next = p;}tl = p;} while ((e = e.next) != null);if ((tab[index] = hd) != null)hd.treeify(tab);}}// Create a regular (non-tree) nodeNode<K,V> newNode(int hash, K key, V value, Node<K,V> next) {return new Node<>(hash, key, value, next);}// For conversion from TreeNodes to plain nodesNode<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {return new Node<>(p.hash, p.key, p.value, next);}/*** 一般用户在链表时使用的结构*/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; }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;}}/*** 转红黑树时使用的结构*/static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {TreeNode<K,V> parent;  // red-black tree linksTreeNode<K,V> left;TreeNode<K,V> right;TreeNode<K,V> prev;    // needed to unlink next upon deletionboolean red;TreeNode(int hash, K key, V val, Node<K,V> next) {super(hash, key, val, next);}......下面代码太多，可以自行源码中查看}}

上面源码中，根据put流程说明，通过源码跟进，我们就可以看出HashMap的结构、hash碰撞时如何保存、扩容逻辑、什么时候开始转红黑树、及一些重要参数的作用等。

TreeMap

TreeMap：基于红黑色树的顺序访问的Map，与HashMap区别在于HashMap中的元素是没有顺序的，而TreeMap中所有的元素都是有某一固定顺序的。TreeMap继承SortedMap类，他保持键的有序顺序，用于给map集合中的键进行排序（排序方法和TreeSet一样，实现comparable 或comparator 接口）

参考源码：

public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{/*** 排序接口*/private final Comparator<? super K> comparator;private transient Entry<K,V> root;public V put(K key, V value) {Entry<K,V> t = root;//如果root第一个节点为空，则将元素保存到rootif (t == null) {//为插入节点进行排序compare(key, key); // type (and possibly null) checkroot = new Entry<>(key, value, null);size = 1;modCount++;return null;}int cmp;Entry<K,V> parent;// split comparator and comparable pathsComparator<? super K> cpr = comparator;// comparator 非空则使用 comparator 判断排序if (cpr != null) {// 基于根节点遍历，通过左小，右大的方式存入到树节点中(注意：最后字节点会插入null，下面代码会用补充)do {parent = t;cmp = cpr.compare(key, t.key);if (cmp < 0)t = t.left;else if (cmp > 0)t = t.right;elsereturn t.setValue(value);} while (t != null);}// comparator 为空，则使用Comparable 判断排序，其他逻辑与上面差不多else {if (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;elsereturn t.setValue(value);} while (t != null);}Entry<K,V> e = new Entry<>(key, value, parent);// 对最后字节点进行补充if (cmp < 0)parent.left = e;elseparent.right = e;//进行红黑树的旋转等操作fixAfterInsertion(e);size++;modCount++;return null;}// 通过两个Key比较来排序，comparator 不存在则使用 Comparablefinal int compare(Object k1, Object k2) {return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2): comparator.compare((K)k1, (K)k2);}static final class Entry<K,V> implements Map.Entry<K,V> {K key;V value;//左子节点Entry<K,V> left;//又子节点Entry<K,V> right;//父节点Entry<K,V> parent;//颜色标记-红色/黑色boolean color = BLACK;/*** Make a new cell with given key, value, and parent, and with* {@code null} child links, and BLACK color.*/Entry(K key, V value, Entry<K,V> parent) {this.key = key;this.value = value;this.parent = parent;}public V setValue(V value) {V oldValue = this.value;this.value = value;return oldValue;}......省略}}

源码中可以看到，TreeMap内部使用的是Entry结构，Entry结构中，又声明了 letf ,right等变量用于保存左、右子节点,color标记颜色（红/黑），源码开始形成的是二叉树，执行了fixAfterInsertion(e);后才生成的红黑树对整个树进行平衡。详见如下fixAfterInsertion源码

public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{//红/黑色标记private static final boolean RED   = false;private static final boolean BLACK = true;//获取颜色private static <K,V> boolean colorOf(Entry<K,V> p) {return (p == null ? BLACK : p.color);}//获取父节点private static <K,V> Entry<K,V> parentOf(Entry<K,V> p) {return (p == null ? null: p.parent);}//设置颜色private static <K,V> void setColor(Entry<K,V> p, boolean c) {if (p != null)p.color = c;}//获取左节点private static <K,V> Entry<K,V> leftOf(Entry<K,V> p) {return (p == null) ? null: p.left;}//获取又节点private static <K,V> Entry<K,V> rightOf(Entry<K,V> p) {return (p == null) ? null: p.right;}/** 向左旋转 */private void rotateLeft(Entry<K,V> p) {if (p != null) {Entry<K,V> r = p.right;p.right = r.left;if (r.left != null)r.left.parent = p;r.parent = p.parent;if (p.parent == null)root = r;else if (p.parent.left == p)p.parent.left = r;elsep.parent.right = r;r.left = p;p.parent = r;}}/**向右旋转 */private void rotateRight(Entry<K,V> p) {if (p != null) {Entry<K,V> l = p.left;p.left = l.right;if (l.right != null) l.right.parent = p;l.parent = p.parent;if (p.parent == null)root = l;else if (p.parent.right == p)p.parent.right = l;else p.parent.left = l;l.right = p;p.parent = l;}}//红黑树平衡设置private void fixAfterInsertion(Entry<K,V> x) {//新节设置为红色x.color = RED;//循环条件=非空&非根节点&x的父节点颜色为红色while (x != null && x != root && x.parent.color == RED) {//判断父节点是否是在左边的节点if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {//获取祖父节点的右子节点Entry<K,V> y = rightOf(parentOf(parentOf(x)));//右叔叔节点为红色，则更新相关颜色if (colorOf(y) == RED) {                    setColor(parentOf(x), BLACK);        //父节点设置为黑色setColor(y, BLACK);                  //叔叔节点置为黑色setColor(parentOf(parentOf(x)), RED);//祖父节点置为红色x = parentOf(parentOf(x));           //将继续循环赋予X，继续循环} else {//如果x在右节点-则进行左旋父节点if (x == rightOf(parentOf(x))) {x = parentOf(x);rotateLeft(x);   //左旋父节点}setColor(parentOf(x), BLACK);        //父节点设置为黑色setColor(parentOf(parentOf(x)), RED);//祖父节点置为红色rotateRight(parentOf(parentOf(x)));  //右旋祖父节点}} else {    //否则是右边的节点 - 其他逻辑与上面的相似Entry<K,V> y = leftOf(parentOf(parentOf(x)));if (colorOf(y) == RED) {setColor(parentOf(x), BLACK);setColor(y, BLACK);setColor(parentOf(parentOf(x)), RED);x = parentOf(parentOf(x));} else {if (x == leftOf(parentOf(x))) {x = parentOf(x);rotateRight(x);}setColor(parentOf(x), BLACK);setColor(parentOf(parentOf(x)), RED);rotateLeft(parentOf(parentOf(x)));}}}root.color = BLACK;}}

LinkedHashMap

LinkedHashMap：继承自 HashMap，在 HashMap 基础上，通过维护一个具有双重链表解决了 HashMap 不能随时保持遍历顺序和插入顺序一致的问题。另外LinkedHashMap可以实现快速的查询第一个元素（First）跟结尾（Last）

对于LinkedHashMap详解，可参考如下文章：java之LinkedHashMap详解_linkedhashmap使用_三木易不爱卷的博客-CSDN博客