1. 序章

このチュートリアルでは、コンピュータサイエンスにおける2つの非常に重要なデータ構造、ハッシュテーブルと二分探索木（BST）、特にその自己平衡型について見ていきます。 それらの主な違いを分析し、目前の問題に応じてどちらを使用するかを判断します。

2. 概要

2.1. ハッシュ表

ハッシュテーブル（ハッシュマップとも呼ばれます）は、キーを並べ替えられていない方法で値にマップするために使用されるデータ構造です。ここでのキーとは、格納している値を指す一意の識別子を意味します。

概念の簡単な例は電話帳です。 キーとして連絡先の名前の文字列があり、保存するデータとして対応する電話番号があるとします。 ただし、コンピューターは文字列をデータに直接関連付けることはできず、数値を処理します。

そのため、ハッシュテーブル電話帳へのすべての新しいエントリは、インデックスを計算するハッシュ関数を通過する必要があります。 このインデックスは、すべての連絡先データの配列内のバケットを指すために使用されます。

後で電話帳で誰かに電話をかける必要がある場合、名前をハッシュして対応する値を見つけることで、簡単に番号を取得できます。

この概念は非常に効率的ですが、ハッシュ関数の選択にも非常に依存しています。 完全な関数は各キーを一意のバケットに割り当てますが、実際には、ハッシュテーブルの実装は不完全なハッシュ関数を使用するため、2つの異なる入力が同じインデックスになる可能性があります。

この例では、これは、異なる名前の2人が同じ電話番号を指すことを意味します。 これは衝突とも呼ばれ、通常はオープンアドレッシングやチェーニングなどの方法を使用して対応されます。

2.2. 自己平衡BST

ツリーの各ノードに最大で2つの子（左の子と右の子と呼ばれる）がある場合、ツリーはbinaryと呼ばれます。

A 二分探索木はバイナリツリーであり、その内部ノードはそれぞれキーを格納し、それぞれに2つの区別されたサブツリーがあります。 左と右。 さらに、各ノードのキーは、ノードの左側のサブツリーのすべてのキーよりも大きく、右側のサブツリーのキーよりも小さくなっています。

この特定の構造により、数値などのデータをきちんと並べ替えて保存できますが、ほとんどの操作には木の高さに正比例して時間がかかります。 そのため、木の高さをできるだけ低く保つために、木の回転ルーチンを適用できます。 そのようなルーチンが存在する場合、ツリーはセルフバランシングと呼ばれます。 典型的なバリアントには、AVLツリー、 Bツリー、赤黒木などがあります。

3. 考慮事項

3.1. 速度に関する考慮事項

衝突は必要な要素へのアクセスを遅くするため、ハッシュテーブルの速度は主にハッシュ関数の選択に依存します 。 挿入、削除、検索などのハッシュテーブルの操作は非常に高速で、平均して実行されます。

ただし、常に同じバケットを指す非常に悪いハッシュ関数がある場合、取得できる最悪の値はです。 この場合、配列やリンクリストのようにすべての要素を繰り返し処理します。

ハッシュテーブルに線形時間が必要なもう1つの状況は、テーブルが最初に割り当てられたサイズよりも大きくなる場合です。 次に、それ自体をより大きなテーブルに再作成し、その中のすべての要素を再ハッシュする必要があります。 このため、絶えず増大するライブデータを操作する場合、ハッシュマップはあまり適していません。

自己平衡二分探索木の同じ挿入、検索、削除操作の時間計算量は平均です。 これらの3つの操作のみを考慮すると、これはハッシュテーブルと比較して大幅に遅くなります。

とはいえ、アプリケーションが数値に最も近い下位または上位の要素を検索したり、範囲クエリを実行したりするなど、より複雑なタスクを必要とする場合、BSTの並べ替えられた構造は、比較してはるかに高速に検索を実行します。

3.2. メモリに関する考慮事項

二分探索木は、必要以上のメモリを予約しないため、一般的にメモリ効率が高くなります。 一方、格納する要素の正確な数がわからない場合、ハッシュテーブルはもう少し要求が厳しくなる可能性があります。

通常、ハッシュテーブルは配列を割り当て、この配列のサイズで均一にハッシュすることで衝突を回避します。 したがって、最初に100個の要素用に予約されたメモリを持つハッシュテーブルがあるが、20個だけを使用すると、残りのメモリが無駄になります。

4. 結論

この記事では、ハッシュテーブルと自己平衡二分探索木を確認し、それらの個々の詳細を調べて、さまざまなシナリオで比較しました。

自己平衡二分探索木に対するハッシュテーブルの主な利点は、アクセス速度が一定であることです。  エントリの最大数がわかっている場合は部分的に効率的であるため、基になるバケット配列を1回割り当てて、サイズを変更することはできません。

一方、多くのサイズ変更と複雑なクエリを必要とする動的データを処理している場合は、セルフバランシングBSTのソートされた構造を活用する方が効率的です。