1. 数据结构：树、数组、链表、堆、栈、队列

1. 树

1. 二叉树：节点存值
   1. 容易形成单链表形式，如果是单链表形式，查询时间复杂度On，如果是二叉树形式，查询时间复杂度Ologn
   2. 遍历方式
      1. 前序：根左右
      2. 中序：左根右
      3. 后序：左右根
2. BST二叉搜索树：节点存值
   1. 节点值按照左根右升序排序，其中序遍历是递增序列，容易形成单链表形式，如果是单链表形式，查询时间复杂度On，如果是二叉树形式，查询时间复杂度Ologn
3. AVL二叉平衡树
   1. 能够维持二叉树结构，查询时间复杂度Ologn，但是增删改需要通过旋转来维持平衡树的结构，开销大
4. 红黑树
   1. 根节点是黑节点，每一层红黑相间
   2. 红黑树是一种特殊的二叉平衡树，能够维持二叉平衡树的结构，查询时间复杂度Ologn，增删改需要旋转来维持，开销大
5. B树
   1. 是一种多路平衡树，节点存多个值，M阶B树一个节点可以存M-1个值，通过将节点读入内存，然后进行二分查找来搜索
   2. 缺点：查询效率不稳定，数据可能在树的任意一层，时间复杂度Ologn
6. B+树
   1. 是一种多路平衡树，节点存多个值，非叶子节点存数据的索引，叶子节点存数据，叶子节点的数据按照升序排序
   2. 优点：查询效率稳定，数据必定在叶子节点，查询时间复杂度Ologn

2. 数组

1. 在内存中连续存储，通过索引来随机访问元素，查询快增删慢，增删需要调用System.arrayCopy()实现，开销大
   1. 查询O1，头插On，尾插O1，删除On
   2. 初始容量，扩容需要新建数组

3. 链表

1. 在内存中非连续存储，通过指针指向来固定元素位置，只能顺序访问，查询慢增删快，增删只需要改变前后指针的指向就能实现
   1. 查询On，头插On，尾插O1，删除O1
   2. 无初始容量，不需要扩容

4. 堆栈队列

1. 堆：特殊的完全二叉树，有大根堆和小根堆
2. 栈：先进后出
3. 队列：先进先出

2. Java集合

1. List：有序可重复

1. ArrayList：数组
2. LinkedList：双向链表
3. Vector：数组，线程安全

2. Set：无序无重复

1. HashSet：哈希表，底层是HashMap
2. TreeSet：红黑树，底层是TreeMap
3. LinkedHashSet：双向链表+哈希表

3. Queue

1. LinkedList
2. PriorityQueue

4. Map：kv键值对，key无重复，value可重复

1. HashMap：1.8之前数组+链表，1.8之后数组+链表+红黑树，无序无重复
2. TreeMap：红黑树，有序无重复
3. LinkedHashMap：双向链表+哈希表
4. HashTable：哈希表，线程安全
5. ConcurrentHashMap：数组+链表+红黑树，线程安全

3. List列表

1. ArrayList和Vector

1. 数据结构：数组
2. 初始容量和扩容：
   1. ArrayList初始容量10，扩容1.5倍。
   2. Vector初始容量10，扩容2倍
3. 线程安全：ArrayList线程不安全，Vector的add和get方法加了synchronized实现线程安全
4. ArrayList的add、get和grow都需要调用System.arrayCopy()

2. ArrayList和LinkedList

1. 数据结构
   1. ArrayList：数组
   2. LinkedList：双向链表
2. 初始容量
   1. ArrayList初始容量10，扩容1.5倍
   2. LinkedList无
3. 时间复杂度
   1. ArrayList：查询O1、删除On、头插On、尾插O1
   2. LinkedList：查询On、删除O1、头插On、尾插O1
4. 存100W数据
   1. 头插：LinkedList完胜，因为ArrayList的add和grow都要调用System.arraycopy()进行转移元素，开销大
   2. 尾插：ArrayList完胜，且效率越来越高。因为ArrayList前期扩容频繁，但是后期扩容越来越少。

3. ArrayList删除元素

1. 正序for遍历，不行，删除之后会将后一个元素前移，i++后会忽略这个元素
2. 倒序for遍历，不行，会报错
3. foreach遍历，不行，会报错
4. Iterator迭代器，通过hasNext()判断是否还有元素，正确的方式

4. Set集合

1. HashSet：底层是封装了一个HashMap，通过hashcode和equals实现元素的唯一，无序唯一
2. TreeSet：底层是封装了一个TreeMap，通过树结构实现有序，hashcode和equals实现唯一，有序唯一

5. Map

1. HashMap：数据结构 、初始容量、扩容机制、树化、查询时间复杂度

1. 1.8之前
   1. 数据结构：数组+链表，table数组存放Entry节点
   2. 初始容量：16，加载因子0.75，扩容阈值12
   3. 不会树化
   4. 时间复杂度：无hash冲突时O1，发生hash冲突形成链表On
2. 1.8之后
   1. 数据结构：数组+链表+红黑树，table数组存放Node节点
   2. 初始容量：16，加载因子0.75，扩容阈值12
   3. 当链表节点数大于等于8并且table数组长度大于64时转换为红黑树，当红黑树节点数小于等于6时退化回链表
   4. 时间复杂度：链表On，红黑树Ologn，无hash冲突O1

2. 为什么要转化为红黑树：红黑树时间复杂度Ologn，链表时间复杂度On

3. 为什么在8时转化：链表的节点数量分布符合泊松分布，当节点数量为8时，概率已经非常低了，因此将8作为上限

4. 为什么在6时退化：红黑树的空间开销比链表大，退化能减少空间开销

5. 为什么在8时转化，在6时退化：设置一个缓冲区防止频繁进行转化和退化，节省时间开销

6. 负载因子为什么是0.75

1. 是空间利用率和时间复杂度的折中权衡
2. 如果是0.5，使用一半数组就扩容，虽然减少了出现hash冲突的概率，避免了形成链表导致时间复杂度变高，但是空间利用率却降低了
3. 如果是1，数组使用完之后才扩容，虽然空间利用率变高了，但是容易出现hash冲突形成链表导致时间复杂度变高

7. hash扰动函数

1. 为了得到一个更加散列的hash值，然后再跟数组长度-1进行与运算得到index位置，为了减少hash冲突的概率
2. 8之前：将高20位和高12位右移进行异或运算，再将高7位和高4位右移进行异或运算。一共5次异或
3. 8之后：将高低16位分别进行右移异或运算。一共1次异或
4. 与运算的目的：因为hash值是正负21亿的int值，table数组明显不能存放这么多数据，因此通过hash值和数组长度-1进行与运算，消除hash值的高位

8. HashMap解决hash冲突

1. 拉链法，1.8之前，如果出现hash冲突，在table[index]下形成链表，1.8之后加入了红黑树的数据结构，当出现hash冲突时，先在table[index]下形成链表，当链表节点数到达8个并且table数组长度大于64时转化为红黑树

9. 为什么数组长度是2的n次方，扩容是2倍

1. 减少hash冲突的概率
2. 数组长度为2的n次方，数组长度-1的二进制数全部为1，然后跟hash值进行与运算计算index位置时，能够让节点在数组上的分布更均匀，减少了hash冲突的概率
3. 如果初始容量设置不是2的n次方，也会通过左移运算得到第一个比它大的2的n次方的值作为容量

10. HashMap线程不安全问题

1. 1.8之前扩容采用头插法，将旧数组的链表翻转，转移时可能出现线程切换，可能导致两个节点指向同一个位置造成死循环
2. 1.8之后采用尾插法，解决了死循环问题。但是Put存放元素时可能出现数据覆盖问题。比如线程A计算得到index位置后，发生线程切换，线程B也计算得到相同的index位置，线程B存入元素。然后线程A继续执行，直接将数据覆盖而不形成链表

11. Put机制

1. 8之前

1. 如果数组为空，新建数组
2. 如果key为null，存入table[0]
3. 如果key不为null，将key的hash值传入indexFor计算index位置，存入table[index]
   1. 如果table[index]为空，直接存入
   2. 如果table[index]有一个值，判断是否相同，否则形成链表
   3. 如果table[index]是链表，遍历判断是否相同
4. addentry头插，容量+1，判断是否需要扩容

1.8之后

1. 如果数组为空，新建数组
2. 如果key为null，存入table[0]
3. 如果key不为null，将key的hash值和数组长度-1进行与运算得到index，存入table[index]
   1. 如果table[index]为空，直接存入
   2. 如果table[index]只有一个值，判断是否相同，否则形成链表
   3. 如果table[index]是链表，遍历判断是否相同，否则尾插法存入，判断链表长度是否大于等于8，如果是，进行树化
   4. 如果table[index]是红黑树，调用putTreeVal存入
4. 容量+1，判断是否需要扩容

12. Get机制

1.8之前

1. 如果数组为空，返回null
2. 如果key为null，查询table[0]
3. 如果key不为null，将key的hash值和数组长度传入indexFor计算index，查询table[index]
   1. 如果table[index]为空，返回null
   2. 如果table[index]只有一个值，判断是否相同，相同返回value，否则返回null
   3. 如果table[index]是链表，遍历链表，判断是否有相同，有就返回value，否则返回null

1.8之后

1. 如果数组为空，返回null
2. 如果key不为null，将key的hash值和数组长度-1进行与运算得到index，查询table[index]
   1. 如果table[index]为空，返回null
   2. 如果table[index]只有一个值，判断是否相同，相同返回value，否则返回null
   3. 如果table[index]是链表，遍历链表，判断是否有相同，有就返回value，否则返回null
   4. 如果table[index]是红黑树，调用getTreeVal查询

13. Resize扩容

1.8之前

1. addEntry中判断是否需要扩容，调用resize进行扩容
2. resize先判断旧数组长度是否大于最大容量，如果是，将阈值设置为Integer.MAX_VALUE，不扩容，返回。否则就新建一个数组，长度为原来的两倍，调用transfer进行转移
3. transfer遍历旧数组，提取Entry节点，如果需要进行rehash，重新计算hash值，调用indexFor方法重新计算index，利用头插法将元素转移到新数组

1.8之后

1. 重新规划长度
   1. 如果旧数组长度大于最大容量，不扩容，返回
   2. 如果旧数组的两倍小于MAX_VALUE，扩容两倍
   3. 如果阈值大于0，将阈值设置为新数组长度
   4. 进行初始化，长度16，阈值12
2. 重新计算位置
   1. 遍历旧数组，提取Node节点
   2. 如果Node节点没有next指针，计算新下标的位置存入新数组
   3. 如果是树节点，调用split方法
   4. 如果是链表，分为超出旧数组和未超出旧数组两部分。如果是未超出旧数组的部分，存入原来的位置。如果是超出旧数组的部分，计算新下标=旧数组长度+旧下标，存入新数组

14. HashMap和HashTable

1. 数据结构
   1. HashMap：8之前数组+链表，8之后数组+链表+红黑树
   2. HashTable：数组+链表
2. 线程安全
   1. HashMap不是线程安全
   2. HashTable在put和get加synchronized实现线程安全
3. HashMap的key和value可以为null，HashTable的key和value不能为null
4. 初始容量
   1. HashMap初始容量16，扩容2倍
   2. HashTable初始容量11，扩容2倍+1

15. ConcurrentHashMap如何解决线程安全

1. 8之前通过Segment+Entry解决线程安全，Segment分段锁实现了ReentrantLock，多个Segment分段锁共同维护整个table数组，多个线程可以同时访问不同的分段锁
2. 8之后通过synchronized+CAS+Node实现，当table[index]下没有元素时使用CAS方式存入，synchronized只锁住当前Node节点，锁粒度小，效率高。并且Node节点的next指针和value值都是使用了volatile修饰的，多线程下修改是线程间可见的，因此get方法不需要加synchronized。

16. Put机制

1. 判断key和value是否为null，如果为null，返回
2. 计算key的index位置，提取Node数组对象
3. while true循环
   1. 如果数组为空，新建数组
   2. 提取Node节点
   3. 如果table[index]为空，CAS方式存入
   4. 如果正在发生扩容，提取扩容后的数组对象
   5. synchronized对Node节点上锁
      1. 如果Node节点是树节点，调用putTreeval存入key和value
      2. 如果Node节点是链表节点，遍历table[index]下的链表，判断key是否相同，相同就替换value，否则遍历到链表尾部，尾插法存入key和value。
         判断链表长度是否大于等于8，如果是，进行树化