阅读 3

数据结构-字典

前言

日常生活中我们经常会遇到查询的问题,在前面我们用到的大都是线性结构的数据结构存储数据,我们是否需要遍历线性结构来达到查找目的,这样显然是很不合理的。想必都用过字典,我们查找字得时候,只需要根据索引来查找,又快又准,我们依照字典创建一个索引结构,只需要根据关键字key来找到对应的内容(一一映射的关系),我们称之为字典。

字典特征

是根据关键码值 (Key-Value) 而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。哈希表的实现主要需要解决两个问题,哈希函数和冲突解决。

代码实现

var Dictionary = function(){
    let 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){
        return items[key]
    }
    this.keys = function(){
        return Object.keys(items)
    }
    this.getItems = function(){
        return items;
    }
}
复制代码

此结构的实现比较简单,就不一一介绍了。接下来介绍和字典相关散列表(又称哈希表)是怎么一回事。

散列表(哈希表)

何为哈希表?先举个例子,比如电话谱保存姓名,我们需要将姓名保存在字典里,键值对的key如何设置,让key呈现一定规律,方便比较,利于查询,同时不能重复。这里就得用到哈希算法,通过 ascii 码 计算不同的hash值(也称为散列值,一个16进制的数)来设置不同key.而这样的一个表就是所谓的哈希表。

哈希算法

哈希算法有两种实现方式。

  • loseloseHashCode算法(宽松算法)
  • djb2HashCode算法 loseloseHashCode算法:
var loseloseHashCode = function(key){
    let hash = 0;
    for(let i=0; i< key.length; i++){
        hash += key[i].charCodeAt();
    }
    return hash%37;
}
复制代码

此算法说白了就是所有字符的 ascii 码的和取余,这个算法简单明了,但是不可避免出现哈希值相同的问题(例如Donie和Ana就一样),会造成值覆盖,这就是所谓的散列冲突,如何解决这个问题,这里有两种解决方案。

1、分离链式法:

在相同哈希值地址,创建一个链表,将hash值相同的数值依次存放在链表中,这样,查找的顺序就分两步,先找到哈希地址,然后在链表中查询信息。这样就能避免值覆盖的问题了。 缺点: 查询的效率并不是很高。

/**
 * 分离链接法
 * 缺点:牺牲了查找的便捷性
 */
 var HashTable_L = function(){
    var table = [];  
    var Node = function(key, value){
        this.key = key;
        this.value = value;
    }
    var loseloseHashCode = function(key){
        let hash = 0;
        for(let i=0; i< key.length; i++){
            hash += key[i].charCodeAt();
        }
        return hash%37;
    }

    this.put = function(key, value){
        let position = loseloseHashCode(key);
        if(table[position]){
            table[position].append(new Node(key, value));
        }else{
            let l = new LinkedList();
            table[position] = l;
            table[position].append(new Node(key, value));
        }
    }
    // 查找
    this.get = function(key){
        let position = loseloseHashCode(key);
        if(table[position]){
            let current = table[position].getHead();
            // 链表遍历
            while(current){
               if(current.element.key == key){
                   return current.element.value
               }  
               current = current.next;
            }
        }else{
            return undefined;
        }
    }
    this.remove = function(key){
        let position = loseloseHashCode(key);
        if(table[position]){
            let current = table[position].getHead();
            while(current){
                if(current.element.key == key){
                    table[position].remove(current.element);
                    // 当链表为空的时候,链表清空
                    if(table[position].isEmpty()){
                        table[position] = undefined;
                    }
                    return true;
                }
                current = current.next;
            }
        }else{
            return false;
        }
    }
}
复制代码

2、线性探测: 当出现哈希地址相同的情况,后面出现的在原有hash值上加1,能够避免hash不重复。 缺点:添加很麻烦,每次都得比较,比如多个相同hash值的字符,就得不断的往后查询加1.

/**
 * 线性探查法
 */
var HashTable_X = function(){
    var table = [];
    var Node = function(key, value){
        this.key = key;
        this.value = value;
    }
    var loseloseHashCode = function(key){
        let hash = 0;
        for(let i=0; i< key.length; i++){
            hash += key[i].charCodeAt();
        }
        return hash%37;
    }
    this.put = function(){
        let position = loseloseHashCode(key);
        if(table[position] == undefined){
            table[position] = new Node(key, value);
        }else{
            // 这个位置已经被占据
            let index = position+1;
            while(table[index] !== undefined){
                index++;
            }
            table[index] = new Node(key, value);
        }
    }

    this.get = function(key){
        return items[loseloseHashCode(key)].element.value;  
    }
}

复制代码

上面两种方法,都有不尽人意的地方,有没有更好的方式,一步到位,不同的字符的hash码一定不相同,下面djb2HashCode算法就是解决这个问题的。

   /**
    * djb2HashCode函数彻底解决冲突,hash数不重复 
    */
    var djb2HashCode = function(key){
        var hash = 5381;
        for(let i = 0; i < key.length; i++){
            hash = hash*33 + key[i].charCodeAt();
        }
        return hash % 1013;
    }
复制代码

至于这个算法的具体参数怎么来的,请参考地址,有兴趣看看。

关注下面的标签,发现更多相似文章
评论