博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
学习数据结构与算法之字典和散列表
阅读量:5757 次
发布时间:2019-06-18

本文共 5839 字,大约阅读时间需要 19 分钟。

本系列所有文章:

第一篇文章:
第二篇文章:
第三篇文章:
第四篇文章:
第五篇文章:

字典

不是新华字典哦,这里的字典也称作_映射_,是一种数据结构,跟set集合很相似的一种数据结构,都可以用来存储无序不重复的数据。不同的地方是集合以[值,值]的形式存储,而字典则是以[键,值]或者叫作{key: value}的形式。

用JavaScript实现字典

先实现一个构造函数:

function Dictionary () {  var items = {}}

字典需要实现以下方法:

  • set(key, value):向字典中添加新元素
  • remove(key):通过使用key来从字典中移除对应元素
  • has(key):通过key来判断字典中是否有该元素
  • get(key):通过key来找到特定的数值并返回
  • clear():清空字典
  • size():返回字典包含元素的数量
  • keys():返回字典所包含的所有键名,以数组形式返回
  • values():同上一个方法一样,只不过键名换成了数值,也是以数组形式返回

实现has

因为后面的方法都要用到has,所以先实现这个方法

this.has = function (key) {  // 书上用的是in操作符来判断,但是in对于继承来的属性也会返回true,所以我换成了这个  return items.hasOwnProperty(key)}

实现set

没啥好说的,简单的赋值

this.set = function (key, value) {  items[key] = value}

实现remove

首先判断key是否属于该字典,然后再删除

this.remove = function (key) {  if (this.has(key)) {    delete items[key]    return true  }  return false}

实现values

返回由数值组成的数组

this.values = function () {  var values = []  for (var k in items) {    if (items.has(k)) {      values.push(items[k])    }  }  return values}

实现其他的方法

其他的比较简单,和集合的方法实现类似,我就直接贴源代码了

this.keys = function () {  return Object.keys(items)}this.size = function () {  return Object.keys(items).length}this.clear = function () {  items = {}}this.getItems = function () {  return items}this.get = function (key) {  return this.has(key) ? items[key] : undefined }

源代码在此:

散列表

关于散列表的定义,这里摘抄一下维基百科的解释:

散列表Hash table,也叫哈希表),是根据键(Key)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称做散列函数,存放记录的数组称做散列表

可以理解为,数据中的键通过一个散列函数的计算后返回一个数据存放的地址,因此可以直接通过地址来访问它的值,这样的查找就非常快。

用JavaScript实现散列表

先看这个构造函数,注意:存储数据用的是数组,因为寻址访问元素最方便的还是数组了。

function HashTable () {    var table = []}

需要实现的方法:

  • put(key, value):向散列表增加一个新的项
  • remove(key):根据键值从散列表中移除值
  • get(key):返回根据键值检索到的特定的值

先实现散列函数

把键名的每个字母转成ASCII码再相加起来,最后和一个任意的数求余,得到数据存储的地址。

var loseloseHashCode = function (key) {  var hash = 0  for (var i = 0; i < key.length; i++) {    hash += key.charCodeAt(i)  }  return hash % 37}

简单实现

因为这里的方法比较简单,我就直接全贴上来了

this.put = function (key, value) {  var position = loseloseHashCode(key)  console.log(position + ' - ' + key)  table[position] = value}this.remove = function (key) {  table[loseloseHashCode(key)] = undefined}this.get = function (key) {  return table[loseloseHashCode(key)]}// 用来输出整个散列表,查看结果用的this.print = function () {  for (var i = 0; i < table.length; i++) {    if (table[i] !== undefined) {      console.log(i + ': ' + table[i])    }  }}

稍等,还没完呢,现在看似很完美,我们调用一下刚才写的:

var hash = new HashTable()hash.put('Gandalf', 'gandalf@email.com')hash.put('John', 'johnsnow@email.com')hash.put('Tyrion', 'tyrion@email.com')// 输出结果// 19 - Gandalf// 29 - John// 16 - Tyrion

好像没什么不对,但是仔细想想:如果在某些情况下,散列函数根据传入的键计算得到的地址是一样的会怎么样呢?

看看下面这个例子:

var hash = new HashTable()hash.put('Gandalf', 'gandalf@email.com')hash.put('John', 'john@email.com')hash.put('Tyrion', 'tyrion@email.com')hash.put('Aaron', 'aaron@email.com')hash.put('Donnie', 'donnie@email.com')hash.put('Ana', 'ana@email.com')hash.put('Jonathan', 'jonathan@email.com')hash.put('Jamie', 'jamie@email.com')hash.put('Sue', 'sue@email.com')hash.put('Mindy', 'mindy@email.com')hash.put('Paul', 'paul@email.com')hash.put('Nathan', 'nathan@email.com')// 输出结果// 19 - Gandalf// 29 - John// 16 - Tyrion// 16 - Aaron// 13 - Donnie// 13 - Ana// 5 - Jonathan// 5 - Jamie// 5 - Sue// 32 - Mindy// 32 - Paul// 10 - Nathan

这种情况就比较复杂了:Tyrion和Aaron的值都是16,Donnie和Ana都是13,还有其他很多重复的值,这时散列表表中是什么情况呢

hash.print()// 输出结果// 5: sue@email.com// 10: nathan@email.com// 13: ana@email.com// 16: aaron@email.com// 19: gandalf@email.com// 29: john@email.com// 32: paul@email.com

很明显,后面的元素会覆盖前面的元素,但这样是不行的,要想办法解决冲突

解决冲突

目前主流的方法主要是两种:分离链接法和线性探查法,这里就简单介绍一下分离链接法。

分离链接法

思路很简单:你不是重复了吗,那我就在同一个位置里面放一个链表,重复的数据全都放在链表里面,你要找数据就在链表里面找。

如果不理解,可以参见下图:

哈希表-分离链接法

(图片来源谷歌搜索,侵删)

根据这个思路,我们重新实现一下三个方法,不过在这之前,我们需要一个对象来保存键值对

var ValuePair = function (key, value) {  this.key = key  this.value = value    // 重写toString主要是方便输出查看  this.toString = function () {    return '[' + this.key + ' - ' + this.value + ']'  }}

接下来就是重写方法了

this.put = function (key, value) {  var position = loseloseHashCode(key)  // 如果发现该位置还没有元素,就先放一个链表,再用append加进去  if (table[position] === undefined) {    // 因为使用node执行文件,这里LinkedList是我在顶部用require引入的LinkedList.js    table[position] = new LinkedList()  }  table[position].append(new ValuePair(key, value))}this.get = function (key) {  var position = loseloseHashCode(key)  if (table[position] !== undefined) {    var current = table[position].getHead()    // 遍历链表查找值    while (current.next) {      if (current.element.key === key) {        return current.element.value      }      current = current.next    }    // 检查元素如果是最后一个的情况    if (current.element.key === key) {      return current.element.value    }  }  return undefined}this.remove = function (key) {  var position = loseloseHashCode(key)  if (table[position] !== undefined) {    var current = table[position].getHead()    // 遍历查找值    while (current.next) {      if (current.element.key === key) {        // 使用链表的remove方法        table[position].remove(current.element)        // 当链表为空了,就把散列表该位置设为undefined        if (table[position].isEmpty()) {          table[position] = undefined        }        return true      }      current = current.next    }    if (current.element.key === key) {      table[position].remove(current.element)      if (table[position].isEmpty()) {        table[position] = undefined      }      return true    }  }  return false}

以上就是用分离链接法重写的哈希表。

线性探查法

第二种办法思路更粗暴:你不是占了这个位置嘛,那我就占下一个,下个位置还被占了?那就占再下一个~

具体的实现我就不贴出来了,读者可以自行思考并实现,然后对照代码看看。

这里先把源代码放出来了

创建更好的散列函数

以上是哈希表的两个冲突解决办法,但实际上应用哈希表的时候能避免冲突就尽量避免冲突,一开始的散列函数不是一个好的函数,因为冲突太多了,这里就贴书上的一个不错的散列函数(社区),原理大致是:相加所得的hash数要够大,且尽量为质数,用hash与另一个大于散列表大小的质数做求余,这样得到的地址也能尽量不重复。

var djb2HashCode = function (key) {  var hash = 5381  for (var i = 0; i < key.length; i++) {    hash = hash * 33 + key.charCodeAt(i)  }  return hash % 1013}

小结

实现了字典和哈希表感觉没有想象中那么困难,当然这还是开始。

不过,这几天自己不断地研究数据结构,也让自己对于JS的理解进一步加深了。继续努力吧~

转载地址:http://xevkx.baihongyu.com/

你可能感兴趣的文章
洛谷P2672 推销员
查看>>
基于TCP协议的socket通信
查看>>
acts_as_nested_set
查看>>
USACO 1.4
查看>>
系统引导修复 ---- Windows 和 Ubuntu
查看>>
网格布局(GridLayout) 行数与列数
查看>>
C# 捕捉键盘事件
查看>>
时间对于程序员的价值,以及如何高效地利用时间,同时划分下勤奋度的等级...
查看>>
C#实现鼠标拖动自定义窗口
查看>>
Beta冲刺NO.6
查看>>
Django 中间件
查看>>
步步为营UML建模系列七、表图(Data model diagram)
查看>>
The Elements of C# Style -General Principles
查看>>
android textView的渐入效果
查看>>
linux上安装fastdfs+nginx+ngin-module实践并解决多个异常篇
查看>>
迭代器和生成器
查看>>
设计模式之原型模式
查看>>
Unity用GUI绘制Debug/print窗口/控制台-打包后测试
查看>>
移动开发
查看>>
小P的故事——神奇的Dota 背包
查看>>