JavaScript - Hashing(linear probing, simple dictionary)

Data Structures and Algorithms With Javascript
(O'Reilly Media)
Michael McMillan(著)

開発環境

• OS X Yosemite - Apple (OS)
• Emacs (Text Editor)
• JavaScript (プログラミング言語)
• SpiderMonkey, Node.js(V8) (JavaScript engine)

Data Structures and Algorithms With Javascript (Michael McMillan(著)、O'Reilly Media)のChapter 8(Hashing)、Exercises 1.(No. 5324)を解いてみる。

Exercises 1.(No. 5324)

JavaScript(Emacs)

/*jslint         browser : true, continue : true,
  devel  : true, indent  : 4,    maxerr   : 50,
  newcap : true, nomen   : true, plusplus : false,
  regexp : true, sloppy  : true, vars     : false,
  white  : true
*/

/*global print, read, readline */
var HashTable,
    dictionary,
    word_def,
    words,
    word,
    i,
    max;

HashTable = function () {
    this.table = new Array(137);
    this.values = [];
};
HashTable.prototype = {
    constructor: HashTable,
    betterHash: function (string) {
        var H = 31,
            total = 0,
            i,
            max;

        for (i = 0, max = string.length; i < max; i += 1) {
            total += H * total + string.charCodeAt(i);
        }
        total = total % this.table.length;
        if (total < 0) {
            total += this.table.length + 1;
        }
        return parseInt(total, 10);
    },
    showDistro: function () {
        var i,
            max;

        for (i = 0, max = this.table.length; i < max; i += 1) {
            if (this.table[i] !== undefined) {
                print(i + ': ' + this.table[i]);
            }
        }
    },
    put: function (key, data) {
        var pos = this.betterHash(key);
        
        if (this.table[pos] === undefined) {
            this.table[pos] = key;
            this.values[pos] = data;
        } else {
            while (this.table[pos] !== undefined) {
                pos += 1;
            }
            this.table[pos] = key;
            this.values[pos] = data;
        }
    },
    get: function (key) {
        var hash = -1,
            i;
        
        hash = this.betterHash(key);           
        if (hash > -1) {
            for (i = hash; this.table[hash] !== undefined; i += 1) {
                if (this.table[i] === key) {
                    return this.values[hash];
                }
            }
        }
        return undefined;
    }
};

dictionary = new HashTable();
words = read('words.txt').split('\n');
for (i = 0, max = words.length; i < max; i += 1) {
    word_def = words[i].split(',');
    if (word_def.length === 2) {
        dictionary.put(word_def[0].trim(), word_def[1].trim());
    }
}

while (true) {
    word = readline();
    if (word === 'quit') {
        break;
    }
    print(dictionary.get(word));    
}

出力結果(Terminal, shell, SpiderMonkey)

$ jslint sample1.js

sample1.js is OK.
$ js sample1
word1
definition1
word5
definition5
word2
definition2
quit
$ cat words.txt
word1, definition1
word2, definition2
word3, definition3
word4, definition4
word5, definition5
$