Hajautusfunktio

Tarkastellaan seuraavaa hajautusfunktiota:

(c_0 A^{n-1} + c_1 A^{n-2} \cdots + c_{n-1} A^0) \bmod M

Funktio laskee hajautusarvon merkkijonolle, jonka merkit ovat c_0,c_1,\dots,c_{n-1}. Jokainen merkki on välillä a–z ja merkit on koodattu niin, että a on 0, b on 1, c on 2, jne. Funktiossa on kaksi vakiota, joiden arvot ovat A=23 ja M=2^{32}.

Esimerkiksi kun merkkijono on kissa, hajautusfunktion arvo on

(10 \cdot 23^4 + 8 \cdot 23^3 + 18 \cdot 23^2 + 18 \cdot 23^1 + 0 \cdot 23^0) \bmod 2^{32} = 2905682.

Toteuta tiedostoon hashing.py funktio hash_value, joka laskee parametrina annetun merkkijonon hajautusarvon.

def hash_value(string):
    # TODO

if __name__ == "__main__":
    print(hash_value("abc")) # 25
    print(hash_value("kissa")) # 2905682
    print(hash_value("aybabtu")) # 154753059
    print(hash_value("tira")) # 235796
    print(hash_value("zzzzzzzzzz")) # 2739360440