C LANGUAGE TECHNOLOGY

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

2021年10月11日

悩んでいる人

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

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

本記事の信頼性

  • リアルタイムシステムの研究歴12年.
  • 東大教員の時に,英語でOS(Linuxカーネル)の授業.
  • 2012年9月~2013年8月にアメリカのノースカロライナ大学チャペルヒル校(UNC)コンピュータサイエンス学部で客員研究員として勤務.C言語でリアルタイムLinuxの研究開発.
  • プログラミング歴15年以上,習得している言語: C/C++PythonSolidity/Vyper,Java,Ruby,Go,Rust,D,HTML/CSS/JS/PHP,MATLAB,Assembler (x64,ARM).
  • 東大教員の時に,C++言語で開発した「LLVMコンパイラの拡張」,C言語で開発した独自のリアルタイムOS「Mcube Kernel」GitHubにオープンソースとして公開
  • 2020年1月~現在はアメリカのノースカロライナ州チャペルヒルにあるGuarantee Happiness LLCのCTOとしてECサイト開発やWeb/SNSマーケティングの業務.2022年6月~現在はアメリカのノースカロライナ州チャペルヒルにあるJapanese Tar Heel, Inc.のCEO兼CTO.
  • 最近は自然言語処理AIイーサリアムに関する有益な情報発信に従事.
    • (AI全般を含む)自然言語処理AIの論文の日本語訳や,AIチャットボット(ChatGPT,Auto-GPT,Gemini(旧Bard)など)の記事を50本以上執筆.アメリカのサンフランシスコ(広義のシリコンバレー)の会社でプロンプトエンジニア・マネージャー・Quality Assurance(QA)の業務委託の経験あり.
    • (スマートコントラクトのプログラミングを含む)イーサリアムや仮想通貨全般の記事を200本以上執筆.イギリスのロンドンの会社で仮想通貨の英語の記事を日本語に翻訳する業務委託の経験あり.

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

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

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

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

友だち追加

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

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

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

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

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

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

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

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

これに対して,C言語の標準ライブラリにはハッシュテーブルの実装がありません.

また,GNUのC言語ライブラリにはハッシュテーブルの管理関数(hcreate/hsearch/hdestroy/hcreate_r/hsearch_r/hdestroy_r関数)はありますが,使い方が少し難しいです.

ハッシュテーブルの管理関数の使い方を知りたいあなたはこちらからどうぞ.

本記事では,C言語でハッシュテーブルを深く理解するための自作コードを紹介します.

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

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

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

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

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

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

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

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

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

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

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

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

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

まとめ

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

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

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

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

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

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

友だち追加

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

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