バイナリ検索ツリーを使用したハッシュテーブルの実装

Question

これは、ハッシュテーブルのコーディングインタビューをクラッキングしたことによる論争の的となっている行です。

ハッシュテーブルの別の一般的な実装（リンクリストに加えて）は、基礎となるデータ構造としてBSTを使用することです。

私はこの質問が以前に尋ねられたことを知っています...誰もが2つの異なる答えを与えているので、それはとても混乱しています。例

Why implement a Hashtable with a Binary Search Tree?

の最高は、この記事で答えを投票上に引用文が根底にある配列なしで、二分探索木を使用して、ハッシュテーブルの実装について話を言っていると述べています。私は、挿入された各要素がハッシュ値（整数）を取得するので、要素が合計順序を形成することを理解しました（すべての対は<と>と比較できます）。したがって、単純にバイナリ検索ツリーを使用してハッシュテーブルの要素を保持することができます。一方

、他の人がこの本は、我々は二分探索木との衝突を扱うべきであると言っている

Hash table - implementing with Binary Search Tree

言います。そのため、基になる配列があり、複数の要素が同じハッシュ値を取得して配列の同じスロットに配置されるため、衝突するとBSTが入ります。

配列の各スロットは、同じハッシュ値を持つ要素を保持するBST。

最初の投稿は、そのようなハッシュテーブルの実装がどのように衝突を処理できるかを実際には説明しないので、私は第2の投稿の議論に傾いています。そして、私はそれが予想されるO（1）挿入/削除/ルックアップ時間を達成できるとは思わない。

しかし、同じハッシュ値を取得し、BSTに配置された複数の要素がある場合、これらの要素がどのように順序付けられているかわかりません（どのようにしてそれらを比較できますか）。

私は、この質問に一度も終わらせてください！

Answer 1

最初の投稿は本当にBSTとの衝突

を扱うことができるか、そのようなハッシュテーブルの実装がないがあるだろうので、あなたは何の重複キーを生成しないだろうハッシュ関数を使用することができます説明していません衝突。ここでの利点は、スピードではなくメモリ消費量を減らし、最悪の場合の保証が得られることです。クリティカルなリアルタイムシステム用のソフトウェアを作成している場合、ハッシュテーブルのO（n）サイズ変更を許容できない場合があります。

我々は同じハッシュ値を取得し、BSTに配置された複数の要素を持っている場合、私はこれらの要素が順序付けされているかどうかはわかりません（それらがどのように相互に比較することができますか？）

別の機能で再ハッシュ。

最終的には、データ構造がどのような目的で使用されているか（メモリとスピードの重要性、償却されたパフォーマンスと最悪の場合のパフォーマンスの重要性など））