Optimal Arrangement of Keys in a Hash Table
When open addressing is used to resolve collisions in a hash table, a given set of keys may be arranged in many ways; typically this depends on the order in which the keys are inserted. We show that arrangements minimizing either the average or worst-case number of probes required to retrieve any ke...
| Main Author: | |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/148901 |
| Summary: | When open addressing is used to resolve collisions in a hash table, a given set of keys may be arranged in many ways; typically this depends on the order in which the keys are inserted. We show that arrangements minimizing either the average or worst-case number of probes required to retrieve any key in the table can be found using an algorithm for the assignment problem. The worst-case retrieval time can be reduced to 0(log2(M)) with probability 1-E(M), when storing M keys in a table of size M, where E(M) -> 0 aas M -> infinity. We also examine insertion algorithms to see how to apply these ideas for a dynamically changing set of keys. |
|---|