Dynamic perfect hashing: Difference between revisions
mNo edit summary |
m robot Removing: lv:Dinamiskais hešings |
||
| Line 10: | Line 10: | ||
{{reflist}} |
{{reflist}} |
||
[[lv:Dinamiskais hešings]] |
|||
[[Category:Hashing]] |
[[Category:Hashing]] |
||
Revision as of 14:01, 17 September 2010
Dynamic perfect hashing is a programming technique for resolving collisions in a hash table data structure [1][2][3].
In this method, the entries that hash to the same slot of the table are organized as separate second-level hash table. If there are k entries in this set, the second-level table is allocated with k2 slots, and its hash function is selected at random from a universal hash function set so that it is collision-free (i.e. a perfect hash function). Therefore, the lookup cost is guaranteed to be constant in the worst-case.
Although each second-level table requires quadratic space, if the keys inserted into the first-level hash table are uniformly distributed, the structure as a whole occupies expected O(n) space, since bucket sizes are small with high probability.[1]
If a collision occurs during the insertion of a new entry, the bucket's second-level table is rebuilt with a different randomly-selected hash function. Because the load factor of the second-level table is kept low (1/k), rebuilding is infrequent, and the amortized cost of insertions is low.
References
- ^ a b Fredman, M. L., Komlós, J., and Szemerédi, E. 1984. Storing a Sparse Table with 0(1) Worst Case Access Time. J. ACM 31, 3 (Jun. 1984), 538-544 http://portal.acm.org/citation.cfm?id=1884#
- ^ Dietzfelbinger, M., Karlin, A., Mehlhorn, K., Meyer auf der Heide, F., Rohnert, H., and Tarjan, R. E. 1994. Dynamic Perfect Hashing: Upper and Lower Bounds. SIAM J. Comput. 23, 4 (Aug. 1994), 738-761. http://portal.acm.org/citation.cfm?id=182370#
- ^ Erik Demaine, Jeff Lind. 6.897: Advanced Data Structures. MIT Computer Science and Artificial Intelligence Laboratory. Spring 2003. http://courses.csail.mit.edu/6.897/spring03/scribe_notes/L2/lecture2.pdf
 | This computer-programming-related article is a stub. You can help Wikipedia by expanding it. |