Course topic 13 exercises

Open Hashing

[JSAV Placeholder: open_hashing]

Hash tables

1
2
3
4
5
6
7
8
9
 int y(x, buckets) {
   int result = 0;
   while ( x != 0 ){
     // Multiply the first and last digits of x and add it to result.
     result += last_digit(x) * first_digit(x)
     x = remove_first_and_last_digit(x)
     }
 return (result mod buckets)
 }
What bucket will the key 12345678 hash into, when the hash function is the y shown above and there are 100 buckets?
Which one of the following hash functions distributes the following items {”Eetu”, ”Kai”, ”Nelli”, ”Kaisa”, ”Elias”} most evenly, if there are 9 buckets? (Note. All of the hash functions given are actually quite bad.)
What is the load factor of the hash table from the previous question? Give your answer as a fraction.