数据结构

从底层数据结构来看，可分为三类

• 数组
• 链表
• 二叉树

从使用特性或者抽象概念来说来说可分为

• 集合
• Map
• 队列 Queue
• 栈 stack

线性表

数组

数组是一种存储单元连续，用来存储固定大小元素的线性表。java中对应的集合实现，比如ArrayList。

链表

链表又分单链表和双链表，是在物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。java中对应的集合实现，比如LinkedList。

常用的线性表类

List

1. ArrayList
   内部实现是数组
2. LinkedList
   内部实现是链表
3. Vector
   线程安全
4. CopyOnWriteArrayList
   • 支持高效率并发且是线程安全的,读操作无锁的ArrayList。
   • 它不存在扩容的概念，每次写操作都要复制一个副本，在副本的基础上修改后改变Array引用。CopyOnWriteArrayList中写操作需要大面积复制数组，所以写入性能比较差。
   • 合适读多写少的场景

Set

1. HashSet
2. ArraySet
3. LinkedHashSet

SparseArray

Map

1. HashMap
   • 哈希碰撞
   • 数组+链表
   • 当hashmap中的元素个数超过数组大小*加载因子（默认0.75）时，就会进行数组扩容
   • 扩容时，需要新建一个长度为之前数组2倍的新的数组，然后将当前的Entry数组中的元素全部传输过去，扩容后的新数组长度为之前的2倍，所以扩容相对来说是个耗资源的操作。
   • JDK1.8增加了红黑树来进行优化。当链表长度超过8时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能
   • 初始为数组大小为16，每次扩容数组长度是原来的两倍，并且数组长度一定是2的n次幂,如果通过构造方法设置大小为5，最终大小其实是 8
     因为求数组Index的算法为 hash(key) & (length-1),数组长度为2的次幂，可以保证lenght-1变为二进制所有位数为1，hashCode所有位数都能决定&运算结果，减少了Hash碰撞

     1
     2
     3
     4
      static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
      }
     

2. LinkedHashMap
3. Hashtable
   线程安全
4. TreeMap
5. ConcurrentHashMap
   • 线程安全
   • 在新增节点后，检测到链表长度大于8时，会将链表转换为红黑树，增加查找效率，但在这之前，会检查数组长度，若小于64，则会优先做扩容操作
   • 运用各类CAS操作，即保证了线程安全，又提高了并发性能。
   • JDK 1.7 版本，是通过每次只锁链表，而不是整个HashMap，解决并发问题,因为HashMap的操作实际上是 对链表的操作
   • 从JDK1.7版本的ReentrantLock+Segment+HashEntry，到JDK1.8版本中synchronized+CAS+HashEntry+红黑树
   • 1.7 和 1.8 版本区别

栈

栈，是一种运算受限的线性表，重点掌握其后进先出的特点。表的末端叫栈顶，基本操作有push(进栈)和pop(出栈)。java中stack就是简单的栈实现。

队列

队列也是一种操作受限制的线性表，重点掌握其先进先出的特点。表的前端只允许进行删除操作，表的后端进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。java中很多Queue的实现，消息中间件的队列本质也是基于此的。

树

1. 二叉搜索树
2. 平衡二叉树
3. 红黑树

图

面试题型

栈

堆

贪心算法

排序

• 冒泡排序
  
• 选择排序
  
• 插入排序
  
• 归并排序
  
• 快速排序
  

  位运算

  树

  递归

  链表

  双指针

  二分查找

  动态规划

  回溯算法

---

• Previous
  多线程
• Next
  混淆

---