4. Hajautus

Hajautus (hashing) on tekniikka, jota käytetään usein tehokkaiden tietorakenteiden toteuttamisessa. Pythonissa tietorakenteet joukko (set) ja sanakirja (dict) perustuvat hajautukseen.

Tutustumme tässä luvussa hajautusta käyttävien tietorakenteiden ominaisuuksiin ja niiden taustalla olevaan teoriaan. Näemme myös, miten hajautusrakenteita voidaan käyttää tehokkaiden algoritmien suunnittelussa.

Joukko

Pythonin tietorakenne set pitää yllä alkioiden joukkoa ja tarjoaa tehokkaat operaatiot, joiden avulla voidaan lisätä alkio joukkoon, tarkastaa alkion kuuluminen joukkoon sekä poistaa alkio joukosta.

Seuraava koodi luo joukon numbers ja lisää sinne alkioita metodilla add:

numbers = set()

numbers.add(1)
numbers.add(2)
numbers.add(3)

print(numbers) # {1, 2, 3}

Joukko voidaan myös luoda suoraan listan perusteella:

numbers = set([1, 2, 3])

print(numbers) # {1, 2, 3}

Operaattori in tarkastaa, kuuluuko tietty alkio joukkoon:

print(3 in numbers) # True
print(4 in numbers) # False

Metodi remove puolestaan poistaa alkion joukosta:

print(numbers) # {1, 2, 3}
numbers.remove(2)
print(numbers) # {1, 3}

Lista vs. joukko

Lista ja joukko ovat tietyllä tavalla samantapaisia tietorakenteita, koska molemmissa voi lisätä, etsiä ja poistaa alkioita. Kuitenkin tietorakenteiden tehokkuudessa ja ominaisuuksissa on myös suuria eroja.

Tehokkuus

Listassa alkion lisääminen on tehokasta, mutta on hidasta etsiä alkiota listasta sekä poistaa alkio listasta.

Joukossa on tehokasta lisätä alkio joukkoon, etsiä alkiota joukosta sekä poistaa alkio joukosta.

Indeksointi

Listassa alkioita voidaan käsitellä indeksien perusteella:

numbers = [1, 2, 3]
print(numbers[1]) # 2

Joukon alkioihin sen sijaan ei voida viitata indekseillä:

numbers = set([1, 2, 3])
print(numbers[1]) # TypeError: 'set' object is not subscriptable

Toistuvat alkiot

Listassa sama alkio voi esiintyä useita kertoja:

numbers = []

numbers.append(5)
numbers.append(5)
numbers.append(5)

print(numbers) # [5, 5, 5]

Joukossa sama alkio voi esiintyä enintään kerran. Jos alkio lisätään monta kertaa joukkoon, tällä ei ole vaikutusta:

numbers = set()

numbers.add(5)
numbers.add(5)
numbers.add(5)

print(numbers) # {5}

Esimerkki: Montako eri lukua?

Tehtävä

Voimme ratkaista tämän tehtävän listan avulla seuraavasti:

def count_distinct(numbers):
    seen = []
    for x in numbers:
        if x not in seen:
            seen.append(x)
    return len(seen)

Algoritmi käy läpi luvut ja lisää luvun listaan seen, jos lukua ei ole vielä listassa. Lopuksi listan seen koko on yhtä suuri kuin eri lukujen määrä.

Tämä algoritmi on toimiva mutta ei tehokas, koska jokaisella silmukan kierroksella vie aikaa \(O(n)\) tarkastaa operaattorilla in, onko luku listassa. Tämän vuoksi algoritmin aikavaativuus on \(O(n^2)\).

Algoritmia on kuitenkin helppoa parantaa käyttämällä listan sijasta joukkoa. Tällöin algoritmi muuttuu näin:

def count_distinct(numbers):
    seen = set()
    for x in numbers:
        if x not in seen:
            seen.add(x)
    return len(seen)

Erona edelliseen funktioon seen on nyt joukko ja alkiot lisätään metodilla add. Tällä muutoksella on suuri vaikutus algoritmin tehokkuuteen. Muutoksen jälkeen operaattori in vie aikaa \(O(1)\) ja algoritmin aikavaativuus on vain \(O(n)\).

Koodia on mahdollista tiivistää, koska sama alkio ei mene useita kertoja joukkoon. Niinpä koodista voi poistaa tähän liittyvän tarkastuksen:

def count_distinct(numbers):
    seen = set()
    for x in numbers:
        seen.add(x)
    return len(seen)

Itse asiassa koodia voi tiivistää vielä lisää luomalla joukon suoraan listan pohjalta. Tämän ansiosta riittää loppujen lopuksi yksi rivi koodia:

def count_distinct(numbers):
    return len(set(numbers))

Sanakirja

Pythonin tietorakenne dict eli sanakirja on tietorakenne, johon voidaan tallentaa avain-arvo-pareja. Esimerkiksi seuraava koodi luo sanakirjan weights, jossa avaimet ovat merkkijonoja ja arvot ovat lukuja.

weights = {}

weights["apina"] = 100
weights["banaani"] = 1
weights["cembalo"] = 500

Yllä olevan sanakirjan voi luoda myös näin:

weights = {"apina": 100, "banaani": 1, "cembalo": 500}

Sanakirjaa voi ajatella listan yleistyksenä: listassa avaimet ovat indeksit \(0 \dots n-1\) kun taas sanakirjassa avaimet voivat olla mitä tahansa alkioita. Sanakirjan arvoja voi käsitellä samaan tapaan kuin listan arvoja:

print(weights["apina"]) # 100
weights["apina"] = 150
print(weights["apina"]) # 150

Operaattori in tarkastaa, onko sanakirjassa tiettyä avainta:

print("apina" in weights) # True
print("ananas" in weights) # False

Komento del poistaa avaimen ja siihen liittyvän arvon sanakirjasta:

print(weights) # {'apina': 100, 'banaani': 1, 'cembalo': 500}
del weights["banaani"]
print(weights) # {'apina': 100, 'cembalo': 500}

Sanakirjassa ovat tehokkaita operaatiot, joissa käsitellään tietoa avainten perusteella. Kaikki yllä käsitellyt operaatiot toimivat ajassa \(O(1)\).

Sanakirjan käyttäminen

Seuraavassa on kolme tavallista sanakirjan käyttötarkoitusta algoritmien suunnittelussa:

Onko alkiota esiintynyt

Sanakirjan avulla voidaan pitää yllä tietoa, mitkä alkiot ovat esiintyneet:

seen = {}
for x in numbers:
    seen[x] = True

Tässä tapauksessa avaimeen liittyvä arvo on aina True, minkä vuoksi voimme käyttää myös joukkoa kuten aiemmin:

seen = set()
for x in numbers:
    seen.add(x)

Voikin ajatella, että joukko on sanakirjan erikoistapaus, jossa jokaisella avaimella on arvona True (tai jokin muu sama arvo).

Alkion esiintymiskerrat

Tavallinen sanakirjan käyttötarkoitus on laskea, montako kertaa mikäkin alkio on esiintynyt.

count = {}
for x in numbers:
    if x not in count:
        count[x] = 0
    count[x] += 1

Koodi laskee esiintymiskerrat sanakirjan count avulla. Jos alkiota x ei ole vielä sanakirjassa, koodi asettaa sen esiintymiskertojen määräksi 0. Tämän jälkeen koodi kasvattaa alkion x esiintymiskertoja yhdellä.

Alkion esiintymiskohta

Joissakin algoritmeissa on hyödyllistä pitää yllä tietoa siitä, missä kohdassa mikäkin alkio on esiintynyt.

pos = {}
for i, x in enumerate(numbers):
    pos[x] = i

Tässä sanakirjassa pos on kunkin alkion viimeisin esiintymiskohta listassa. Funktion enumerate avulla lista voidaan käydä läpi niin, että joka kierroksella i sisältää alkion indeksin ja x itse alkion.

Esimerkki: Moodi

Tehtävä

Voimme ratkaista tehtävän luomalla sanakirjan, jossa avaimet ovat listan lukuja ja arvot ovat niiden esiintymiskertoja. Ideana on käydä läpi lista ja pitää yllä tietoa lukujen esiintymiskerroista ja tämänhetkisestä moodista.

def find_mode(numbers):
    count = {}
    mode_times = 0
    mode_value = 0
    for x in numbers:
        if x not in count:
            count[x] = 0
        count[x] += 1
        if count[x] > mode_times:
            mode_times = count[x]
            mode_value = x
    return mode_value

Tässä count on sanakirja, joka sisältää lukujen esiintymiskerrat. Lukua x käsitellessä count[x] kertoo, montako kertaa luku on esiintynyt listassa. Muuttujat mode_times ja mode_value puolestaan pitävät yllä tietoa moodista: montako kertaa tähän mennessä yleisin luku on esiintynyt ja mikä kyseinen luku on.

Silmukassa tarkastetaan ensin, onko luku x esiintynyt aiemmin. Jos ei ole, sen esiintymiskertojen määräksi alustetaan 0. Tämän jälkeen esiintymiskertojen määrää kasvatetaan yhdellä. Jos luku x on esiintynyt useammin kuin tällä hetkellä tiedossa oleva moodi, luvusta x tulee uusi moodi ja muuttujat mode_times ja mode_value päivitetään. Funktio palauttaa muuttujan mode_value arvon.

Koodia on mahdollista vielä tiivistää näin:

def find_mode(numbers):
    count = {}
    mode = (0, 0)
    for x in numbers:
        if x not in count:
            count[x] = 0
        count[x] += 1
        mode = max(mode, (count[x], x))
    return mode[1]

Nyt pari mode korvaa vanhat muuttujat mode_times ja mode_value. Tämän toteutuksen etuna on, että moodia pystyy päivittämään max-funktion avulla. Tässä max-funktio vertailee ensisijaisesti parin ensimmäistä alkiota ja toissijaisesti parin toista alkiota. Koska parin ensimmäinen alkio on esiintymiskertojen määrä, parin arvo on sitä suurempi mitä useammin luku on esiintynyt.

Huomaa, että yllä olevat kaksi funktiota toimivat vähän eri tavalla tilanteessa, jossa on useita mahdollisia vaihtoehtoja moodiksi. Ensimmäinen funktio valitsee moodin, jonka viimeinen esiintymiskerta tulee vastaan ensimmäisenä. Toinen funktio puolestaan valitsee moodin, joka on arvoltaan suurin, koska pareissa vertaillaan toissijaisesti luvun suuruutta.

Esimerkki: Kierrokset

Tehtävä

Oleellinen havainto on, että uusi kierros täytyy aloittaa aina silloin, kun kerättävä luku on edellisen kerätyn luvun vasemmalla puolella. Esimerkiksi yllä olevassa listassa luku \(3\) aloittaa uuden kierroksen, koska se on luvun \(2\) vasemmalla puolella. Seuraava algoritmi toteuttaa tämän idean listojen avulla:

def count_rounds(numbers):
    n = len(numbers)
    
    rounds = 1
    for i in range(2, n + 1):
        if numbers.index(i) < numbers.index(i - 1):
            rounds += 1
            
    return rounds

Tässä käytössä on metodi index, joka antaa luvun sijainnin listassa. Tämän takia algoritmi on kuitenkin hidas, koska metodi index vie aikaa \(O(n)\) ja koko algoritmin aikavaativuus on \(O(n^2)\).

Voimme toteuttaa saman idean tehokkaasti ottamalla käyttöön sanakirjan, joka sisältää kunkin luvun kohdan listassa:

def count_rounds(numbers):
    n = len(numbers)
    
    pos = {}
    for i, x in enumerate(numbers):
        pos[x] = i
        
    rounds = 1
    for i in range(2, n + 1):
        if pos[i] < pos[i - 1]:
            rounds += 1

    return rounds

Tämän jälkeen ei tarvitse käyttää metodia index vaan luvun sijainnin listasta saa haettua tehokkaasti sanakirjasta. Algoritmissa on kaksi silmukkaa, jotka toimivat molemmat ajassa \(O(n)\), joten koko algoritmin aikavaativuus on \(O(n)\).

Esimerkki: Soittolista

Tehtävä

Hyvä lähestymistapa tähän tehtävään on laskea jokaiseen soittolistan kohtaan, kuinka pitkä on pisin kyseiseen kohtaan päättyvä soittolistan osa, jossa ei esiinny kahta samaa laulua. Näistä pituuksista suurin on tehtävän haluttu vastaus. Äskeisessä esimerkissä nämä pituudet ovat:

Kun olemme tietyssä soittolistan kohdassa ja vastaan tulee aiemmin listalla esiintynyt laulu, tämä rajoittaa soittolistan osan pituutta, koska kyseinen laulu ei saa esiintyä kahta kertaa. Niinpä soittolistan osan tulee alkaa laulun edellisen esiintymän jälkeen. Tämän avulla voimme päätellä, mistä kohdasta soittolistan osa voi alkaa.

Seuraava tehokas algoritmi perustuu yllä oleviin ideoihin:

def max_length(songs):
    n = len(songs)
    
    pos = {}
    start = 0
    length = 0
    
    for i, song in enumerate(songs):
        if song in pos:
            start = max(start, pos[song] + 1)
        length = max(length, i - start + 1)
        pos[song] = i
        
    return length

Sanakirja pos kertoo kustakin laulusta, missä kohtaa soittolistaa laulu on esiintynyt viimeksi. Muuttujassa start on kohta, josta soittolistan osa voi alkaa, ja muuttujassa length on pisin soittolistan osan pituus.

Algoritmi käy läpi soittolistan ja päivittää muuttujaa start aina, kun vastaan tulee laulu, joka on esiintynyt aiemmin soittolistalla. Tässä tilanteessa muuttujan start arvo kasvaa, jos laulun edellisen esiintymän kohta on aiempaa suurempi.

Tuloksena oleva algoritmi toimii ajassa \(O(n)\) hajautuksen ansiosta.

Esimerkki: Listan summat

Tehtävä

Merkitään \(\sum(a,b)\) listan osalistan lukujen summaa indeksistä \(a\) indeksiin \(b\). Esimerkiksi äskeisessä listassa \(\sum(1,2)=3+5=8\).

Hyödyllinen tekniikka tällaisessa tehtävässä on tarkastella listan alkuosien lukujen summia eli summia muotoa \(\sum(0,i)\). Tällaisten summien avulla on mahdollista laskea minkä tahansa osalistan summa, koska \(\sum(a,b)\) voidaan esittää muodossa \(\sum(0,b)-\sum(0,a-1)\). Tässä oletuksena on, että \(\sum(0,-1)=0\), jotta kaava toimii myös tapauksessa \(a=0\).

Koetetaan nyt tehdä algoritmi, joka käy listan läpi vasemmalta oikealle ja laskee jokaisessa kohdassa, monessako kyseiseen kohtaan päättyvässä osalistassa lukujen summa on \(x\). Oletetaan, että olemme kohdassa \(i\) ja on jokin aiempi kohta \(j\) niin, että \(\sum(j,i)=x\). Tämä tarkoittaa, että \(\sum(0,i)-\sum(0,j-1)=x\) eli \(\sum(0,j-1)=\sum(0,i)-x\). Toisin sanoen riittää laskea, monessako aiemmassa listan alkuosassa lukujen summa on ollut \(\sum(0,i)-x\).

Tuloksena saadaan \(O(n)\)-aikainen algoritmi:

def count_sublists(numbers, x):
    count = {0: 1}
    prefix_sum = 0
    result = 0
    
    for i in range(len(numbers)):
        prefix_sum += numbers[i]
        if prefix_sum - x in count:
            result += count[prefix_sum - x]
        
        if prefix_sum not in count:
            count[prefix_sum] = 0
        count[prefix_sum] += 1
        
    return result    

Tässä sanakirjaan count lasketaan, montako kertaa mikäkin summa on esiintynyt listan alkuosien summissa. Sanakirjassa on valmiina tyhjää listaa tarkoittava summa \(0\), jotta algoritmi laskee oikein myös tapaukset, joissa osalista alkaa listan alusta.

Miten hajautus toimii?

Tässä luvussa esitellyt Pythonin tietorakenteet käyttävät hajautusta, mutta mitä hajautus tarkoittaa?

Hajautuksessa on ideana luoda hajautustaulu (hash table), johon tallennetaan tietorakenteen sisältö. Hajautustaulussa on \(N\) paikkaa, jotka on indeksoitu \(0 \dots N-1\). Lisäksi tarvitaan hajautusfunktio (hash function), jolla voidaan laskea alkion hajautusarvo (hash value) eli sen sijainti hajautustaulussa.

Tarkastellaan esimerkkiä, jossa joukkoon lisätään merkkijonoja:

words = set()

words.add("apina")
words.add("banaani")
words.add("cembalo")

Pythonin tietorakenteiden käyttämä hajautusfunktio on hash, joka antaa hajautusarvoksi 64-bittisen kokonaisluvun. Funktio toimii näin:

print(hash("apina")) # 4555111141407266158
print(hash("banaani")) # 3986692207867524999
print(hash("cembalo")) # -6117333143154475247

Oletetaan seuraavaksi, että hajautustaulun kokona on \(N=8\). Alkion paikka hajautustaulussa saadaan hajautusarvosta jakojäännöksen avulla:

N = 8

print(hash("apina") % N) # 6
print(hash("banaani") % N) # 7 
print(hash("cembalo") % N) # 1

Tässä tapauksessa hajautustaulun sisällöksi tulee:

Hajautustaulun etuna on, että kun halutaan etsiä tietty alkio, ei tarvitse käydä läpi koko hajautustaulua vaan riittää laskea alkion hajautusarvo, joka kertoo suoraan alkion paikan hajautustaulussa. Niinpä on tehokasta tarkastaa, onko tietty alkio joukossa sekä poistaa alkio joukosta.

Hajautuksessa on kuitenkin yksi ongelma: kahdelle eri alkiolle voi tulla sama paikka hajautustaulussa. Oletetaan esimerkkinä, että yllä olevaan joukkoon lisätään vielä merkkijono "dyyni":

print(hash("dyyni")) # -6000775759920277714
print(hash("dyyni") % N) # 6

Tässä merkkijonoilla "apina" ja "dyyni" on sama paikka hajautustaulussa, koska niiden hajautusarvojen jakojäännös \(N\):llä on sama. Tällaista tilannetta kutsutaan nimellä törmäys (collision). Riippumatta hajautusfunktiosta törmäyksiä voi esiintyä, koska eri alkioiden määrä on suurempi kuin hajautustaulun koko \(N\). Niinpä hajautustaulun tulee pystyä käsittelemään törmäyksiä.

Yksi tapa käsitellä törmäykset on toteuttaa alkion paikan valinta niin, että jos hajautusarvon mukainen paikka on jo toisen alkion käytössä, alkiolle aletaan etsiä uutta paikkaa sopivan matemaattisen kaavan avulla. Etsintää jatketaan, kunnes hajautustaulusta löytyy tyhjä paikka, johon alkio voidaan tallentaa. Esimerkiksi Pythonissa hajautustaulun toteutus perustuu tällaiseen ideaan.

Käytännössä törmäyksiä ei esiinny yleensä paljon, jos hajautusfunktio, hajautustaulun koko ja törmäysten käsittelytapa on valittu sopivalla tavalla. Tämän ansiosta voidaan olettaa, että alkion paikan etsiminen ei vie yleensä kauan aikaa ja hajautustaulun operaatiot toimivat \(O(1)\)-ajassa. Silti on mahdollista, että operaatiot toimivat hitaasti, jos syöte on valittu sopivalla tavalla.

Mitä voi hajauttaa?

Seuraava koodi ei toimi Pythonissa:

lists = set()
lists.add([1, 2, 3]) # TypeError: unhashable type: 'list'

Ongelmana on, että listalle ei voi laskea hajautusarvoa:

print(hash([1, 2, 3])) # TypeError: unhashable type: 'list'

Pythonissa on periaatteena, että hajautusarvon voi laskea vain oliolle, jonka sisältö on muuttumaton (immutable). Listan sisältö ei ole muuttumaton, koska listassa on esimerkiksi metodi append, joka lisää siihen uuden alkion. Tämän vuoksi listalle ei voi laskea hajautusarvoa.

Muuttumattomia olioita ovat esimerkiksi luvut, merkkijonot ja näitä sisältävät tuplet. Niille voi laskea hajautusarvon:

print(hash(123)) # 123
print(hash("apina")) # 4555111141407266158
print(hash((3, -5))) # -3089947874767036032

Omaa luokkaa voi käyttää hajautuksessa määrittelemällä sille seuraavat metodit:

• __hash__: palauttaa olion hajautusarvon
• __eq__: vertailee, onko olion sisältö sama kuin toisen olion sisältö

Seuraavassa on esimerkki metodien määrittelystä. Tässä metodi __hash__ palauttaa olion sisältöä vastaavan tuplen hajautusarvon.

class Location:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __hash__(self):
        return hash((self.x, self.y))

    def __eq__(self, other):
        return (self.x, self.y) == (other.x, other.y)

Tämän jälkeen esimerkiksi seuraava koodi toimii tarkoitetulla tavalla:

locations = set()
locations.add(Location(1, 2))
locations.add(Location(3, -5))

Hajautus muissa kielissä

Hajautusta käyttävät tietorakenteet ovat yleisiä eri ohjelmointikielissä. Monissa kielissä Pythonin sanakirjaa vastaa tietorakenne nimeltä map, josta voidaan käyttää suomeksi nimeä hakemisto.

C++:ssa tietorakenteet std::unordered_set ja std::unordered_map toteuttavat hajautusta käyttävän joukon ja hakemiston.

std::unordered_set<int> numbers;

numbers.add(1);
numbers.add(2);
numbers.add(3);

std::unordered_map<std::string, int> weights;

weights["apina"] = 100;
weights["banaani"] = 1;
weights["cembalo"] = 500;

Javassa vastaavat tietorakenteet ovat HashSet ja HashMap:

HashSet<Integer> numbers = new HashSet<Integer>();

numbers.add(1);
numbers.add(2);
numbers.add(3);

HashMap<String, Integer> weights = new HashMap<String, Integer>();

weights.put("apina", 100);
weights.put("banaani", 1);
weights.put("cembalo", 500);

JavaScriptissä tietorakenne Set toteuttaa joukon:

let numbers = new Set();

numbers.add(1);
numbers.add(2);
numbers.add(3);

JavaScriptin perinteinen tapa luoda hakemisto on määritellä olio:

let weights = {};

weights["apina"] = 100;
weights["banaani"] = 1;
weights["cembalo"] = 500;

Uudempi tapa on käyttää erillistä tietorakennetta Map:

let weights = new Map();

weights.set("apina", 100);
weights.set("banaani", 1);
weights.set("cembalo", 500);