返回Google圖書搜尋

The Tree Model for Hashing: Lower and Upper Bounds

University of British Columbia. Department of Computer ScienceJoseph GilAvi Wigderson

出版	University of British Columbia, Department of Computer Science, 1991
URL	http://books.google.com.hk/books?id=pV01GwAACAAJ&hl=&source=gbs_api

註釋Abstract: "We define a new simple general model which captures many natural (sequential and parallel) hashing algorithms. In a game against nature, the algorithm and coin-tosses cause the evolution of a random tree, whose size corresponds to space (hash table size), and two notions of depth correspond to the longest probe sequences for insertion (parallel insertion time) and search of a key, respectively. We study these parameters of hashing schemes by analyzing the underlying stochastic process, and derive tight lower and upper bounds on the relation between the amount of memory allocated to the hashing execution and the worst case insertion time. In particular, we show that if linear memory is used then not all key insertions to the hash table can be done in constant time