欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

散列(hashtable)的javascript实现

程序员文章站 2022-03-15 19:39:20
...

起因

最近在看《数据结构与算法--javascript描述》,然后上npmjs.org去搜索,想找合适的库参考并记录下来,以备以后用时能拿来即用,最没有发现很合自己意的,于是就决定自己一一实现出来。

npmjs相关库

  • hashtable 以C++插件方式实现;

  • simple-hashtable 代码风格非常值得借鉴,以单链表实现开链法来解决碰撞。

编程思路

  • 以链表来解决实现开链法来解决碰撞,并使用自己写的单链表库LinkedList;

  • 用裸对象来存储;

  • ValuePair简单封装键值对;

  • 以模块模式组织代码;

自己的实现

valuePair.js

(function(){
    "use strict";

    function ValuePair(key, value){
        this.key = key;
        this.value = value;
    }

    ValuePair.prototype.toString = function(){
        return "[" + this.key + ":" + this.value + "]";
    };

    module.exports = ValuePair;

})();

hashtable.js

(function(){

    "use strict";

    var ValuePair = require("./lib/ValuePair");
    var LinkedList = require("./LinkedList");

    function Hashtable(){
        this.table = Object.create(null);
        this._size = 0;
    }

    Hashtable.prototype.isEmpty = function(){
        return this._size === 0;
    };

    Hashtable.prototype.size = function(){
        return this._size;
    };

    Hashtable.prototype.remove = function(key){
        var index = hashCode(key);

        if(this.table[index] == null){
            return false;
        }else{
            var currNode = this.table[index].getHead();
            while(currNode.next){
                currNode = currNode.next;
                if(currNode.element.key == key){
                    this.table[index].remove(currNode.element);
                    this._size--;
                    return true;
                }
            }
            return false;
        }
    };

    Hashtable.prototype.get = function(key){
        var index = hashCode(key);

        if(this.table[index] == null){
            return null;
        }else{
            var currNode = this.table[index].getHead();
            while(currNode.next){
                currNode = currNode.next;
                if(currNode.element.key == key){
                    return currNode.element;
                }
            }
            return null;
        }
    };

    Hashtable.prototype.put = function(key, value){
        var index = hashCode(key);

        if(this.table[index] == null){
            this.table[index] = new LinkedList();
        }

        var currNode = this.table[index].getHead();
        while(currNode.next){                       //key若已经存在,修改value值为新值
            currNode = currNode.next;
            if(currNode.element.key == key){
                currNode.element.value = value;
                break;
            }
        }

        if(currNode.next == null && currNode.element.value != value){                  //key不存在,加入新值.注意边界值
            this.table[index].add(new ValuePair(key,value));
            this._size++;
        }

        return this;
    };

    Hashtable.prototype.display = function(){
        for(var key in this.table){
            var currNode = this.table[key].getHead();
            while(currNode.next){
                currNode = currNode.next;
                console.log(currNode.element.toString());
            }
        }
    };


    /*********************** Utility Functions ********************************/

    function hashCode(key) {                //霍纳算法,质数取37
        var hashValue = 6011;
        for (var i = 0; i < key.length; i++) {
            hashValue = hashValue * 37 + key.charCodeAt(i);
        }
        return hashValue % 1019;
    }

    module.exports = Hashtable;

})();

源代码地址

https://github.com/zhoutk/js-data-struct
http://git.oschina.net/zhoutk/jsDataStructs