Experiments with universal hashing
Authors:Jyrki Katajainen and Michael Lykke
Publication:Report 96/8, Department of Computer Science, University of Copenhagen (1996), 17 pp.
Abstract:The practical performance of randomized chain-hashing and double-hashing schemes is studied. The results of this study show that, if the keys are integers, by using multiplicative hash functions a double-hashing scheme is obtained, for which the observed (worst-case) cost of an access operation is the same as the corresponding (average-case) cost achieved by the chain-hashing scheme, which has been the fastest access method according to earlier experiments. The observed (amortized expected) cost of insert and delete operations for a dynamic double-hashing scheme is comparable to the corresponding (worst-case) cost for balanced search trees, whereas the behaviour of dynamic chain hashing is still better on an average. If the keys are strings, dynamic chain hashing with random-table hash functions outperforms clearly balanced search trees.
BibLATEX:
@report{KL1996R,
  author = {Jyrki Katajainen and Michael Lykke},
  title = {Experiments with universal hashing},
  type = {Report},
  number = {96/8},
  institution = {Department of Computer Science, University of Copenhagen},
  year = {1996},
  pagetotal = {17},
}
This page was generated by Jyrki Katajainen <jyrki@di.ku.dk> on 31.12.2011.