常见的数据结构

1. 线性表
   • 数组
   • 链表
2. 栈与队列
3. 树
4. 堆
5. 散列表

顶层接口

Collection和Map

集合框架图 from https://www.jianshu.com/p/63e76826e852

Collection

三个子接口：List、Set、Queue

List，对应线性表

• ArrayList，对应数组
• LinkedList，对应链表

Set

• HashSet
• LinkedHashSet
  插入序
• TreeSet

Stack和Queue

• Stack
  继承自Vector，如java doc所言，如果需要栈这种结构，可以使用Deque的实现类

A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class. For example:
Deque<Integer> stack = new ArrayDeque<Integer>();

• Queue
  队列接口，offer-poll，add-remove，后者失败throws，前者返回null或false。element和peek，前者失败throws，后者null
• Deque
  继承Queue（头插头出），扩展了从另一端操作队列（头插尾插，头出尾出）的功能，也就拥有了作为stack使用的能力，实现类包括ArrayDeque和LinkedList，对应队列的数组实现和链表实现。

Map

• HashMap，对应散列表

  1. 数组+链表实现，1.8之后链表长度大于8会转为红黑树，优化查询效率
  2. 长度length为2的幂次方，可以使得
     hash % length = hash & (length - 1)
     成立，于是可以使用二进制运算&来提升计算效率
  3. 多线程死循环
     并发rehash导致链表成环，1.8修复了这个问题。不过本来HashMap也不是并发安全的，0202年了，不会还有人问怎么成环吧，那也太low了
     疫苗：JAVA HASHMAP的死循环
     

• TreeMap，对应红黑树
  遍历有序，实现接口如下图。主要的是SortedMap和NavigableMap，一个提供了排序能力，一个提供了搜索能力（如lowEntry，小于指定key的最大的entry），navigable的意思是可导航的。

  
  TreeMap类图

• LinkedHashMap
  HashMap+LinkedList
  继承自HashMap，同时维护头尾链表节点（双向，1.8），每个插入的节点都会拼到尾部。自带lru特性，访问后会调整到尾部，插入后会删除eldest（实现removeEldestEntry即可）

补充

1. ConcurrentHashMap
   将哈希桶分配在若干Segment（继承自ReetrantLock）下，依靠分段锁实现线程安全
   1.8之后取消了Segment的设计，直接锁HashMap的桶