《数据结构与算法之美》基础篇笔记（三）

2020-10-11

摘要：极客时间《数据结构与算法之美》基础篇笔记，二分查找、跳表、散列表、哈希算法

二分查找

二分查找针对的是一个有序集合，每次都通过跟区间的中间元素对比，将查找区间缩小为原来的一半，直到查找到目标元素或区间缩小到 0。
假设数据量为 n，每次查找后数据量缩小为之前的 1/2，每次缩小操作只涉及两个数据的大小比较，经过 k 次查询后，时间复杂度为 O(k)，区间数据量为 1/2^k。当区间数据量为 1 的时候 n/2^k=1，k=log2(n)，则其时间复杂度为 O(logn)

简单情况

有序数组中不存在重复元素

function biaryFind(sortedArr, target) {
  if (sortedArr.length === 0) return -1
  // 获取起止下标
  let low = 0
  let high = sortedArr.length - 1
  while (low <= high) {
    // 获取中间索引
    const mid = Math.floor((low + high) / 2)
    if (target === sortedArr[mid]) {
      return mid
    } else if (target < sortedArr[mid]) {
      high = mid - 1
    } else {
      low = mid + 1
    }
  }
  return -1
}

易错的三个地方：
1、循环退出条件：low<=high
2、mid 的取值。low+high 可能会溢出，可以换 low+Math.floor((high-low)/2) 或 low+((high-low)>>1)，注意优先级
3、low 与 high 的更新。如果直接写成 low=mid 或者 high=mid，有可能会发生死循环
二分查找除了使用循环来实现，还可以使用递归实现

function bsearch(sortedArr, target) {
  return bsearchInternally(sortedArr, 0, sortedArr.length - 1, target)
}
function bsearchInternally(sortedArr, low, high, target) {
  const mid = Math.floor((low + high) / 2)
  if (sortedArr[mid] == target) {
    return mid;
  } else if (sortedArr[mid] < target) {
    return bsearchInternally(sortedArr, mid + 1, high, target);
  } else {
    return bsearchInternally(sortedArr, low, mid - 1, target);
  }
}

二分查找应用场景的局限性

1、二分查找依赖的是顺序表结构，简单点说就是数组。它主要是需要按照下标随机访问元素，因而链表是不可以的
2、二分查找针对的是有序数据。二分查找前，数据必须是排好序的。因而它只能用在插入、删除操作不频繁的情况下使用，否则每次都要排序，这样排序成本会很高
3、数据量太小不适合二分查找。数据量很小的情况下，直接遍历即可。但如果每次比较都很耗时，还是推荐使用二分查找，比如比较的元素都是长度超过 300 的字符串
4、数据量太大也不适合二分查找。数组为了支持随机访问的特性，对内存的要求比较苛刻，要求内存空间必须是“连续”的
应用：
1、有 1000 万个整数数据，每个数据占 8 个字节，在内存只有 100MB 的情况下，如何快速判断某个整数是否出现在这 1000 万数据中？使用二分法可以快速查找到，而且二分法散列表、二叉树也可以解决，但使用的内存绝对不止 100MB
2、编程实现“求一个数的平方根”并精确到小数点后 6 位。

function sqrt(target, inf = 1e-6) {
  if (target < 0) return NaN
  let low = 0;
  let high = target
  if (target < 1) {
    high = 1;
  }
  let mid = low + ((high - low) >> 2)
  while (high - low > inf) {
    mid = low + ((high - low) >> 2)
    if (mid * mid == target) {
      break
    } else if (mid * mid > target) {
      high = mid;
    } else {
      low = mid;
    }
  }
  return mid;
}

二分查找变体

1、查找第一个值等于给定值的元素

function biaryFindFirst(sortedArr, target) {
  if (sortedArr.length === 0) return -1
  let low = 0
  let high = sortedArr.length - 1
  while (low <= high) {
    const mid = low + ((high - low) >> 1)
    if (target < sortedArr[mid]) {
      high = mid - 1
    } else if (target > sortedArr[mid]) {
      low = mid + 1
    } else {
      if (mid === 0 || sortedArr[mid - 1] < target) return mid
      high = mid - 1
    }
  }
  return -1
}

2、查找最后一个值等于给定值的元素

function biaryFindLast(sortedArr, target) {
  if (sortedArr.length === 0) return -1
  let low = 0
  let high = sortedArr.length - 1
  while (low <= high) {
    const mid = low + ((high - low) >> 1)
    if (target < sortedArr[mid]) {
      high = mid - 1
    } else if (target > sortedArr[mid]) {
      low = mid + 1
    } else {
      if (mid === sortedArr.length - 1 || sortedArr[mid + 1] > target) return mid
      low = mid + 1
    }1
    }
  }
  return -1
}

3、查找第一个大于等于给定值的元素

function biaryFindFistBig(sortedArr, target) {
  if (sortedArr.length === 0) return -1
  let low = 0
  let high = sortedArr.length - 1
  while (low <= high) {
    const mid = low + ((high - low) >> 1)
    if (target <= sortedArr[mid]) {
      if (mid === 0 || sortedArr[mid - 1] < target) return mid
      high = mid - 1
    } else {
      low = mid + 1
    }
  }
  return -1
}

4、查找最后一个小于等于给定值的元素

function biaryFindFistBig(sortedArr, target) {
  if (sortedArr.length === 0) return -1
  let low = 0
  let high = sortedArr.length - 1
  while (low <= high) {
    const mid = low + ((high - low) >> 1)
    if (target < sortedArr[mid]) {
      high = mid - 1;
    } else {
      if (mid == sortedArr.length || sortedArr[mid + 1] > target) return mid
      low = mid + 1
    }
  }
  return -1
}

应用：
1、如何快速定位出一个 IP 地址的归属地？将 IP 地址转化为 32 位的整型数，然后进行排序，将问题转化为第 4 中变形问题。通过二分法找到起始 IP 小于等于给定 IP 的区间，判断 IP 是否在该区间即可找到对应归属地
2、对于循环有序数组，实现求“值等于给定值”的二分查找算法。循环有序数组性质：将一个循环有序数组一分为二，一定得到一个有序数组和另一个循环有序数组，如果首元素小于 mid，说明前半部分是有序的，后半部分是循环有序数组；
如果首元素大于 mid，说明后半部分是有序的，前半部分是循环有序的数组；如果目标元素在有序数组范围中，使用二分查找；如果目标元素在循环有序数组中，设定数组边界后，使用以上方法继续查找。时间复杂度为 O(logN)

function search(array, target) {
  let low = 0;
  let high = array.length - 1;
  while (low <= high) {
    let mid = low + ((high - low) >> 1);
    if (target == array[mid]) {
      return mid;
    } else if (array[low] < array[mid]) { // 左侧为有序数组
      if (target == array[low]) {
        return low
      } else if (target > array[low] && target < array[mid]) { // 如果在左侧，使用二分查找
        high = mid - 1
      } else {
        low = mid + 1
      }
    } else { // 右侧为有序数组
      if (target == array[high]) {
        return high
      } else if (target > array[mid] && target < array[high]) { // 如果在右侧，使用二分查找
        low = mid + 1
      } else {
        high = mid - 1
      }
    }
  }
  return -1
}

跳表

链表加多级索引的结构就是跳表，它是一种各方面性能都很优秀的动态数据结构，可以支持快速查找、插入、删除操作。Redis 中的有序集合就是由跳表和散列表实现。
如果每两个结点抽出一个结点作为上一级索引的结点，那么第一级索引有 n/2 个，第二级索引有 n/4 个，第三级索引有 n/8 个，第 k 级索引有 n/2^k 个。假设最后一级有 2 个结点，那么 n/2^k=2，得到 k=log2(n)-1。如果包含原始链表这一层，这个链表的的层级有 k=log2(n)。如果在跳表中查询数据时，每一级要遍历 m 个结点，那么查询的时间复杂度为 O(mlogn)。像前面每两个节点抽出一个索引节点的话，m=3(假设在 k 级索引中，查找的数据 x 大于 y 而小于 z，那么在 k-1 级索引中，x 还要遍历 3 个节点：y、z、y 与 z 的中间值)，即每次遍历 3 个节点，时间复杂度为 O(logn)。索引的节点总和是 n/2+n/4+n/8+…+8+4+2=n-2，空间复杂度为 O(n)。以空间换时间，建立很多级索引提升查询效率。
如果每三个结点或五个结点抽出一个结点到上级索引，共需要 n/3+n/9+n/27+…+9+3+1 个结点，这是一个等比数列。根据等比数列求和公式Sn=(an*q-a1)/(q-1) (q≠1)，当 q=3、a1=1、an=n/3 时，Sn=(n-1)/2，空间复杂度仍为 O(n)，但索引结点减少了一半左右。实际上，开发中不必太在意索引占用的额外空间：链表中的数据可能是很大的对象，而索引结点只存储关键值和几个指针，索引所占的额外空间可以忽略。
跳表查询的时间复杂度为 O(logn)，插入和删除的时间复杂度也为 O(logn)，因为单纯的插入和删除操作时间复杂度为 O(1)，时间都用来查找要插入或删除的位置。
当跳表某两个结点之前的数据插入过多时，其查找耗时就会向普通单链表退化，性能下降。当结点增多时，通过随机函数增加相应的索引结点，避免复杂度退化。这个随机函数决定将新添加的结点插入到哪一级的索引中

// 最大层级
const MAX_LEVEL = 16;
// 结点辅助类
class Node {
  constructor({
    data = -1,
    maxLevel = 0,
    refer = new Array(MAX_LEVEL)
  } = {}) {
    this.data = data; // 结点存储的数据
    this.maxLevel = maxLevel; // 索引结点最大层级
    this.refer = refer  // 存储每层索引后面一个结点的信息
  }
}
// 假设有一节点
// node = {
//   data: 1,
//   maxLevel: 5, 
//   refer: [nodeObj1, nodeObj2, nodeObj3, nodeObj4, nodeObj5, empty * 11
// }
// 表示该节点数据值为 1
// 包含原始链表这一层级的的最大层级为 5，即抽出的索引有 4 层
// 第一层原始链表中该节点后面的数据是 nodeObj1，第二层抽出索引后面的数据是 nodeObj2，依次类推，超出最大层级的后面都为 undefined

// 跳表类
class SkipList {
  constructor() {
    this.head = new Node(); // head 结点
    this.levelCount = 1; // 整个跳表的最大层级
  }
  // 层级随机函数
  randomLevel() {
    let level = 1;
    for (let i = 1; i < MAX_LEVEL; i++) {
      if (Math.random() < 0.5) { // 这个判断使每层抽出的结点索引大约为上一层的一半
        level++;
      }
    }
    return level;
  }
  // 查找
  find(value) {
    if (!value) { return null }
    let p = this.head;
    for (let i = this.levelCount - 1; i >= 0; i--) { // 从最高层索引链开始向下遍历，两个循环遍历到最后可以找到原始链中最后一个小于目标数据的结点
      while (p.refer[i] && p.refer[i].data < value) { // 找到该层级最后一个小于目标数据的结点
        p = p.refer[i];
      }
    }
    if (p.refer[0] && p.refer[0].data === value) { // 如果最后一个小于目标数据的结点的下一个结点数据等于要查找的值，说明找到了，否则，链表中没有该数据
      return p.refer[0];
    }
    return null;
  }
  // 添加
  insert(value) {
    const level = this.randomLevel(); // 确定索引加到哪一层级
    const newNode = new Node(); // 创建一个新结点
    newNode.data = value; // 设置新结点的值
    newNode.maxLevel = level; // 设置新节点索引的层级
    const update = new Array(level); // 创建一个长度为随机数层级的数组，用以保存每一层级链表要插入位置的前一个结点（最后一个小于目标数据的结点）
    let p = this.head;
    for (let i = level - 1; i >= 0; i--) { // 遍历找到各层级最后一个小于目标数据的结点
      while (p.refer[i] && p.refer[i].data < value) {
        p = p.refer[i];
      }
      update[i] = p; // 存储新节点在各层级的前一个结点
    }
    for (let i = 0; i < level; i++) { // 遍历将目标结点插入到各层级的链表中，注意链表插入结点时的操作顺序
      newNode.refer[i] = update[i].refer[i];
      update[i].refer[i] = newNode;
    }
    if (this.levelCount < level) { // 更新整个链表的最大层级
      this.levelCount = level;
    }
  }
  // 删除
  remove(value) {
    if (!value) { return null }
    let p = this.head;
    const update = new Array(this.levelCount);
    for (let i = this.levelCount - 1; i >= 0; i--) { // 同上
      while (p.refer[i] && p.refer[i].data < value) {
        p = p.refer[i];
      }
      update[i] = p;
    }
    if (p.refer[0] && p.refer[0].data === value) { // 如果原始链的下一个结点的值等于目标数据，就说明下一个结点就是要删除的结点
      const _node = p.refer[0]; // 要删除的目标结点
      for (let i = 0; i <= _node.maxLevel - 1; i++) { // 各层级链表删除目标节点
        if (update[i].refer[i] && update[i].refer[i].data === value) {
          update[i].refer[i] = update[i].refer[i].refer[i]; // 直接将索引指向目标结点的下一个结点
        }
      }
      return _node;
    }
    return null;
  }
  // 辅助方法 打印所有数据
  printAll() {
    let p = this.head;
    while (p.refer[0]) { // 遍历原始链打印所有数据
      console.log(p.refer[0].data)
      p = p.refer[0];
    }
  }
}

Redis 中的有序集合是通过跳表和散列表实现的，有序集合的核心操作有：
1、插入一个数据
2、删除一个数据
3、查找一个数据
4、按照区间查找数据
5、迭代输出有序序列
其中的 1、2、3、5 操作红黑树也可以完成，且与跳表的时间复杂度相同，但红黑树操作 4 的效率没有跳表高。很多编程语言的 Map 类型由红黑树来实现。跳表需要自己实现，但要比红黑树简单的多，为了代码更简单已读，倾向于使用跳表

散列表

散列表用的就是数组支持按照下标随机访问，时间复杂度是 O(1) 的特性。
散列思想：被存储数据的编号与被存储数据的数组之间有映射关系。其中的编号叫做“键”或者“关键字”，数组叫做散列表，映射关系被称作散列函数（或“Hash 函数”“哈希函数”），散列函数计算的值叫做散列值（或“Hash 值”“哈希值”）。散列表的两个核心问题是设计散列函数和解决散列冲突

// 简单的散列表
class HashTable {
  constructor() {
    this.table = [];
  }
  // 散列函数
  hashCode(key) {
    let hash = 0;
    // 从 ASCII 表中查到的 ASCII 值加到 hash 中
    for (let i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i);
    }
    // 为了得到比较小的数值，我们会用hash和任意数除余
    return hash % 37;
  }
  // 向散列表增加一个新的项
  add(key, value) {
    let position = this.hashCode(key);
    console.log(position + '-' + key);
    this.table[position] = value;
  }
  // 根据键从散列表删除值
  remove(key) {
    this.table[this.hashCode(key)] = undefined;
  }
  // 返回根据键值检索到的特定的值
  get(key) {
    console.log(this.table[this.hashCode(key)])
    return this.table[this.hashCode(key)
  }
  print() {
    for (let i = 0; i < this.table.length; ++i) {
      if (this.table[i] !== undefined) {
        console.log(i + ':' + this.table[i]);
      }
    }
  }
}

在 js 中，通常是直接将 Object、Map 或 Set 来当散列表用

散列函数

散列函数设计的基本要求：
1、散列函数计算得到的散列值是一个非负整数，因为数组下标是从 0 开始的
2、如果 key1 = key2，那么 hash(key1) == hash(key2)，键相同得到的散列值也要相同
3、如果 key1 ≠ key2，那么 hash(key1) ≠ hash(key2)，但基本做不到，因为散列表中槽的个数一般都小于要放入的数据的个数，根据鸽巢原理，总会有冲突的情况

散列冲突

解决散列冲突的常用的方法：
一、开放寻址法。核心思想：如果出现了散列冲突，我们就重新探测一个空闲位置，将其插入。常用的有线性探测、二次探测和双重散列。
1、线性探测。散列表插入数据时经过散列函数得到的位置已经被占用，那么就从当前位置开始依次向后查找，直到找到空闲位置。查找数据的时候，也是从散列函数计算得到的位置开始比较数组的元素和要查找的元素，如果相等，说明就是要查找的元素；否则就依次遍历数组查找，如果遍历到数组的空闲位置仍没找到，说明要查找的元素不在散列表中。如果是删除元素，位置元素需要添加 deleted 标识，避免后面删除元素留下的空闲位置影响到查找算法
2、二次探测。它跟线性探测很像，线性探测每次的步长为 1，即每次下标序列是 hash(key)+0，hash(key)+1，hash(key)+2……而二次探测的步长则为原来的二次方：hash(key)+0，hash(key)+1^2，hash(key)+2^2……
3、双重散列。使用一组散列函数，如果第一个散列函数 hash1(key) 计算得到的位置已经被占用，就使用第二个散列函数 hash2(key)，依次类推，直到找到空闲位置
无论哪种探测方法，当散列表中的空闲位置不多时，散列冲突的概率就会大大增加。装载因子用以表示散列表中空余位置的多少：散列表的装载因子=填入表中的元素个数/散列表的长度，即装载因子越大，空余位置越少，冲突越多，性能越差
二、链表法。链表法更加常用，且比开放寻址法要简单。散列表的每一个位置（桶/槽）对应一条链表，我们将所有散列值相同的元素放到对应链表中。插入数据时，通过散列函数计算得到对应的散列槽位，直接将数据插入链表中，时间复杂度为 O(1)。查找和删除操作也是遍历链表进行操作，时间复杂度为与链表的长度有关。如果一个散列比较均匀的散列函数，散列表中有 n 个数据，m 个位置（桶/槽），那么每个链表的长度为 n/m，其查找、删除的时间复杂度为 O(n/m)

应用

1、实现 Word 文档中单词拼写检查功能。
常用英文单次有 20 万个左右，假设单词的平均长度为 10，那么每个单词占用 10 字节的空间，20 万个占用约 2M，可以用散列表来存储整个英文单词词典并直接放入内存中。当用户输入单词的时候，拿输入的单词去散列表中查找，如果能找到，说明拼写正确；否则，说明拼写有误。
2、按照访问次数为 10 万条 URL 访问记录排序
遍历 10 万条数据，以 URL 为 key，访问次数等信息做为 value 用链表法存入散列表，时间复杂度为 O(n)。同时记录下访问次数的最大值 K，如果 K 不是很大，使用桶排序，时间复杂度为 O(n)；如果 K 很大，使用快速排序，时间复杂度为 O(nlogn)
3、两个各有 10 万条字符串的数组，快速找出两个数组中相同的字符串
以第一个数组元素作为散列表的 key，存入散列表中，遍历另一个数组，如果能在散列表中找到对应的 value，说明存在相同的字符串，时间复杂度为 O(n)

设计工业级散列表

散列表的查询效率跟散列函数、装在银子、散列冲突等都有关系

设计散列函数

首先，散列函数的设计不能太复杂，太复杂的散列函数会消耗很多计算时间，间接影响到散列表的性能
其次，散列函数生成的值要尽可能随机并且均匀分布。这样才能避免或最小化散列冲突的可能性，同时也会使散列到每个槽中的数据比较均匀，综合性能最好
综合考虑各种因素：关键字的长度、特点、分布、大小等
设计散列函数常用的方法：数据分析法
应用：
1、不太会重复的值——运动会编号、手机号后几位等作为散列值
2、实现 word 拼写检查功能——单词中每个字母的 ASCII 码值“进位相加”，然后再跟散列表的大小求余、取模，作为散列值。比如：hash("nice")=(("n"-"a") * 26*26*26 + ("i"-"a") * 26*26 + ("c"-"a") * 26 + ("e"-"a")) / 78987

装载因子阈值

装载因子越大，说明散列表中的元素越多，空闲位置越少，散列冲突的概率就越大。对于没有频繁插入和删除的静态数据集合来说，我们可以设计出完美的、比较少冲突的散列函数。但是对于频繁变动数据的散列表，我们无法预知数据的个数，因此也无法事先申请一个足够大的散列表。数据越多，装载因子越大，散列冲突不可避免。此时，我们需要对散列表进行动态扩容，申请一个更大的散列表。
散列表扩容后，长度会发生变化，如果散列函数中使用了与散列表长度相关的操作，势必会对数据的存储位置造成影响。支持动态扩容的散列表插入数据，最好情况下时间复杂度为 O(1)；动态扩容需要搬移数据，因而最坏时间复杂度为 O(n)；使用摊还分析法，均摊情况下时间复杂度为 O(1)
如果对空间高度消耗非常敏感的话，同样可以进行动态缩容。但无论是扩容还是缩容，装载因子必须要设计的合理，阈值的设置要全很时间、空间复杂度。如果内存空间不紧张，对执行效率要求很高，可以降低装载因子的阈值，以空间换时间；如果空间紧张，对执行效率要求不高，可以增加装载因子的值，甚至可以大于 1(比如链表法的装载因子就可以大于 1)
最坏情况下需要迁移数据，非常耗时。用户操作时遇到这种情况也会非常崩溃，如何解决一次性扩容耗时过多的情况能？可以将扩容操作穿插在插入操作的过程中：申请新空间后，并不将老数据搬移到新的散列表中，而是有新数据需要插入时，先将数据插入到新的散列表中，在从老的散列表中拿出一个数据放到新的散列表中。这样把搬移的工作分到每次的插入操作中，避免一次性数据搬移耗时太久的问题，时间复杂度永远为 O(1)。搬移期间要注意，查询数据需要查询新散列表后还要查询老散列表。

解决散列冲突

解决散列冲突主要的两种方法：
1、开放寻址法
优点：使用开放寻址法的散列表的数据都存储在数组中，可以有效的利用 CPU 缓存加快查询速度，而且序列化起来比较简单，链表法包含指针，序列化没这么容易
缺点：删除数据时需要特殊标记已经删除掉的数据，而且所有数据都存储在一个数组中，装载因子必须小于 1。接近 1 时就可能造成大量的散列冲突，导致大量的探测、再散列。因而装载因子的上限不能太大，会比链表法更浪费内存空间
总结：当数据量比较小、装载因子小的时候，适合采用开放寻址法
2、链表法
优点：链表法对内存的利用率比开放寻址法要高，可以在需要的时候再创建。链表法对装载因子的容忍度更高，装载因子可以大于 1。只要散列函数的值随机均匀，装载因子变大大也只是造成链表的长度变大，查找效率有所下降，但仍比顺序查找快。而且可以将链表改造成其他高校的动态数据结构，比如跳表、红黑树。即使出现散列冲突，极端情况下全部散列到一个桶中，时间复杂度也是变成 O(logn)
缺点：链表存储的是指针，对于比较小的对象存储，添加指针（4 或 8 个字节）是比较消耗内存的，但对于大对象，指针的内存消耗就可以忽略了。链表中的结点时零散、非连续的分布在内存中，对 CPU 的缓存是不友好的，对执行效率也有一定的影响
总结：对于存储大对象、大数据量的数据，比较适合链表法。而且他支持更多的优化策略，比如用红黑树代替链表

具体应用

一、Java 中的 HashMap
1、初始大小。HashMap 默认的初始大小是 16，可以修改。如果已知大概数据量，可以减少动扩容的次数，提高其性能
2、装载因子和动态扩容策略。HashMap 默认的装载因子最大值为 0.75，大于这个值就会进行扩容，容量变为原来的两倍
3、散列冲突的解决方法。HashMap 底层采用链表法解决冲突，在 JDK1.8 版本中，当链表的长度大于一定的值（默认为 8）时，会将链表转换为红黑树，小于 8 时又会转换为链表。红黑树需要维护平衡，数据量小的时候在性能上不比链表突出
4、散列函数。散列函数追求的是简单高效、分布均匀

int hash(Object key) {
  int h = key.hashCode(); // hashCode 是 32 位整型值
  return (h ^ (h >>> 16)) & (capicity - 1); // 先无符号右移 16 位，然后再和自己做异或运算，这样计算出来的整型值将“具有”高位和低位的性质；capicity 永远是 2 的幂次方，等式 A % B = A & (B - 1) 成立，也就是求余得到自身在数组中的位置
}

// String 类型的对象的 hashCode 方法
public int hashCode() {
  int var1 = this.hash;
  if(int var1 == 0 && this.value.length > 0) {
    char[] var2 = this.value;
    for(int var3 = 0;var3 < this.value.length; ++var3) {
      var1 = 31 * var1 + var2[var3];
    }
    this.hash = var1;
  }
  return var1;
}

二、LRU 缓存淘汰算法
一个缓存（cache）系统主要有三个操作：
1、往缓存中添加一个数据
2、从缓存中删除一个数据
3、在缓存中查找一个数据
仅仅使用链表实现的 LRU 缓存淘汰算法，因为每个操作要遍历链表，所以时间复杂度为 O(n)。而将散列表和链表两种数据结构组合使用，则可以将三种操作的时间复杂度都降为 O(1)。由于我们的散列表是通过链表法解决散列冲突的，所以每个结点会在两条链中。一个链是存储数据的双向链表，另一个链是散列表中的单链表。每个结点包含存储数据(data)、前驱指针(prev)、后继指针(next)和散列表中的链表指针(hnext)
LRU 缓存淘汰算法
上面三个操作的过程：
1、查找，通过散列表查找数据，时间复杂度为 O(1)。找到数据后，将它移到双向链表的尾部
2、删除，先查找到要删除的数据，时间复杂度为 O(1)。因为使用的是双向链表，可以在 O(1)时间复杂度获得其前驱结点然后删除
3、添加，先查询是否已经在缓存中，如果已经存在，将其移到双向链表的尾部；如果不存在且缓存没满，则直接将数据放到链表的尾部；如果缓存已经满了，则将双向链表头部的结点删除，再将数据放到链表的尾部
整个过程的查找操作都可以通过散列表完成，时间复杂度为 O(1)，其他双向链表的删除、插入等操作等也都可以在 O(1) 的时间复杂度内完成，所以这三个操作的时间复杂度都是 O(1)

三、Redis 有序集合
在有序集合中，每个成员对象有两个重要的属性，key（键值）和 score（分值）。
细化一下 Redis 有序集合的操作：
1、添加一个成员对象
2、按照键值来删除一个成员对象
3、按照键值来查找一个成员对象
4、按照分值区间查找数据
5、按照分值从小到大排序成员变量
按照分值将对象构建成跳表，删除、查找的时间复杂度为 O(logn)。而使用键值构建一个散列表，按照 key 进行删除、查找的时间复杂度就为 O(1)，然后再结合分值跳表可以快速查按照区间查找数据。

四、Java LinkedHashMap
LinkedHashMap 是通过双向链表和散列表这两种数据结构组合实现的。LinkedHashMap 中的“Linked”实际上是指的是双向链表，并非指用链表法解决散列冲突。按照访问时间排序的 LinkedHashMap 本身就是一个支持 LRU 缓存淘汰策略的缓存系统，它们两个的实现原理一模一样

散列表与链表

散列表虽然支持非常高效的数据插入、删除、查找操作，但散列表中的数据都是通过散列函数打散后无序存储的，如果我们想要将数据按照某种顺序排列，那就要先把数据拷贝到数组中，先排序再遍历，而且散列表是动态数据结构，不停的有数据插入、删除，这样每次遍历都需要重新排序，效率势必很慢。因而散列表经常与链表配合使用，链表或跳表用来实现排序的功能

哈希算法

将任意长度的二进制串映射为固定长度的二进制串，这个映射的规则就是哈希算法，通过原始数据映射之后得到的二进制串就是哈希值
哈希算法要求：
1、从哈希值不能反向推导出原始数据，哈希算法也叫单向哈希算法
2、对输入数据非常敏感，微小的改动也会使得到的哈希值大不相同
3、散列冲突的概率要很小
4、哈希算法的执行效率要尽量高效，长文本也能快速计算出哈希值
哈希算法常见应用：安全加密、唯一标识、数据校验、散列函数、负载均衡、数据分片、分布式存储

安全加密

常用的加密哈希算法是 MD5 消息摘要算法和 SHA 安全散列算法。对于加密算法，有两点哈希算法格外重要：1、很难根据哈希值反推出原始数据；2、散列冲突的概率要很小。根据鸽巢原理（抽屉原理），如果有 10 个鸽巢，有 11 只鸽子，那么肯定有 2 只鸽子在 1 个鸽巢内。类似的，哈希算法产生的哈希值的长度是固定且有限的，而我们要哈希的数据是无穷的，所以无法做到零冲突，我们只能尽量减少冲突的概率。一般情况下，哈希值越长，散列冲突的概率越低。
没有绝对安全的加密，而且越复杂、越难破解的加密算法，需要的计算时间也越长。在实际开发中，需要权衡破解难度和计算时间来选择合适的加密算法。针对字典攻击，我们可以对用户的密码进行加盐加密，增加密码的破解难度。

唯一标识

在海量的图库中搜索一张图是否存在，只对比图片的名称是不行的，因为图片的名称与图片数据不是强绑定关系，可以随意修改。笨办法是将图片的二进制码串与图库中所有的图片的二进制码串一一对比，但这种方法太耗时。我们可以给每个图片取一个唯一标识：将图片的二进制码串开头、中间、结尾各取 100 个字节拼起来，在通过哈希算法得到一个哈希字符串，用它做图片的唯一标识。通过这个唯一标识来判段图片是否存在，如果不存在该标识，说明图库中不存在改图片；如果存在，就对标识相同的图片进行全量对比，看是否真的完全一样。

数据校验

基于 P2P 协议的 BT 下载软件在下载电影时，会将一个电影文件分割成很多文件块，等所有文件块都下载完成之后再组装成一个完整的电影文件。但是下载的文件块有可能被其他人恶意修改，为了电脑的安全，需要校验文件块的正确性和完整性。其中一种校验思路是利用哈希算法对数据的敏感，只要文件块有改变，计算出的哈希值就会不同，然后通过与种子文件中保存的哈希值对比，这样就能判断文件块是否发生改变

散列函数

散列函数更看重散列的平均性和哈希算法的执行效率，而对散列冲突和安全性的要求要低很多，只要冲突不是过于严重，可以通过开放寻址法或链表法来解决，计算的到的值否能反向解密也不关心。而且复杂的算法会降低散列函数的执行效率，进而影响散列表的性能，因而散列函数用的散列算法一般比较简单

负载均衡

会话粘滞的负载均衡算法：在同一个客户端上，在一次会话中的所有请求都路由到同一个服务器上
通过哈希算法，对客户端 IP 地址或者会话 ID 计算哈希值，将取得的哈希值与服务器列表的大小进行取模运算，最终得到的值就是应该北路有道的服务器编号

数据分片

1、统计“搜索关键词”出现的次数
快速统计出 1T 的日志文件中每个关键词被搜索的次数，需要解决两个难点：1、日志很大，没法放到一台机器的内存中；2、如果只使用一台机器处理这么巨大的数据，速度会很慢
解决这两个难点可以这么做：先对数据进行分片，然后采用多台机器处理的方法。具体方法：使用 n 台机器并行处理，需要先从日志文件中依次读出每个关键词，并且通过哈希函数计算得到哈希值，然后跟机器总数 n 取模，最终的到的值就是应该被分配到的机器编号。这样是哈希值相同的关键词就都分配到同一台机器上，每台机器分别计算关键词出现的次数，最后合并起来就是最终的结果。这也是 MapReduce 的基本设计思想

2、快速判断图片是否在图库中
前面的方法是获取图片的唯一标识构建散列表，但如果图库中 1 亿张图片，甚至更多，这样只在一台机器上构建散列表是不行的。我们同样可以数据进行分片，然后采用多机处理，每台机器仅维护磨一部分图片对应的散列表。像第 1 个例子一样，先计算唯一标识，然后与机器总数进行求余取模，得到对应分配的机器编号，然后将这个图片的唯一标识和图片路径发往对应的机器构建散列表。如果我们需要判断一个图片是否在图库中的时候，也是先通过同样的哈希算法得到唯一标识，然后与机器总数求模取余，得到对应的机器编号，最后在该机器散列表中进行查找
首先，我们先估算一下 1 亿张图片构建散列表需要多少台机器。假设散列表中每个数据单元包含哈希值和图片文件路径这两个信息，如果通过 MD5 来计算哈希值，那么长度就是 128 比特（16 字节）。文件路径长度的上限是 256 字节，假设平均长度是 128 字节，如果使用链表法来解决冲突，还需要 8 字节的指针，每个数据单元预计需要占用 152 字节。假设一台机器内存是 2GB，散列表的装载因子是 0.75，那么一台机器可以给2*1024*1024*1024*0.75/152≈1000w张图片构建散列表，那么 1 亿张图片大约需要十多台机器。
针对海量数据的处理问题都可以采用分布式处理，这样可以突破单机存储、CPU 等资源的限制

分布式存储

现在互联网有海量的数据，这些数据都需要缓存，需要将数据分不到多台机器上。借用数据分片的思想，可以将数据分布在多台机器上，但如果数据增多，需要扩容就会出现问题：因为机器数量增多，之前计算时有取模运算，几乎所有位置都会发生改变。而数据量又大，我们又不能将所有缓存重新计算哈希值，否则之前的缓存就全都失效了，而大量缓存同时失效会引起雪崩使数据库压力瞬间增大，很有可能压垮整个服务。利用一致性哈希算法可以解决这个问题，一致性哈希算法也是使用取模的方法，只是之前的取模法是对服务器数量取模，而一致性哈希是对 2^32 取模。白话解析：一致性哈希算法 consistent hashing、一致性哈希算法原理和实现