HashMap，TreeMap，TreeSet

HashMap

哈希桶+链表+数据结构（红黑树，Java8以后）
O(1)的平均插入，查找，删除时间复杂度
致命缺陷是hash碰撞
哈希算法：先计算hashCode，再映射到索引

默认初始容量为16
负载因子为0.75

为什么初始容量必须为2的幂，并且扩充也是乘以2：
1、减1之后全为1，方便将哈希值映射为桶的编号（hash & size-1)；
2、方便扩充，扩充*2，保证通量仍为2的幂，使得扩充后的数据还在原来位置或者在原来的位置加旧桶的的大小。

• Java7中HashMap的缺点：
  1、 HashMap不是线程安全的，扩容后和扩容前链表顺序不一致，采用头插法，会造成死循环；
  2、过多碰撞会退化为链表，导致查询时间为O(n)。
• Java8中对Java7中缺点的改进：
  1、保证扩容后和扩容前链表顺序一致，采用尾插法，防止死循环，但也不是线程安全的，线程安全的hashmap请用concurrentHashMap；
  2、链表长度超过8时采用红黑树存储，时间复杂度为O（logn)；小于6时回退为链表。

简单记录一下红黑树，红黑树是一颗自平衡二叉查找树，也就是说当插入或者删除一个节点破坏了树的平衡时，会采用左旋或者右旋自动恢复平衡。红黑树的左子树的值小于根节点，右子树的值大于根节点。红黑树的插入查找删除时间复杂度均为O(log n)。

• 一个对象是如何被映射到桶里：
  首先计算hashCode->rehash(使得hashCode分布更加均匀，减少碰撞出现的次数）->index计算桶的编号

LinkedHashMap是在HashTable的基础上，加入了一些指针，使得entry按照插入顺序排序。可以用于实现LRU缓存机制。

TreeMap底层是红黑树，可以在创建一个TreeMap时传入一个comparator，自定义排序。

TreeMap<Integer, String> map = new TreeMap<>(Comparator.reverseOrder());
map.put(3, "val");
map.put(2, "val");
map.put(1, "val");
map.put(5, "val");
map.put(4, "val");
System.out.println(map); // {5=val, 4=val, 3=val, 2=val, 1=val}

TreeSet是基于TreeMap实现的

TreeSet.png