1. Java集合中设计了一个接口Java.util.Map，它实现类中hashMap、hashTable、TreeMap、ConcurrentHashMap、LinkedHashMap。
2. Map类型的集合用来做键值对存储的，也就是key-value形式的。所以不允许键重复，值是可以重复的。

hashMap

1. hashMap 底层结构是：数组+链表+红黑树（jdk1.8之前就是存储的数组+链表）

   说明：

    数组的特点：查询效率高，插入，删除效率低。
    链表的特点：查询效率低，插入删除效率高。
    在HashMap底层使用数组加（链表+红黑树）的结构完美的解决了数组和链表的问题，使得查询和插入，删除的效率都很高。
    当链表的长度达到某个阀值（8）的时候，这个链表就将转换成红黑树。
    删除的时候可能导致红黑树转换为链表
    扩容也可能导致红黑树转化为链表 扩容有可能导致红黑树拆成两部分, 在这两部分中, 任意部分, 如果元素数量是小于等于6的话, 会由红黑树转化为链表。
    在jdk1.8中，如果链表长度大于8且节点数组长度大于64的时候，就把链表下所有的节点转为红黑树。树形化还有一个要求就是数组长度必须大于等于64，否则继续采用扩容策略
   

2. 默认初始容量16, 负载因子0.75,扩容机制是原容量的2倍。且要求容量一定为2的整数次幂

   说明：用数组容量大小乘以负载因子得到一个值，当数组中存储的元素个数超过该值就会调用rehash方法将数组容量增加到原来的两倍。在扩容的时候会生成一个新的数组，原来的所有数据需要重新计算哈希码值重新分配到新的数组，所以扩容的操作非常消耗性能.

3. 无序的，允许存null（键，值），线程不安全的。可以使用 Collections的synchronizedMap方法保证安全。

4. 存储过程
   说明：存储数据时计算Key的hashCode值再%数组的长度得到对应的数组下标，如果这个下标没有值就直接存入，如果有值就会计算euqals()的值是不是相等，相等就覆盖，不相等就往下链。链的太多时会转换为红黑树。

LinkedHashMap

1. LinkedHashMap是HashMap一个子类，基本完全复用和遵从HashMap的特点
2. LinkedHashMap在HashMap的基础上维护了一个双向链表，意味着他是有序的。

TreeMap

1. TreeMap它是基于红黑树的NavigableMap实现。（树中的每个节点的值都会大于或等于它的左子树中的所有节点的值，并且小于或等于它的右子树中的所有节点的值），实现了SortMap接口，能够对保存的记录根据键进行排序。
2. 不允许NULL（键，值），线程不安全的
3. 在TreeMap中存储数据时, key-value, 我们可以有两种方式： 一个就是让key本身可以比较(继承Comparable接口实现compareTo) 另一个就是可以在创建TreeMap的时候手动提供一个比较器

HashTable

1. 无序，线程安全的(几乎所有的方法都加锁)，不能存储null值，null键
2. 底层结构是数组+链表
3. 默认初始容量11，扩容时2倍+1。且不要求底层数组的容量一定要为2的整数次幂；

ConcurrentHashMap

1. ConcurrentHashMap 是线程安全的，相比较HashTable，jdk1.8之前ConcurrentHashMap是分段锁（Segment），继承了ReentrantLock。jdk1.8开始线程安全性由synchronized 和 CAS 来保证。
2. ConcurrentHashMap可以一边更新、一边遍历，也就是说在遍历的时候，ConcurrentHashMap也可以进行remove,put操作，且遍历的数据会随着remove,put操作产生变化。HashTable会抛异常。
3. get方法没有加锁，remove put是要加锁的。
   说明：jdk1.8之前是分段锁，一般不会出现锁的争抢，jdk1.8开始分的更细了，使用cas机制添加到树的头节点，如果失败了，说明有其他线程在操作，那就再次循环上一步添加操作。如果头节点已经存在了，通过synchronized获得头节点锁，进行后续的操作。

总结

1. 平常使用HashMap，访问速度快，效率高。
2. 有排序需求的，并且需要自定义排序规则的使用TreeMap。
3. 有线程安全并发的需求时考虑使用ConcurrentHashMap。
4. 需要快速增删改查而且需要保证遍历和插入顺序一致的存储功能 LinkedHashMap。

补充

1. 二叉树
   特点：左子节点的值小于父节点，右子节点的值大于父子节点。当有序列表时，会变成链表结构
2. 平衡二叉树 AVL
   特点：和二叉树唯一不同的就是左子节点和右子节点的高度差最多等于1。
3. 红黑树
   特点：通过左旋或者右旋维持树的平衡，因为AVL太严格，当树的节点发生变化时会破坏平衡。