Service Manuals, User Guides, Schematic Diagrams or docs for : xerox parc techReports CSL-76-3_The_Analysis_of_Hashing_Algorithms

<< Back | Home

Most service manuals and schematics are PDF files, so You will need Adobre Acrobat Reader to view : Acrobat Download Some of the files are DjVu format. Readers and resources available here : DjVu Resources
For the compressed files, most common are zip and rar. Please, extract files with Your favorite compression software ( WinZip, WinRAR ... ) before viewing. If a document has multiple parts, You should download all, before extracting.
Good luck. Repair on Your own risk. Make sure You know what You are doing.



Image preview - the first page of the document



>> Download CSL-76-3_The_Analysis_of_Hashing_Algorithms documenatation <<

Text preview - extract from the document

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 random probes and
the subsequent sequence of probes is completely determined by the location of the k
initial probes. Such techniques may be very bad; for instance, the average number of
probes necessary for insertion may grow linearly with the table size. However, on the
average (that is if the permutations describing the method are randomly chosen), k-ary
clustering techniques for k) 1 are very good. In fact the average performance is
asymptotically equivalent to the performance of uniform probing, a method that exhibits
no clustering and is known to be optimal in a certain sense.


Perharps the most famous among tertiary clustering techniques is double hashing, the
method in which we probe the hash table along arithmetic progressions where the initial
element and the increment of the progression are chosen randomly and independently
depending only on the key K of the search. We prove that double hashing 

◦ Jabse Service Manual Search 2024 ◦ Jabse Pravopis ◦ onTap.bg ◦ Other service manual resources online : Fixya ◦ eServiceinfo