Java 数据结构
集合框架
- Collection 接口（增删改查）
- List 接口
- ArrayList：基于数组实现，动态扩容
- LinkedList: 基于双向链表实现
- Vector： 与ArrayList 类似，但是是线程安全
- Stack：继承自Vector，线程安全，后进先出
- Queue 接口：队列，即一个先入先出，前端进行删除操作，而在表的后端进行插入操作
- ArrayBlockingQueue：基于数组的阻塞队列，有界队列，创建时需要给定大小，且不可变，线程安全，容量满，则阻塞进队操作；容量空，则阻塞出队操作
- PriorityQueue：无边界，支持优先级队列实现类，非线程安全，数组实现，折半查找算法
- PriorityBlockingQueue：CAS实现的自旋锁来控制队列的动态扩容，无界，且线程安全
- LinkedList: 基于双向链表实现
- Set 接口
- HashSet：底层用HashMap实现，但是value为一个固定的object，无序的
- TreeSet： 底层用TreeMap实现（红黑树），有序
- LinkedHashSet：底层用LinkedHashMap，维护元素插入顺序
- List 接口
- Map 接口（key-value）
- HashMap:数组+链表的方式实现，（jdk1.8用数组+红黑树实现），无序
- TreeMap：红黑树实现，有序
- HashTable:线程安全 ，现在不推荐用，它继承自Dictionary
- LinkedHashMap:HashMap的子类，多了一个双向链表维护元素插入的顺序
- ArrayMap 对内存有优化，但是元素过多会有性能开销，随着手机内存越来越大，不推荐使用，
- Deque 接口：双端队列
- LinkedList：双端队列实现
有哪些集合的Key/Value不能为null
- 不能为null：
- ConcurrentHashMap（Key/Value:多线程get(key)方法的二义性）
- HashTable（Key/Value:多线程get(key)方法的二义性）
- TreeMap(Value：默认的Comparator 方法会抛出空指针异常)
- TreeSet（Value：默认的Comparator 方法会抛出空指针异常）
ConcurrentHashMap 实现
通过segement + HashEntry（数组+链表的方式，即HashMap的方式）自旋锁实现线程安全。
如何深拷贝一个List集合
实现元素的clone方法，在新建一个list时调用原list中元素的clone方法
Collection 和 Collections区别
Collection是接口
Collections是个工具类，静态方法，提供一些集合操作
