删除|字节算法大神熬了三个通宵整理的数据结构与算法笔记（万字长文）( 三 )

，链表实现的队列称为「链式队列」。
阻塞队列：
“生产者-消费者”模型。即队列的两端分别对应生产者和消费者，队列满的时候，生产者阻塞等待；队列空的时候，消费者阻塞等待。示意图：

实现类有 ArrayBlockingQueue、LinkedBlockingQueue 等。
小结
本文主要总结了复杂度和线性表的一些概念。
复杂度
衡量代码执行速度和占用空间的标尺。包括时间复杂度和空间复杂度，用大O复杂度表示法。
线性表
常用的线性表包括数组、链表、栈、队列等。其中，可以认为数组和链表是最基本的数据结构，其他一些更复杂的数据结构通常可以基于二者实现或经过变形而来。
数据结构与算法（二）跳表
前面的数据结构笔记中分析过链表，如图所示：

由于它的内存空间非连续，因此查找某个元素时只能从头到尾遍历，时间复杂度为O(n) 。那么能不能提高链表的查找效率呢？
我们可以对链表进行改造，在链表上建立一级“索引” ，如图：

这样，在查找的时候就可以先在索引层查找，然后再根据索引去查数据（有点类似数据库的索引）。
为了进一步提高查找效率，还可以建立二级索引，如图：

以此类推，还可以建立更多层级的索引：

这种数据结构称为跳表（Skip List）。这样做查找速度更快了，但同时也会耗费更多的存储空间，它的思想其实就是空间换时间。
应用场景：Redis 的有序集合。
散列表
散列表（Hash table），又称“哈希表”或“Hash表” 。利用的是数组支持按照下标访问数据（时间复杂度为O(1)）的特性，是数组的一种扩展。示意图：

其中的key为可理解为要存入的数据的键（键-值对形式）；hash()是「散列函数」，它根据key计算得到一个非负整数，是哈希表实现的一个关键点；table为存放数据的数组。
散列表存入数据的大概流程是：将key经过散列函数计算得到一个值（保证在数组长度范围内）作为数组的下标，然后将key的值保存在数组下标对应的位置。
散列函数
散列函数设计的基本要求：
1. 散列函数计算得到的散列值是一个非负整数（数组下标从 0 开始的）；
2. 如果key1=key2 ，那么hash(key1)=hash(key2)；
3. 如果key1≠key2 ，那么hash(key1)≠hash(key2) 。
此外，散列函数的设计不能太复杂（会消耗很多计算时间），而且生成的值要尽可能随机并且均匀分布（尽量最小化散列冲突）。
例如， JDK 1.8 中 HashMap 的散列函数设计如下：
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

注：
真实情况下，不同 key 对应的散列值都不一样的散列函数几乎是不存在的。业界著名的 MD5、SHA、CRC 等哈希算法也无法避免这种散列冲突。

因此，需要其他途径来解决散列冲突的问题。
散列冲突
解决散列冲突常用的有两种方法：开放寻址法（open addressing）和链表法（chaining）。
1. 开放寻址法
核心思想：如果出现了散列冲突，就重新探测一个空闲位置将其插入。常用的探测方法有三种：
1.1 线性探测（Linear Probing）
往散列表中插入数据时，若某个数据经散列函数散列之后，存储位置已经被占用，就从当前位置开始依次往后查找，直到找到空闲位置插入。示意图：

缺点：散列表中的数据越来越多时，空闲位置越来越少，散列冲突的可能性会越来越大，线性探测的时间会越来越久。