JavaScriptでハッシュテーブルを作る

JavaScriptオブジェクトのプロパティアクセスにおけるビッグ・オーで書いたようにJavaScriptのオブジェクトは基本ハッシュテーブルであるし、Mapオブジェクトも中の実装はChromeではハッシュテーブルであると書かれてある(Optimizing hash tables: hiding the hash code)。だからJavaScriptで自前のハッシュテーブルを作るというのは必要のないことなのだけど試しに作ってみたかった。

const stringHash = require("string-hash");

module.exports = class MyHashTable {
  constructor(numberOfBucket) {
    this.numberOfBucket = parseInt(numberOfBucket, 10);
    this.hashTable = new Array(this.numberOfBucket);
  }
  get(key) {
    key = '' + key;
    const hashTableIndex = this.getHashTableIndex(key);
    const bucket = this.hashTable[hashTableIndex] || [];
    const bucketLength = bucket.length;
    for (let i=0; i<bucketLength; i++) {
      const data = bucket[i];
      if (data[0] === key) {
        return data[1];
      }
    }
  }
  set(key, value) {
    key = '' + key;
    const hashTableIndex = this.getHashTableIndex(key);
    if (!this.hashTable[hashTableIndex]) {
      this.hashTable[hashTableIndex] = [];
    }
    this.hashTable[hashTableIndex].push([key, value]);
  }
  getHashTableIndex(key){
    const hash = stringHash(key);
    return hash % this.numberOfBucket;
  }
}

実装はHow to implement a simple hash table in JavaScript – freeCodeCampやImplementing a hash table in JavaScriptを参考にしている。

string-hashは、与えられた文字列を0から4294967295の数値にして返してくれる。

ハッシュテーブルのサイズは、ハッシュ関数の処理やコンフリクトしたときの対応方法によるらしいのだけど、とりあえずインスタンス作成時に設定するようにして、ハッシュテーブルに入れるデータ数に1.3をかけた値より大きな素数を使うようにした。素数についてはThe Prime Database: The Nth Prime Pageを使って出した。

But a good general “rule of thumb” is:
The hash table should be an array with length about 1.3 times the maximum number of keys that will actually be in the table, and
Size of hash table array should be a prime number
http://cseweb.ucsd.edu/~kube/cls/100/Lectures/lec16/lec16-8.html#pgfId-975583

下記のような感じで簡単に測定してみた。

const dataLength =  10000;
const numberOfBucket = 13003;
const MyHashTable = require('./my-hash-table');
const myHashTable = new MyHashTable(numberOfBucket);
console.time('set');
let key, value;
for (let i=0; i<dataLength; i++) {
  key = Math.floor(Math.random()*dataLength).toString(16);
  value = Math.floor(Math.random()*dataLength).toString(16);
  myHashTable.set(key, value);
}
console.timeEnd('set');
console.time('get');
myHashTable.get(key);
console.timeEnd('get');

結果が10000件の追加に19.117msで取得に0.067ms。

データを以下のように変更して再度実行

const dataLength =  100000;
const numberOfBucket = 130003;

結果が100000件の追加に112.608msで取得が0.061ms。

データを1000000件にすると追加に1592.088msで取得に0.068ms。データの件数が増えても、データの取得に時間がかかるようにはなっていない。いい感じに見える。

なおデータを1000000件でハッシュテーブルのサイズを1（検索にO(n)かかるはず）にしたら、追加には870.672msとなり取得には12.525msかかった（繰り返し測定してみると、早い時は2msくらいで終わる）。

上記の計測をオブジェクトに置き換えて

const dataLength =  1000000;
const myHashTable = {};
console.time('set');
let key, value;
for (let i=0; i<dataLength; i++) {
  key = Math.floor(Math.random()*dataLength).toString(16);
  value = Math.floor(Math.random()*dataLength).toString(16);
  myHashTable[key] = value;
}
console.timeEnd('set');
console.time('get');
myHashTable[key];
console.timeEnd('get');

としてみたろころ、データの追加には1632.026msで、取得には0.008msになった。繰り返し計測してみないと誤差の範囲かどうかは明確には言えないけど、ほぼ同じパフォーマンスのように思う。

さらにMapに置き換えてみた。

const dataLength =  1000000;
const myHashTable = new Map();
console.time('set');
let key, value;
for (let i=0; i<dataLength; i++) {
  key = Math.floor(Math.random()*dataLength).toString(16);
  value = Math.floor(Math.random()*dataLength).toString(16);
  myHashTable.set(key, value);
}
console.timeEnd('set');
console.time('get');
myHashTable.get(key);
console.timeEnd('get');

データの追加には1178.558msで、取得には0.006msになった。

そのほか参考

以上。