ハッシュテーブルを学んだ

2021-07-20

ハッシュテーブルを学びました。

ハッシュテーブル

keyとvalueがペアで格納されているデータ構造です。keyを選ぶとペアとなっているvalueが取得できます。例として、引っ越しの荷造りを思い出してください。ダンボールがあったとして、その中に本棚にあった書籍を全部入れます。

完結している漫画を同じ場所にいれておきたいので今回は、進撃の巨人をダンボールに詰めたいと思います。全34巻なので、すべて1つのダンボールに入れてガムテープで閉じます。そしてダンボールに「進撃の巨人」とマジックで書きます。***この時「進撃の巨人」はkeyになり、ダンボールの中に入っている34巻のそれぞれがvalueとなります。***後で引越し先で開封する際に「進撃の巨人」を知っていれば、34巻全てを取り出すことができますね。このようなデータ構造がハッシュテーブルです。

ハッシュ関数

プログラムの場合は「進撃の巨人」というkeyを数字として取り扱わないといけません。この時「進撃の巨人」をハッシュ関数というものに放り込むと適当な数字になって返ってきます。返ってきた数字を使って「進撃の巨人」のダンボールに入っているvalueを探し出すことができます。出力した値はハッシュ値と呼びます。

※ 補足すると適当な数字というのは、あるルールに従って（関数のロジック）ランダムな値を返すということです。

ハッシュ関数の特徴として

入力するまで何が返ってくるかわからない
ただし同じ入力をすると同じ値が返ってくる
出力値だけをみて入力値を求めることはできない

という性質を持ちます。この特徴を暗号化（SHA−256とか）、データが正しいかどうかなどの用途で使われています。

実装

自分は、JavaScriptし書けませんが、まず前提としてJavaScriptでハッシュテーブルを実装することなんてほぼありません。既にObjectやMapがあるのでこれらで機能としては補えます。（ハッシュ値を読み取るなどはあったりしますが。。）

実装したコードはこちらです。

ハッシュ関数は入力した値が常に同じ出力を返す性質があるためそのように実装していきます。文字列をループ処理してcharCodeAtメソッドを使って、UTF-16の数値にしつつ*100をしています。最後にコンストラクタで設定したサイズで割ると実現できます。

 /**
   * ハッシュ関数
   * @param {string} key
   * @return {*} 
   * @memberof HashTable
   */
  hash(key: string) {
    const codeAtNumber = 100
    let id = 0
    for (let i = 0; i < key.length; i++) {
      /** 
       * @see https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/String/charCodeAt
       **/
      id += key.charCodeAt(i) * codeAtNumber
    }
    return id % this.hashTableSize
  }

衝突

ハッシュテーブルのサイズが小さい場合、違うキーを放り込んでも同一の値が返ってきてしまうことがあります。（上書きされる可能性がある）これを衝突と呼びます。解決策としてチェイン法などがあります。今回の実装では以前作成したLinkedListを使って衝突が起こった場合にLinkedListにデータをpushして衝突を避ける実装をしています。

やってみて

codeAtNumberメソッドはほぼ初見でしたので、仕組みを知れてよかったです。機会があれば最強のハッシュ関数でも作ってみたいものです。その時は今回あまり深く学んでいない衝突の解決策を勉強したいです。

次回

次回は木構造を学んでいきます。