集合（Collection）

在 Java 开发中集合大概是出场率最高的组件之一。无论是存储一组对象、做去重判断还是建立键值映射关系几乎处处都有它的身影。但很多人用了很久的 ArrayList 和 HashMap却对整个集合框架的全貌缺乏清晰认知——List、Set 有什么区别Collection 和 Map 到底是什么关系本文就从顶层接口开始把 Java 集合框架的脉络彻底理清楚。 简述集合体系结构单列集合Collection 分为有序 List 和 无序Set List Set Collection 均为接口 需要实现类来实现List的实现类有 ArrayList LinkedList Vector ArrayList 底层数据结构为数组 查询快 增删慢 线程不安全 效率快 LinkedList 底层数据结构为链表 查询慢 增删快 线程不安全 效率快 Vector 底层数据结构为数组 查询快 增删慢 线程安全 效率慢Set的实现类有 HashSet LinkHashSet TreeSet HashSet 底层是hash表 特点是值无序 唯一 LinkedHashSet 底层是hash表链表 特点是值有序 唯一 (存取顺序一致) TreeSet 底层是红黑树 特点是有自动排序 唯一双列Map集合Map的实现类有 HashMap LinkedHashMap TreeMap HashMap 底层是数组链表红黑树 键无序 唯一(局部有序只有每个桶中的树是有序的) LinkedHashMap 底层是数组链表红黑树双向链表 键有序 唯一 (存取顺序一致) TreeMap 底层是红黑树 键有自动排序 唯一(全局有序,整个Map只有一棵树,所以是全局有序)HashMap的底层实现原理首先数据通过HashCode()计算出对应的哈希值 再通过其他处理选择桶(默认长度为16,扩容因子为0.75),如果桶内没有元素,则直接存储即可;如果桶中有元素,则需要通过equals()与桶中每个元素进行比较,如果比较结果为true,则为重复元素,不添加;反之为false,不重复元素,存储在桶中的链表或红黑树中