ソフトウェアエンジニアを目指す人のブログ

ソフトウェアエンジニアになるために勉強したことを書いていきます

Hash Tables (Cousera Data Structure Week 4)

CouseraのData Strucureコースのweek4の内容です。
www.coursera.org

前回のweek3の内容の記事はこちら
rikeiin.hatenablog.com

Week4の内容はHash Tablesです。

Hashingの応用例

IP Addresses

あるWebサーバにアクセスしてきた各IPアドレスが過去一定期間にアクセスがあったか判定するという問題を考える。

単純に配列を使った実装の場合、考えうるIPアドレス数の長さの配列を用意し、該当するIPアドレスに対応するインデックスの要素をインクリメントする方法がある。
このとき、

  • アクセスリストを更新する操作は(UpdateAccessList)は一つのログにつきO(1)
  • 一定期間にアクセスがあったか判定する操作(AccessedLastHour)はO(1)
  • IPv4でも2の32乗のメモリが必要
  • IPv6では2の128乗であり、もはやメモリに乗らない

配列を使った実装はメモリを多く消費するため、リストを使った実装を考える。

List-based Mapping

過去一定期間にアクセスしてきたIPアドレスのみをリストに保存する。
このとき、アクセス順にリストにつなげていく。

f:id:rikeiin:20180503183048p:plain

  • nは一定期間にアクセスがあったIPアドレスの数
  • メモリ消費量は\Theta (n)
  • L.Append, L.Top, L.Popは\Theta (1)
  • L.Find, L.Eraseは\Theta (n)
  • UpdateAccessListは\Theta (n)
  • AccessedLastHourは\Theta (n)

Hash Functions

ハッシュ関数の定義

あるオブジェクトの集合\mathcal Sm>0となる整数があるとき、関数h: \mathcal S \rightarrow \{0, 1,\dots, m-1\}ハッシュ関数と呼ぶ。

このとき、mハッシュ関数hの基数(cardinality)と呼ぶ。

ハッシュ関数の望ましい要件

  • hの計算が早い
  • 異なるオブジェクトには異なる値
  • メモリ使用量がO(m)でマップできる
  • 基数mは小さくしたい
  • もしオブジェクトの数|\mathcal S|mより大きいとき、すべてを異なる値にマップすることは不可能である

Collisions

h(o_1)=h(o_2)かつo_1\neq o_2のとき、これを衝突(collision)と呼ぶ。

Chaining

Map

マップはあるオブジェクトからあるオブジェクトへのマッピングを行う。
例えば、以下のような例がある。

  • ファイル名→ディスク上のファイルの場所
  • 学生ID→学生名
  • 契約名→契約電話番号

\mathcal Sから\mathcal VへのマップはHashKey(O), Get(O), Set(O, v)の操作を持つデータ構造である。このとき、O\in S, v \in V

Chaining

f:id:rikeiin:20180505224216p:plain

マップに関する各操作の疑似コードを以下に示す。

f:id:rikeiin:20180505225558p:plain
f:id:rikeiin:20180505225620p:plain
f:id:rikeiin:20180505225641p:plain

  • Aの最大のチェインの長さをcとすると、HashKey, Get, Setの時間計算量は\Theta(c+1)
    • c=0のときO(1)
  • nを現在のマップの異なるキーOの数、mハッシュ関数の基数とするとメモリの消費量は\Theta(n+m)

Hash Tables

Set

SetはAdd(O), Remove(O), Find(O)の操作を持つデータ構造である。
chainingを使ったSetの実装方法は二通りある。
f:id:rikeiin:20180505233025p:plain

  • SetはSからV=\{true, false\}へのマップと等しい
  • (O, v)のペアを保存する代わりにOのみを保存する

Setに対する各操作の疑似コードを以下に示す。

f:id:rikeiin:20180505233025p:plain
f:id:rikeiin:20180505233046p:plain
f:id:rikeiin:20180505233204p:plain

SetもしくはMapを用いたhashingの実装をHash tableと呼ぶ。

プログラミング言語では以下のようなクラスに実装されている。

まとめ

  • Chainingはhash tableを実装するためのテクニックのひとつである
  • メモリ消費量はO(n+m)
  • 各操作の時間計算量はO(c+1)
  • どのようにmとcの両方を小さくするか?