👻

データ構造②　ハッシュテーブル(Hash Tables)

2024/03/17に公開

アルゴリズムとデータ構造

ハッシュテーブルとは

ハッシュテーブルとは、データをキー(key)と対応する値(value)によって管理するデータ構造である。
キーをハッシュ関数によってハッシュ値を計算することで、データの検索を効率的に行うことができる。

javascriptではobject、pythonではdictionaryと呼ばれている。

// key: 名前, value: 年齢
var hashTable = {
    'suzuki': 22,
    'tanaka': 21
};

console.log(hashTable['suzuki']); // 22

この書き方でもいい。

var hashTable = {};
hashTable['suzuki'] = 22;
hashTable['tanaka'] = 21;

console.log(hashTable['suzuki']); // 22

実装

ハッシュテーブルの実装は以下のように書くことができる。
ただしハッシュ関数は簡単なものを実装しており、ハッシュ値が重複する可能性もあるため、その他の重複がなく計算が簡単なハッシュ関数を用いるのが理想。

get関数では、ハッシュ値が被ってしまい、あるハッシュ値に複数の値が格納されている場合でも、値の取り出しができるように実装されている。

class HashTable {
    // 初期化
    constructor(size){
        this.data = new Array(size);
    }

    // ハッシュ関数
    _hash(key) {
        let hash = 0;
        for (let i = 0; i < key.length; i++){
            hash = (hash + key.charCodeAt(i) * i) % this.data.length
        }
        return hash;
    }

    // データの追加
    set(key, value) {
        let address = this._hash(key);
        if (!this.data[address]) {
          this.data[address] = [];
        }
        this.data[address].push([key, value]);
        return this.data;
    }

    // データの取得
    get(key){
        const address = this._hash(key);
        const currentBucket = this.data[address]
        if (currentBucket) {
            for(let i = 0; i < currentBucket.length; i++){
                if(currentBucket[i][0] === key) {
                    return currentBucket[i][1]
                }
            }
        }
        return undefined;
    }
}

それぞれの操作の計算量

それぞれの操作にかかる計算量は以下。ただし、lookupは特定のデータを検索する操作。
ハッシュテーブルの利点は、データの検索や追加、削除を高速に行える点である。
また、keyやvalueにさまざまなデータの型を用いることもできる。

欠点としては、ハッシュ値のためのメモリが必要となるためデータセットが大きい場合メモリ使用量が問題になる場合があること、データを順序立てて整理することが難しいことなどが挙げられる。

操作	計算量
search	O(1)
lookup	O(1)
insert	O(1)
delete	O(1)

参考webサイト

このUdemyの講座を参考にしています。

ハッシュテーブルとは

実装

それぞれの操作の計算量

参考webサイト

Discussion