2.14 集合框架底层数据结构总结

先来看⼀下Collection接⼝下⾯的集合。
1. List

• Arraylist：Object[]数组
• Vector：Object[]数组
• LinkedList：`双向链表(JDK1.6 之前为循环链表，JDK1.7 取消了循环)
  2. Set
• HashSet（⽆序，唯⼀）：基于HashMap实现的，底层采⽤HashMap来保存元素
• LinkedHashSet：LinkedHashSet是HashSet的⼦类，并且其内部是通过LinkedHashMap来实现的。有点类似于我们之前说的LinkedHashMap其内部是基于HashMap实现⼀样，不过还是有⼀点点区别的
• TreeSet（有序，唯⼀）：红⿊树（⾃平衡的排序⼆叉树）再来看看Map接⼝下⾯的集合。
  3. Map
• HashMap：JDK1.8 之前HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突⽽存在的（“拉链法”解决冲突）。JDK1.8 以后在解决哈希冲突时有了较⼤的变化，当链表⻓度⼤于阈值（默认为 8）（将链表转换成红⿊树前会判断，如
  果当前数组的⻓度⼩于 64，那么会选择先进⾏数组扩容，⽽不是转换为红⿊树）时，将链表转化为红⿊树，以减少搜索时间
• LinkedHashMap：LinkedHashMap继承⾃HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红⿊树组成。另外，LinkedHashMap在上⾯结构的基础上，增加了⼀条双向链表，使得上⾯的结构可以保持键值对的插⼊顺序。同时通过对链表进⾏相应的
  操作，实现了访问顺序相关逻辑。详细可以查看：《LinkedHashMap 源码详细分析（JDK1.8）》
• Hashtable：数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突⽽存在的
• TreeMap：红⿊树（⾃平衡的排序⼆叉树）