Kurssiaiheen 13 tehtävät

Ketjutettu hajautus

[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)
 }
Mihin ämpäriin avain 12345678 sijoittuu, kun hajautusfunktio on yläpuolella näkyvä y ja on ämpäreitä on 100?
Mikä seuraavista hajautusfunktioista jakaa seuraavat alkiot {“Eetu”, “Kai”, “Nelli”, “Kaisa”, “Elias”} tasaisimmin, jos ämpäreiden lukumäärä on 9? (Huomaa. Kaikki annetut hajautusfunktiot ovat itse asiassa melko huonoja.)
Mikä on edellisen kysymyksen hajautustaulun täyttöaste? Anna vastaus murtolukuna.