Hash Tables
Exercise 1
Find a hash function to convert numeric
personal numbers into values between 1
and 10. Write a program to generate some
random numeric personal numbers test
your function.
Exercise 2
Use the following values:
66 47 87 90 126 140 145 153 177 285 393 395 467 566 620 735
Store the values into a hash table with 20 positions, using the
division method of hashing and the linear probing method of
resolving collisions.
Hints:
Store the values into a hash table with 20 positions, using rehashing
as the method of collision resolution. Use key % tableSize as the
hash function, and (key + 3) % tableSize as the rehash function.
Store the values into a hash table with ten buckets, each containing
three slots. If a bucket is full, use the next (sequential) bucket that
contains a free slot.
Store the values into a hash table that uses the hash function key %
10 to determine into which of ten chains to put the value.
Hash Table Implementation
#include <stdio.h>
#include <string.h>
#include "linked_list.h"
#define VMAX 17
#define P 13
template<typename Tkey, typename Tvalue> struct elem_info {
Tkey key;
Tvalue value; };
template<typename Tkey, typename Tvalue> class Hashtable {
private:
LinkedList<struct elem_info<Tkey, Tvalue> > *H;
int HMAX;
int (*hash) (Tkey);
public:
Hashtable(int hmax, int (*h) (Tkey)) {
HMAX = hmax;
hash = h;
H = new LinkedList<struct elem_info<Tkey,
Tvalue> > [HMAX]; }
~Hashtable() {
for (int i = 0; i < HMAX; i++) {
while (!H[i].isEmpty())
H[i].removeFirst();
}
delete H;
}
Part 2
Tvalue get(Tkey key) {
void put(Tkey key, Tvalue value) { struct list_elem<struct elem_info<Tkey, Tvalue> > *p;
struct list_elem<struct elem_info<Tkey, Tvalue> > *p; int hkey = hash(key);
struct elem_info<Tkey, Tvalue> info; p = H[hkey].pfirst;
int hkey = hash(key); while (p != NULL) {
if (p->[Link] == key) break;
p = H[hkey].pfirst; p = p->next;
}
while (p != NULL) {
if (p != NULL)
return p->[Link];
if (p->[Link] == key) else {
break; fprintf(stderr, "Error 101 - The key does not exist in the hashtable\n");
p = p->next; Tvalue x;
return x;
} }
}
if (p != NULL)
int hasKey(Tkey key) {
p->[Link] = value; struct list_elem<struct elem_info<Tkey, Tvalue> > *p;
else {
[Link] = key; int hkey = hash(key);
[Link] = value; p = H[hkey].pfirst;
H[hkey].addLast(info); while (p != NULL) {
} if (p->[Link] == key)
} break;
p = p->next;
}
if (p != NULL)
return 1;
else
return 0;
}
};
Part 3
int hfunc(int key) {
return (P * key) % VMAX;
}
Hashtable<int, double> hid(VMAX, hfunc);
int hfunc2(char* key) {
int hkey = 0;
for (int i = 0; i < strlen(key); i++)
hkey = (hkey * P + key[i]) % VMAX;
return hkey;
}
Hashtable<char*, int> hci(VMAX, hfunc2);
char *k1 = "abc";
char *k2 = "xyze";
char *k3 = "Abc";
char *k4 = "abcD";
int main() {
[Link](3, 7.9);
[Link](2, 8.3);
printf("%.3lf\n", [Link](3));
[Link](3, 10.2);
printf("%.3lf\n", [Link](3));
printf("%.3lf\n", [Link](2));
printf("%d\n", [Link](5));
printf("%d\n", [Link](2));
printf("%.3lf\n", [Link](5));
[Link](k1, 10);
[Link](k2, 20);
printf("%d\n", [Link](k1));
[Link](k1, 30);
printf("%d\n", [Link](k1));
printf("%d\n", [Link](k2));
printf("%d\n", [Link](k3));
printf("%d\n", [Link](k2));
printf("%d\n", [Link](k4));
return 0;
}