Skip to content

Latest commit

 

History

History
427 lines (323 loc) · 12 KB

5-散列（第8章）.md

File metadata and controls

427 lines (323 loc) · 12 KB
Raw

5-散列

散列是一种常用的数据存储技术，散列后的数据可以快速的插入和取用。散列使用的数据结构叫散列表。在散列表上插入、删除和取用数据是非常快的，但是对于查找操作来说却是效率低下。

5.1 散列的概榄

我们的散列表是基于数组进行设计的。数组的长度是预先设定的，如有需要，可以随时增加。所有元素根据和该元素对应的键，保存在数组的特定位置，该键和我们前面讲到的字典中的键是类似的概念。使用散列表存储数据时，通过一个散列函数将键映射为一个数字，这个数字的范围是 0 到散列表的长度。

理想情况下，散列函数会将每个键值映射为一个唯一的数组索引。然而，键的数量是无限的，数组的长度是有限的（理论上，在 JavaScript 中是这样），一个更现实的目标是让散列函数尽量将键均匀地映射到数组中。

即使使用一个高效的散列函数，仍然存在将两个键映射成同一个值的可能，这种现象称为碰撞（collision），当碰撞发生时，我们需要有方案去解决。本章稍后部分将详细讨论如何解决碰撞。

要确定的最后一个问题是：散列表中的数组究竟应该有多大？这是编写散列函数时必须要考虑的。对数组大小常见的限制是：数组长度应该是一个质数。在实现各种散列函数时，我们将讨论为什么要求数组长度为质数。之后，会有多种确定数组大小的策略，所有的策略都基于处理碰撞的技术。

5.2 HashTable类

我们是用hashtable类来表示散列表。这个类包括了计算散列值的方法、向散列表中插入和读取数据的方法。一个简单的散列函数如下:

function simpleHash (data) {
  var total = 0
  for (var i = 0; i < data.length; i++) {
    total += data.charCodeAt(i)
  }
  return total % this.table.length
}

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

function put (data) {
  var pos = this.simpleHash(data)
  this.table[pos] = data
}

function HashTable () {
  // 数组长度137是我随机设置的一个数。
  this.table = new Array(137)
  // 散列函数。
  this.simpleHash = simpleHash
  // 显示散列表中的全部数据
  this.showDistro = showDistro
  // 将数据存入散列表
  this.put = put
  
}

散列表存储数据的原理是：有个数据data，我们要把它存在数组中。我们通过某个函数（散列函数）计算这个data应该存在数组的那个位置。然后我们把这个data存储在数组的相应位置。

5.2.1 散列函数

下面我们来研究下，散列函数。散列函数的选择依赖于键值的数据类型。如果键是整型，最简单的散列函数就是以数组的长度对键取余, 这也是数组的长度为什么要是质数的原因之一. 如果键是随机的整数，则散列函数应该更均匀地分布这些键。这种散列方式称为除留余数法。

在很多应用中，键是字符串类型， 选择针对字符串类型的散列函数是很难的。将字符串中每个字符的 ASCII 码值相加似乎是一个不错的散列函数。

所以我们刚才的散列函数是这样的

function simpleHash (data) {
 var total = 0
 for (var i = 0; i < data.length; i++) {
   total += data.charCodeAt(i)
 }
 return total % this.table.length
}

这个散列函数能不能用呢，我们找个数据验证下。

var someNames = ["David", "Jennifer", "Donnie", "Raymond", "Cynthia", "Mike", "Clayton", "Danny", "Jonathan"];

var hTable = new HashTable()
for (var i = 0; i < someNames.length; i++) {
  hTable.put(someNames[i])
}

hTable.showDistro()
// 打印结果
35 : Cynthia
45 : Clayton
57 : Donnie
77 : David
95 : Danny
116 : Mike
132 : Jennifer
134 : Jonathan

看起来我们写的散列表能正常工作，不过仔细看就会发现，数据并不均匀，而是后端偏多。另一个更严重的问题是，我们的数组someNames有9个名字，但是散列表中只存储了8个名字。这是因为我们在存储的时候发生了碰撞。名字“Clayton”和“Raymond”的散列值是一样的，都是45。所以后面出现的“Clayton”就覆盖了前面的“Raymond”。导致名字少了一个。

5.2.2 一个更加优化散列函数

避免散列碰撞的方法有3个

  • 用来存储数据的数组大小是一个质数
  • 数组大小要合适
  • 采取更好的算法

本例中我们把数组大小设置成137，100以下的质数更容易产生碰撞。算法我们采用霍纳算法。

在此算法中，新的散列函数仍然先计算字符串中各字符的 ASCII 码值，不过求和时每次要乘以一个质数。大多数算法书建议使用一个较小的质数，比如 31，但是对于我们的数据集， 31 不起作用，我们使用 47（原书是37，37还是会产生碰撞，作者不知道是不是眼瞎了，他用37测试的结果是不对的，他还说是对的），这样刚好不会产生碰撞。

我们新的散列函数

function betterHash(data) {
  const H = 37
  var total = 0
  for (var i = 0; i < data.length; i++) {
    total += H * total + data.charCodeAt(i)
  }
  total = total % this.table.length
  if (total < 0) {
    total += this.table.length - 1
  }
  console.log(total)
}

我们新的散列类

function simpleHash(data) {
  var total = 0
  for (var i = 0; i < data.length; i++) {
    total += data.charCodeAt(i)
  }
  return total % this.table.length
}

function betterHash(data) {
  const H = 47
  var total = 0
  for (var i = 0; i < data.length; i++) {
    total += H * total + data.charCodeAt(i)
  }
  total = total % this.table.length
  if (total < 0) {
    total += this.table.length - 1
  }
  return total

}


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

function put(data) {
  var pos = this.betterHash(data)
  this.table[pos] = data
}

function HashTable() {
  // 数组长度137是我随机设置的一个数
  this.table = new Array(137)
  // 散列函数。
  this.simpleHash = simpleHash
  // 优化后的散列函数
  this.betterHash = betterHash
  // 显示散列表中的全部数据
  this.showDistro = showDistro
  // 将数据存入散列表
  this.put = put
}

测试：

var someNames = ["David", "Jennifer", "Donnie", "Raymond", "Cynthia", "Mike", "Clayton", "Danny", "Jonathan"];

var hTable = new HashTable()
for (var i = 0; i < someNames.length; i++) {
  hTable.put(someNames[i])
}

hTable.showDistro()

// 打印结果
29 : Cynthia
55 : Clayton
78 : David
84 : Mike
91 : Jennifer
96 : Jonathan
116 : Donnie
128 : Danny
132 : Raymond

这样测试结果才是对的，再次强调下，原书是错的。自此我们大概完成了我们的需求。其实还有问题的，当我们的someName数组变化的时候，我们还要去调整我们数组，否则还有可能发生碰撞，怎么解决这个问题了？

5.3碰撞

5.3.1 开链法

当碰撞发生时，我们仍然希望将键存储到通过散列算法产生的索引位置上，但实际上，不可能将多份数据存储到一个数组单元中。开链法是指实现散列表的底层数组中，每个数组元素又是一个新的数据结构，比如另一个数组，这样就能存储多个键了 。

开链函数:

function buildChains() {
  for (var i = 0; i < this.table.length; i++) {
    this.table[i] = new Array()
  }
}

使用开链法后需要对我们的put和showDistro函数进行调整。如下

function buildChains() {
  for (var i = 0; i < this.table.length; i++) {
    this.table[i] = new Array()
  }
}

function betterHash(data) {
  const H = 47
  var total = 0
  for (var i = 0; i < data.length; i++) {
    total += H * total + data.charCodeAt(i)
  }
  total = total % this.table.length
  if (total < 0) {
    total += this.table.length - 1
  }
  // console.log('total data:', total, data)
  return total

}


function showDistro() {
  for (var i = 0; i < this.table.length; i++) {
    if (this.table[i].length > 0) {
      console.log(i + ' : ' + this.table[i])
    }
  }
}

function put(data) {
  var pos = this.betterHash(data)
  var index = 0

  while (this.table[pos][index] != undefined) {
    index++
  }
  this.table[pos][index] = data

}

function HashTable() {
  // 开链
  this.buildChains = buildChains
  // 数组长度137是我随机设置的一个数
  this.table = new Array(137)
  // 优化后的散列函数
  this.betterHash = betterHash
  // 显示散列表中的全部数据
  this.showDistro = showDistro
  // 将数据存入散列表
  this.put = put
}

测试。**注意：我们的someNames数组的最后一项和倒数第二项是一样的。设置成一样目的就是为了验证碰撞

var someNames = ["David", "Jennifer", "Donnie", "Raymond", "Cynthia", "Mike", "Clayton", "Danny", "Jonathan", "Jonathan"];

var hTable = new HashTable()
hTable.buildChains()
for (var i = 0; i < someNames.length; i++) {
  hTable.put(someNames[i])
}

// console.log('hTable.table:', hTable.table)
hTable.showDistro()

测试结果：

29 : Cynthia
55 : Clayton
78 : David
84 : Mike
91 : Jennifer
96 : Jonathan,Jonathan
116 : Donnie
128 : Danny
132 : Raymond

测试感觉没有问题。

5.3.2 线性探索法

第二种处理碰撞的方法是线性探测法。线性探测法隶属于一种更一般化的散列技术： 开放寻址散列。当发生碰撞时，线性探测法检查散列表中的下一个位置是否为空。如果为空，就将数据存入该位置；如果不为空，则继续检查下一个位置，直到找到一个空的位置为止。该技术是基于这样一个事实：每个散列表都会有很多空的单元格，可以使用它们来存 储数据 。

我们修改put和showDistro方法

function betterHash (data) {
  const H = 47
  var total = 0
  for (var i = 0; i < data.length; i++) {
    total += H * total + data.charCodeAt(i)
  }
  total = total % this.table.length
  if (total < 0) {
    total += this.table.length - 1
  }
  // console.log('total data:', total, data)
  return total
}

function showDistro () {
  for (var i = 0; i < this.table.length; i++) {
    if (this.table[i]) {
      console.log(i + ' : ' + this.table[i])
    }
  }
}

function put (data) {
  var pos = this.betterHash(data)
  while (this.table[pos] != undefined) {
    pos++
  }
  this.table[pos] = data
}

function HashTable () {
  // 数组长度137是我随机设置的一个数
  this.table = new Array(137)
  // 优化后的散列函数
  this.betterHash = betterHash
  // 显示散列表中的全部数据
  this.showDistro = showDistro
  // 将数据存入散列表
  this.put = put
}

测试

var someNames = [
  'David',
  'Jennifer',
  'Donnie',
  'Raymond',
  'Cynthia',
  'Mike',
  'Clayton',
  'Danny',
  'Jonathan',
  'Jonathan'
]

var hTable = new HashTable()
for (var i = 0; i < someNames.length; i++) {
  hTable.put(someNames[i])
}

hTable.showDistro()

结果:

29 : Cynthia
55 : Clayton
78 : David
84 : Mike
91 : Jennifer
96 : Jonathan
97 : Jonathan
116 : Donnie
128 : Danny
132 : Raymond

线性探索法也满足了我们的需求，没有发生碰撞

5.3.3 方法的选择

我们现在有两种方法解决碰撞，1个是开链法，一个是线性探索法，那么我们该用什么方法呢？

如果数组的大小是待存储数据个数的 1.5 倍，那么使用开链法；如果数组的大小是待存储数据的两倍及两倍以上时，那么使用线性探测法。

个人点评：为什么要用散列这个数据结构，我也不清楚，总感觉没啥用，当然也可能是自己太浅陋了，还没到用的时候。另外这本书的作者简直太不用心了，写的程序漏洞百出。这种情况下，这书竟然都能出版，实在是惊奇*