C LANGUAGE TECHNOLOGY

【C言語】ハッシュテーブルとは【ハッシュチェイン法,オープンアドレス法】

悩んでいる人

C言語でハッシュテーブルを教えて!

こういった悩みにお答えします.

本記事の信頼性

  • リアルタイムシステムの研究歴12年.
  • 東大教員の時に,英語でOSの授業.
  • 2012年9月~2013年8月にアメリカのノースカロライナ大学チャペルヒル校コンピュータサイエンス学部2021年の世界大学学術ランキングで20位)で客員研究員として勤務.C言語でリアルタイムLinuxの研究開発
  • プログラミング歴15年以上,習得している言語: C/C++Solidity,Java,Python,Ruby,HTML/CSS/JS/PHP,MATLAB,Assembler (x64,ARM).
  • 東大教員の時に,C++言語で開発した「LLVMコンパイラの拡張」,C言語で開発した独自のリアルタイムOS「Mcube Kernel」GitHubにオープンソースとして公開

こういった私から学べます.

ハッシュテーブル(ハッシュ表)

ハッシュテーブル(ハッシュ表)とは,キー(key)と値(value)のペアでデータを管理し,キーに対応する値を高速に参照するためのデータ構造です.

ハッシュテーブルは連想配列や集合の効率的な実装の一つですので,よく利用されます.

C++言語のSTLにはC++11規格からハッシュテーブルの実装としてstd::unordered_mapstd::unordered_setが採用されました.

しかし,C言語の標準ライブラリにはハッシュテーブルの実装はありませんので,自作コードを紹介します.

複数の異なるキーが同じハッシュ値(ハッシュ関数から計算した添字)になることを衝突(collision),同じハッシュ値となるキーを同族キー,ハッシュテーブルにある各々の値のことをバケットと呼びます.

ハッシュ値の衝突が発生した場合は,ハッシュチェイン法(オープンハッシュ法)とオープンアドレス法(クローズドハッシュ法)で主に対処するので,それぞれ解説していきます.

ハッシュチェイン法(オープンハッシュ法)

ハッシュチェイン法(オープンハッシュ法) は,ハッシュテーブルで衝突を起こしたキー同士をポインタでつなぐ連結リスト(linked list)で値を格納します.

ハッシュテーブルの各々の番地にはキーそのものではなく,同族キーを保持する連結リストを格納します.

連結リストを知りたいあなたはこちらからどうぞ.(番兵ノードありの実装です.)

C言語 リスト
【C言語】連結リストとは【片方向リスト,双方向リスト,双方向循環リスト】

こういった悩みにお答えします. こういった私から学べます. 目次1 連結リスト2 C言語のリスト2.1 片方向リスト2.2 双方向リスト2.3 双方向循環リスト3 リストの実例:Linuxカーネル3. ...

続きを見る

ハッシュチェイン法を利用するコードは以下になります.(番兵ノードなしの実装です.)

実行結果は以下になります.

オープンアドレス法(クローズドハッシュ法)

オープンアドレス法(クローズドハッシュ法)は,衝突が発生した場合,ハッシュテーブル中の空いている別の番地を探す方式です.

例えば,線形探索法(linear probing)では,次の添字(添字を+1した場所)の空いているキーの場所に値を格納します.

線形探索法でオープンアドレス法を利用するコードは以下になります.

実行結果は以下になります.

まとめ

C言語でハッシュテーブルを紹介しました.

ハッシュ値の衝突が発生した場合は,ハッシュチェイン法とオープンアドレス法で対処することがわかりました.

C言語を独学で習得することは難しいです.

私にC言語の無料相談をしたいあなたは,公式LINE「ChishiroのC言語」の友だち追加をお願い致します.

友だち追加

独学が難しいあなたは,C言語を学べるおすすめのオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう.後悔はさせません!

-C LANGUAGE, TECHNOLOGY
-, , , , , ,