前言

下图为Map接口以及其相关子类实现类的简易结构图：

接下来对上图中的实现类的原理及使用方面进行一个简单的介绍。

1、HashMap类

    Hash的底层实现为数组+链表/红黑树的结构形式，在JDK1.8之前HashMap底层实现为数组+链表的形式，JDK1.8以后添加了红黑树，至于何时进行链表和红黑树的转换，待下面分析源码的时候进行讲解；先来展示下HashMap类的继承实现关系：

public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {.........}

下面是一个典型的HashMap的结构图：

图片来源于网络

1.1、源码分析

接下来看下实现类中的静态变量及成员变量：

    /*** 设置table初始化时的容量默认值为16*/static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16/*** 设置数组最大的容量值为2的30次方*/static final int MAXIMUM_CAPACITY = 1 << 30;/*** 默认负载因子为0.75*/static final float DEFAULT_LOAD_FACTOR = 0.75f;/*** 以下三个静态常量是链表和红黑树相互转换的阈值因子；* 链表和红黑树相互转换的条件：* 	1）链表中的元素个数大于8个，同时数组table的元素个数大于64时才会转换为红黑树* 	2）如果红黑树中的节点个数小于UNTREEIFY_THRESHOLD，则由红黑树转化为链表*/static final int TREEIFY_THRESHOLD = 8;static final int UNTREEIFY_THRESHOLD = 6;static final int MIN_TREEIFY_CAPACITY = 64;/********************成员变量**************************//*** table变量是一个Node数组，负责存储键值对*/transient Node<K,V>[] table;/*** 存放具体元素的集合*/transient Set<Map.Entry<K,V>> entrySet;/*** 记录map中键值对的个数*/transient int size;/*** 计数器，记录hashMap结构变化的次数*/transient int modCount;/*** 设置扩容的阈值，大小为数组table容量*负载因子* 例如：默认容量为16*默认负载因子0.75=12，当key-value的个数大于12时进行扩容操作* * 扩容后hashmap的容量为之前的2倍*/int threshold;/*** 真实装载因子，不设置默认为0.75；可以通过构造函数来修改*/final float loadFactor;

HashMap的构造函数：

/*** 指定初始化容量和负载因子的构造函数*/
public HashMap(int initialCapacity, float loadFactor) {// 判断初始化容量initialCapacity是否小于0if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);// 判断初始化容量initialCapacity是否大于集合的最大容量MAXIMUM_CAPACITY->2的30次幂                                   if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);this.loadFactor = loadFactor;// tableSizeFor(initialCapacity) 判断指定的初始化容量是否是2的n次幂，// 如果不是那么会变为比指定初始化容量大的最小的2的n次幂。this.threshold = tableSizeFor(initialCapacity);}// tableSizeFor() 实现，可以自己测试，返回的数据刚好如上边说的一样：如果不是2的n次幂那么会变为比指定初始化容量大的最小的2的n次幂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; }/*** 根据输入Map构造一个新的HashMap对象*/public HashMap(Map<? extends K, ? extends V> m) {this.loadFactor = DEFAULT_LOAD_FACTOR;putMapEntries(m, false);}final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {// 获取参数集合的长度int s = m.size();// 判断参数集合的长度是否大于0if (s > 0) {// 判断table数组是否初始化if (table == null) { // pre-sizefloat ft = ((float)s / loadFactor) + 1.0F;int t = ((ft < (float)MAXIMUM_CAPACITY) ?(int)ft : MAXIMUM_CAPACITY);// 如果t大于阈值，则初始化阈值if (t > threshold)threshold = tableSizeFor(t);}// 已经初始化且s大于阈值，则进行扩容操作else if (s > threshold)resize();// 遍历执行插入的操作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);}}}

注意：在上述中我们讲到tableSizeFor()会将设定非2的n次幂的容量值转化为大于该值的最小2的n次幂的值；threshold 代表的是数组的阈值，等于数组容量*负载因子；但是上面介绍的 threshold = tableSizeFor(容量)，这是因为这里计算的threshold只是一个初始化的值，而在进行put的时候会对threshold重新计算。

添加数据的方法：

	//先来介绍下hashMap中对key进行hash的方法static final int hash(Object key) {int h;/*** 1)当key为null时，hash的值为0* 2)当不为null时，使用key的hashCode值h与h右移16位以后的值进行或非（^）的操作*/return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}// 注意：这个hash()计算出来的并不是元素在数组table中的位置，如果要计算在数组中的位置还要进行下一步的操作：// 使用hash()计算出来的值与数组table的容量值n减去1进行求与（&）的操作// int index=(n - 1) & hash;/***	Put方法的实现步骤大致如下：*	 1）先通过hash值计算出key映射到哪个bucket,即计算出table中的索引；*	 2）如果bucket上没有碰撞冲突，则直接插入；*	 3）如果出现碰撞冲突了，则需要处理冲突：*		a、如果该bucket使用红黑树处理冲突，则调用红黑树的方法插入数据；*		b、否则采用传统的链式方法插入。如果链的长度达到临界值，则把链转变为红黑树；*   4）如果bucket中存在重复的键，则为该键替换新值value；* 	 5）如果size大于阈值threshold，则进行扩容；*/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）transient Node<K,V>[] table; 表示存储Map集合中元素的数组。2）(tab = table) == null 表示将空的table赋值给tab,然后判断tab是否等于null，第一次肯定是			null3）(n = tab.length) == 0 表示将数组的长度0赋值给n,然后判断n是否等于0，n等于0由于if判断使用双或，满足一个即可，则执行代码 n = (tab = resize()).length; 进行数组初始化。并将初始化好的数组长度赋值给n.4）执行完n = (tab = resize()).length，数组tab每个空间都是null*/if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;/*1）i = (n - 1) & hash 表示计算数组的索引赋值给i;2）p = tab[i = (n - 1) & hash]表示获取计算出的位置的数据赋值给节点p3) (p = tab[i = (n - 1) & hash]) == null 判断节点位置是否等于null，如果为null，则执行代码：tab[i] = newNode(hash, key, value, null);根据键值对创建新的节点放入该位置的bucket中小结：如果当前bucket没有哈希碰撞冲突，则直接把键值对插入空间位置*/ if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {// 当前位置已经有值时Node<K,V> e; K k;// 判断新插入节点的key是否与当前节点原有的数据的key相同if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))// 相同的话则将p赋给ee = p;// 判断当前节点是否为树节点else if (p instanceof TreeNode)// 如果为树节点则使用红黑树的添加方式e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {// 原来的结构为链表格式的结构// 采用循环遍历的方式，判断链表中是否有重复的key，如果有则覆盖value；如果没有则添加到链表的最后for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);// 判断链表中的节点个数是否大于TREEIFY_THRESHOLD临界值8，如果大于则将链表转换为红黑树if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}// 如果e为null,说明原来的map中没有与插入的节点相重复的keyif (e != null) { // existing mapping for keyV oldValue = e.value;// onlyIfAbsent 如果true代表不更改现有的值// onlyIfAbsent=false说明原来的值要被覆盖if (!onlyIfAbsent || oldValue == null)e.value = value;// 执行回调afterNodeAccess(e);// 返回旧值return oldValue;}}// 记录修改的次数++modCount;// 修改size，如果map中键值对的个数size大于阈值则进行扩容if (++size > threshold)resize();afterNodeInsertion(evict);return null;}

将链表转化为红黑树的操作：

  /**替换指定哈希表的索引处桶中的所有链接节点Node<K,V>[] tab = tab 数组名int hash = hash表示哈希值*/final void treeifyBin(Node<K,V>[] tab, int hash) {int n, index; Node<K,V> e;/*如果当前数组为空或者数组的长度小于进行树形化的阈值(MIN_TREEIFY_CAPACITY = 64),就去扩容。而不是将节点变为红黑树。目的：如果数组很小，那么转换红黑树，然后遍历效率要低一些。这时进行扩容，那么重新计算哈希值，链表长度有可能就变短了，数据会放到数组中，这样相对来说效率高一些。*/if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)resize();else if ((e = tab[index = (n - 1) & hash]) != null) {/*1）执行到这里说明哈希表中的数组长度大于阈值64，开始进行树形化2）e = tab[index = (n - 1) & hash]表示将数组中的元素取出赋值给e,e是哈希表中指定位置桶里的链表节点，从第一个开始*///hd：红黑树的头结点   tl :红黑树的尾结点TreeNode<K,V> hd = null, tl = null;do {//新创建一个树的节点，内容和当前链表节点e一致TreeNode<K,V> p = replacementTreeNode(e, null);if (tl == null)//将新创键的p节点赋值给红黑树的头结点hd = p;else {/*p.prev = tl：将上一个节点p赋值给现在的p的前一个节点tl.next = p;将现在节点p作为树的尾结点的下一个节点*/p.prev = tl;tl.next = p;}tl = p;/*e = e.next 将当前节点的下一个节点赋值给e,如果下一个节点不等于null则回到上面继续取出链表中节点转换为红黑树*/} while ((e = e.next) != null);/*让桶中的第一个元素即数组中的元素指向新建的红黑树的节点，以后这个桶里的元素就是红黑树而不是链表数据结构了*/if ((tab[index] = hd) != null)hd.treeify(tab);}}

扩容原理以及对应的源码

    final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;// 获取当前数组的长度int oldCap = (oldTab == null) ? 0 : oldTab.length;//当前阀值点 默认是12(16*0.75)int oldThr = threshold;int newCap, newThr = 0;if (oldCap > 0) {if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}/*** 1）通过位移运算，将容量扩大为原来的2倍，且扩大2倍以后仍然要小于最大容量* 2）原来的容量大小要大于等于默认的初始化容量16*/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 thresholdnewCap = 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;// 创建新的hash表@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 orderNode<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;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.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;}

1.2、hashMap特点及使用建议

特点：

• 存取无序的
• 键和值位置都可以是null，但是键位置只能是一个null，因为键不能重复
• 键位置是唯一的，底层的数据结构控制键的
• jdk1.8前数据结构是：链表 + 数组 jdk1.8之后是 ： 链表 + 数组 /红黑树
• 阈值(边界值) > 8 并且数组长度大于64，才将链表转换为红黑树，变为红黑树的目的是为了高效的查询。

使用时建议：

• 使用时如果知道数据量的大小，尽量使用设置初始容量的构造函数
• 建议设置初始容量的计算公式为：需要存储的元素个数/ 负载因子(0.75F) + 1.0F

2、LinkedHashMap类

    LinkedHashMap是HashMap的子类，对于数据进行存储的过程与HashMap中的一致；但是也有一定的区别，这里对两者的区别以及LinkedHashMap的特点进行简单总结：

• HashMap是无序的，但是LinkedHashMap则是有序的，默认是按照数据插入的顺序；
• jdk1.8以后，HashMap的数据结构为 链表 + 数组 /红黑树，LinkedHashmap数据结构为： 链表 + 双向数组 /红黑树；
• 键和值位置都可以是null，但是键位置只能是一个null；
• 两个实现类均为非线程安全。

2.1、源码分析

先来看一下LinkedHashMap的集成关系：

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>{......}

LinkedHashMap中新增加的成员变量：

    /*** The head (eldest) of the doubly linked list.* 双向链表的头节点，最先插入的节点*/transient LinkedHashMap.Entry<K,V> head;/*** The tail (youngest) of the doubly linked list.* 双向链表的尾节点，最后插入的节点*/transient LinkedHashMap.Entry<K,V> tail;/*** 用来设置顺序，默认为false：按照插入的顺序来排序* 设置为true:按照访问的顺序来排序，最近访问的数据节点会被插入到链表的最末端*/final boolean accessOrder;

再来看一下LinkedHashMap的真实结构如下：

    static class Entry<K,V> extends HashMap.Node<K,V> {Entry<K,V> before, after;Entry(int hash, K key, V value, Node<K,V> next) {super(hash, key, value, next);}}

与HashMap相比，LinkedHashMap在原来的基础上添加了两个属性before，after；所以现在Entry（对应HashMap为Node）的属性包括以下几个：

K key
V value
Entry<K, V> next
int hash
// 下面为新增的
Entry<K, V> before
Entry<K, V> after

再来看一下LinkedHashMap的构造函数，LinkedHashMap共包括5个构造函数，如下所示：

	// 与HashMap的构造函数相比，只是在每一个构造函数中多了一个控制顺序的设置，// 默认是按照插入的顺序排序public LinkedHashMap(int initialCapacity, float loadFactor) {super(initialCapacity, loadFactor);accessOrder = false;}public LinkedHashMap(int initialCapacity) {super(initialCapacity);accessOrder = false;}public LinkedHashMap() {super();accessOrder = false;}public LinkedHashMap(Map<? extends K, ? extends V> m) {super();accessOrder = false;putMapEntries(m, false);}public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {super(initialCapacity, loadFactor);this.accessOrder = accessOrder;}

接下里说一下LinkedHashMap是如何控制顺序的，先来看一下LinkedHashMap获取节点数据的过程，代码如下：

    public V get(Object key) {Node<K,V> e;if ((e = getNode(hash(key), key)) == null)return null;// 如果设置了accessOrder=true，则重新进行序列调整；否则按照插入顺序if (accessOrder)afterNodeAccess(e);return e.value;}// 将已经获取的节点，重新覆写到链表的尾节点void afterNodeAccess(Node<K,V> e) { // move node to lastLinkedHashMap.Entry<K,V> last;// accessOrder=true// 且刚获取的节点不在链表的尾部，就将节点移动到链表的尾部if (accessOrder && (last = tail) != e) {LinkedHashMap.Entry<K,V> p =(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;p.after = null;// 如果刚获取的节点的前一个节点为null,说明该节点在头部，设置其下一个节点为头节点// 否则就将当前节点的下一个节点设置为其前一个节点的下一个节点 if (b == null)head = a;elseb.after = a;if (a != null)a.before = b;elselast = b;if (last == null)head = p;else {p.before = last;last.after = p;}tail = p;// 计数修改的次数++modCount;}}

接下来介绍一下LinkedHashMap添加数据的过程，LinkedHashMap添加数据时调用的是父类的put方法，但在具体执行的时候则对其中的一些方法进行了重写，先来看一下父类的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;if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;if ((p = tab[i = (n - 1) & hash]) == null)// LinkedHashMap对newNode()进行了重写，下边会介绍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)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 1sttreeifyBin(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当accessOrder=true时，* 将操作（查询、覆盖值）过的节点移动到链尾，具体看上边的源码分析*/afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold)resize();// 这个方法，在jdk1.8中没有用到，具体参见下边的分析afterNodeInsertion(evict);return null;}

具体的过程就不解释了，在LinkedHashMap中，对上述方法中的newNode()、putTreeVal()中的newTreeNode()进行了重写，并且实现了两个回调方法afterNodeAccess（上面已经介绍过了）和afterNodeInsertion，下面看一下：

   Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {LinkedHashMap.Entry<K,V> p =new LinkedHashMap.Entry<K,V>(hash, key, value, e);linkNodeLast(p);return p;}// 新建一个节点,并将节点方至链表的尾部private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {LinkedHashMap.Entry<K,V> last = tail;tail = p;if (last == null)head = p;else {p.before = last;last.after = p;}}// afterNodeInsertion()没有用到，因为removeEldestEntry()方法始终返回falsevoid afterNodeInsertion(boolean evict) { // possibly remove eldestLinkedHashMap.Entry<K,V> first;if (evict && (first = head) != null && removeEldestEntry(first)) {K key = first.key;removeNode(hash(key), key, null, false, true);}}

最后来说一下移除节点的操作，移除的过程大致如下：

• 先根据key计算节点在数组table中的索引位置
• 遍历链表或者红黑树删除节点
• 移除节点以后维护双向链表

    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;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);}}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;elsep.next = node.next;++modCount;--size;// 与HashMap有区别的地方是，移除完节点以后对于双向链表结构的维护afterNodeRemoval(node);return node;}}return null;}void afterNodeRemoval(Node<K,V> e) { // unlinkLinkedHashMap.Entry<K,V> p =(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;// 将要移除的节点的前驱和后继节点置为nullp.before = p.after = null;// b为null，说明要删除的节点为头节点if (b == null)head = a;elseb.after = a;// a为null，说明要删除的节点为尾节点if (a == null)tail = b;elsea.before = b;}

关于LinkedHashMap暂时就讲到这里，关于未说到的可以自己看源码在研究，跟HashMap的内容差不多。
参考博客：
LinkedHashMap 源码详细分析（JDK1.8）
LinkedHashMap如何保证顺序性

3、TreeMap类

    TreeMap是一种可以实现自排序的数据结构，底层的数据结构为红黑树，红黑树是平衡树中的一种，关于红黑树的性质可以自己下去研究，这里就不展开了，接下来进行源码分析。

3.1 源码分析

先来看一下TreeMap的继承关系：

public class TreeMap<K,V>extends AbstractMap<K,V>implements NavigableMap<K,V>, Cloneable, java.io.Serializable{......}

接下来介绍下实现类中的成员变量及构造函数：

    /*** The comparator used to maintain order in this tree map, or* null if it uses the natural ordering of its keys.* 自定义比较器，可以为null,如果为null时则默认使用key来进行排序*/private final Comparator<? super K> comparator;// 红黑树的根节点private transient Entry<K,V> root;/*** entry的个数*/private transient int size = 0;/*** The number of structural modifications to the tree.* 结构改变的次数*/private transient int modCount = 0;/*** 构建一个空的构造函数*/public TreeMap() {comparator = null;}/*** 根据自定义的比较器来构建构造函数*/public TreeMap(Comparator<? super K> comparator) {this.comparator = comparator;}/*** 使用默认比较器将Map类型数据转化为一个新的TreeMap结构*/public TreeMap(Map<? extends K, ? extends V> m) {comparator = null;putAll(m);}/*** Constructs a new tree map containing the same mappings and* using the same ordering as the specified sorted map.  This* method runs in linear time.** @param  m the sorted map whose mappings are to be placed in this map,*         and whose comparator is to be used to sort this map* @throws NullPointerException if the specified map is null* 使用已知的SortedMap对象来构建TreeMap*/public TreeMap(SortedMap<K, ? extends V> m) {comparator = m.comparator();try {buildFromSorted(m.size(), m.entrySet().iterator(), null, null);} catch (java.io.IOException cannotHappen) {} catch (ClassNotFoundException cannotHappen) {}}

再来看一下TreeMap每一个节点中的真实结构：

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

一个典型的红黑树节点结构，其中color属性用来设置节点的链接是黑链接还是红链接；
添加数据的操作：

  public V put(K key, V value) {Entry<K,V> t = root;// 如果根节点为null,则创建根节点if (t == null) {/*** 检查key类型，这一点在构造函数的注释上就可以看到原因* All keys inserted into the map must be <em>mutually* comparable</em> by the given comparator: {@code comparator.compare(k1,* k2)} must not throw a {@code ClassCastException} for any keys* {@code k1} and {@code k2} in the map.*/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;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;elsereturn t.setValue(value);} while (t != null);}else {// 用户没有设定比较器时，使用默认比较器对key进行遍历比较// TreeMap的key值不能为nullif (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()方法是对插入的节点进行调整，就是红黑树中着色、左旋、右旋使树再次平衡，这里可以参考红黑树的调整过程fixAfterInsertion(e);size++;modCount++;return null;}

移除节点：

    public V remove(Object key) {Entry<K,V> p = getEntry(key);// 如果没有找到，返回nullif (p == null)return null;// 找到以后返回原来的数据V oldValue = p.value;// 删除指定的entrydeleteEntry(p);return oldValue;}// 先根据key找到指定的entryfinal Entry<K,V> getEntry(Object key) {// Offload comparator-based version for sake of performanceif (comparator != null)// 根据特定的比较器来找到entryreturn getEntryUsingComparator(key);if (key == null)throw new NullPointerException();@SuppressWarnings("unchecked")Comparable<? super K> k = (Comparable<? super K>) key;Entry<K,V> p = root;while (p != null) {int cmp = k.compareTo(p.key);if (cmp < 0)p = p.left;else if (cmp > 0)p = p.right;elsereturn p;}return null;}

关于TreeMap这里讲解的比较简单，关于红黑树的具体过程没有详细展开来说，有兴趣的可以自己下去研究，或者参考此篇博客中的内容：【深入理解java集合】-TreeMap实现原理

小结：

• TreeMap使用时可以自己定义排序比较的规则，可扩展性更好
• TreeMap的键key不能为null，值可以为null
• TreeMap有序但是非线程安全

4、HashTable类

    在JDK1.8中，HashTable采用数组+链表的数据结构，大致的结构如下：

图片来源于网络

4.1、源码分析

首先我们来看一下HashTable的继承关系：

public class Hashtable<K,V>extends Dictionary<K,V>implements Map<K,V>, Cloneable, java.io.Serializable {......}

在HashTable中包含有5个成员变量，4个构造函数，接下来我们对这部分内容进行介绍：

    /*** 存储数据的Entry数组，与hashMap中的一致*/private transient Entry<?,?>[] table;/*** 记录entry的个数，即键值对的个数*/private transient int count;/*** The table is rehashed when its size exceeds this threshold.  (The* value of this field is (int)(capacity * loadFactor).)* 扩容的阈值等于table的容量*负载因子*/private int threshold;/*** 负载因子，默认为0.75*/private float loadFactor;/*** 计数器，记录hashTable结构变化的次数*/private transient int modCount = 0;/***********************HashTable构造函数*******************************//*** 构造函数的具体实现：* 	 1）如果设置的容量为0，则默认设置为1* 	 2）初始化数组table*   3) 扩容的阈值为数组的容量（默认为11）*负载因子（默认为0.75）* Hashtable中数组的容量没有限制为2的n次幂，可以取大于0的任意值*/public Hashtable(int initialCapacity, float loadFactor) {if (initialCapacity < 0)throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal Load: "+loadFactor);if (initialCapacity==0)initialCapacity = 1;this.loadFactor = loadFactor;table = new Entry<?,?>[initialCapacity];threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);}/*** Constructs a new, empty hashtable with the specified initial capacity* and default load factor (0.75).*/public Hashtable(int initialCapacity) {this(initialCapacity, 0.75f);}/*** Constructs a new, empty hashtable with a default initial capacity (11)* and load factor (0.75).*/public Hashtable() {this(11, 0.75f);}/*** Constructs a new hashtable with the same mappings as the given* Map.  The hashtable is created with an initial capacity sufficient to* hold the mappings in the given Map and a default load factor (0.75).** @param t the map whose mappings are to be placed in this map.* @throws NullPointerException if the specified map is null.* @since   1.2*/public Hashtable(Map<? extends K, ? extends V> t) {this(Math.max(2*t.size(), 11), 0.75f);putAll(t);}	

接下来看一下HashTable添加数据的过程：

	/*** 添加的方法采用synchronized 关键字进行修饰，所以是线程安全的*/public synchronized V put(K key, V value) {// value不能为空，否则抛出空指针异常；if (value == null) {throw new NullPointerException();}// Makes sure the key is not already in the hashtable.Entry<?,?> tab[] = table;// key也不能为null，因为null.hashCode会抛出异常int hash = key.hashCode();// 计算entry在数组table中的索引的计算方法，hash值与2^31-1求与，然后与数组的长度进行求余int index = (hash & 0x7FFFFFFF) % tab.length;@SuppressWarnings("unchecked")Entry<K,V> entry = (Entry<K,V>)tab[index];// 遍历table[index]所连接的所有链表，查找是否有节点的key与要插入的key相同，如果存在则替换for(; entry != null ; entry = entry.next) {if ((entry.hash == hash) && entry.key.equals(key)) {V old = entry.value;entry.value = value;return old;}}// 如果不存在相同的key，则执行addEntry操作addEntry(hash, key, value, index);return null;}private void addEntry(int hash, K key, V value, int index) {modCount++;Entry<?,?> tab[] = table;// 判断hashTable中的键值对的个数是否大于等于扩容阈值，// 如果大于等于，则执行扩容的操作if (count >= threshold) {// Rehash the table if the threshold is exceededrehash();tab = table;hash = key.hashCode();index = (hash & 0x7FFFFFFF) % tab.length;}// Creates the new entry.@SuppressWarnings("unchecked")// 取出table中index位置的entry给到e,也就是对应位置链表给到eEntry<K,V> e = (Entry<K,V>) tab[index];// 把新插入的entry插入到链表的第一个节点tab[index] = new Entry<>(hash, key, value, e);count++;}

扩容的操作：

    @SuppressWarnings("unchecked")protected void rehash() {int oldCapacity = table.length;Entry<?,?>[] oldMap = table;// overflow-conscious code// 新的数组的容量为原来数组的2倍+1int newCapacity = (oldCapacity << 1) + 1;// 判断新的数组容量值是否大于最大值if (newCapacity - MAX_ARRAY_SIZE > 0) {if (oldCapacity == MAX_ARRAY_SIZE)// Keep running with MAX_ARRAY_SIZE bucketsreturn;newCapacity = MAX_ARRAY_SIZE;}//使用新的数组容量初始化一个新的数组Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];modCount++;// 计算扩容阈值threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);table = newMap;// 循环遍历将原来的数据添加到新的数组中for (int i = oldCapacity ; i-- > 0 ;) {for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {Entry<K,V> e = old;old = old.next;int index = (e.hash & 0x7FFFFFFF) % newCapacity;e.next = (Entry<K,V>)newMap[index];newMap[index] = e;}}}

最后看一下移除数据的操作：

    public synchronized V remove(Object key) {Entry<?,?> tab[] = table;int hash = key.hashCode();int index = (hash & 0x7FFFFFFF) % tab.length;@SuppressWarnings("unchecked")// 先根据key找到table中对应的索引位置处Entry<K,V> e = (Entry<K,V>)tab[index];// 循环遍历数组index索引处对应的链表for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {if ((e.hash == hash) && e.key.equals(key)) {modCount++;// prev==null,说明链表中的第一个节点即为要移除的节点// 执行的是一个删除链表中节点的操作，相对简单if (prev != null) {prev.next = e.next;} else {tab[index] = e.next;}count--;V oldValue = e.value;e.value = null;return oldValue;}}return null;}

4.2、HashMap与HashTable的比较

• HashMap中的键和值均可以为null，但是HashTable中的键和值均不能为null
• JDK1.8中HashMap采用数组+链表/红黑树结构实现，而HashTable中采用的是数组+链表实现
• HashMap中出现hash冲突时，如果链表节点数小于8时是将新元素加入到链表的末尾(大于8时就要扩容操作了)，而HashTable中出现hash冲突时采用的是将新元素加入到链表的开头
• HashMap中数组容量的大小要求是2的n次方，如果初始化时不符合要求会进行调整，而HashTable中数组容量的大小可以为任意正整数
• 计算entry在数组中的位置的策略不同
• HashMap不是线程安全的，HashTable为线程安全的，其中的添加、移除、获取数据的方法均添加了synchronized关键字
• HashMap的默认容量为16，HashTable默认容量为11