Hashing with chaining is an application of linked lists and gives an approach to collision resolution. In hashing with chaining, the hash table contains linked lists of elements or pointers to elements (Figure 12.1). The lists are referred to as chains, and the technique is called chaining. This is a common technique where a straightforward implementation is desired and maximum efficiency isn't required. Each linked list contains all the elements whose keys hash to the same index. Using chains minimizes search by dividing the set to be searched into lots of smaller pieces. There's nothing inherently wrong with linear search with small sequences; it's just that it gets slower as the sequences to be searched get longer. In this approach to resolving collisions, each sequence of elements whose keys hash to the same value will stay relatively short, so linear search is adequate.
This Hash Table is an array [0 .. m-1] of linked_list.
The table entries are called buckets or slots, and the linked lists are
called chains.
Choice of h: h[x]
Choice of three digit for school phone number e.g.398-3738
x is an interger value.
H[x] = x mod m.
This often yields unpredictable (and thus good) distributions of
the data.
Assume that you wish to take the two digits three positions
from the right of x.
If x = 539 872 178
then h[x] = 72
This is obtained by
H[x] = (x/1000) mod 100
Where (/1000) drops three digits and (x/1000) mod 100 keeps two
digits.
Here we analyse the number of probes in a table for doing "search". A probe is a check of a table entry. All other components of the algorithm are ignored, but as they are collectively bounded by the number of probes, it suffices to just consider probes.
n = input size, m= table size, and a= LOAD FACTOR = n /m
-WORST CASE : (Number of probes for search /insert)
Where 'a' is n/m and '+1' is to check NIl.
And k is uniformly and randomly distributed over all values
in the table.
Where (i-1)/m comes from the time needed to insert the i-th
element in a table with i-1 element. By the unsucceful search
part, the expected time is (i-1)/m.
The hashing is by an order-preserving hash function, thus between linked lists, elements are sorted.
The table which contains buckets, small arrays of entries, can resolve a simple collision. Each bucket contains objects whose keys all hash to the index of that location in the table. A hash value selects one of these buckets, which is then searched sequentially until the target object is located or an empty slot is encountered. If the selected bucket is empty, or none of its objects have keys that match the target key, the object is simply added to the end of the bucket.
If the keys are uniformly distributed over the table, then hashing takes expected time O(n) under a computational model in which the computation of a hash function is done in O(1) worst-case time.
In open addressing, we
assume that insert and search are done by radomly
jumping from location to location, as in a random permutation of 0,1,
...,m-1.
The expected number of probes for unsuccessful search grows is not more
than 1/(1-a).
Where 0 < a < 1.
In conclusion, for expected number of probes, for fixed a, chaining is always better than open addressing.
Chaining for Collision Resolution | Implementatin of hashing, direct addressing, chaining for collision resolution and open addressing. From Oberlin College Computer Science. Rhys Price Jones, Fritz Ruehr, and Richard Salter. |
Direct Chaining | Algorithms on direct chaining, search and insert. From the Departement of Computer Science, University of Chile. Gaston H. Gonnet, Richardo Baeza-Yates. |
Separate chaining | Algorithms on separate chaining, search and insert. From Departement of Computer Science, University of Chile. Gaston H. Gonnet, Richardo Baeza-Yates. |
Object Hashing | A mechanism for generating a unique hash number fot an arbitrary object; from The Mit Scheme object_hashing facility. Provide a small pseudocode of a hash table. |
Hashing Function | An overview of Hashing function. From the MIT LCSClinical Decision Making Group. |
Kiadi Pati
WOrK : Web page design.
CONT@CT:kady@cs.mcgill.ca
Ho-Sheng Cheng
WoRk : Java Applet.
CONT@CT:snowman@cs.mcgill.ca
Hyung Sunt Kim
wORk : Graphics & References.
CONT@CT:hkim@cs.mcgill.ca
Copyright © 1997, Kiadi Pati, Ho-Sheng Cheng and
Hyung Sunk Kim. All rights reserved.
Reproduction of all or part of this work is permitted for educational
or research use provided that this copyright notice is included in any
copy. Disclaimer: this collection of notes is experimental, and does
not serve as-is as a substitute for attendance in the actual class.