「みんなのデータ構造」で学ぶデータ構造 〜 ChainedHashTable

「みんなのデータ構造」でプログラミングで使うデータ構造を学ぶ

「みんなのデータ構造」(Amazonリンク)とは、コンピュータ・サイエンスの基礎となるデータ構造の教科書「Open Data Structure」の日本語訳です。Introduction to Algorithmsといったアルゴリズムの名著への橋渡しになるような、実用的なテーマが丁寧に説明されています。

この本でデータ構造を学ぶ意義は、訳者まえがきで以下のように説かれています。

1. ソフトウェアのほとんどはシンプルなデータ構造の組み合わせでできている。
2. 「みんなのデータ構造の内容がだいたいわかれば、いいエンジニアになれる。

また、わからない部分は読み飛ばしていいとも書かれています。さらに嬉しいことに、この書籍の中でも実務や学術研究で頻繁に登場する内容がピックアップされています。

• 配列: ArrayStack・ArrayQueue・ArrayDeque
• 連結リスト: SLList(Singly-Linked List)・DLList(Doubly-Linked List)
• チェイン法を使ったハッシュテーブル: ChainedHashTable 👈 この記事
• 二分木・二分探索木: BinaryTree・BinarySearchTree
• 赤黒木: RedBlackTree
• 二分ヒープ: BinaryHeap
• ソート: MergeSort・QuickSort
• グラフの探索: 幅優先探索・深さ優先探索

書籍のサンプルコードはC++ですが、何か1つプログラミング言語を知っていれば問題なく読み進めることができます。

弁護士ドットコムでは、エンジニア有志で本書の輪読会をしています。この本の内容をマスターして、競技プログラミングに挑戦するぞ！

この記事は、「ArrayStack、ArrayQueue、ArrayDeque」のまとめです。

ChainedHashTableの感想・考察

• Hashという単語は「不可逆的な潰し方をする」イメージ（ex. ハッシュドポテトはジャガイモを潰して揚げる料理）

  • ある値をHash関数で別の値に変換する

• Hash関数の性能が優れていると、追加、取得、削除はO(1)になる。

  • 逆に、性能が悪いと最悪O(n)になりうる
  • このため、効率的なHash関数について研究がされている

• Mapはキーとバリューが1対1に対応するデータ構造

  • MapとChainedHashTableの関係は、ChainedHashTableはMap（USetインターフェース）の実装方法の1つ
  • 実際、JavaのChainedHashtableクラスはMapインターフェースを実装している

コンピュータ・サイエンスの基礎を学びたい方や、競技プログラミングにチャレンジする方に「みんなのデータ構造」(Amazonリンク)はおすすめです。

ChainedHashTableの定理

ChainedHashTableはUSetインターフェースを実装する。resize()のコストを無視すると、ChainedHashTableにおけるadd(x)、remove(x)、find(x)の期待実行時間はO(1)である。

array<List> t;
int n;

• xのハッシュ値はhash(x)
• リストt[i]は n <= t.length を満たす

add - O(1)

xをリストt[i]に追加する。

bool add(T x) {
  // 同じ値があったらfalseを返す
  if (find(x) != null) return false;
  // リストが満杯だったらリストをresizeする
  if (n+1 > t.length) resize();

  t[hash(x)].add(x);
  n++;
  return true;
}

remove - $O(n_{hash(x)})$

要素の削除。リストの長さをt[i]とすると計算量は$O(n_{hash(x)})$である。

T remove(T x) {
  int j = hash(x);

  for (int i = 0; i < t[j].size(); i++) {
  	T y = t[j].get(i);
  	if (x == y) {
  		t[j].remove(i);
  		n--;
  		return y;
  	}
  }

  return null;
}

find - $O(n_{hash(x)})$

t[hash(x)]を線形に探索する。

T find(T x) {
	int j = hash(x);

	for (int i = 0; i < t[j].size(); i++) {
		if (x == t[j].get(i)) {
			return t[j].get(i);
		}
	}

	return null;
}

計算量

優れたhash関数は、ハッシュテーブルの計算量をO(n/t.length) = O(1)にする。