JavaScript 는 간단 한 HashTable 을 패키지 합 니 다.

해시 표 는 검색 속도 가 빠 르 고 분포 가 균일 하 다 는 특징 을 가지 고 있 습 니 다. 해시 표를 배 워 서 간단 한 해시 표 패 키 징 을 실현 하 세 요 ~
/**
 *    HashTable
 *      
 *  put   
 *  get   
 *  remove   
 *  hashFunc     
 *  resize       
 * @constructor
 */

function HashTable () {

    this.storage = [];  //  
    this.limit = 7;     //    
    this.count = 0;     //    

    //HashTable  

    //  
    HashTable.prototype.put = function (key, value) {

        var index = this.hashFunc(key, this.limit)

        var bucket = this.storage[index]

        if (bucket == null) {
            bucket = []
            this.storage[index] = bucket
        }

        var override = false

        for (var i = 0; i < bucket.length ; i++) {

            var tuple = bucket[i]

            if (tuple[0] === key) {
                tuple[1] = value
                override = true
            }
        }

        if (!override) {

            bucket.push([key, value])

            this.count ++
        }

        if (this.count > this.limit * .75) {

            this.resize(this.limit * 2)
        }
    }

    //  
    HashTable.prototype.get = function (key) {

        var index = this.hashFunc(key, this.limit)

        var bucket = this.storage[index]

        if (bucket == null) {

            return null
        }

        for (var i = 0; i < bucket.length; i++) {

            var tuple = bucket[i]

            if (tuple[0] === key) {

                return tuple[1]
            }
        }

        return null
    }

    //  
    HashTable.prototype.remove = function (key) {

        var index = this.hashFunc(key, this.limit)

        var bucket = this.storage[index]

        if (bucket == null) {

            return null
        }

        for (var i = 0; i < bucket.length; i++) {

            var tuple = bucket[i]

            if (tuple[0] === key) {

                bucket.splice(i, 1)

                this.count --

                if(this.limit > 7 && (this.count < this.limit * .25)) {

                    this.resize(Math.floor(this.limit / 2))
                }

                return tuple[1]

            }
        }
        return null

    }

    //    
    HashTable.prototype.resize = function (newLimit) {

        var oldStorage = this.storage

        this.storage = []
        this.limit = newLimit
        this.count = 0

        for (var i = 0; i < oldStorage.length ; i++) {

            var bucket = oldStorage[i]

            if (bucket == null) {

                continue
            }

            for (var j = 0; j < bucket.length; j++) {

                var tuple = bucket[j]

                this.put(tuple[0], tuple[1])
            }

        }

    }


    //    
    HashTable.prototype.hashFunc = function (str, size) {

        var hashCode = 0

        for (var i = 0; i < str.length; i++) {

            hashCode = 37 * hashCode + str.charCodeAt(i)
        }

        var index = hashCode % size

        return index;
    }
}

var a = new HashTable();

a.put("cat", " ");
a.put("dog", " ");
a.put("egg", " ");

a.put("dogss", " sd");
a.put("eggss", " s");
a.put("eggsssd", " sds");

console.log(a);


a.remove("eggsssd");
a.remove("dogss");
a.remove("eggss");
a.remove("egg");
a.remove("dog");



console.log(a);







좋은 웹페이지 즐겨찾기