《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.length ; i++){
            hash += key.charCodeAt(i)
        }
        return hash % 37   // 这里37是个随意选择的数值，把余数作为将来存储在数组的索引
    }
    this.put = function(key,value){
        var position = loseloseHashCode(key)
        console.log(position + '-' + key)
        table[position] = value
    }

    this.get = function(key){
        var position = loseloseHashCode(key)
        return table[position]
    }

    this.remove = function(key){
        var position = loseloseHashCode(key)
        table[position] = undefined
    }
}

哈希表的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数据结构和算法》中多次提到「顺序数据结构」和「非顺序数据结构」的慨念，并表示

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

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

这个「顺序数据结构」似乎并不是指的在内存中存储形式。问题先记下，回头再查把