Java开发你需要知道的数据结构

基本数据结构：数组、位图、链表、栈、队列、堆、表、哈希散列、⼆叉查找树、红⿊树、DAG、 JSON 。

基本算法：分治、递归、动态规划、贪⼼算法；排序、查找；深度优先遍历、⼴度优先遍历。 预处理思想：通过预排序、预索引、拓扑结构等构造特定的数据结构，以⽀持⾼效查找，⽐如 KMP,

RETE ，倒排索引，都运⽤了这种思想。

⾼效查找：有序查找、哈希查找。有序查找 -- 构建有序结构，⽐如有序链表、跳表、⼆叉查找树、

红⿊树，B+ 树，从⽽使⽤⼆分查找来提升查找效率，减少⽐较次数，查找时间复杂度 O(logn) ; 哈

希查找 -- 构建哈希 key-value 映射结构，解决哈希冲突，查找时间复杂度 O(1) 。哈希查找需要仔细

选择哈希函数（通过参数调优来提升性能），不⽀持 rank 和 select 操作（第 K ⼤元素），通常⽤

于 K-V 结构的存储系统； 顺序查找的查找效率与哈希接近，⽀持 rank 和 select 操作，通常⽤于有

序表、关系型数据库等。可以结合两种查找结构使⽤。⽐如 java8 的 HashMap 是哈希查找与顺序

查找的结合。

最优排序：快速排序、合并排序，时间复杂度 O(nlogn) ， 根据特殊情形可以时间换空间或空间换时

间策略获得更好性能

空间效率：压缩算法（RLE、增量编码、哈夫曼编码、Rice编码、LZ77编码、位表示、Trie前缀

树）; snappy, gzip, lz4; 图像视频压缩（MLP、CNN、GAN）。

判断 key 存在性 ： 位图，布隆过滤器，O(logn)。位图可⽤于稀疏不重复数组的排序。

动态变化的查找： ⼀致性哈希

全⽂检索： 倒排索引

最优分配问题：线性规划

前K最⼤（⼩）值： 堆算法 O(n)

字符串匹配：朴素字符串匹配 - 双重循环，简单，低频场景；有限⾃动机 - 根据模式字符串构造有

限⾃动机，再匹配⽂本，适⽤模式串的不同字符数很少的情形； KMP - 根据模式字符串及构造后缀

匹配数组（PMT，Partial Match Table，前缀集合与后缀集合的交集字符串的最⻓⻓度），避免⽆

⽤位移测试，适⽤⽣产环境。

SkipList : 有序链表，空间换时间，通过在每个节点上新增多级索引指向后继节点，实现跳跃查找，

平均 O(logN) ，最坏 O(N) 查找效率；批量顺序操作；⽐平衡树实现简单。Redis 使⽤ SkipList 实现

有序集合键。

布隆过滤器： 使⽤多个哈希函数将⼀个值映射成多个哈希值，并投影到位图上，并置为 1。如果指

定 key 通过哈希函数映射到位图上，有⼀个位为 0， 则⼀定不存在这个 key 。利⽤布隆过滤器减少

磁盘 IO 或者⽹络请求。

⼀致性哈希：环状队列 + 多哈希 + 虚拟节点。构建⼀个 serverMap = TreeMap[VirtualNodeHash,

Server] 的有序映射。对数据进⾏哈希 h 后，在 serverMap 找到第⼀个不⼩于 h 的键 S，将该数据

分布到服务器 serverMap[S] 上。哈希算法可采⽤ Fowler-Noll-Vo 哈希算法。⼀致性哈希的性质：

平衡性、单调性、分散性、负载、平滑性。

红⿊树：平衡⼆叉树。最坏情况下查找效率 O(logn)。 2-3 树的变体。指向左孩⼦的指针为红⾊的节

点标识 3-节点。左旋与右旋。

哈希计算：主要基于整数或⼆进制位来计算。如果是浮点、字符串、IP地址、对象，先将其转换成

整数型，再进⾏计算。最好能⽤到 key ⾥⾯所有相异的部分。常⻅的哈希函数有取模（模最好是素

数）、MurmurHash2 算法（源码可以在 GitHub 上搜到）。可以编写⼀个程序，来检测哈希值的分

布均匀度。如果哈希计算代价⽐较昂贵，需要做哈希值缓存。

位操作：⼀般⽤于求哈希值、⾼效实现特殊运算（⽐如 m mod 2^n == m & (n-1) ）、状态位设置、

节省空间等。

HashMap: 数组 + 链表（在必要时会变成红⿊树）。 核⼼操作是 put, resize, get。线程不安全。并

发下会发⽣数据丢失( put 更新 value 时)、死循环( resize 复制数据时)。

LinkedHashMap: 保持插⼊序的 Map 。节点采⽤双向链表。新插⼊节点或已访问节点移⾄链表尾

部。线程不安全。

TreeMap: 红⿊树实现。可顺序查找的 Map 。线程不安全。