## 2015年8月13日木曜日

### JavaScript - Hashing(linear probing, simple dictionary)

• 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)); } ```

``` \$ 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 \$ ```