资讯专栏INFORMATION COLUMN

上云采购季！| 爆款云服务器低至4.6元/月，首单享0.9折

免费试用
首页/文章专栏/js数据结构和算法（五）字典和散列（hash）

js数据结构和算法（五）字典和散列（hash）

Hegel_Gu / 1907人阅读

摘要：哈希表也是种数据结构，它可以提供快速的插入操作和查找操作。一个更好的散列函数为了避免碰撞，首先要确保散列表中用来存储数据的数组其大小是个质数，这和计算散列值时使用的取余运算有关。散列函数将学生里的数字相加，使用函数计算出散列值。

什么是字典结构？

字典是以键值对形式存储数据的数据结构，就像电话号码薄里的名字和电话号码那样的一一对应的关系。

javascript的Object类就是以这样的一种字典形式设计的。

键值对在字典中以这样的方式标记：d = {key1 : value1, key2 : value2 }。字典中的键/值对是没有顺序的。如果你想要一个特定的顺序，那么你应该在使用前自己对它们排序。

Dictionary类

Dictionary类的基础是Array类，而不是Object类。我们想对字典中的键排序，而在js中是不能对 对象 的属性进行排序的。话虽如此，但在js中一切皆对象，数组也是对象。以下面的代码开始定义Dictionary类：

先来定义add()方法。该方法接受两个参数：键和值。键是值在字典中的索引，代码如下：

function add(key,value){
        this.datastore[key] = value;
}

接下来定义find()方法，该方法以 键 做为参数，返回和其关联的值。代码如下：

function find(key){
         return this.datastore[key];
     }

从字典中删除键-值对 需要使用js中的delete函数。该函数是Object类的一部分，该函数同时删掉键和与其关联的值：

function remove(key){
         delete  this.datastore[key];
     }

最后，我们希望可以显示字典中所有的键-值对，可以使用如下的方法：

function showAll(){
         for(var key in Object.keys(this.datastore)){
             print(key + "->" + this.datastore[key]);
         }
     }
Dictionary类的辅助方法

我们可以定义一些在特定情况下有用的辅助方法。比如要知道字典中的元素个数可以定义一个count()方法，代码如下：

function count(){
         var n=0;
         for(var key in Object.keys(this.datastore)){
             ++n;
         }
         return n;
     }

为什么不使用length属性？这是因为当键的类型为字符串时，length属性就不管用了

还可以定义一个clear清除方法：

function clear(){
         for each(var key in Object.keys(this.datastore)){
             delete  this.datastore[key];
         }
     }
备注：

for each in（IE6，7，8不支持）无法获得对象的属性名，只能获取到属性值。
另外，遍历对象也尽量使用for in 而不是for each，而遍历数组的话还是使用for循环吧

for each in无法获得对象的属性名，只能获取到属性值。

散列（hash） 什么是哈希表？ 
哈希表(Hash table，也叫散列表)，是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

　　哈希表的做法其实很简单，就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。

　　而当使用哈希表进行查询的时候，就是再次使用哈希函数将key转换为对应的数组下标，并定位到该空间获取value，如此一来，就可以充分利用到数组的定位性能进行数据定位

散列表的查找步骤 
当存储记录时，通过散列函数计算出记录的散列地址

当查找记录时，我们通过同样的是散列函数计算记录的散列地址，并按此散列地址访问该记录

在js中，散列函数会将每个键值映射为一个唯一的数组索引。然而，键的数量是无限的，数组的长度是有限的，所以，应该让散列函数尽量将键均匀地映射到数组中。

哈希表也是种数据结构，它可以提供快速的插入操作和查找操作。哈希表运算速度极快，哈希表的速度明显比树快，树的操作通常需要O(N)的时间级。哈希表不仅速度快，编程实现也相对容易。

哈希表算法

哈希表最常见的例子是以学生学号为关键字的成绩表，１号学生的记录位置在第一条，１０号学生的记录位置在第１０条...

如果我们以学生姓名为关键字，如何建立查找表，使得根据姓名可以直接找到相应记录呢？

用上述得到的数值作为对应记录在表中的位置，得到下表：

上面这张表即哈希表。

如果将来要查李秋梅的成绩，可以用上述方法求出该记录所在位置：

李秋梅:lqm 12+17+13=42 取表中第42条记录即可。

HashTable类

我们使用一个类来表示散列表，该类包含计算散列值的方法、向散列中插入数据的方法、从散列表中读取数据的方法、显示散列表中数据分布的方法等。
HashTable类的构造函数定义如下：

function HashTable(){
         this.table = new Array(137);//设定数组长度为137，质数
         this.simpleHash = simpleHash;
         this.showDistro = showDistro;
         this.put = put;
     }

散列函数的选择依赖于键值的数据类型。如果键是整形，最简单的散列函数就是以数组的长度对键取余。

使用一个简单的散列函数做散列:

   load("HashTable.js");
    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

simpleHash()函数通过使用js的charCodeAt()函数，返回每个字符的ASCII码值，然后再将它们相加得到散列值。put方法通过调用simpleHash()函数得到数组的索引，然后将数据存储到该索引对应的位置上。

一个更好的散列函数

为了避免碰撞，首先要确保散列表中用来存储数据的数组其大小是个质数，这和计算散列值时使用的取余运算有关。数组的长度应该在100以上，这是为了让数据在散列表中分布得更均匀

散列化整型键

这里我们使用一个展示学生成绩的数据集，将随机产生一个9位数的键，用以识别学生身份和一门成绩，下面是产生学生数据（包含ID和成绩）的函数：

function getRandomInt(min,max){
    return Math.floor(Math.random()*(max-min+1))+min;
}
function genStuData(arr){
    for(var i = 0;i


使用getRandomInt()函数时，可以指定随机数的最值。genStuData()函数生成学生的数据。里层的循环用来生成学生的ID，紧跟在循环后面的代码生成一个随机的成绩，并把成绩弄在ID的后面。主程序会把ID和成绩分离。散列函数将学生ID里的数字相加，使用simpleHash()函数计算出散列值。


对散列表排序


put方法同时接受键和数据作为参数，对键值散列后，将数据存储到散列表中：



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




put方法将键值散列化后，将数据存储到散列化后的键值对应在数组中的位置上。


从散列表中取值


定义get()方法，用以读取存储在散列表中的数据。该方法同样需要对键值进行散列化，然后才能知道数据存储在数组的什么位置，代码如下：



function get(key){
    return this.table[this.betterHash(key)];
}
云服务器 GPU服务器 js算法和数据结构 js hash 删除数据 字符串hash算法 最快的hash表算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/85444.html

相关文章

  • 学习数据结构与算法之字典和散列表

    摘要：小结实现了字典和哈希表感觉没有想象中那么困难，当然这还是开始。 本系列所有文章：第一篇文章：学习数据结构与算法之栈与队列第二篇文章：学习数据结构与算法之链表第三篇文章：学习数据结构与算法之集合第四篇文章：学习数据结构与算法之字典和散列表第五篇文章：学习数据结构与算法之二叉搜索树 字典 不是新华字典哦，这里的字典也称作_映射_，是一种数据结构，跟set集合很相似的一种数据结构，都可以用来...

    Heier 评论0 收藏0

  • 《JavaScript数据结构与算法》笔记——第7章 字典和散列表

    摘要：在字典中，存储的是键，值，集合可以看作值，值的形式存储元素，字典也称为映射方法描述备注向字典中添加新元素通过某个键值从字典中移除对应的数据值判断某个键值是存在于这个字典中通过键值获取对应的数据值返回字典所有元素的数量删除字典中所有元素将字典 在字典中，存储的是[键，值]，集合可以看作[值，值]的形式存储元素，字典也称为映射 方法 描述 备注 set(key,...

    zorro 评论0 收藏0

  • 《Javascript数据结构和算法》笔记-「字典和散列表」

    摘要：我经常在业务代码中把数据处理成这种字典的数据结构获取的方法哈希表在学习了类之后，我们会学习散列表，也就是哈希表。 《Javascript数据结构和算法》笔记-「字典和散列表」 集合、字典、散列表存储的都是「不重复」的数据结构 集合：我们更关注每一个元素的值，并把其作为主要元素 字典：我们用[键,值]的形式来存储数据 散列表： 跟字典类似，也会是用[键,值]的形式来存储数据 但是「字...

    wenyiweb 评论0 收藏0

  • 每周一练 之 数据结构与算法（Dictionary 和 HashTable）

    摘要：什么是散列表和散列函数哈希表，也叫散列表，是根据关键码值而直接进行访问的数据结构。根据键值从散列表中移除值。请实现散列表将和存在一个对象中即可定义一个包含和属性的类并分配到散列表。 showImg(https://segmentfault.com/img/remote/1460000019005270); 这是第五周的练习题，上周忘记发啦，这周是复习 Dictionary 和 Hash...

    eternalshallow 评论0 收藏0

  • 每周一练 之 数据结构与算法（Dictionary 和 HashTable）

    摘要：什么是散列表和散列函数哈希表，也叫散列表，是根据关键码值而直接进行访问的数据结构。将字典的所有键名以数组的形式返回。根据键值从散列表中移除值。这是第五周的练习题，上周忘记发啦，这周是复习 Dictionary 和 HashTable。 下面是之前分享的链接： 1.每周一练 之 数据结构与算法（Stack） 2.每周一练 之 数据结构与算法（LinkedList） 3.每周一练 之 数据结构...

    ingood 评论0 收藏0

发表评论

登陆后可评论

0条评论

Hegel_Gu

男|高级讲师
我要私信

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<