Kurssiaiheen 13 tehtävät¶

Ketjutettu hajautus¶

[JSAV Placeholder: open_hashing]

Hash tables¶

 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)
 }

Kysymys 1

Mihin ämpäriin avain 12345678 sijoittuu, kun hajautusfunktio on yläpuolella näkyvä y ja on ämpäreitä on 100?

Kysymys 2

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.)

ensimmäisen kirjaimen juokseva numero aakkosissa mod 9.

avaimen pituus mod 9.

ensimmäisen kirjaimen juokseva numero aakkosissa kerrottuna avaimen pituudella mod 9.

Kysymys 3

Mikä on edellisen kysymyksen hajautustaulun täyttöaste? Anna vastaus murtolukuna.