はじめに
ハッシュテーブルと二分木について、色々と調べたのでまとめた。
アルゴリズム関連では、以下の記事も参考にしてください。
①計算量とソートの基本
②実用的なソート
③探索
④再帰関数
ハッシュテーブルと二分木ってなに？
ハッシュテーブル(hash table)
ハッシュテーブルはm個の要素を格納できる配列T(画像でいうと、hashes)と、データのキーを決定するハッシュ関数(hash functions)から構成されます。
ハッシュ関数へ入力するキーは整数である必要があるため、キーが文字列である場合は対応する整数へ変換する必要があります。
例えば、ハッシュ関数として$h(k)=k~mod~m$などを用いることができます。
ただ異なるキーが同じハッシュ値となる衝突が起きる可能性があるので、それを解決する方法が二つあります。
- オープンアドレス法
- チェイン法
英語のwikipediaにわかりやすい説明が載っていたので、そちらを参考にしてください。
1のチェイン法は、衝突を起こしたキー同士を連結リストで繋いで格納する方法です。
2のオープンアドレス法は衝突が起きると、テーブルの中で空いている別の位置を探す方法で、ハッシュ関数とは別のハッシュ関数を用いて、次の位置を探していきます。
ハッシュテーブルにおいては、衝突が起きなければ$O(1)$で挿入や探索を行うことができます。
参考
What is a HashTable Data Structure - Introduction to Hash Tables , Part 0 - YouTube
ハッシュ法
二分木(binary tree)
二分木とは根付きの木構造で、ノードの持つこの数が高々2であるものを指します。
計算量が常に$logn$になるというのが特徴です。
- ハッシュテーブほどメモリの確保が要らない。
- ハッシュ関数を考えずに、済む。
などのメリットがあります。
ただ木のバランスが取れておらず、片方が長くなると、計算量は$O(n)$に近づくため、左右のバランスをとる平衡木などが考案されています。回転、などの手法によって実現されます。