散列（hashtable）的javascript实现

起因

最近在看《数据结构与算法--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