メモログ

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になった。

そのほか参考

• https://www.quora.com/What-is-a-good-hash-table-array-size
• http://srinvis.blogspot.com/2006/07/hash-table-lengths-and-prime-numbers.html
• https://en.wikipedia.org/wiki/Hash_table

以上。