Subscribed unsubscribe Subscribe Subscribe

SE Can't Code

A Tokyo based Software Engineer. Not System Engineer :(

Hashテーブル

前回記事のWebクローラーの勉強の続きとして、効率的な検索のための簡単なハッシュテーブルの実装を行う。Webクローラーで取得したweb上の文字を単にリストへ格納した場合、検索をかけるとリストの頭からループを行う必要があり、処理時間がかかってしまうため、キー(key)を用いて対応する要素(value)を取得するデータ構造とし、高速な検索を実現する。
ハッシュテーブルとはなんぞやという話は以下参照。

ハッシュテーブルではキーから一定の計算手順により固定長の整数値などに単純化された値を求め、これを添字として配列に値を格納・取得する。この計算手順をハッシュ関数、単純化された値をハッシュ値と呼ぶ。異なるキーから同じハッシュ値が得られることがあるため、配列の各要素はそれ自体が配列やリストになっており、複数の値を格納できるようになっている。
(IT用語辞典より)

Pythonでは組み込み型にディクショナリがあり、簡単かつ高速に実装出来るようになっているが、ハッシュの仕組みを理解するために一から実装を行ってみる。

以下6つの関数から構成されており、それぞれの役割は以下の通りとなる。

① make_hashtable : bucket数を指定し、hashtableを作成する。

② hash_string : hash計算を行い、bucketの位置を出す。

③ hashtabel_get_bucket : hashtable上のbucketを取得する。

④ hashtable_add : hashtableにkeyとvalueを追加する。

➄ hashtable_update : hashtable上にkeyの存在有無を確認し、updateを行う。

➅ hashtable_lookup : hashtable上にkeyが存在しているかどうかを検索する。

hashtable作成 ⇒ update ⇒ 検索

①hashtableに指定した数分の空白bucketを作成し、hashtableの大きさを決定する。➄updateの際に、まず該当bucketを③で取得する。取得の際には、②を用いて指定したkeyをhash計算し、該当するbucketの位置情報を取得する。該当するbucketを取得後、bucket内にkeyが既に存在しているかどうかを確認し、既に存在している場合はvalueの上書きを行う。存在していない場合は、④を用いてbucketに新しく[key, value]のリストを追加する。
➅keyの検索では、③により該当bucketを取得し、keyの存在有無を確認し、存在すれば該当valueを、存在しなければNoneを返す。

hash計算

hash_string関数でで用いているhash計算は、keyの文字列を整数に変換し、bucket数で割った数の余りをbucketの位置情報としている。
keyを整数値に変換しているのは組み込み関数であるord(c)関数であり、長さ1の与えられた文字列(c)に対して整数値を返している。unicodeオブジェクトであるならばUnicodeコードポイントを表す整数値を返し、8bit文字列ならばそのバイト値を返す。ord(c)の対になる関数としてchr(i)関数もあり、8bit文字列のバイト数(i)を文字列として返すことができる。


簡単なhashtable作成は以上となる。
検索の際にリスト内全てをループする処理を入れると処理時間がかかってしまうため、Pythonであるばらばディクショナリを利用して、ループ処理を行わずに実装する方がいい。

Remove all ads