Hashing: The process of mapping a key value to a position in a table.
A hash function maps key values to positions. It is denoted by \(h\).
A hash table is an array that holds the records. It is denoted by HT.
HT has \(M\) slots, indexed form 0 to \(M-1\).
For any value \(K\) in the key range and some hash function \(h\), \(h(K) = i\), \(0 <= i < M\), such that key(HT[i]) \(= K\).
Hashing is appropriate only for sets (no duplicates).
Good for both in-memory and disk-based applications.
Answers the question "What record, if any, has key value K?"
Given: hash function h with keys \(k_1\) and \(k_2\). \(\beta\) is a slot in the hash table.
If \(\mathbf{h}(k_1) = \beta = \mathbf{h}(k_2)\), then \(k_1\) and \(k_2\) have a collision at \(\beta\) under h.
int h(int x) {
return x % 16;
}
int sascii(String x, int M) {
char ch[];
ch = x.toCharArray();
int xlength = x.length();
int i, sum;
for (sum=0, i=0; i < x.length(); i++)
sum += ch[i];
return sum % M;
}
// Use folding on a string, summed 4 bytes at a time
long sfold(String s, int M) {
int intLength = s.length() / 4;
long sum = 0;
for (int j = 0; j < intLength; j++) {
char c[] = s.substring(j * 4, (j * 4) + 4).toCharArray();
long mult = 1;
for (int k = 0; k < c.length; k++) {
sum += c[k] * mult;
mult *= 256;
}
}
char c[] = s.substring(intLength * 4).toCharArray();
long mult = 1;
for (int k = 0; k < c.length; k++) {
sum += c[k] * mult;
mult *= 256;
}
return(Math.abs(sum) % M);
}
.
// Insert e into hash table HT
void hashInsert(const Key& k, const Elem& e) {
int home; // Home position for e
int pos = home = h(k); // Init probe sequence
for (int i=1; EMPTYKEY != (HT[pos]).key(); i++) {
pos = (home + p(k, i)) % M; // probe
if (k == HT[pos].key()) {
println("Duplicates not allowed");
return;
}
}
HT[pos] = e;
}
// Search for the record with Key K
bool hashSearch(const Key& K, Elem& e) const {
int home; // Home position for K
int pos = home = h(K); // Initial position is the home slot
for (int i = 1;
(K != (HT[pos]).key()) && (EMPTYKEY != (HT[pos]).key());
i++)
pos = (home + p(K, i)) % M; // Next on probe sequence
if (K == (HT[pos]).key()) { // Found it
e = HT[pos];
return true;
}
else return false; // K not in hash table
}
Look carefully at the probe function p():
pos = (home + p(k, i)) % M; // probe
Each time p() is called, it generates a value to be added to the home position to generate the new slot to be examined.
\(p()\) is a function both of the element's key value, and of the number of steps taken along the probe sequence. Not all probe functions use both parameters.
Use the following probe function:
p(K, i) = i;
Linear probing simply goes to the next slot in the table.
Past bottom, wrap around to the top.
To avoid infinite loop, one slot in the table must always be empty.
The load factor is \(\alpha = N/M\) where \(N\) is the number of records currently in the table.
Unfortunately, tombstones add to the average path length.