Hash Tables (Cousera Data Structure Week 4) - 機械学習エンジニアの備忘録

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

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

Week4の内容はHash Tablesです。

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

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

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

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

f:id:rikeiin:20180503183048p:plain

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

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

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

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

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

f:id:rikeiin:20180505224216p:plain

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

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

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

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

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

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

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