资讯专栏INFORMATION COLUMN

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

免费试用
首页/文章专栏/《Javascript数据结构和算法》笔记-「字典和散列表」

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

wenyiweb / 2142人阅读

摘要：我经常在业务代码中把数据处理成这种字典的数据结构获取的方法哈希表在学习了类之后，我们会学习散列表，也就是哈希表。

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

集合、字典、散列表存储的都是「不重复」的数据结构

集合：我们更关注每一个元素的值，并把其作为主要元素

字典：我们用[键,值]的形式来存储数据

散列表： 跟字典类似，也会是用[键,值]的形式来存储数据

但是「字典」和「散列表」的实现方式略有不同。

字典

字典也称作映射。我觉得这种数据结构，其实在业务代码中的应用很常见。

与Set类似，ES6同样实现了一个Map类，即我们所说的字典

字典的大致骨架

    function Dictionary(){
        var items = {}
    }

    this.set = function(key,value){}
    this.get = function(key){}
    this.delete = function(key){}
    this.has = function(key){}
    this.clear = function(){}
    this.size = function(){}
    this.keys = function(){}  // 将字典所包含的所有键，以一个数组返回
    this.values = function(){}  // 将字典所包含的所有值，以一个数组返回

字典类的实现，十分简单就直接粘贴全部代码了。

我觉得在JS中，对象本身就可以作为字典来使用。我经常在业务代码中把数据处理成这种字典的数据结构

        function Dictionary() {
            var items = {}

            this.has = function ( key ) {
                return items.hasOwnProperty( key )
            }

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

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

            this.get = function ( key ) {
                if ( this.has( key ) ) {
                    return items[ key ]
                } else {
                    return undefined
                }
            }

            this.values = function(){
                return Object.values(items)
            }

            this.keys = function(){
                return Object.keys(items)
            }

            this.clear = function(){
                this.items = {}
            }

            this.size = function(){
                return this.keys().length
            }

            this.getItems = function(){   // 获取items的方法
                return items
            }
        }

        var dictionary = new Dictionary()

        dictionary.set("Gandalf","gandalf@email.com")
        dictionary.set("John","johnsnow@email.com")
        dictionary.set("Tyrion","tyrion@email.com")

        console.log(dictionary.has("Gandalf"))
        console.log(dictionary.size())
        console.log(dictionary.keys())
        console.log(dictionary.values())
        console.log(dictionary.get("Tyrion"))
        dictionary.delete("John")
        console.log(dictionary.keys())
        console.log(dictionary.values())
        console.log(dictionary.getItems())
哈希表

在学习了Dictionary类之后，我们会学习散列表，也就是哈希表。它是Dictionary类的另外一种实现方式

我在读到这里时，对于「字典」和「哈希表」2个慨念之间的区别还没弄清，当然书中也没有太多解释。

所以这里，我写记录一下自己查阅资料后的个人理解

「字典」指的是Key-Value这种存储数据的结构

那么哈希表也是字典，但是它是用另外的一种实现方式来做的。

那么我们我为什么要使用这种方式来实现「字典」呢，是不是字典存在某种缺点呢？

是的，比如说这样的一组字典数据

k1, k2, k3, k4, k4 ....
v1, v2, v3, v4, v5 ....

当你输入key，命令电脑查询key对应的value时，电脑其实是没法立刻找到key所对应的value呢

看上去是直接根据key得到value，但实际上电脑还是需要遍历k1、k2、k3去比较kn是否等于key。如果是的话就取出对应的值

那么为了省去这个遍历的过程，才想到用哈希表来实现「字典」

哈希表利用数组实现「字典」这种数据结构，那么用数组来实现字典的话，用户传入的key对应哪个索引呢？所以我们需要一个「散列算法」

「散列算法」，可以求出这个key在数组里对应的位置，用哈希表实现的目的就是尽可能快地在字典中找到一个值。

function HashTable(){
    let table = []

    // 散列算法
    var loseloseHashCode = function(key){
        var hash = 0;
        for(var i = 0 ; i
哈希表的key值冲突

我们哈希表的散列算法，是为求出用户传入的key所对应的一个索引


那么这个索引是有可能重复的，一旦重复就会导致后面的值覆盖前面的值。


这种情况，叫做哈希表的冲突。所以我们了解2种处理冲突的方法原理



分离链接: 把数组的每一个元素都实例成链表结构。这样key相同的值，也可以用单链表的形式不断存储。不会覆盖


线性探查: 当用散列算法求出的这个索引index重复时，就index++，直到index不重复为止。


实现更好的散列函数

之前实现的"lose lose"散列函数，用来求值其实是非常容易产生key冲突的。


如果经常冲突的话，那么插入和查询一个元素的时间就会变慢(性能变差)


所以一个优秀的散列算法，应该是可以尽可能少出现冲突的


这里给出一个比较好的社区的实现。至于为什么这种算法,可以减少冲突我也不太理解，


可能是hash是质数，然后质数*33,最后在跟1013取模的话，不太会产生一样的余数，这个感觉是数学问题。


var djb2HashCode = function(key){
    var hash = 5381

    for(var i = 0 ; i < key.length ; i++){
        hash = hash*33 + key.charCodeAt(i)
    }

    return hash % 1013
}



简单回顾一下，集合、字典、哈希表吧


首先他们的元素都是不重复的



集合： 是无序的，[value value]的形式的一组数据结构


字典： 是由一对对 [key-value] 组成的数据结构


哈希表： 是字典的另外一种实现方式，优点在于可能更快的根据key取到value



记录一下书中没搞清楚的小疑问：


《javascript数据结构和算法》中多次提到「顺序数据结构」和「非顺序数据结构」的慨念，并表示

- 「顺序数据结构」：栈、队列、数组、链表、集合
- 「非顺序数据结构」: 散列表 、 树

可是我觉得链表、集合是无序的，数组是有序的呀

这个「顺序数据结构」似乎并不是指的在内存中存储形式。问题先记下，回头再查把
专线服务 服务器托管 字典匹配算法 字典学习算法 字典压缩算法 字典优化算法

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

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

相关文章

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

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

    zorro 评论0 收藏0

  • CSS技巧

    摘要：技巧使你的更加专业这是上关于技巧的一篇译文，另外你也可以在本项目看到原文。列举了一些很实用的技巧，比如给空内容的标签添加内容，逗号分隔列表等等。排序算法看源码，把它背下来吧排序算法的封装。主要帮助初学者更好的掌握排序算法的实现。 成为专业程序员路上用到的各种优秀资料、神器及框架 成为一名专业程序员的道路上，需要坚持练习、学习与积累，技术方面既要有一定的广度，更要有自己的深度。 Java...

    DangoSky 评论0 收藏0

  • CSS技巧

    摘要：技巧使你的更加专业这是上关于技巧的一篇译文，另外你也可以在本项目看到原文。列举了一些很实用的技巧，比如给空内容的标签添加内容，逗号分隔列表等等。排序算法看源码，把它背下来吧排序算法的封装。主要帮助初学者更好的掌握排序算法的实现。 成为专业程序员路上用到的各种优秀资料、神器及框架 成为一名专业程序员的道路上，需要坚持练习、学习与积累，技术方面既要有一定的广度，更要有自己的深度。 Java...

    zgbgx 评论0 收藏0

  • CSS技巧 - 收藏集 - 掘金

    摘要：笔者作为一位，将工作以来用到的各种优秀资料神器及框架整理在此，毕竟好记性不如烂键盘，此前端知识点大百科全书前端掘金，，不定期更新技巧前端掘金技巧，偶尔更新。计算数组的极值技巧使你的更加专业前端掘金一个帮你提升技巧的收藏集。 CSS 样式画各种图形 - 前端 - 掘金下面是一些我在 CSS 中经常用到的图案，还有一些是在css-tricks看到的。记录一下，以后会用到。会持续更新… 一、...

    Jonathan Shieber 评论0 收藏0

  • CSS技巧 - 收藏集 - 掘金

    摘要：笔者作为一位，将工作以来用到的各种优秀资料神器及框架整理在此，毕竟好记性不如烂键盘，此前端知识点大百科全书前端掘金，，不定期更新技巧前端掘金技巧，偶尔更新。计算数组的极值技巧使你的更加专业前端掘金一个帮你提升技巧的收藏集。 CSS 样式画各种图形 - 前端 - 掘金下面是一些我在 CSS 中经常用到的图案，还有一些是在css-tricks看到的。记录一下，以后会用到。会持续更新… 一、...

    SHERlocked93 评论0 收藏0

发表评论

登陆后可评论

0条评论

wenyiweb

男|高级讲师
我要私信

TA的文章

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