集合类

你知道的数据结构有哪些
线性结构
● 动态数组：相对于普通数组可以扩容
○ java 中 ArrayList 就属于动态数组
○ 数组的特点是其中元素是连续存储的
● 链表：由多个节点链在一起
○ java 中的 LinkedList 就属于链表
○ 链表的特点是其中元素是不连续存储的，每次需要根据当前节点，才能找到相邻节点
● 栈：符合 First In Last Out（先进后出）规则
○ java 中的 LinkedList 可以充当栈
○ 它的 push 方法向栈顶添加元素
○ 它的 pop 方法从栈顶移除元素
○ 它的 peek 方法从栈顶获取元素（不移除）
● 队列：符合 First In First Out（先进先出）规则
○ java 中 LinkedList 也可以充当队列
○ 它的 offer 方法用来向队列尾部添加元素（入队）
○ 它的 poll 方法用来从队列头部移除元素（出队）
非线性结构
● 优先级队列：在队列基础上增加了优先级，队列会根据优先级调整元素顺序，保证优先级高的元素先出队
○ java 中 PriorityQueue 可以作为优先级队列
○ 它底层用大顶堆或小顶堆来实现
○ 它适用于实现排行榜、任务调度等编码
○ 它特别适合于流式数据的处理，利用它能够大大节省内存
● Hash 表（哈希表，也叫散列表）：由多对 key - value 组成，会根据 key 的 hash 码把它们分散存储在数组当中，其中 key 的 hash 码与数组索引相对应
○ java 中的 HashMap，Hashtable 都属于哈希表
○ 它特别适用于实现数据的快速查找
● 红黑树：可以自平衡的二叉查找树，相对于线性结构来说，拥有更好的性能
○ java 中的 TreeMap 属于红黑树
● 跳表：多级链表结构，也能达到与红黑树同级的性能，且实现更为简单
○ java 中的 ConcurrentSkipListMap 用跳表结构实现
○ redis 中的 SortedSet 也是用跳表实现
● B+ 树：可以自平衡的 N 叉查找树
○ 关系型数据库的索引常用 B+ 树实现