二分查找

思想说明

1. 针对有序数据集合的查找算法，依赖于顺序表结构，即数组
2. 每次通过和区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或区间被缩小至 0

分析

1. 时间复杂度 O（log(n)）
2. 代码实操注意事项
   • 循环退出条件 low <= high
   • mid 的取值，如果 low 和 high 比较大的话，两者之和可能会溢出，改进为：low + ( high - low ) / 2，更进一步，将性能优化到极致 low + (( high - low) » 1)
   • low 和 high 的更新，low = mid + 1，high = mid - 1
   • 可以使用循环和递归两种实现方式

应用场景

1. 只能应用在数据是通过顺序表来存储的数据结构上
2. 只能应用在有序数据，且插入、删除操作不频繁，一次排序多次查找的场景
3. 数据量的要求
   • 数据量太小不适合二分查找，直接顺序遍历就足够，但如果数据之间的比较操作非常耗时，使用二分查找尽可能地减少比较次数，例如 数组中存储的都是长度超过 300 的字符串
   • 数据量太大也不适合二分查找，二分查找的底层需要依赖数组这种数据结构，而数组为了支持随机访问的特性，要求内存空间连续
4. 非常适合用在“近似”查找问题
5. 凡是用二分查找能解决的，绝大部分更倾向于用散列表或者二叉树查找

常见的二分查找变形问题

• 查找第一个值等于给定值的元素
  1. 当 a[mid] > value，high = mid - 1
  2. 当 a[mid] < value，low = mid + 1
  3. 当 a[mid] == value
     • 如果 mid == 0，或者 a[mid - 1] != value，则 mid 就是第一个等于给定值的元素
     • 如果不是，则继续 high = mid - 1，要找的元素一定在 [ low，mid - 1] 中
• 查找最后一个值等于给定值的元素
  1. 当 a[mid] > value，high = mid - 1
  2. 当 a[mid] < value，low = mid + 1
  3. 当 a[mid] == value
     • 如果 mid == n - 1，或者 a[mid + 1] != value，则 mid 就是最后一个值等于给定值的元素
     • 如果不是，则继续 low = mid + 1，要找的元素一定在 [ mid + 1， high ] 中
• 查找第一个大于等于给定值的元素
  1. 当 a[mid] >= value
     • 如果 mid == 0，或者 a[mid + 1] < value，则 mid 就是第一个大于等于给定值的元素
     • 如果不是，则继续 high = mid - 1，要找的元素一定在 [ low，mid - 1 ] 中
  2. 当 a[mid] < value，low = mid + 1
• 查找最后一个小于等于给定值的元素
  1. 当 a[mid] <= value
     • 如果 mid == n - 1，或者 a[mid + 1] > value，则 mid 就是最后一个小于等于给定值的元素
     • 如果不是，则继续 low = mid + 1，要找的元素一定在 [ mid + 1，high ] 中
  2. 当 a[mid] > value，high = mid - 1

跳表

思想说明

1. 将原始有序链表每 n 个结点就提取一个结点到上层索引，添加多层索引
2. 链表 ➕ 多级索引的结构，就是跳表

分析

1. 查找、插入、删除操作，时间复杂度均为 O（log(n)）
   • 查找时间复杂度
     • 假设每 m 个结点抽出一个结点作为上一级索引的结点
     • 第一级索引的结点个数大约为 n / m，第二级索引的结点个数 n / m，第 k 级索引的结点个数是 n / （），
     • 假设 h 级索引，最高级索引有 m 个结点， n / （） = m，，整个跳表的高度就是
     • 时间复杂度 = 每层需要遍历的结点数 x 跳表的高度 = O（m * ） = O（log(n)）
2. 空间复杂度 O（n）
   • 假设每 m 个结点抽出一个结点作为上一级索引的结点
   • 索引结点的总和就是 n / m + n / + n / + ….+ + m
   • 在实际的软件开发中，原始链表中存储的有可能是很大的对象，而索引结点只需要存储关键值和几个指针，并不需要存储对象，所以当对象比索引结点大很多时，索引占用的额外空间就可以忽略
3. 索引动态更新
   • 当不停地往跳表中插入数据是，如果不更新索引，就有可能出现某 2 个索引结点之间数据非常多的情况
   • 通过一个随机函数，来决定将这个结点插入到哪几级索引中，譬如随机函数生成了值 k，就将这个结点添加到 第 1 级至第 k 级 这 k 级索引中

应用场景

1. Redis 中的有序集合，使用跳表、散列表来实现
   • 使得【按照区间查找数据】功能，可以在时间复杂度 O（log(n)）定位区间的起点，然后在原始链表中顺序往后遍历就可以了
   • 跳表更为灵活，可以通过改变索引构建策略，有效平衡执行效率和内存消耗
   • 跳表的代码实现更加容易

散列表

思想说明

1. 散列表是一种数组的扩展，用的是数组支持按照下表随机访问数据的特性
2. 关键字 / 键 key
   • 标识数据
3. 散列函数（Hash 函数）
   • 将数据转化为数组下标的映射方法
4. 散列值
   • 由散列函数计算得到的值
5. 装载因子（load factor）
   • 表示空位的多少
   • 散列表的装载因子 = 填入表中的元素个数 / 散列表的长度
   • 装载因子越大，说明空闲位置越少，冲突越多

散列函数设计的基本要求

1. 散列函数计算得到的散列值是一个非负整数
2. 如果 key1 = key2，那么 hash( key1 ) == hash( key2 )
3. 如果 key1 ≠ key2，那么 hash( key1 ) ≠ hash( key2 )
   • 在真实情况下，要想找到一个不同的 key 对应的散列值都不一样的散列函数，几乎是不可能的，存在散列冲突
   • 由于数组的存储空间有限，也会加大散列冲突的概率

常见的解决散列冲突的办法

• 开放寻址法

  • 线性探测（Linear Probing）

    1. 插入：如果出现了散列冲突，重新探测一个空闲位置，将其插入
    2. 查找：通过散列函数求出要查找元素的键值对应的散列值，比较数组中下标为散列值的元素和要查找的元素，如果相等，则说明找到了，否则就顺序往后依次查找，如果遍历到数组中的空闲位置还没有找到，则说明查找的元素不存在散列表中
    3. 删除：将删除的元素标记为 deleted，当线性探测查找时，遇到标记为 deleted 的空间，并不是停下来，而是继续往下探测
    4. 最好时间复杂度 O（1），最坏时间复杂度 O（n）

  • 二次探测（Quadratic Probing）

    1. 类似线性探测，线性探测每次探测的步长是 1，hash( key ) + 0，hash( key ) + 1，，hash( key ) + 2
    2. 二次探测每次探测的步长是原来的平方，hash( key ) + 0，hash( key ) + 1^2，hash( key ) + 2^2

  • 双重散列（Double Hashing）

    1. 使用一组散列函数，先用第一个散列函数，如果计算得到的存储位置已经被占用，再用第二个散列函数，依此类推，直到找到空闲的存储位置
• 链表法
  1. 在散列表中，每个“桶（bucket）”或者“槽（slot）”会对应一条链表，所有散列值相同的元素放在相同槽位对应的链表中
  2. 插入：通过散列函数计算出对应的散列槽位，将其插入到对应链表中，时间复杂度为 O（1）
  3. 查找、删除：通过散列函数计算得出对应的散列槽位，遍历链表查找或删除，时间复杂度跟链表的长度 k 成正比，O（k），对于散列比较均匀的散列函数来说，k = n / m，n 为散列表中数据的个数，m 为散列表中“槽”的个数

设计工业级散列表

• 设计要求
  • 避免在散列冲突的情况下，性能急剧下降
  • 能抵抗散列碰撞攻击
• 散列函数的设计
  • 散列函数的设计不能太复杂
  • 散列函数生成的值要尽可能随机并且均匀分布
  • 需要综合考虑各种因素，如 关键字的长度、特点、分布、散列表的大小等
  • 散列函数的常见设计：数据分析法、直接寻址法、平方取中法、折叠法、随机数法 等
• 装载因子，动态扩容策略
  1. 装载因子越大，说明散列表中元素越多，空闲位置越少，散列冲突的概率越大
  2. 对于没有频繁插入和删除的静态数据集合，根据数据的特点、分布等，很容易设计出极少冲突的散列函数
  3. 对于动态散列表，数据集合是频繁变动的，当装载因子过大时，可以进行动态扩容，重新申请一个更大的散列表，将数据搬移到新散列表中
     • 插入操作，最好时间复杂为 O（1），最坏时间复杂度为 O（n），均摊时间复杂度为 O（1）
     • 如果对空间消耗比较敏感，可以在装载因子小于某个值后，启动动态缩容
     • 如果对效率比较敏感，可以容忍多消耗一点内存空间，就不需要缩容
     • 装载因子阈值的设置要权衡时间、空间复杂度
       • 内存空间不紧张，对执行效率要就很高，可以降低装载因子的阈值
       • 内存空间紧张，对执行效率要求不高，可以增加装载因子的阈值，甚至可以大于 1
  4. 如何避免低效地扩容
     • 当极个别非常慢的插入操作（扩容并搬移数据）不能被容忍时，“一次性”扩容机制不能满足要求
     • 可以将扩容操作穿插在插入操作的过程中，分批完成
     • 当装载因子达到阈值时，只申请新空间，并不将老的数据搬移至新散列表中
     • 当有新数据要插入时，将新数据插入新散列表中，并且从老的散列表中拿出一个数据放入到新散列表中
     • 对于查询操作，为了兼容新、老散列表中的数据，先从新散列表中查找，如果没有找到，再去老的散列表中查找
• 如何选择冲突解决方法
  • 开放寻址法
    1. 优点
       • 散列表中的数据都存储在数组中，可以有效地利用 CPU 缓存加快查询速度
       • 序列化简单
    2. 缺点
       • 删除数据时，需要特殊标记已经删除掉的数据
       • 所有的数据都存储在一个数组中，冲突的代价更高
       • 在使用开放寻址法解决冲突的散列表中，装载因子的上限不能太大，更浪费内存空间
    3. 适合场景
       • 数据量比较小、装载因子小
       • 例如 Java 中的 ThreadLocalMap
  • 链表法
    1. 优点
       • 对大装载因子的容忍度更高
       • 可以对链表法中的链表改造为其他更为高效的动态数据结构，如 跳表、红黑树，即便出现散列冲突，在极端情况下，所有的数据都散列到一个桶内，最终退化成的散列表的查询时间为 O（logn），有效地避免了散列碰撞攻击
    2. 缺点
       • 链表需要存储指针，对于比较小的对象的存储，比较消耗内存
       • 链表中的节点是零散分布在内存中的，不是连续的，对 CPU 缓存不友好，如果是存储大对象的话，指针的内存消耗可以忽略不计
    3. 适用场景
       • 存储大对象、大数据量，更为灵活，可以支持更多的优化策略

工业级散列表 Java HashMap 分析

• 初始大小
  • 默认是 16，如果事先知道数据量的大概范围，可以通过修改默认初始值，减少动态扩容的次数，提高 HashMap 的性能
• 装载因子和动态扩容
  • 最大装载因子默认是 0.75，当 HashMap 中元素个数超过 0.75 x capacity，就会启动扩容，每次扩容都会扩容原来的两倍
• 散列冲突解决方法
  • 采用链表法来解决冲突
  • 当链表长度太长（默认超过 8）时，链表就转换成红黑树
• 散列函数
  • 简单高效、分布均匀
• 特性
  • 支持快速的查询、插入、删除操作
  • 内存占用合理，不能浪费过多的内存空间
  • 性能稳定，极端情况下，散列表的性能也不会退化到无法接受的情况

散列表和链表的组合使用

• LRU 缓存淘汰算法（Least Recently Used）
  1. 借助散列表，将 LRU 缓存淘汰算法的时间复杂度降低为 O（1）
  2. 使用双向链表存储数据，链表中每个节点处理存储数据 data、前驱指针 prev、后继指针 next、散列表的拉链指针 hnext，前驱和后继指针是为了将节点串在双向链表中，hnext 指针是为了将结点串在散列表的拉链中
  3. 查找数据：在散列表中查找，当找到数据后，将它移动到双向链表的尾部
  4. 删除数据：查找数据并将结点删除
  5. 添加数据：先看下数据是否存在缓存中，如果已经存在，则将它移动到双向链表的尾部，如果不在其中，查看缓存是否已经满了，如果满了，则将双向链表的头结点删除，再将数据放到链表的尾部，如果没有满，则直接将数据放到链表的尾部
• Redis 有序集合
  1. 按照分值将成员对象组织成跳表的结构
  2. 按照键值构建一个散列表
• Java LinkedHashMap
  1. 通过双向链表和散列表两种数据结构组合实现
  2. LinkedHashMap 中的 “Linked”实际上指的是双向链表，并非用链表法解决散列冲突
• 散列表和链表经常一起使用的原因
  1. 散列表的数据结构支持非常高效的插入、删除、查找操作，但是无法支持按照某种顺序快速地遍历数据
  2. 为了能够按照顺序遍历散列表中的数据时，将散列表和链表（或者跳表）结合在一起使用

哈希算法

1. 将任意长度的二进制值串映射为固定长度的二进制值串，其中映射的规则就是哈希算法，通过原始数据映射之后得到的二进制值串就是哈希值
2. 哈希算法的要求
   1. 从哈希值不能反向推导出原始数据，即单向
   2. 对输入数据非常敏感，哪怕原始数据的改动微小，最后得到的哈希值也大不相同
   3. 散列冲突的概率要很小
   4. 哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值

哈希算法的应用

• 安全加密
  1. MD5（Message-Digest Algorithm，MD5 信息摘要算法）
  2. SHA（Secure Hash Algorithm，安全散列算法）
  3. DES（Data Encryption Standard，数据加密标准）
  4. AES（Advanced Encryption Standard，高级加密标准）
  5. 着重注意点
     • 单向推导，不能根据哈希值反向推导出原始数据
     • 散列冲突的概率很小
• 唯一标识
  • 图片的信息摘要，将图片的二进制码串的开头取一百个字节，中间一百个字节，结尾再取一百个字节，将这三百个字节通过哈希算法（例如 MD5），得到一个哈希字符串，用它作为图片的唯一标识
• 数据校验
  • 下载的文件块校验，对文件块分别取哈希值，并且保存在种子文件中。当文件块下载完成之后，可以通过相同的哈希算法，对下载好的文件块逐一求哈希值，跟种子文件中保存的哈希值对比
• 散列函数
  1. 散列函数更注重数据能否均匀地散列在各个槽中和散列函数执行的效率、性能
  2. 对于散列冲突，使用开放寻址法或者链表法解决
• 负载均衡
  • 会话粘滞的负载均衡算法
    1. 在同一个客户端上，再一次会话中的所有请求都路由到同一个服务器上
    2. 简单粗暴法
       • 维护一张映射关系表，客户端 IP 地址或者会话 ID 与服务器编号的映射关系
       • 弊端
         • 客户端很多，映射表会很大，浪费内存空间
         • 客户端上下线、服务器扩容缩容都会导致映射失效，维护映射表的成本会增大
    3. 哈希算法
       • 对客户端 IP 地址或者会话 ID 计算哈希值
       • 将取得的哈希值与服务器列表的大小进行取模运算，得到应该被路由到的服务器编号
       • 将同一个 IP 过来的所有请求，都路由到同一个后端服务器上
• 数据分片
  • 如何统计“搜索关键字”
    1. 难点
       • 搜索日志很大，没办法放在一台机器的内存中
       • 如果只用一台机器处理，处理时间会很长
    2. 解决方法（MapReduce）
       • 对数据进行分片，采用 n 台机器处理
       • 从搜索日志中依次读出每个搜索关键词，通过哈希函数计算哈希值，对 n 取模，最终得到的值，就是被分配到的机器编号
       • 哈希值相同的搜索关键词被分配到了同一台机器上
  • 如何快速判断图片是否在图库中
    1. 难点
       • 图片的数量达到一定规模后，没办法在单台机器上构建散列表
    2. 解决方法
       • 对数据进行分片，采用 n 台机器处理，每台机器只维护某部分图片对应的散列表
       • 从图库中读取一个图片，计算唯一标识，与 n 求余取模，得到对应要分配的机器编号，然后将图片的唯一标识和图片路径发送到对应的机器上构建散列表
       • 当要判断图片是否在图库中时，首先通过哈希算法，计算图片的唯一标识，然后与 n 求余取模，到对应机器上构建的散列表中查找
• 分布式存储
  1. 使用数据分片的思想，即通过哈希算法对数据取哈希值，然后对机器个数取模，这个最终值就是应该存储的缓存机器编号
  2. 考虑到数据会持续增多，当需要扩容时，需要一种方法，在新加入一台机器后，不需要做大量的数据搬移
  3. 使用一致性哈希算，n 台机器，数据的哈希值范围是 [0, MAX]。将整个范围划分为 m 个小区间，m 远大于 n，每个机器负责 m / n 个小区间。这样当有新机器加入时，将某几个小区间的数据，从原来的机器上搬移到新的机器中。
  4. 参考资料
     • https://en.wikipedia.org/wiki/Consistent_hashing
     • http://www.zsythink.net/archives/1182