はじめに

業務で多量のデータを扱う場面はたくさんあると思います。
その際、Javaでよく使うのがコレクションフレームワーク(Collection Framework)です。このコレクションフレームワークはデータを保存するデータ構造とデータを処理するアルゴリズムを構造化し、クラスで実装したものです。
多量のデータをグループ化し、効率的に保存・管理ができる機能を提供しています。

今回はその中で、keyとvalueをペアで保存する「Map」、そのもととなる
ハッシュテーブル(Hash Table)について調べていきたいと思います。

注意
この記事ではHash Tableの概念や動作方法について簡単に記述されています。
詳しいアルゴリズムなどは記述しません。

ハッシュテーブル(Hash Table)とは？

まず、ハッシュテーブルとは何か簡単に調べましょう。

ハッシュテーブルとは？

keyをハッシュ関数(hash function)で整数に変換させて、その値をインデックス(index)として、keyとvalueを保存するデータ構造(data structure)
keyでデータを参照するため、処理速度が速い
保存順序が維持されない
Javaの「Map」、C・Pythonの「dictionary」がその例

など、ハッシュテーブルにはこのように色んな特徴がまります。

ハッシュ関数(hash function)とは？

まずは、ハッシュ関数についてです。

ハッシュ関数は、任意のデータから、別の（多くの場合は短い固定長の）typeのデータに変換させる関数のことを言います。
ハッシュテーブル(Hash Table)では任意のデータを整数に変換させる関数と考えると理解しやすいかもしれません。

下記の図を参照して説明します。

ハッシュ関数にINPUTデータで「"010-9876-5432"」を渡します。すると、ハッシュ関数のOUTPUTデータとして「4310」という整数が出力されました。ハッシュテーブルはハッシュ関数から出力されたデータ「4310」を活用して、データの保存を行います。

注意
この記事で記載されているHashは理解をしやすくするための任意の値のため、
実際の結果とは異なります。

ハッシュテーブル(Hash Table)の仕組み

ここでは、実際にハッシュテーブルはどのように動作するのかについて確認しましょう。

データ保存

データ保存の流れとしては、下記のようです。

keyをインデックスで使えるように整数に変換させます。
①の整数をインデックスとして、データを配列に保存します。

簡単ですが、これがハッシュテーブルの基本的な動作です。

keyの変換についてもう少し説明すると、
keyをインデクスに変換させるにはハッシュ関数で整数に変換する必要があります。その後、出力された「Hash」を保存する「配列の長さと割り算し、その余り」をインデックスにするという流れになります。

ここで「Capacity」は配列の長さ、「bucket」と「solt」は配列の各要素を言います。

データ参照

データ参照も基本は同じです。
参照したいデータのkeyを入力すると、そのkeyをハッシュ関数でインデックスに変換させます。その後、配列の該当インデックスに保存されているデータを見て、入力したkeyと保存されているデータのkeyが一致すればそのデータ返却します。

しかし、このやり方ではデメリットがあります。

ここでこういう疑問に思うはずです。
入力したkeyは違うけど、インデックスが一緒である場合もあります。それを「ハッシュ衝突(hash Collision)」といいます。

ハッシュ衝突(hash Collision)

ハッシュ衝突が発生するのは、大きく２つあります。

keyは異なるが「hash」が同じ場合
keyもhashも異なるが、「hash % capacity」の結果が同じ場合

図のようにkey「"A"」と「"D"」が同じHashが出力される場合、それをハッシュ衝突といいます。

ハッシュ関数が無限に近いINPUTデータに対してハッシュ関数が出力するOUTPUTの数は有限であるため、こういうハッシュ衝突が発生しないハッシュ関数を作るのは不可能に近いです。
したがって、ハッシュ衝突緩和する対策を考えなけらばなりません。

それが下記の２つの方法です。

Separate chaining
open addressing

それぞれの対策を調べていきます。

Separate chaining

「Separate chaining」方式は同じbucketに保存されるデータをそれぞれチェーンで繋いだ状態でデータを保存します。
その際、「LinkedList」や「tree」などを使って次のデータを保存します。
Javaで採用した方法です。

下記の図では「"BANANA"」「"APPLE"」「"PEACH"」すべてのkeyのHashが同じであるため、ハッシュ衝突発生していますす。しかし、LinkedListで各データをつないでいるため、同じインデックスにデータが保存できることが分かります。

「Separate chaining」方式にももちろんデメリットはあります。
保存されるデータが増えると、その分同じbucketにchainingされるデータが増えて、使用するメモリリソースも増えます。
また、処理速度が低下するかもしれません。

open addressing

「open addressing」は、データをbucketに保存さる際、該当インデックスに既にデータがある場合、次のインデックス(空のbucket)に保存する方法です。
空のbucketを探す際に、線形探索(Linear Probing), 二分探索(Quadratic Probing), ダブルハッシュを使います。
C、Pythonで採用した方法です。

下記の図を見ると、インデックス「２」bucketに「"BANANA"」が保存されている状態で、APPLEを保存しようとしています。インデックス「２」bucketにはすでに「"BANANA"」が保存されているため、次のbucketに「"APPLE"」を保存します。

「open addressing」はメモリを効率よく使える保存するデータ量が少ないときに効率的なやり方です。しかし、テーブルよりデータが多いときは、テーブルの拡張が必要になりデメリットもあります。

hash table resizing

「open addressing」の内容で、全bucketにデータが保存され、からのbucketがない場合はテーブルの拡張が必要だと記述しました。では、実際にテーブルの拡張による変化を図で説明します。

下記の図を見ると、各データは自分のHashを持っていることが分かります。このHashを使って拡張されたテーブルに対して、「Capacity」と割り算を行い、その余りをインデックスに再度設定を行います。

「Capacity」が８のテーブルでは「"BANANA"」「"APPLE"」のインデックスが「２」で同じだったのが、「Capacity」が１６で拡張に従い、それぞれ「"BANANA"」は「10」、「"APPLE"」は「２」のbucketに保存されたことが分かります。

おわりに

こうやってハッシュテーブルについて調べました。
今回はとてもいい勉強になりました。
ただ、使ってきたHashMapについても少し、詳しく理解できるようになりました。

記事を見ていただきありがとうございました。

ここからは雑談です。

今まで、JavaのHashMapをよく使っていましたが、mapの仕組みをこれだけ詳細まで勉強する機会がなかったので、今回いい勉強になりました。
mapのkeyには文字列を使うのが大半だったので、map.get()でデータを参照する際にはmapの全データをループさせ、equals()で一致するデータを返すかと思いましたが、全然違いました。
確かに、パソコンって0と1しか理解できないので、すべてのデータは数値で変換して処理していました。
CSの基礎知識だったのにそれを忘れていました。
これを経験にこれからもいろいろ勉強していきたいですね。

「データ構造」ハッシュテーブル(Hash Table)を簡単に説明します。