| CSL-76-3_The_Analysis_of_Hashing_Algorithms.pdf | | THE ANALYSIS OF
HASHING ALGORITHMS
BY LEONIDAS J. GUIBAS
CSL-76-3 JULY 1976 '
See abstract on next page.
KEY WORDS AND PHRASES
algorithmic analysis, arithmetic progression, hashing, information storage and retrieval,
generating function, recurrence relation, Farey series, clustering, hypergeometric
distribution, table overflow
CR CATEGORIES
3.74, 5.24, 5.25, 5.30
XEROX
PALO ALTO RESEARCH CENTER
3333 COYOTE HILL ROAD / PALO ALTO / CALIFORNIA 94304
ABSTRACT
In this thesis we relate the performance of hashing algorithms to the notion of
clustering, that is the pile-up phenomenon that occurs because many keys may probe
the table locations in the same sequence. We will say that a hashing technique exhibits
k-ary clustering if the search for a key begins with k independent |
