JavaScript 数据结构之散列表的创建(2)

目录
  • 一、处理散列值冲突
    • 1.分离链接
    • 2.put 方法
    • 3.get 方法

前言：

上一篇我们介绍了什么是散列表，并且用通俗的语言解析了散列表的存储结构，最后动手实现了一个散列表，相信大家对散列表已经不陌生了。

如果还不清楚散列表，请先阅读上一篇文章：JavaScript 数据结构之散列表的创建(1)

上篇末尾我们遗留了一个问题，就是将字符串转化为散列值后可能出现重复。当以散列值（hash 值）为 key 存储数据时，就会有覆盖已有数据的风险。本篇我们看如何处理散列值冲突的问题，并实现更完美的散列表。

一、处理散列值冲突

有时候一些键会有相同的散列值。比如 aab 和 baa，从字符串的角度来说它们是不同的值，但是按照我们的散列函数逻辑，将每个字母的 Unicode 码累加得出的散列值，一定是一样的。

我们知道在 JavaScript 对象当中，如果赋值时指定的 key 已存在，那么就会覆盖原有的值，比如这个例子：

var json = { 18: '雷欧' }
json[18] = '欧布'
console.log(json) // { 18: '欧布' }

为了避免上述代码中出现的风险，我们需要想办法处理，如何使 key != key，则 hash != hash？

目前可靠的方法有两个，分别是：分离链接 和 线性探查。

1.分离链接

分离链接法是指在散列表存储数据时，value 部分用 链表 来代替之前的 键值对。键值对只能存储一个，而链表可以存储多个键值对。如果遇到相同的散列值，则在已有的链表中添加一个键值对即可。

我们需要重写三个方法：put、get 和 remove。我们看如何实现：

class HashTableSeparateChaining {
  constructor() {
    this.table = {}
  }
}

2.put 方法

首先还是基本的类结构，然后看 put 方法：

put(key, value) {
  if(key !== null && value !== null) {
    let pos = this.hashCode(key)
    if(!this.table[pos]) {
      this.table[pos] = new LinkedList()
    }
    this.table[pos].push(new ValuePair(key, value))
    return true;
  }
  return false;
}

LinkedList 类是标准的链表类，在链表篇讲过如何实现，这里直接使用

对比上篇的散列表 put 方法，你会发现差别不大，变化的部分如下：

// 变化前
this.table[pos] = new ValuePair(key, value)

// 变化后
if(!this.table[pos]) {
  this.table[pos] = new LinkedList()
}
this.table[pos].push(new ValuePair(key, value))

优化后的逻辑是，在存储数据时，将键值对存在一个链表里。如果有相同的 hash 值，则向已有的链表中添加一个键值对，这样就避免了覆盖。

不过这种方式也有弊端，每添加一个键值对就要创建一个链表，会增加额外的内存空间。

3.get 方法

get 方法：

get(key) {
  let linkedList = this.table[this.hashCode(key)]
  if(linkedList && !linkedList.isEmpty()) {
    let current = linkedList.getItemAt(0);
    while(current) {
      if(current.value.key == key) {
        return current.value.value
      }
      current = current.next
    }
  }
  return undefined;
}

新的 get 方法明显比之前的复杂了许多。主要逻辑是根据 key 找到一个链表，然后再遍历链表找到与参数 key 相匹配的键值对，最后返回找到的值。

while 循环中使用 return 可以直接中止当前函数

到此这篇关于 JavaScript 数据结构之散列表的创建的文章就介绍到这了,更多相关 JavaScript 散列表内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • Go语言的数据结构转JSON

    目录 结构体转为 JSON 格式 接口转为 JSON 格式 Marshal() 函数的原型 总结 在日常工作中,除了需要从 JSON 转化为 Go 的数据结构.但往往相反的情况是:我们需要将数据以 JSON 字符串的形式发送到 Web 服务器.今天我们将学会如何从一个结构化数据编码为 JSON . Json(Javascript Object Nanotation)是一种数据交换格式,常用于前后端数据传输.任意一端将数据转换成json 字符串,另一端再将该字符串解析成相应的数据结构,如strin

  • javascript将扁平的数据转为树形结构的高效率算法

    当我们需要将一个一维数组转换成一个多层结构的时候,最简单但是最慢的就是多个for循环嵌套,但是这样做有一些缺点,那就是效率太低.而且有多少层就需要嵌套几个for循环,不好用. 我实现了用O(n)级算法将 一个扁平的数组即一维数组代表的菜单结构转换成一个多层级的菜单结构. 一位数组中每一个元素必须要包含以下属性: 拥有一个唯一的id 拥有一个parent_id, 这个id指向它父级的id 其他则为每一个元素中的一些信息,我这里是菜单,就有菜单的名称和url信息. 注: 在层级结构中,第一层的par

  • JavaScript 数据结构 之集合创建

    目录 一.什么是集合 二.创建集合类 1.has 方法 2.add 方法 3.delete 和 clear 方法 4.size 方法 5.values 方法 三.使用集合 总结 前言: 集合这个词应该比较耳熟,大多数人没接触代码前就学过了.回想一下你的高一数学课本上是不是出现过这个词,就在第一章,概念如下: 一般地,我们把研究的对象统称为元素,把一些元素组成的总体叫作集合. 你看,集合,元素,是不是与今天我们学习的数据结构相通呢? 一.什么是集合 集合是由一组无序且唯一(不能重复)的元素组成.数

  • JS使用reduce()方法处理树形结构数据

    JS使用reduce()方法处理树形结构数据

    定义 reduce() 方法对数组中的每个元素执行一个由您提供的reducer函数(升序执行),将其结果汇总为单个返回值. reduce() 与forEach().map().filter()这些方法一样,也会对数组中的每一项进行遍历,但是reduce() 可以将遍历的前一个数组项产生的结果与当前遍历项进行运算. 语法 array.reduce(function(prev, cur, index, array){ ... }, init); 回调函数中的参数: prev 必需.表示调用回调时的返

  • js实现无限层级树形数据结构(创新算法)

    由于做项目的需要,把一个线性数组转成树形数组,在网上查了很多文章,觉得他们写的太复杂了,于是自己写了一个,在折腾了一下午终于把它写出来啦(激动.gif),用两个filter过滤器就搞定了,代码简洁明了,数据结构小白都能看懂. js代码:把扁平数据转成树形数据 function setTreeData(source){ let cloneData = JSON.parse(JSON.stringify(source)) // 对源数据深度克隆 return cloneData.filter(fat

  • JavaScript中的Map数据结构详解

    JavaScript中的Map数据结构详解

    目录 1. 什么是 Map 2. Map 构造函数 2.1) 数组 2.2) Set 2.3) Map 3. Map 的实例属性和方法 3.1) Map 的属性 size 3.2) Map 的方法 set get has delete clear forEach 4. Map的注意事项 5. Map的使用场景 总结 1. 什么是 Map Map 就是映射的意思,即从键到值的映射. Map 保存键值对,并且能够记住键的原始插入顺序. 那么它和 Object 有什么区别 ? 对象一般用字符串作键 c

  •  JavaScript 数据结构之散列表的创建

     JavaScript 数据结构之散列表的创建

    目录 一.什么是散列表 二.创建散列表 1.创建散列函数 2.put 方法 3.get 方法 4.delete 方法 三.使用散列表 四.总结 散列表与字典基本一致,区别是字典存储的 key 是字符串,而散列表是一个数值(哈希值). 到底如何理解散列表呢?下面进入正题. 一.什么是散列表 散列表,也叫做哈希表,可以根据键(Key)直接访问数据在内存中存储的位置. 简单来说,散列表就是字典的另一种实现,它的优势是比字典能更快地找到一个值.在常规的字典操作中,使用get()方法获得一个值,需要遍历整

  • JavaScript 数据结构之集合创建(2)

    目录 前言 一.集合运算 1.并集 2.交集 3.差集 4.子集 二.使用集合运算 三.总结 前言 上一篇JavaScript 数据结构 之集合创建(1)我们介绍了什么是集合,并且手动实现了一个集合的类.简单总结,集合就是一组元素唯一,并且没有顺序的数据集,关键是元素唯一. ES6 提供了原生的集合支持,就是新增的 Set 数据类型.其实在上篇我们几乎已经实现了 Set 的所有功能,如果还不了解集合,请看上篇内容 但是我们也说到,Set 的基本功能中不包含数学运算如 交集,并集,差集,事实上这也

  • JavaScript 数据结构之字典方法

    目录 一.什么是字典 二.创建字典类 1.hasKey 方法 2.set 方法 3.remove 方法 4.get 方法 5.keys, values, keyValues 方法 6.forEach 方法 7.clear, size, isEmpty 方法 三.使用字典 四.总结 前言: 经过上一篇JavaScript 数据结构之集合创建(2)的学习,数据结构的集合部分已经完结了.那么下面我们又要认识一个新的数据结构,它的名字相信你绝不陌生,它就是字典. 这个字典可不是查汉字时用的那个字典.字典

  •  JavaScript 数据结构之散列表的创建(2)

    目录 一.处理散列值冲突 1.分离链接 2.put 方法 3.get 方法 前言: 上一篇我们介绍了什么是散列表,并且用通俗的语言解析了散列表的存储结构,最后动手实现了一个散列表,相信大家对散列表已经不陌生了. 如果还不清楚散列表,请先阅读上一篇文章:JavaScript 数据结构之散列表的创建(1) 上篇末尾我们遗留了一个问题,就是将字符串转化为散列值后可能出现重复.当以散列值(hash 值)为 key 存储数据时,就会有覆盖已有数据的风险.本篇我们看如何处理散列值冲突的问题,并实现更完美的散

  • Java数据结构之散列表(动力节点Java学院整理)

    Java数据结构之散列表(动力节点Java学院整理)

    基本概念 散列表(Hash table,也叫哈希表),是根据关键字(key value)而直接进行访问的数据结构. 说的具体点就是它通过吧key值映射到表中的一个位置来访问记录,从而加快查找的速度. 实现key值映射的函数就叫做散列函数 存放记录的数组就就叫做散列表 实现散列表的过程通常就称为散列(hashing),也就是常说的hash 散列 这里的散列的概念不仅限于数据结构了,在计算机科学领域中,散列-哈希是一种对信息的处理方法,通过某种特定的函数/算法(散列函数/hash()方法)将要检索的

  • Java数据结构之散列表详解

    Java数据结构之散列表详解

    目录 介绍 1 散列表概述 1.1 散列表概述 1.2 散列冲突(hash collision) 2 散列函数的选择 2.1 散列函数的要求 2.2 散列函数构造方法 3 散列冲突的解决 3.1 分离链接法 3.2 开放定址法 3.3 再散列法 4 散列表的简单实现 4.1 测试 介绍 本文详细介绍了散列表的概念.散列函数的选择.散列冲突的解决办法,并且最后提供了一种散列表的Java代码实现. 数组的特点是寻址容易,插入和删除困难:而链表的特点是寻址困难,插入和删除容易.而对于tree结构,它们

  • Javascript数据结构与算法之列表详解

    Javascript数据结构与算法之列表详解

    前言:在日常生活中,人们经常要使用列表,比如我们有时候要去购物时,为了购物时东西要买全,我们可以在去之前,列下要买的东西,这就要用的列表了,或者我们小时候上学那段时间,每次考完试后,学校都会列出这次考试成绩前十名的同学的排名及成绩单,等等这些都是列表的列子.我们计算机内也在使用列表,那么列表适合使用在什么地方呢?不适合使用在什么地方呢? 适合使用在:当列表的元素不是很多的情况下,可以使用列表,因为对列表中的元素查找或者排序时,效率还算非常高,反之:如果列表元素非常多的情况下,就不适合使用列表了.

  • javascript数据结构之多叉树经典操作示例【创建、添加、遍历、移除等】

    javascript数据结构之多叉树经典操作示例【创建、添加、遍历、移除等】

    本文实例讲述了javascript数据结构之多叉树经典操作.分享给大家供大家参考,具体如下: 多叉树可以实现复杂的数据结构的存储,通过遍历方法可以方便高效的查找数据,提高查找的效率,同时方便管理节点数据.javascript的DOM其实就是以多叉树的形式存储的.下面用javascript来实现多叉树的数据结构 1.创造一个节点 数据是以节点的形式存储的: class Node { constructor(data) { this.data = data; this.parent = null;

  • JavaScript数据结构学习之数组、栈与队列

    前言 数据结构就是关系,没错,就是数据元素相互之间存在的一种或多种特定关系的集合. 常用的数据结构有: 数组,队列(queue),堆(heap),栈(stack),链表(linked list ),树(tree),图(graph)和散列表(hash) 本文主要介绍的是数组.栈与队列,下面来一起看看详细的介绍吧. 一.数组 数组是平时使用最常用的数据结构,在JavaScript中数组是动态的分配大小,在这里我不会介绍JavaScript里面数组的所有的方法,而是针对数据结构这个方向谈谈所用到的方法

  • JavaScript数据结构之二叉查找树的定义与表示方法

    本文实例讲述了JavaScript数据结构之二叉查找树的定义与表示方法.分享给大家供大家参考,具体如下: 树是一种非线性的数据结构,以分层的方式存储数据.树被用来存储具有层级关系的数据,比如文件系统中的文件:树还被用来存储有序列表.这里将研究一种特殊的树:二叉树.选择树而不是那些基本的数据结构,是因为在二叉树上进行查找非常快(而在链表上查找则不是这样),为二叉树添加或删除元素也非常快(而对数组执行添加或删除操作则不是这样). 树是n个结点的有限集.最上面的为根,下面为根的子树.树的节点包含一个数

随机推荐