散列表查找
2020-06-22
Essay
28 分钟 读完 (大约 4147 个字)

散列表查找

之前我们在 查找算法 的章节当中介绍了一些比较常见的查找算法，比如对于数组 a[]，如果我们要在其中查找 key 关键字的记录，可以使用顺序表查找的方式，一个一个挨着排查，也可以使用有序表的一些查找方式，比如二分，插值等

但是如果序列是无序的呢，针对于无序序列，我们之前也介绍过了 二叉排序树 的方式来进行查找，但是二叉排序树的生成过程比较复杂，那么有没有一种针对不太复杂的无序序列，使用起来更为简便的形式呢，那就是我们今天所要介绍的『散列表查找』

散列表查找

散列是一种常用的数据存储技术，散列后的数据可以快速地插入或取用，散列使用的数据结构叫做『散列表』，散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系 f，使得每个关键字 key 对应一个存储位置 f(key)，这里我们把这种对应关系 f 称为散列函数，又称为哈希（Hash）函数

采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间成为散列表或哈希表（Hash table），在散列表上插入、删除和提取数据的速度都是非常快的，当存储记录时，通过散列函数计算出记录的散列地址，而当查找记录时，我们通过同样的是散列函数计算记录的散列地址，并按此散列地址访问该记录

本章主要包括三部分内容，即如何构造哈希函数和冲突的处理，以及最后的代码实现

散列函数设计

构造哈希函数的原则是

  • 函数本身便于计算
  • 计算出来的地址分布均匀，即对任一关键字 k，f(k) 对应不同地址的概率相等，目的是尽可能减少冲突

下面我们来看一些业界前辈总结的一些比较好的设计方式

直接定址法

例如有一个从 1 到 100 岁的人口数字统计表，其中『年龄』作为关键字，哈希函数取关键字自身，即 f(key) = key，也就是下图这样

又或者现在要统计的是 1980 年以后出生的人口数，那么我们也可以对出生年份这个关键字可以变换为用年份减去 1980 的值来作为地址，即 f(key) = key – 1980，也就是下面这样

数字分析法

数字分析法通常适合处理『关键字位数比较大』的情况，例如我们现在要存储某家公司员工登记表，如果用手机号作为关键字，那么我们发现『抽取』后面的四位数字作为散列地址是不错的选择

平方取中法

平方取中法是将『关键字平方』之后取中间若干位数字作为散列地址，比如 1234^2 = 1522756 的，所以我们可以考虑使用 227 来作为关键字

折叠法

折叠法是将关键字从左到右分割成位数相等的几部分，然后将这几部分叠加求和，并按散列表表长取后几位作为散列地址，比如我们的关键字是 9876543210 的话，我们就可以将其分割成为相等的几部分（位数如果不够可以使用 0 来进行填充），也就是 987，654，321，000，然后把这几部分进行相加，它们的结果是 1962，所以我们就可以采用 962 来作为关键字

除留余数法

需要注意的是，这个方法也是『最常用』的构造散列函数方法，对于散列表长为 m 的散列函数计算公式为

1
f(key) = key mod p（p <= m，mod 是取模的意思）

事实上，这个方法不仅可以对关键字直接取模，也可以通过折叠、平方取中后再取模，例如下表，我们对有 12 个记录的关键字构造散列表时，就可以用 f(key) = key mod 12 的方法

但是 p 的选择是关键，如果对于这个表格的关键字，p 如果还是选择 12 的话，那就不是一个很好的方式了

不过针对上面这种情况，如果我们把 p 改为 11 也是可以的，如下

随机数法

选择一个随机数，取关键字的随机函数值为它的散列地址，即 f(key) = random(key)，这里的 random 是随机函数，当关键字的长度不等时，采用这个方法构造散列函数是比较合适的

总结

我们可以视不同的情况采用不同的散列函数，在现实中，我们应该视不同的情况采用不同的散列函数，下面是一些需要考虑的方向

  • 计算散列地址所需的时间
  • 关键字的长度
  • 散列表的大小
  • 关键字的分布情况
  • 记录查找的频率

处理散列冲突的方法

通过构造性能良好的哈希函数，可以减少冲突，但一般不可能完全避免冲突，因此解决冲突是哈希法的另一个关键问题，创建哈希表和查找哈希表都会遇到冲突，两种情况下解决冲突的方法应该一致，下面我们就来看几种常用的解决冲突方法

开放定址法

所谓的开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入，它的公式是 fi(key) = (f(key) + di) MOD m (di = 1, 2 ... m - 1)，比如我们的关键字集合为 { 12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48 }，如果使用的是『除留余数法（m = 12）』，下面是散列表的排列形式

需要注意，此时我们需要添加元素 37，但是发现 37 % 12 = 1 的，而此时 1 的位置已经存在元素了，所以就发生了冲突，所以此时我们可以调用公式 fi(key) = (f(1) + 1) MOD 12，它的结果是 2，所以它填充在 2 的位置，也就下面这样

最终完成后是下面这样

但是我们可以发现，开放定址法虽然好，但是比较盲目，因为它是线性查找方式，逐渐递增的（即每次只增加一个位置），所以我们可以修改 di 的取值方式，例如使用平方运算来尽量解决『堆积』问题

1
fi(key) = (f(key) + di) MOD m（di = 1², -1², 2², -2² ... q², -q², q <= m / 1）

还有一种方法是，在冲突时对于位移量 di 采用『随机函数』计算得到，我们称之为『随机探测法』

1
fi(key) = (f(key) + di) MOD m（di 是由一个随机函数获得的数列）

再散列函数法

这种方法是同时构造多个不同的哈希函数 fi(key) = RHi(key)（i = 1, 2, 3 ... k），当哈希地址 fi(key) = RHi(key) 发生冲突时，再计算 fi(key) = RH2(key) ... 直到冲突不再产生，这种方法不易产生聚集，但增加了计算时间

链地址法

这种方法的基本思想是将所有哈希地址为 i 的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第 i 个单元中，因而查找、插入和删除主要在同义词链中进行，链地址法适用于经常进行插入和删除的情况

我们还是以之前的示例为例，我们假设集合为 { 12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 37 }，同样使用除留余数法求散列表是下面这样的

公共溢出区法

这种方法的基本思想是，将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表，还是以上面的例子为例，结果是下面这样的

代码实现

最后，我们来看看如何用代码进行实现，在 JavaScript 当中，我们采用数组来进行设计散列表，数组的长度是预先设定的，如有需要，可以随时增加，所有元素根据和该元素对应的键，保存在数组的特定位置，使用散列表存储数据时，通过一个散列函数将键映射为一个数字，这个数字的范围是 0 到散列表的长度

散列函数会将每个键值映射为一个唯一的数组索引，然而键的数量是无限的，数组的长度是有限的，一个更现实的目标是让『散列函数尽量将键均匀地映射到数组中』，即使使用一个高效的散列函数，仍然存在将两个键映射成同一个值的可能，这种现象称为碰撞（collision），当碰撞发生时，我们需要利用一定的方法去解决碰撞，也就是上面所介绍的几种方式

HashTable 类

我们使用 HashTable 类来表示散列表，该类包含计算散列值的方法、向散列中插入数据，读取数据和显示散列表中数据分布等方法

1
2
3
4
5
6
7
8
9
10
11
function HashTable() {
  this.table = new Array(137)
  this.simpleHash = simpleHash
  this.showDistro = showDistro
  this.put = put
  this.get = get
  this.buildChains = buildChains

  // 如果使用线性探测法，则需要额外添加一个数组
  this.values = []
}

散列函数

散列函数的选择依赖于键值的数据类型，如果键是整型，最简单的散列函数就是以数组的长度对键取余，而选择针对字符串类型的散列函数比较困难，一种比较简单的散列函数是针对字符串中每个字符的 ASCII 码值相加然后再除以数组长度，将得出的余数做为散列值

1
2
3
4
5
6
7
function simpleHash(data) {
  var total = 0
  for (var i = 0; i < data.length; ++i) {
    total += data.charCodeAt(i)
  }
  return total % this.table.length
}

put() 和 showDistro() 两个方法一个用来将数据存入散列表，而另一个则是用来显示散列表中的数据

1
2
3
4
5
6
7
8
9
10
11
12
13
function put(data) {
  var pos = this.simpleHash(data);
  this.table[pos] = data
}

function showDistro() {
  var n = 0
  for (var i = 0; i < this.table.length; ++i) {
    if (this.table[i] != undefined) {
      print(i + ': ' + this.table[i])
    }
  }
}

但是使用比较简单的散列函数时，它的数据并不是均匀分布的，而是向数组的两端集中，并且数据很大概率将会产生碰撞而不会全部显示出来，所以这里我们也可以采用另外一种方式，那就是『霍纳算法』

霍纳算法是一种比较好的散列函数算法，计算时仍然先计算字符串中各字符的 ASCII 码值，不过求和时每次要乘以一个质数，为了避免碰撞，首先要确保散列表中用来存储数据的数组其大小是个质数，这一点和计算散列值时使用的取余运算有关，数组的长度应该在 100 以上，这是为了让数据在散列表中分布得更加均匀

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function betterHash(string, arr) {
  // 质数
  const H = 37
  var total = 0
  for (var i = 0; i < string.length; ++i) {
    total += H * total + string.charCodeAt(i)
  }
  total = total % arr.length
  return parseInt(total)
}

// 接受键和数据作为参数的 put() 方法
function put(key, data) {
  // 使用霍纳算法
  var pos = this.betterHash(key)
  this.table[pos] = data
}

// 读取存储在散列表中的数据
function get(key) {
  return this.table[this.betterHash(key)]
}

碰撞处理

当散列函数对于不同的输入产生同样的散列值时，就产生了碰撞，这里我们主要来看两种碰撞解决办法『开链法』和『线性探测法』，关于开链法，当碰撞发生时，仍然将键存储到通过散列算法产生的索引位置上，但实际上每个数组元素又是一个新的数据结构，比如另一个数组，这样就能存储多个键了（即用二维数组实现）

1
2
3
4
5
6
// 创建二维数组
function buildChains() {
  for (var i = 0; i < this.table.length; ++i) {
    this.table[i] = new Array()
  }
}

使用了开链法后，我们要重新定义 put() 和 get() 方法，新的 put() 方法将键值散列，散列后的值对应数组中的一个位置，先尝试将数据放到该位置上的数组中的第一个单元格，如果该单元格里已经有数据了则 put() 方法会搜索下一个位置，直到找到能放置数据的单元格，并把数据存储进去，它既保存数据，也保存键值，该方法使用链中两个连续的单元格，第一个用来保存键值，第二个用来保存数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function put(key, data) {
  var pos = this.betterHash(key)
  var index = 0
  if (this.table[pos][index] == undefined) {
    this.table[pos][index] = key
    this.table[pos][index + 1] = data
  } else {
    while (this.table[pos][index] != undefined) {
      ++index
    }
    this.table[pos][index] = key
    this.table[pos][index + 1] = data
  }
}

新的 get() 方法先对键值散列，根据散列后的值找到散列表中相应的位置，然后搜索该位置上的链，直到找到键值，如果找到，就将紧跟在键值后面的数据返回

1
2
3
4
5
6
7
8
9
10
11
12
function get(key) {
  var index = 0
  var pos = this.betterHash(key)
  if (this.table[pos][index] == key) {
    return this.table[pos][index + 1]
  } else {
    while (this.table[pos][index] != key) {
      index += 2
    }
    return this.table[pos][index + 1]
  }
}

最后我们再来看下『线性探测法』，线性探测法隶属于一种更一般化的散列技术，也就是『开放寻址散列』，当发生碰撞时，线性探测法检查散列表中的下一个位置是否为空，如果为空，就将数据存入该位置，如果不为空，则继续检查下一个位置，直到找到一个空的位置为止，关于选择哪种实现方式

  • 当存储数据使用的数组特别大时，选择线性探测法要比开链法好
  • 如果数组的大小是待存储数据个数的 1.5 倍，那就使用开链法
  • 如果数组的大小是待存储数据的两倍及两倍以上时，那么使用线性探测法

使用线性探测法需要为 HashTable 类增加一个新的数组，用来存储数据，数组 table 和 values 并行工作，当将一个键值保存到数组 table 中时，将数据存入数组 values 中相应的位置上，即在 HashTable 的构造函数中加入下面一行代码 this.values = []，然后再来重写我们的 put() 和 get() 方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function put(key, data) {
  var pos = this.betterHash(key)
  if (this.table[pos] == undefined) {
    this.table[pos] = key
    this.values[pos] = data
  } else {
    while (this.table[pos] != undefined) {
      pos++
    }
    this.table[pos] = key
    this.values[pos] = data
  }
}

function get(key) {
  var hash = this.betterHash(key)
  for (var i = hash; this.table[hash] != undefined; i++) {
    if (this.table[hash] == key) {
      return this.values[hash]
    }
  }
  return undefined
}
# Essay
React 生命周期
平衡二叉排序树

评论

分类

标签云

Angular CSS Essay GIS HTTP JavaScript Node.js React Vue

最新文章

归档

标签

Angular 15
CSS 14
Essay 29
GIS 11
HTTP 11
JavaScript 45
Node.js 14
React 20
Vue 5
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×