Java 数据结构与算法

Java 数据结构

集合框架

• Collection 接口（增删改查）
  1. List 接口
     • ArrayList：基于数组实现，动态扩容
     • LinkedList: 基于双向链表实现
     • Vector： 与ArrayList 类似，但是是线程安全
     • Stack：继承自Vector，线程安全，后进先出
  2. Queue 接口：队列，即一个先入先出，前端进行删除操作，而在表的后端进行插入操作
     • ArrayBlockingQueue：基于数组的阻塞队列，有界队列，创建时需要给定大小，且不可变，线程安全，容量满，则阻塞进队操作；容量空，则阻塞出队操作
     • PriorityQueue：无边界，支持优先级队列实现类，非线程安全，数组实现，折半查找算法
     • PriorityBlockingQueue：CAS实现的自旋锁来控制队列的动态扩容，无界，且线程安全
     • LinkedList: 基于双向链表实现
  3. Set 接口
     • HashSet：底层用HashMap实现，但是value为一个固定的object，无序的
     • TreeSet： 底层用TreeMap实现（红黑树），有序
     • LinkedHashSet：底层用LinkedHashMap，维护元素插入顺序
• Map 接口（key-value）
  1. HashMap:数组+链表的方式实现，（jdk1.8用数组+红黑树实现），无序
  2. TreeMap：红黑树实现，有序
  3. HashTable:线程安全 ，现在不推荐用，它继承自Dictionary
  4. LinkedHashMap:HashMap的子类，多了一个双向链表维护元素插入的顺序
  5. ArrayMap 对内存有优化，但是元素过多会有性能开销，随着手机内存越来越大，不推荐使用，
• Deque 接口：双端队列
  1. 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是个工具类，静态方法，提供一些集合操作