常见集合的差异:

  1. List: 存储的元素是有序的,数据内容可重复
  2. Map: 存储的元素是无序的,内容可重复 ,键不可重复
  3. Set: 存储元素结构是无序的,不可重复

list 与 set 集成自Collection 接口

List

常见的List的实现类为 ArrayList 与 LinkedList , ArrayList 为数组结构,LinkedList 是链表结构,
ArrayList 相比于原生list 实现了动态扩容机制,每次扩容为1.5倍

Vector 底层是数组的线程安全数据结构,每次扩容为2倍基本不用

线程安全问题

  • ⽤Collections来将ArrayList来包装⼀下

    1. List<String> list = Collections.synchronizedList(new ArrayList<String>());

  • 使用java.util.concurrent包下 CopyOnWriteArrayList 类(保证最终一致性)

CopyOnWriteArrayList 的扩容是通过写时复制机制(cow)完成的的,每次增加和修改都很耗内存,写时加锁,读不加锁

Map

  • HashMap: ： JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链 表则是主要为了解决哈希冲突⽽存在的（“拉链法”解决冲突）。JDK1.8 以后在解决哈希冲突 时有了᫾⼤的变化，当链表⻓度⼤于阈值（默认为 8）（将链表转换成红⿊树前会判断，如 果当前数组的⻓度⼩于 64，那么会选择先进⾏数组扩容，⽽不是转换为红⿊树）时，将链 表转化为红⿊树，以减少搜索时
  • LinkedHashMap ： LinkedHashMap 继承⾃ HashMap ，所以它的底层仍然是基于拉链式散 列结构即由数组和链表或红⿊树组成。另外， LinkedHashMap 在上⾯结构的基础上，增加 了⼀条双向链表，使得上⾯的结构可以保持键值对的插⼊顺序。同时通过对链表进⾏相应的 操作，实现了访问顺序相关逻辑。详细可以查看：《LinkedHashMap 源码详细分析 （JDK1.8）
  • Hashtable ： 数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲 突⽽存在的
  • TreeMap ： 红⿊树（⾃平衡的排序⼆叉树）

image.png

set

  • HashSet （⽆序，唯⼀）: 基于 HashMap 实现的，底层采⽤ HashMap 来保存元素
  • LinkedHashSet ： LinkedHashSet 是 HashSet 的⼦类，并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的
  • LinkedHashMap 其内部是基于 HashMap 实现⼀样， 不过还是有⼀点点区别的 TreeSet （有序，唯⼀）： 红⿊树(⾃平衡的排序⼆⼆叉树)

如何选用合适的集合

需要根据键值对获取值时,就用map 接口下的类,需要排序就用 TreeMap
,不需要排序就用 HashMap ,需要线程安全就用 ConcurrentHashMap

保存元素值时,如果要求键唯一,就用set ,接口的实现 TreeSet 和 HashSet ,不要求就用 List,接口的实现集合: ArrayList , linkedList