一、HashMap

1、底层实现原理

1.1 JDK7

1. 在实例化HashMap map = new HashMap()之后，底层会创建一个长度为 16 的 Entry[] table
2. 调用map.put(key1,value1)方法之后
   1. 调用 key1 所在类的的 hashCode()计算 key1 的哈希值，对此哈希值进行某种算法（与运算）在实例化HashMap map = new HashMap()之后之后，得到在 Entry 数组中存放的位置索引。
      1. 如果位置上的数据为空，那么此时的 (key1,value1)添加成功 情况1
      2. 如果位置上的数据不为空，那么意味着此位置上存在着一个或多个数据（链表的形式），则需要将key1 和已经存在的一个或多个数据进行比较哈希值。
         1. 如果 key1 的哈希值和参与比较的数据的哈希值都不相同，那么就直接插入成功 情况2
         2. 如果 key1 的哈希值和已经存在的某个数据(key2,value2)哈希值相同，那么就调用 key1 所在类的 equals(key2)
            1. 如果equals(key2)为假，那么就直接添加成功。 情况3
            2. 如果equals(key2)为真，那么会使用 value1 来替换 value2

注意：对于情况2和情况3，此时的 (key,value) 和原来的数据以链表的方式存储。
在不断添加元素的过程中，会涉及到扩容的问题，默认的扩容方式是为原来容量的两倍（左移1位）

1.2 JDK8

1. 在实例化HashMap map = new HashMap()之后，底层并没有创建数组。
2. JDK8中，底层的数组是Node[]而非Entry[]
3. 在第一次调用put()的时候，才会创建底层数组

4. JDK7中底层结构只有：数组+链表，而JDK8中是：数组+链表+红黑树

   二、LinkedHashMap

   三、TreeMap

   注意点：

5. 要求 key 必须是同一个类所创建的对象

6. 排序是根据 key 来进行排序（编写比较函数）
   1. 自然排序
   2. 定制排序