Java为数据结构中的映射定义了一个接口java.util.Map，此接口主要有四个常用的实现类，分别是HashMap、Hashtable、LinkedHashMap和TreeMap，类继承关系如下图所示：
每个类的特点，可以通过看源码了解具体实现：
1. HashMap，通过key的hashCode进行高位运算，再与数组的大小取模运算得到数组下标，数组value是一个链表，如果长度超过8会转换为红黑树，初始化长度length(默认值是16)，loadFactor为负载因子(默认值是0.75)，threshold是HashMap所能容纳的最大数据量的键值对个数，size是实际键值对数量，如果size超过threshold，就会扩容length，设计为2的n次方（为了取模和扩容时的优化）。并发的多线程使用场景中使用HashMap可能造成死循环。
2. HashTable，遗留类，继承自Dictionary，线程安全，锁全部，基本不用了。
3. LinkedHashMap，继承自HashMap，双向链表保存顺序，遍历时先获取先插入的，还可以在new对象时带参数，按照访问次序排序。
4. TreeMap，实现自SortedMap接口，可以根据key排序，默认是升序，也可以指定排序比较器，使用时必须实现Comparable接口或new时传入自定义的Comparator，不然会抛异常。
5. ConcurrentHashMap，多线程读取数据不加锁，并且其内部的结构可以让其在进行写操作的时候能够将锁的粒度保持地尽量地小，允许多个修改操作并发进行，其关键在于使用了锁分段技术，JDK1.8锁的粒度就是HashEntry（首节点），采用了CAS无锁算法。
相关概念：
二叉查找树：
1、要么为一颗空树，要么就是一颗具有如下特性的二叉树。
2、左子节点的值必须小于等于父节点的值。
3、右子节点的值必须大于等于父节点的值。
平衡二叉树：
1、要么为一颗空树，要么就是一颗具有如下特性的二叉查找树。
2、它的左子树和右子树都是平衡二叉树。
3、它的左子树和右子树的深度差的绝对值不超过1。
红黑树：
1、每个节点要么是黑色，要么是红色。
2、根节点是黑色。
3、所有叶子节点是黑色，即空节点（null）。
4、如果一个节点是红色的，则它的两个子节点必须是黑色的，也就是父子节点不能都为红色。
5、从一个节点到其所有叶子节点的所有路径上包含相同数目的黑节点。
为什么不用平衡二叉树作为底层实现?
那是因为平衡二叉是高度平衡的树, 而每一次对树的修改, 都要 rebalance, 这里的开销会比红黑树大. 如果插入一个node引起了树的不平衡，平衡二叉树和红黑树都是最多只需要2次旋转操作，即两者都是O(1)；但是在删除node引起树的不平衡时，最坏情况下，平衡二叉树需要维护从被删node到root这条路径上所有node的平衡性，因此需要旋转的量级O(logN)，而红黑树最多只需3次旋转，只需要O(1)的复杂度, 所以平衡二叉树需要rebalance的频率会更高，因此红黑树在大量插入和删除的场景下效率更高。
