algorithm - 自己均衡ツリーを使用して実装された連想配列での衝突の処理

Question

自己平衡ツリーを使用して実装された連想配列で衝突はどのように処理されますか? 2 つのオブジェクトが同じハッシュを持つ場合、それらはツリー ノードに接続されたリンク リストに格納されますか、それとも 2 つのノードが作成されますか? 前者の場合はO(log n)どうですか？後者の場合、二分探索木はどのように同じキー（ハッシュ）を処理できますか？

Answer 1

検索ツリーは同じキーを持つ 2 つのノードを確実に処理できないため、競合するキーを持つエントリを別のデータ構造 (通常は、ツリー ノードに接続されたリンク リスト) に格納する必要があります。ハッシュテーブルとして実装された連想配列に最悪の O(1) 操作がないのと同じように、最悪の場合の複雑さが O(log n) になることはありません。

エピタフ ノートのように、試みるべきことの 1 つは、衝突を起こさないように、ハッシュ キーの長さを増やすことです。ただし、そうしないことを保証することはできず、同じハッシュを持つ 2 つのオブジェクトに対して何らかの準備をする必要があります。ただし、ハッシュアルゴリズムを適切に選択した場合、これはまれなケースであり、ルックアップの平均時間の複雑さは O(log n) になりますが、すべてが同じハッシュキー。