C LANGUAGE TECHNOLOGY

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

悩んでいる人

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

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

本記事の信頼性

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

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

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

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

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

ハッシュテーブルの平均計算量は\(\mathcal{O}(1)\)ですが,最悪計算量は\(\mathcal{O}(n)\)になります.

また,ハッシュテーブルは探索アルゴリズムの側面を持ちます.

代表的な探索アルゴリズムである線形探索と二分探索を知りたいあなたはこちらからどうぞ.

C言語 線形探索 二分探索
【C言語】線形探索と二分探索で数値と文字列の検索【lfind/lsearch/bsearch関数と自作関数】

こういった悩みにお答えします. こういった私から学べます. 目次1 線形探索と二分探索2 線形探索と二分探索の標準ライブラリ関数2.1 lfind/lsearch関数2.2 bsearch関数3 線形 ...

続きを見る

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言語でハッシュテーブルを紹介しました.

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

ハッシュテーブルの管理関数(hcreate/hsearch/hdestroy/hcreate_r/hsearch_r/hdestroy_r関数)の使い方を知りたいあなたはこちらからどうぞ.

C言語 ハッシュテーブル 管理関数
【C言語】ハッシュテーブルの管理関数の使い方【hcreate/hsearch/hdestroy/hcreate_r/hsearch_r/hdestroy_r関数】

こういった悩みにお答えします. こういった私から学べます. 目次1 ハッシュテーブルの管理関数2 ハッシュテーブルの管理関数の使い方2.1 hcreate/hsearch/hdestroy関数の使い方 ...

続きを見る

ハッシュテーブルの応用のマークル木とマークルパトリシア木を知りたいあなたはこちらからどうぞ.

C言語 マークル木 マークルパトリシア木
【C言語】マークル木とマークルパトリシア木【ビットコインとイーサリアムで利用】

こういった悩みにお答えします. こういった私から学べます. 本記事では,ハッシュテーブルを理解していることを前提とします. 目次1 マークル木(マークルハッシュ木,ハッシュ木)【ビットコインで利用】2 ...

続きを見る

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

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

私のキャパシティもあり,一定数に達したら終了しますので,今すぐ追加しましょう!

友だち追加

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

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