ハッシュ テーブルに関する私の知識は限られており、現在学習中です。オープンハッシュまたは個別チェーンハッシュによるハッシュ衝突の解決について質問があります。
この場合のハッシュ バケットは、同じキーにマップされるすべての要素がリンクされているリンク リストへのポインタを保持していることを理解しています。したがって、検索の複雑さは o(n) のオーダーになります。ここで、n はリンクされたリスト内の要素の数です。これを簡単にする方法はありますか？
また、リンクされたリストのサイズに制約がある場合、最大 5 つの要素しか保持できないと言って、5 つを超える要素が同じバケットにハッシュされる場合、このシナリオを処理する最良の方法は何ですか?
上記についてさらに学ぶための指針と助けをいただければ幸いです。
ハッシュの衝突はあまり一般的ではありません。さもなければ、何か間違ったことをしている可能性があります (たとえば、不適切なハッシュ関数や十分な大きさのハッシュ テーブルがないなど)。したがって、各連結リストの要素数は最小限に抑える必要があり、O(n) の複雑さはそれほど悪くないはずです。
理論的には、他の多くのデータ構造の 1 つに置き換えることができます。たとえば、二分探索木は O(log n) の検索時間 (アイテムが比較可能であると仮定) を取得しますが、挿入時間は O(1) ではなく O(log n) になり、さらに時間がかかります。スペース。
リスト内の要素数に上限はありません。存在する場合は、おそらくプローブ (例: 線形プローブ) に頼ることができますが、要素をかなり移動する必要がある場合があるため、削除は悪夢になる可能性があります。