5. Asociatívne polia

S dátovou štruktúrou slovník, resp. asociatívne pole (pythonovský typ dict, niekedy sa mu hovorí aj map, keďže sa mapujú kľúče na nejaké hodnoty) už máme dlhšie nemalé programátorské skúsenosti:

  • je podobné obyčajnému zoznamu s tým rozdielom, že indexom nemusia byť len celé čísla od 0 po nejakú konkrétnu hodnotu, ale indexom môže byť skoro hocijaká hodnota, napr. aj desatinné čísla, reťazce aj n-tice hodnôt, napr.

    >>> d = {}
    >>> d[3.14] = 'pi'
    >>> d['sto'] = 100
    >>> d[100, 200] = turtle.Turtle()
    
  • indexy asociatívnych polí nazývame kľúče a máme možnosť získať postupnosť všetkých kľúčov, napr.

    >>> list(d.keys())   # metóda keys() je iterátor
    [3.14, (100, 200), 'sto']
    
  • vieme získať aj všetky hodnoty, ktoré sú asociované (namapované) na kľúče, napr.

    >>> list(d.values())   # metóda values() je iterátor
    ['pi', <turtle.Turtle object>, 100]
    
  • okrem tohoto vieme získať aj všetky dvojice (kľúč, hodnota), z ktorých je asociatívne pole zložené, napr.

    >>> list(d.items())   # metóda items() je iterátor
    [(3.14, 'pi'), ((100, 200), <turtle.Turtle object>), ('sto', 100)]
    

V prvom ročníku sme použili takéto asociatívne pole na zisťovanie počtu výskytov nejakých hodnôt (frekvenčná tabuľka), napr. v zozname:

import random

zoz = [random.randrange(100) for i in range(1000)]
d = {}
for prvok in zoz:
    d[prvok] = d.get(prvok, 0) + 1

print('najcastejsie: ', *sorted(d.items(), key=lambda x: x[1])[-5:])

Tento program vypíše 5 čísel s najčastejším výskytom v danom zozname. Kľúčmi asociatívneho poľa d sú prvky zoznamu zoz a príslušnými hodnotami sú počty výskytov daného prvku. Kľúčmi nemusia byť len čísla, ale aj reťazce. Tento program bude fungovať napr. aj pre takýto zoznam slov:

zoz = 'mama ma emu a ema ma mamu a mama emy ma mamu mamy'.split()

Cieľom tejto témy je ukázať, akým spôsobom musia byť naprogramované tieto operácie (metódy), prípadne aká je ich zložitosť.

Abstraktný dátový typ

Budeme sa zaoberať rôznymi implementáciami a budeme skúmať efektívnosť zodpovedajúcich operácií. Preto najprv zvolíme minimálnu množinu operácií, ktoré charakterizujú tento typ, teda, keď ich zrealizujeme, môžeme tvrdiť, že sme implementovali asociatívne pole. V každom prípade je asociatívne pole dátovou štruktúrou, ktorá nejako uchováva dvojice (kľúč, hodnota) pričom kľúč je jedinečný, t. j. môže sa vyskytovať len v jednej dvojici.

Operácie budeme porovnávať s pythonovským typom dict, teda s premennou d a s dvojicou (key, value), teda pre asociatívne pole a:

  • a.valueof(key) vráti príslušnú hodnotu k danému kľúču
    • ak pre daný kľúč neexistuje príslušná hodnota, metóda vyvolá KeyError
    • v Pythone tomu zodpovedá d[key]
  • a.add(key, value) zaradí do asociatívneho poľa novú dvojicu (key, value)
    • ak už predtým v poli existovala dvojica s týmto kľúčom, tak ju nahradí novou dvojicou
    • v Pythone tomu zodpovedá d[key] = value
  • a.delete(key) vyhodí z asociatívneho poľa dvojicu s daným kľúčom
    • ak daný kľúč neexistuje, metóda vyvolá KeyError
    • v Pythone tomu zodpovedá del d[key]
  • len(a) (teda metóda a.__len__()) vráti počet prvkov (dvojíc) v asociatívnom poli
    • v Pythone tomu tiež zodpovedá len(d)
  • iter(a) (teda metóda a.__iter__()) vráti iterátor, vďaka ktorému môžeme postupne prechádzať všetky kľúče
    • v Pythone tomu tiež zodpovedá iter(d)
    • najčastejšie iterovanie využijeme vo for-cykle: for kluc in a: ...

Zadefinujme abstraktnú triedu MapBase, ktorá bude obsahovať všetky tieto metódy, ale aj podtriedu _Item na uchovávanie dvojíc (key, value):

from abc import ABC, abstractmethod

class MapBase(ABC):

    class _Item:
        def __init__(self, key, value):
            self._key, self._value = key, value

        def __repr__(self):
            return repr(self._key) + ':' + repr(self._value)

    #------------------

    @abstractmethod
    def valueof(self, key):
        pass

    @abstractmethod
    def add(self, key, value):
        pass

    @abstractmethod
    def delete(self, key):
        pass

    @abstractmethod
    def __len__(self):
        pass

    @abstractmethod
    def __iter__(self):
        pass

Zrejme sa táto trieda zatiaľ testovať nedá, musíme najprv implementovať nejakú konkrétnu realizáciu. V skutočnosti nebude rôzne realizácie implementovať ako triedy, ale pre čitateľnosť algoritmov ich zapíšeme len ako tri globálne funkcie valueof(key), add(key, value) a delete(key), ktoré pracujú s jedným globálnym zoznamom table. Z tohto dôvodu presťahujeme aj pomocnú lokálnu triedu _Item ako globálnu definíciu Item:

class Item:
    def __init__(self, key, value):
        self.key, self.value = key, value
    def __repr__(self):
        return repr(self.key) + ':' + repr(self.value)

table = [...]

def valueof(key):
    ...
    raise KeyError

def add(key, value):
    ...

def delete(self, key):
    ...
    raise KeyError

Podobne upravíme aj samotné otestovanie realizácie:

import random

zoz = [random.randrange(100) for i in range(10000)]
d = {}
for i in zoz:
    try:
        add(i, valueof(i) + 1)
    except KeyError:
        add(i, 1)
    d[i] = d.get(i, 0) + 1

set1 = {(it.key, it.value) for it in table}      # pripadne tu pozmeníme generovanie dvojíc
set2 = set(d.items())
print(set1 == set2)

Asociatívne pole pomocou neutriedenej postupnosti

Najjednoduchším typom implementácie asociatívneho poľa bude použitie obyčajného pythonovského zoznamu (typ list), do ktorého budeme ukladať dvojice v tom poradí, ako prichádzajú (s novým kľúčom) pomocou operácie add. Základné operácie budeme teda realizovať takto:

  • samotný obsah asociatívneho poľa budeme ukladať do tabuľky table typu list, prvkami tohto zoznamu budú neskôr dvojice typu Item
  • funkcia valueof(key) vyhľadá key v zozname table: keďže zoznam nie je nijako usporiadaný, musí ho prehľadávať postupne cez všetky jeho prvky, keď nájde prvok s hľadaným kľúčom, vráti príslušnú hodnotu, inak vyvolá výnimku KeyError
  • funkcia add(key, value) opäť vyhľadá prvok s daným kľúčom a ak ho nájde vymení mu príslušnú hodnotu, inak pridá nový prvok s kľúčom a hodnotou (key, value) na koniec zoznamu table
  • funkcia delete(key) vyhľadá prvok s daným kľúčom a ak ho nájde, zo zoznamu ho vyhodí, inak, ak nenašiel prvok s hľadaným kľúčom, vyvolá výnimku KeyError

Zapíšme túto implementáciu:

# implementácia UnsortedMap

table = []

def valueof(key):
    for item in table:
        if key == item.key:
            return item.value
    raise KeyError

def add(key, value):
    for item in table:
        if key == item.key:
            item.value = value
            return
    table.append(Item(key, value))

def delete(self, key):
    for ix in range(len(table)):
        if key == table[ix].key:
            del table[ix]
            return
    raise KeyError

Môžete prekontrolovať, že tento program bude fungovať nielen pre zoznam čísel, ale aj zoznam reťazcov. Ak ale zoznam reťazcov bude trochu väčšie (vytvoríme ho napr. prečítaním zo súboru), výpočet môže trvať aj desiatky sekúnd.

Dôvodom, prečo je realizácia neutriedeným zoznamom tak pomalá, je ten, že operácie add() aj valueof() sú výrazne pomalšie ako originálne pythonovské operácie s asociatívnym poľom. Zapíšme do tabuľky zložitosť operácií našej triedy:

Zložitosť operácií
operácie unsorted  
valueof() O(n)  
add() O(n)  
delete() O(n)  

Teraz by malo byť jasné, prečo náš testovací program s frekvenčnou tabuľkou môže trvať tak dlho: for-cyklus, ktorý zvyšuje o 1 ďalší výskyt hodnoty, má zložitosť O(n**2). Toto pre veľké n môže naozaj trvať dosť dlho.

Asociatívne pole pomocou utriedenej postupnosti

Predchádzajúcu implementáciu neutriedeným zoznamom vylepšíme tak, že zoznam table budeme udržiavať utriedený podľa kľúča. Hoci v tejto verzii predpokladáme jedno dôležité obmedzenie, aj tak to otestujeme. Tým obmedzením je podmienka, že všetky kľúče sa musia dať navzájom porovnávať. To ale znamená, že v našej novej implementácii by už nemalo šancu prejsť ani pythonovské:

>>> d = {}
>>> d[3.14] = 'pi'
>>> d['sto'] = 100

Kľúče 3.14 a 'sto' sa nedajú navzájom porovnať na to, aby sme zistili, ktorý z nich je menší. Keď ale zanedbáme toto obmedzenie, dostávame realizáciu, ktorá má šancu byť rýchlejšia ako UnsortedMap.

V implementácii sme použili pomocnú funkciu find_index(), pomocou ktorej veľmi rýchlo vyhľadáme index požadovaného kľúča.

# implementácia SortedMap

table = []

def find_index(key, low, high):
    '''vrati bud index kluca, alebo poziciu, kam vlozit'''
    if high < low:
        return high + 1
    else:
        mid = (low + high) // 2
        if key == table[mid].key:
            return mid
        elif key < table[mid].key:
            return find_index(key, low, mid - 1)
        else:
            return find_index(key, mid + 1, high)

def valueof(key):
    ix = find_index(key, 0, len(table) - 1)
    if ix == len(table) or table[ix].key != key:
        raise KeyError
    return table[ix].value

def add(key, value):
    ix = find_index(key, 0, len(table) - 1)
    if ix < len(table) and table[ix].key == key:
        table[ix].value = value
    else:
        table.insert(ix, Item(key, value))

def delete(key):
    ix = find_index(key, 0, len(table) - 1)
    if ix == len(table) or table[ix].key != key:
        raise KeyError
    del table[ix]

Ak teraz spustíme rovnaké testy, ako pri predchádzajúcej implementácii, môžeme vidieť, že aj táto verzia je funkčná, dokonca je o trochu rýchlejšia, ale stále pre veľký zoznam trvá desiatky sekúnd. Doplňme tabuľku zložitosti operácií aj pre túto triedu:

Zložitosť operácií
operácie unsorted sorted  
valueof() O(n) O(log n)  
add() O(n) O(log n), O(n)  
delete() O(n) O(n)  

Operácia add() má zložitosť O(log n) len v prípade, že daný kľúč sa v poli nachádzal už predtým. Inak musí vložiť nový prvok (key, value) na správne miesto do zoznamu table. Keďže toto vkladanie sa robí metódou insert(), zložitosť operácie add() bude vtedy O(n).

Hašovacia tabuľka

V ďalšej časti budeme v niekoľkých krokoch vylepšovať jednu novú ideu, ktorú postupne dotiahneme až do veľmi zaujímavej zložitosti operácií.

Index ako kľúč

Začneme tým, že budeme predpokladať:

  • kľúče budú len celé čísla
  • kľúče budú mať hodnoty len z intervalu <0, max-1> (pre dopredu známe max, tzv. kapacita tabuľky)

Vďaka tomuto obmedzeniu môžeme výrazne zjednodušiť realizáciu všetkých operácií:

  • už na začiatku sa v zozname table vyhradí maximálna kapacita a do každého prvku sa priradí None
  • funkcia valueof(key): keďže key je indexom do zoznamu, stačí pozrieť, či tam nie je None (vtedy vyvolá výnimku KeyError) a vráti hodnotu v tomto prvku; zrejme skontroluje aj to, či je kľúč zo správneno intervalu
  • funkcia add(key, value): ak je key index zo správneho intervalu, priamo na túto pozíciu priradí novú hodnotu
  • funkcia delete(key): ak je key index zo správneho intervalu, do zoznamu na príslušné miesto priradí None

Implementácia:

# implementácia TestMap

table = [None] * 1000    # nejaka predpokladana kapacita tabulky

def valueof(key):
    if key < 0 or key >= len(table) or table[key] is None:
        raise KeyError
    return table[key].value

def add(key, value):
    if key < 0 or key >= len(table):
        raise KeyError
    table[key] = Item(key, value)

def delete(key):
    if key < 0 or key >= len(table) or table[key] is None:
        raise KeyError
    table[key] = None

Zložitosť všetkých operácií je teraz O(1):

Zložitosť operácií
operácie unsorted sorted test  
valueof() O(n) O(log n) O(1)  
add() O(n) O(n) O(1)  
delete() O(n) O(n) O(1)  

Vyzerá to veľmi optimisticky. Naozaj aj test s väčším počtom dvojíc, kde je kľúč aj z väčšieho intervalu, prejde veľmi rýchlo:

zoz = [random.randrange(1000000) for i in range(50000)]
...

Zrejme veľkosť zoznamu table treba teraz nastaviť na maximálnu hodnotu kľúča, teda na 1000000.

Riešenie kolízií

V ďalšom kroku vylepšovania tejto idey zrušíme predpoklad, vďaka ktorému sme všetky prvky asociatívneho poľa mohli ukladať priamo do jedného veľkého zoznamu, lebo kľúče priamo zodpovedali indexom do tohto zoznamu (od 0 do nejakého max-1). Teraz vyhradíme menší zoznam, ako je rozsah očakávaných kľúčov a pozíciu v zozname zistíme tak, že kľúč vydelíme veľkosťou tohto zoznamu a zvyšok po delení bude hľadaný index. Kvôli tomuto sa ale môže stať to, že pre dva rôzne kľúče dostávame rovnaký index do zoznamu. Tomuto hovoríme kolízia a musíme to nejako rozumne vyriešiť.

Naša prvá verzia riešenia kolízií, bude pomocou tzv. vedierok (bucket): prvkami samotného zoznamu budú namiesto dvojíc (kľúč, hodnota) vedierka, t. j. postupnosti všetkých takých dvojíc (kľúč, hodnota), pre ktoré sa kľúč prepočítal na ten istý index prvku zoznamu (majú rovnaký zvyšok po delení kľúča veľkosťou zoznamu). Vedierka môžeme realizovať rôznymi spôsobmi (napr. spájaným zoznamom), my na to použijeme pythonovský zoznam (opäť typ list) a pridávať nový kľúč budeme vždy na koniec tohto malého zoznamu (vedierka).

Nová verzia realizácie asociatívneho poľa pomocou vedierok:

# implementácia TestMap1

table = [[] for i in range(50)]    # nejaka predpokladana kapacita tabulky

def valueof(key):
    bucket = table[key % len(table)]
    for item in bucket:
        if item.key == key:
            return item.value
    raise KeyError

def add(key, value):
    bucket = table[key % len(table)]
    for item in bucket:
        if item.key == key:
            item.value = value
            return
    bucket.append(Item(key, value))

def delete(key):
    bucket = table[key % len(table)]
    for i in range(len(bucket)):
        if bucket[i].key == key:
            del bucket[i]
            return
    raise KeyError

Táto definícia sa veľmi podobá predchádzajúcej realizácii TestMap s tým rozdielom, že zoznam table obsahuje vedierka namiesto samotných prvkov Item. Každé vedierko je na začiatku prázdny zoznam, t. j. []. Každá operácia najprv zistí, s ktorým vedierkom sa bude pracovať a potom túto operáciu urobí práve len s týmto jedným vedierkom. Každé vedierko je teda malé asociatívne pole realizované ako UnsortedMap. Z toho potom vyplýva táto zložitosť operácií:

Zložitosť operácií
operácie unsorted sorted test test1  
valueof() O(n) O(log n) O(1) O(k)  
add() O(n) O(n) O(1) O(k)  
delete() O(n) O(n) O(1) O(k)  

kde k v O(k) označuje zložitosť vedierka, keďže zložitosť operácií závisí od veľkosti zoznamu s vedierkom. Kým sú vedierka malé, k je malá konštanta, potom sa aj všetky operácie blížia k O(1). Keď sa budú vedierka veľkosťou blížiť k n, zložitosť operácií bude O(n). Takže by mohlo stačiť vhodne zvoliť veľkosť poľa tak, aby sa zložitosť blížila k O(1).

Hašovacia funkcia

Verzia TestMap1 má ešte takýmalý ale podstatný nedostatok (obmedzenie), že kľúčom musí byť celé číslo. Ak by sme potrebovali napr. ukladať kľúče typu znakový reťazec, museli by sme na to zvoliť nejakú rozumnú stratégiu. Zvoľme takýto spôsob prekódovania reťazca na celé číslo:

def koduj(retazec):
    vysl = 0
    for znak in retazec:
        vysl = vysl + ord(znak)
    return vysl

Takáto funkcia naozaj prevedie ľubovoľný reťazec na celé číslo, ale má takúto nie najlepšiu vlastnosť: všetky tieto reťazce 'abc', 'acb', 'bac', 'bca', … sa zakódujú rovnakým celým číslom 294. Zrejme tomuto algoritmu nezáleží na poradí znakov v reťazci. Vhodnejšie by bolo, keby funkcia počítala kód napr. takto:

def koduj(retazec):
    vysl = 0
    for znak in retazec:
        vysl = 100 * vysl + ord(znak)
    return vysl

Konštanta 100 sa častejšie nahradí nejakou mocninou 2, napr. 32. Dokonca malým vylepšením môžeme zabezpečiť, aby funkcia fungovala nielen pre reťazce ale aj pre ľubovoľný iný typ:

def koduj(kluc):
    vysl = 0
    for znak in str(kluc):
        vysl = 32 * vysl + ord(znak)
    return vysl

Vďaka takémuto kódovaniu, by sme mohli zabezpečiť, aby asociatívne pole fungovalo naozaj pre ľubovoľný typ kľúča. V našom prípade sa takejto funkcii hovorí hašovacia funkcia (hash function). Teda hašovacou funkciou sa nazýva taká funkcia, ktorá z hodnoty (skoro) ľubovoľného typu vyrobí číselný kód, ktorý sa dá použiť na mapovanie kľúčov na indexy tabuľky. Štruktúra, ktorej kľúče mapujeme na indexy tabuľky pomocou hašovacej funkcie, sa nazýva hašovacia tabuľka (hash table). Upravme TestMap1 na hašovaciu tabuľku:

# implementácia HashMap

table = [[] for i in range(50)]    # nejaka predpokladana kapacita tabulky

def hash(key):
    res = 0
    for ch in str(key):
        res = res * 32 + ord(ch)
    return res

def valueof(key):
    ix = hash(key) % len(table)
    bucket = table[ix]
    for item in bucket:
        if item.key == key:
            return item.value
    raise KeyError

def add(key, value):
    ix = hash(key) % len(table)
    bucket = table[ix]
    for item in bucket:
        if item.key == key:
            item.value = value
            return
    bucket.append(Item(key, value))

def delete(key):
    ix = hash(key) % len(table)
    bucket = table[ix]
    for i in range(len(bucket)):
        if bucket[i].key == key:
            del bucket[i]
            return
    raise KeyError

Zhrňme:

  • použili sme tu pomocnú funkciu hash(), ktorá ľubovoľný kľúč prevedie na celé číslo (najprv ju prevedie na reťazec a z neho potom postupne poskladá celé číslo)
  • aby sme z tohto čísla dostali index do poľa, zistíme zvyšok po delení veľkosťou zoznamu table - takto sa dostávame k príslušnému vedierku (bucket)
  • zrejme musíme už na začiatku nejako rozumne odhadnúť veľkosť zoznamu: skúsenosti ukazujú, že by malo byť aspoň dvojnásobne veľké ako sa odhaduje počet kľúčov, inak bude veľmi narastať počet kolízií a budú neúmerne veľké skupiny dvojíc s rovnakým kľúčom

Teraz zvoľme takýto zjednodušený test:

zoz = [(55,'a'),(42,'b'),(15,'c'),(60,'d'),(78,'e'),
       (35,'f'),(22,'g'),(10,'h'),(11,'i'),(8,'j'),
       (75,'k'),(32,'l')]
# kapacita nech je 10
for key, value in zoz:
    add(key, value)

Do asociatívneho poľa sme postupne pridali týchto 12 dvojíc. Keďže kľúčom sú len celé čísla, zjednodušíme funkciu hash(), tak aby hašovacia funkcia priamo vrátila kľúč:

def hash(key):
    return key

Vďaka tomuto vieme aj ručne odkrokovať, ako sa vedierka postupne zapĺňajú (budeme počítať zvyšok po delení 10, teda nás zaujíma len posledná cifra kľúča). Po zaradení všetkých dvanástich dvojíc (kľúč, hodnota) dostávame takýto obsah poľa table aj s vedierkami:

for index, bucket in enumerate(table):
    print(index, bucket)

takýto výpis:

0 [60:d, 10:h]
1 [11:i]
2 [42:b, 22:g, 32:l]
3 []
4 []
5 [55:a, 15:c, 35:f, 75:k]
6 []
7 []
8 [78:e, 8:j]
9 []

Vidíme, že niektoré vedierka sú prázdne, kým v niektorých je viac prvkov, napr. piate vedierko obsahuje až 4 prvky.

Takémuto hašovaniu sa hovorí uzavreté adresovanie alebo zreťazené hašovanie (kolízie sú uzavreté v jednej reťazi dvojíc - niekedy sa vedierko realizuje nie zoznamom dvojíc ale spájaným zoznamom). Aby nás to viac poplietlo, uzavreté adresovanie označuje otvorené hašovanie. Táto realizácia má tú výhodu, že sa ľahko implementuje, ale má aj niekoľko nedostatkov, napr.:

  • má vyššie pamäťové nároky (okrem samotných dvojíc, zoznamu ako hašovacej tabuľky potrebujeme ešte minimálne toľko ďalších štruktúr ako je počet neprázdnych vedierok) - čím viac prvkov je vo vedierkach tým viac je nevyužitého priestoru v samotnej tabuľke (sú prázdne vedierka)
  • ak sa vedierka zaplnia nad nejakú kritickú hranicu (napr. príde priveľa dvojíc s rovnakým indexom do tabuľky), výrazne sa spomalí celá realizácia asociatívneho poľa (operácie môžu mať zložitosť O(n)) - čím viac je prvkov v tabuľke, tým sú všetky operácie s ňou pomalšie
  • ak máme viac kľúčov s veľmi blízkymi hašovacími hodnotami, tak tieto sa zvyknú sústrediť blízko seba (ak robíme len modulo veľkosťou tabuľky)

Toto uzavreté adresovanie môžeme trochu vylepšiť, napr. takto:

  • na začiatku rezervujeme len malú tabuľku vedierok a tento zoznam budeme v niektorých prípadoch nafukovať (podobne ako sme to robili pri dynamických poliach a operácii append)

  • prázdne vedierko nebudeme uchovávať ako prázdny zoznam [] ale ako hodnotu None (urýchli to zmenu veľkosti resize)

  • takže tabuľka table bude mať počiatočnú vyhradenú veľkosť napr. 11:

    table = [None] * 11
    
  • upravíme aj hašovaciu funkciu tak, že bude priamo počítať index do tabuľky, teda bude počítať zvyšok po delení veľkosťou tabuľky:

    def hash(key):
        res = 0
        for ch in str(key):
            res = res * 32 + ord(ch)
        return res % len(table)
    
  • keďže prázdne vedierka (bucket) sú teraz v tabuľke zaznačené ako None, nemôžeme ich hneď prechádzať pomocou for-cyklu, ale najprv musíme otestovať, či nie sú prázdne, napr.

    def valueof(key):
        bucket = table[hash(key)]
        if bucket is not None:
            for item in bucket:
                if item.key == key:
                    return item.value
        raise KeyError
    

Nafukovať tabuľku budeme vo funkcii add() vždy vtedy, keď počet prvkov, ktoré sú v ňom uložené, presiahne nejakú konkrétnu hranicu. Tu bude dôležitý práve pomer zaplnenia tabuľky (tzv. load factor), t.j. pomer počtu zaplnených prvkov k veľkosti celej tabuľky. Nemalo by to presiahnuť hodnotu 1. V praxi sa ukazuje, že tabuľka má dobrú veľkosť, keď je zaplnená na maximálne 90%. Všimnite si, že vo vyššie uvedenom príklade s hašovacou tabuľkou veľkosti 10, po pridaní aj posledného kľúča 22, bude load factor 1.2, čo je viac ako 90%. Tabuľku zrejme bude treba nafukovať vtedy, keď sa do nej bude pridávať nový prvok (pomocou add()) a pritom sa presiahne pomer zaplnenia

  • napr.

    def add(key, value):
        ...
        if num > len(table) * 0.9:
            resize(len(table) * 2)
    

Samotný resize tabuľky bude podobný tomu, ako sme to robili pri nafukovaní dynamického poľa v operácii append():

  • do pomocného zoznamu si odložíme momentálny obsah tabuľky (všetky dvojice (kľúč, hodnota))
  • vytvoríme novú prázdnu tabuľku požadovanej veľkosti
  • postupne sem pridáme všetky zapamätané dvojice (kľúč, hodnota)

Kompletný listing pre zreťazené hašovanie:

# implementácia ChainHashMap

table = [None] * 11
num = 0               # skutocny pocet prvkov

def hash(key):
    res = 0
    for ch in str(key):
        res = res * 32 + ord(ch)
    return res % len(table)

def valueof(key):
    bucket = table[hash(key)]
    if bucket is not None:
        for item in bucket:
            if item.key == key:
                return item.value
    raise KeyError

def add(key, value):
    ix = hash(key)
    bucket = table[ix]
    if bucket is not None:
        for item in bucket:
            if item.key == key:
                item.value = value
                return
    else:
        bucket = table[ix] = []
    bucket.append(Item(key, value))
    global num; num += 1
    if num > len(table) * 0.9:
        resize(len(table) * 2)

def delete(key):
    ix = hash(key)
    bucket = table[ix]
    if bucket is not None:
        for i in range(len(bucket)):
            if bucket[i].key == key:
                del bucket[i]
                global num; num -= 1
                if len(bucket) == 0:
                    table[ix] = None
                return
    raise KeyError

def resize(new_size):
    global table, num
    old_table = table
    table = [None] * new_size
    num = 0
    for bucket in old_table:
        if bucket is not None:
            for item in bucket:
                add(item.key, item.value)

Aj túto implementáciu môžeme otestovať podobne ako sme to testovali predtým. Globálne premenné num a table sa zrejme pri implementácii pomocou triedy zmenia na atribúty.

Otvorené adresovanie

Zmeňme stratégiu pri riešení kolízií:

  • do tabuľky budeme na vypočítané pozície ukladať priamo dvojicu (kľúč, hodnota) - namiesto reťaze dvojíc
  • kým nepríde ku kolízii (máme umiestniť novú dvojicu (kľúč, hodnota) na obsadenú pozíciu), je všetko v poriadku
  • ak je teda vypočítaná pozícia už obsadená, treba vybrať nejakú inú, ale tak, aby sme ju pri neskoršom hľadaní našli
  • možností je viac, ale najjednoduchšou je použiť nasledovné políčko v tabuľke, resp. postupne hľadať najbližšie voľné
  • tomuto hovoríme otvorené adresovanie, tieto dva pojmy sú synonymá, lebo:
    • otvorené adresovanie (open addressing) označuje, že vypočítaná adresa (pomocou hash()) ešte nie je konečná, ale od tejto adresy sa bude hľadať konečná pozícia, bude to fungovať len v uzavretom hašovaní
    • uzavreté hašovanie (closed hashing) označuje, že vkladať sa bude iba niekam do tejto jednej tabuľky a nikam inam, dá sa to docieliť len otvoreným adresovaním
  • na rozdiel od uzavreté adresovanie, kde aj tieto dva pojmy sú synonymá:
    • uzavreté adresovanie (closed addressing) označuje, že vypočítaná adresa jednoznačne určuje presnú pozíciu tabuľky (teda kde sa nachádza vedierko), ale toto bude fungovať len v otvorenom hašovaní, kde na „jednej pozícií“ (v jednom vedierku) sa nejako môže nachádzať viac prvkov
    • otvorené hašovanie (open hashing) označuje, že do tabuľky sa naozaj žiaden objekt nevkladá, vkladá sa do vedierok, ktoré sú niekde mimo samotnej tabuľky

Keďže pri kolízii hľadáme najbližšie voľné políčko v tabuľke, budeme tomu hovoriť linear probing, t.j. lineárne pokusy. Výpočet indexu by sme mohli zapísať:

index = (hash(key) + i) % N

Kde N je veľkosť tabuľky a i je i-ty pokus o nájdenie voľného miesta, teda na začiatku 0, potom 1, …

Hľadanie skutočnej pozície kľúča bude teraz trochu komplikovanejšie (zapíšeme to do pomocnej funkcie find(key)):

  • podľa kľúča zistíme, na akom indexe by sa mal nachádzať (pomocná funkcia hash(key))
  • ak je to prázdne políčko tabuľky, znamená to, že sme nenašli a vrátime hodnotu False
  • ak je to dvojica (kľúč, hodnota), porovnáme kľúč s hľadaným key, ak to sedí, vrátime True a nájdený index
  • inak zvýšime index o 1 (prípadne urobíme modulo veľkosť tabuľky) a pokračujeme v hľadaní

Ak nie je tabuľka úplne zaplnená, určite skončíme buď na None alebo na políčku s hľadaným kľúčom. Podobne ako pri zreťazenom hašovaní, aj pri tomto otvorenom adresovaní (uzavretom hašovaní) musíme zabezpečiť, aby boli v tabuľke voľné miesta. V tomto prípade sú voľné miesta ešte dôležitejšie, lebo nám robia zarážky pri hľadaní. Preto load factor by mal byť výrazne menší ako 1, odporúča sa medzi 0.5 a 0.8. Napr. rôzne implementácie hašovacích tabuliek v rôznych programovacích jazykoch používajú rôzne hodnoty, napr. v Jave je to 75%, v Pythone 66%.

Vyhodenie prvku z tabuľky

Keď nájdeme prvok, ktorý chceme vyhodiť (vo funkcii delete()), nemôžeme ho jednoducho nahradiť None, lebo takýto None pre nás znamená zarážku v hľadaní, teda v lineárnych pokusoch (linear probing). Vyhadzovaný prvok nahradíme špeciálnou hodnotou avail (môže byť ľubovoľného typu, len aby sme to rozpoznali od None a od dvojice Item). Pri hľadaní políčka s kľúčom budeme túto hodnotu avail preskakovať, ale pri pridávaní nového kľúča (vo funkcii add()) je tento avail kandidátom na pridanie novej dvojice.

Takže musíme opraviť pomocnú funkciu find(key) tak, aby preskakovala políčka s avail, ale pritom si prvý takýto výskyt zapamätala, keby bolo treba do tabuľky pridávať. Funkcia bude vždy vracať dvojicu:

  • (True, index) - keď nájde políčko s hľadaným kľúčom, v index je jeho pozícia
  • (False, index) - keď nenájde takéto políčko, v index je pozícia prvého voľného políčka na zápis (buď je to políčko s avail alebo None)
avail = 'avail'

def find(key):
    ix = hash(key)
    av = None                # prvy volny
    while True:
        item = table[ix]
        if item is None:
            if av is None:
                av = ix
            return False, av
        if item == avail:
            if av is None:
                av = ix
        elif item.key == key:
            return True, ix
        ix = (ix + 1) % len(table)

Všimnite si, že avail je tu nejaký znakový reťazec, čo sa ľahko rozlíši od None alebo Item.

Kompletný listing pre otvorené adresovanie:

# implementácia ProbeHashMap

table = [None] * 11    # nejaka predpokladana kapacita tabulky
avail = 'avail'
num = 0

def hash(key):
    res = 0
    for ch in str(key):
        res = res * 32 + ord(ch)
    return res % len(table)

def find(key):
    '''vrati dvojicu
        (True, index) - ak najde kluc
        (False, prvy volny) - ak nenajde kluc
    '''
    ix = hash(key)
    av = None                # prvy volny
    while True:
        item = table[ix]
        if item is None:
            if av is None:
                av = ix
            return False, av
        if item == avail:
            if av is None:
                av = ix
        elif item.key == key:
            return True, ix
        ix = (ix + 1) % len(table)

def valueof(key):
    found, ix = find(key)
    if found:
        return table[ix].value
    raise KeyError

def add(key, value):
    found, ix = find(key)
    if found:
        table[ix].value = value
        return
    global num; num += 1
    table[ix] = Item(key, value)
    if num > len(table) * 0.66:
        resize(len(table) * 2)

def delete(key):
    found, ix = find(key)
    if found:
        table[ix] = avail
        global num; num -= 1
    else:
        raise KeyError

def resize(new_size):
    global table, num
    old_table = table
    table = [None] * new_size
    num = 0
    for item in old_table:
        if item is not None and item is not avail:
            add(item.key, item.value)

Resize tabuľky robíme vždy vtedy, keď počet prvkov tabuľke presiahne 66% veľkosti celej tabuľky.

Otestovanie môžete urobiť rovnaké, ako v predchádzajúcej realizácii ChainHashMap.

Iné metódy riešenia kolízií

Informatici hľadajú aj vhodnejšie spôsoby, ako vyriešiť kolízie: linear probing nie je najlepší, lebo kľúče s blízkymi hašovacími hodnotami sa zhlukujú (clustering) vedľa seba a tým sa spomaľuje samotné hľadanie - niekedy treba prezerať dlhú postupnosť prvkov v poli, ktoré sú tesne vedľa seba. Aj pri malom load factore (v tabuľke je veľa voľných políčok) bude treba často prekontrolovať skoro všetky prvky tabuľky. Bolo by vhodnejšie, keby mohli byť v poli viac rozptýlené. Vymenujme niekoľko ďalších možností:

  • lineárne pokusy s nejakým krokom c > 1:

    index = (hash(key) + i * c) % N
    

    kde c by mala byť konštanta, ktorá je nesúdeliteľná s N - veľkosťou tabuľky

    • ani toto nerieši problémom so zhlukovaním (clustering)
  • kvadratické pokusy:

    index = (hash(key) + i**2) % N
    

    krok sa stále zväčšuje a teda je väčšia šanca, že sa prvky nebudú až tak zhlukovávať

  • dvojité hašovanie (double hashing):

    index = (hash(key) + i * hash2(key)) % N
    

    druhá hašovacia funkcia hash2() by pre žiaden kľúč nemala vrátiť 0

    vychádza sa z toho, že ak majú dva rôzne kľúče rovnakú hodnotu hash(), tak práve v hash2() by sa mohli líšiť a teda sa znižuje šanca zhlukovania prvkov v poli

  • využitie pseudo-random generátora (využíva to aj štandardný typ dict v Pythone):

    • namiesto hash(key) najprv nastavíme náhodný generátor pomocou random.seed(key)
    • a potom postupne voláme random.randrange(N), ktorý nám vracia indexy do tabuľky
    • dôležité je, že pre každý kľúč bude táto postupnosť vygenerovaných indexov vždy rovnaká (pre rôzne kľúče bude samozrejme rôzna)

Python využíva asociatívne polia aj na vnútornú reprezentáciu menných priestorov (name space) - t.j. každý objekt, každé volanie funkcie (metódy) vytvára nové a nové menné priestory - sem si ukladá mená atribútov, lokálnych premenných a pod. Preto musí byť realizácia asociatívnych polí v Pythone veľmi rýchla a vysoko spoľahlivá.

Aby sa naša implementácia čo najviac priblížila k pythonovskému typu dict, mali by sme tomu prispôsobiť aj metódy, teda premenovať

  • valueof() na __getitem__()
  • add() na __setitem__()
  • delete() na __delitem__()

Okrem toho môžeme využiť štandardnú pythonovskú funkciu hash(), ktorá za nás vypočíta hašovaciu hodnotu.

Ešte by sme do abstraktnej triedy mali dodefinovať všetky metódy tak ako to má dict, teda

clear()
copy()
fromkeys()
get()
pop()
popitem()
setdefault()
update()

aj magické metódy:

__contains__()
__repr__()

ale aj iterátory

items()
keys()
values()

Python okrem modulu abc (abstract base classes) ponúka aj modul collections, z ktorého môžeme využiť:

from collections import MutableMapping as MapBase

Už len dodefinujeme podtriedu _Item a máme komplet všetky metódy z dict.

Realizácia množiny

V Pythone je aj štandardný typ množina set realizovaný pomocou hašovacej tabuľky:

  • do tabuľky neukladáme dvojice (kľúč, hodnota), ale len samotné kľúče
  • použijeme otvorené adresovanie, napr. linear probing, pričom vyhodené prvky tiež označíme ako _avail

Abstraktný dátový typ prispôsobíme základným operáciám na množine (namiesto valueof(), add() a delete()):

from abc import ABC, abstractmethod

class SetBase(ABC):

    @abstractmethod
    def __contains__(self, key):
        '''zisti, ci je v mnozine'''
        pass

    @abstractmethod
    def add(self, key):
        '''ak nie je v mnozine, prida'''
        pass

    @abstractmethod
    def discard(self, key):
        '''ak je v mnozine, vyhodi'''
        pass

    @abstractmethod
    def __len__(self):
        '''pocet prvkov v mnozine'''
        pass

    @abstractmethod
    def __iter__(self):
        '''prechadza vsetky prvky v mnozine'''
        pass

Samotná trieda pre množiny je veľmi zjednodušenou verziou ProbeHashMap:

class HashSet(SetBase):
    _avail = object()

    def __init__(self):
        self._table = [None] * 11        # capacity = 11
        self._num = 0

    def _hash(self, key):
        return hash(key) % len(self._table)

    def _find(self, key):
        ix = self._hash(key)
        av = None
        while True:
            item = self._table[ix]
            if item is None:
                if av is None:
                    av = ix
                return False, av
            if item == self._avail:
                if av is None:
                    av = ix
            elif item == key:
                return True, ix
            ix = (ix + 1) % len(self._table)

    def __contains__(self, key):
        found, ix = self._find(key)
        return found

    def add(self, key):
        found, ix = self._find(key)
        if found:
            return
        self._num += 1
        self._table[ix] = key
        if self._num > len(self._table) * 0.66:
            self._resize(len(self._table) * 2)

    def discard(self, key):
        found, ix = self._find(key)
        if found:
            self._table[ix] = self._avail
            self._num -= 1

    def __len__(self):
        return self._num

    def __iter__(self):
        for item in self._table:
            if item is not None and item is not self._avail:
                yield item

    def _resize(self, new_size):
        old_table = self._table
        self._table = [None] * new_size
        for item in old_table:
            if item is not None and item is not self._avail:
                found, ix = self._find(item)
                self._table[ix] = item

Hodnota _avail nemôže byť ani znakový reťazec ani žiaden iný typ, ktorý by mohol byť prvkom množiny, preto sme zvolili inštanciu object(). Táto sa vytvorí pri definovaní triedy ako „privátny“ triedny atribút a je to určite unikátna hodnota, ktorá sa nikdy neobjaví ako pridávaný kľúč. Všimnite si, že naša definícia triedy nebude správne fungovať pre prvok None. Mohli by sme použiť takú istú fintu ako sme použili pre _avail.

Podobne ako môžeme využiť pythonovský modul collections pre abstraktnú triedu MapBase môžeme využiť aj

from collections import MutableSet as SetBase

Vďaka čomu sú zadefinované nielen všetky metódy, ale aj operácie (napr. zjednotenie, prienik, rozdiel).

Pomocou hašovacích tabuliek sa zvyknú definovať aj ďalšie užitočné štruktúry, napr. MultiSet a MultiMap.

MultiSet

Je dátová štruktúra množina, v ktorej sa môžu prvky vyskytovať aj viackrát. Môžeme to riešiť napr. tak, že v hašovacej tabuľke ukladáme dvojice (kľúč, hodnota), kde kľúč je opäť prvok množiny (ako pri obyčajných množinách) ale v položke hodnota si pamätáme počet opakovaní výskytu tohto kľúča v množine. Takže pre množinu {‚a‘, ‚a‘, ‚b‘, ‚a‘} vytvoríme v hašovacej tabuľke dve dvojice: (‚a‘, 3), (‚b‘, 1).

MultiMap

Je také asociatívne pole, v ktorom každý kľúč môže mať niekoľko hodnôt. Realizuje sa to pomocou hašovacej tabuľky napr. tak, že pre každý kľúč sa pamätá nie jedna hodnota, ale zoznam zodpovedajúcich hodnôt.



Cvičenia

L.I.S.T.

  1. Hašovaciu tabuľku vytvárame v 7-prvkovom poli, pričom kolízie riešime pomocou vedierok (bucket), ktoré realizujeme malými jednorozmernými zoznamami (prvky pridávame na ich koniec). Kľúčmi sú celé čísla (asociované hodnoty si teraz nevšímame), pričom hašovacia funkcia počíta zvyšok po delení kľúča veľkosťou tabuľky.

    • Postupne vlož do tabuľky tieto čísla:

      17, 36, 76, 76, 9, 52, 40, 24, 29, 26, 68, 7, 89, 76, 80, 59, 59, 2
      

      zapíš tieto kľúče do príslušných vedierok (na začiatku sú všetky prázdne):

      0 ->
      1 ->
      2 ->
      3 ->
      4 ->
      5 ->
      6 ->
      

      V tejto úlohe nebudeme riešiť problém zaplnenia tabuľky pomocou resize()


  1. Úlohu (1) rieš pre otvorené adresovanie (čo je vlastne uzavreté hašovanie), v ktorom sa hodnoty vkladajú do jednorozmerného zoznamu a kolízie sa riešia metódou linear probing. Na začiatku je vyhradené 11-prvková tabuľka a po vložení 8. prvku bude load factor väčší ako 0.66 preto sa zmení veľkosť zoznamu na dvojnásobok. Pritom bude treba všetky doterajšie prvky presypať do nového zoznamu - zrejme takto dostanú nové pozície (ich hash() sa bude deliť 22). Keď už vložíme do tohto nového zoznamu 15. prvok, opäť sa prešvihne load factor a treba presypať zoznam na nové pozície.
    • realizuj postupné vkladanie týchto 18 prvkov aj s prípadnými resize tabuľky
    • urob aspoň niekoľko krokov ručne, na zvyšok dát môžeš použiť program
    • skontroluj, akú konkrétnu hodnotu bude mať load factor po vložení 8. a 15. prvku
    • zisti, po koľkých ďalších vloženiach do tabuľky bude opäť load factor väčší ako 0.66 a mal by sa robiť resize

  1. Otestuj algoritmus ProbeHashMap z prednášky na jednom z týchto súborov. Do tabuľky vkladaj len samotné slová - t.j. kľúčmi sú slová, hodnota môže byť None. Na záver vypíš počet vkladaných slov, počet rôznych slov v tabuľke, pri akom zaplnení tabuľky sa robil resize a aká najdlhšia bola séria kolízií pri vkladaní jednej hodnoty (počet prechodov v pomocnej funkcii find).

  1. Vyrob a otestuj triedu ProbeHashMap (otvorené adresovanie):

    • použi tento kód:

      from map_base import MapBase
      
      class ProbeHashMap(MapBase):
          _avail = 'avail'
      
          def __init__(self):
              self._table = [None] * 11        # capacity = 11
              self._num = 0
      
          def _hash(self, key):
              res = 0
              for ch in str(key):
                  res = res * 32 + ord(ch)
              return res % len(self._table)
      
          def _find(self, key):
              ...
      
          def valueof(self, key):
              ...
      
          def add(self, key, value):
              ...
      
          def delete(self, key):
              ...
      
          def __len__(self):
              ...
      
          def __iter__(self):
              ...
      
          def _resize(self, new_size):
              ...
      

      otestuj ho podobne ako v tretej úlohe


  1. V definícii tried MapBase aj ProbeHashMap premenujte metódy:

    • valueof() na __getitem__()
    • add() na __setitem__()
    • delete() na __delitem__()

    Otestuj volania týchto nových metód (napr. namiesto apole.add(kluc, hodnota) by malo fungovat apole[kluc] = hodnota) na podobnom programe, ktorým sa testovali úlohy 3. a 4.


  1. Do triedy MapBase doprogramuj tieto metódy, ktoré ale už nebudú abstraktné (používať budú iba metódy z MapBase a budú fungovať pre všetky neskôr odvodené triedy, napr. UnsortedMap, SortedMap, …, ProbeHashMap, bez toho aby sa museli preprogramovať):
    • __repr__() vráti reťazec v tvare {key1:value1, key2:value2, key3:value3, ...}
    • __contains__(key) zistí, či sa daný kľúč nachádza v poli
    • setdefault(key, default=None) vráti príslušnú hodnotu pre daný kľúč, ale v prípade, že sa v poli nenachádza, priradí default a potom aj vráti
    • pop(key, default=None) vyhodí dvojicu (kľúč, hodnota), pritom ako výsledok funkcie vráti príslušnú hodnotu; ak sa kľúč v poli nenachádza, vyvolá výnimku KeyError, alebo ak default parameter nie je None, vráti túto hodnotu
    • values() - iterátor, ktorý postupne vygeneruje všetky hodnoty v asociatívnom poli
    • items() - iterátor, ktorý postupne vygeneruje všetky dvojice (kľúč, hodnota) (ako tuple)

  1. Otvor modul _collectins_abc (je súčasťou modulu collections) a nájdi, ako sú v ňom realizované metódy z úlohy (6)
    • hľadaj triedu MutableMapping
    • môžeš sa inšpirovať pythonovskou realizáciou metód, ktoré si programoval v (6) úlohe.

  1. Otestuj, ako sa bude správať ProbeHashMap ak sa v pomocnej metóde _find() využije pseudo-random generátor:

    • namiesto ix = self._hash(key) sa použije:

      random.seed(key)
      ix = random.randrange(len(self._table))
      
    • namiesto zvyšovania ix o 1 pri kolízii sa opäť použije:

      ix = random.randrange(len(self._table))
      
    • testuj podobnými testami ako v úlohe (3), ale porovnaj s pôvodnou realizáciou linear probing ProbeHashMap


  1. V definícii triedy ProbeHashMap nahraď základnú triedu MapBase z prednášky triedou z modulu collections

    • vlož na začiatok:

      from collections import MutableMapping as MapBase
      
    • z pôvodnej triedy MapBase bude treba niekam preniesť _Item

    • otestuj, či je to teraz funkčná trieda, napr. by malo fungovať:

      zoz = [random.randrange(10000) for i in range(100000)]
      d1 = {}
      d2 = ProbeHashMap()
      for i in zoz:
          d1[i] = d1.get(i, 0) + 1
          d2[i] = d2.get(i, 0) + 1
      
      set1 = set(d1.items())
      set2 = set(d2.items())
      print(set1 == set2)
      



3. Domáce zadanie

L.I.S.T.

Implementujte metódy asociatívneho poľa pomocou otvoreného hašovania, v ktorom sa kolízie riešia zreťazovaním - ukladaním do vedierok (bucket). Kľúčmi v asociatívnom poli budú len celé čísla, preto hašovacia funkcia bude z tohto celého čísla počítať len zvyšok po delení veľkosťou tabuľky. Tabuľka sa bude resizovať len v tom prípade, keď počet kľúčov presiahne (bude väčší) ako 90% veľkosti tabuľky. Samotné vedierka realizujte jednosmerným spájaným zoznamom (linked list) tak, že v každom prvku _Item sa okrem kľúča a hodnoty (_key a _value) nachádza aj referencia na nasledovný prvok vo vedierku (_next).

Na riešenie úlohy použite deklarácie v súbore riesenie3.py z úlohového servera L.I.S.T. kde

  • inicializácia __init__ nastaví počiatočnú veľkosť hašovacej tabuľky _table; prvkami tejto tabuľky budú buď None (voľný prvok) alebo objekt typu _Item
  • metóda add, ak daný kľúč existuje, zmení mu v tabuľke hodnotu, ak neexistuje, najprv do tabuľky (do príslušného vedierka) vloží dvojicu key, value; ak je teraz tabuľka viac ako na 90% obsadená, tabuľka sa resize na dvojnásobok plus 1
  • nemeňte _Item a _hash, môžete dodefinovať ďalšie pomocné metódy
  • metóda print slúži len na pomoc pri ladení, pri testovaní sa nepoužije
class ChainHashMap:
    class _Item:
        def __init__(self, key, value, next=None):
            self._key, self._value, self._next = key, value, next

        def __repr__(self):
            return repr(self._key) + ':' + repr(self._value)

    #------------------

    def __init__(self, capacity=11):
        self._table = ...

    def _hash(self, key):
        return key % len(self._table)

    def valueof(self, key):
        raise KeyError

    def add(self, key, value=None):
        ...

    def delete(self, key):
        raise KeyError

    def __len__(self):
        return 0

    def __iter__(self):
        ...

    def print(self):
        for index, bucket in enumerate(self._table):
            print(index, end=' ')
            while bucket:
                print(bucket, end=' -> ')
                bucket = bucket._next
            print(None)

Váš program môžete testovať napr. takto:

if __name__ == '__main__':
    a = ChainHashMap(10)
    pole = [(55,'a'),(42,'b'),(15,'c'),(60,'d'),(78,'e'),
            (35,'f'),(22,'g'),(10,'h'),(11,'i'),(15,'j')]
    for key, value in pole:
        a.add(key, value)
    a.print()

    a = ChainHashMap(5)
    d = {}
    for i in 3, 16, 5, 11, 23, 25, 15, 18, 15, 14, 25:
        try:
            a.add(i, a.valueof(i) + 1)
        except KeyError:
            a.add(i, 1)
        d[i] = d.get(i, 0) + 1
    set1 = {(it, a.valueof(it)) for it in a}
    set2 = set(d.items())
    print('=== druhy test', set1 == set2)
    a.print()

Výpis potom bude takýto:

0 10:'h' -> 60:'d' -> None
1 11:'i' -> None
2 22:'g' -> 42:'b' -> None
3 None
4 None
5 35:'f' -> 15:'j' -> 55:'a' -> None
6 None
7 None
8 78:'e' -> None
9 None
=== druhy test True
0 11:1 -> None
1 23:1 -> None
2 None
3 14:1 -> 25:2 -> 3:1 -> None
4 15:2 -> None
5 16:1 -> 5:1 -> None
6 None
7 18:1 -> None
8 None
9 None
10 None

Definíciu triedy ChainHashMap uložte do súboru riesenie3.py a na začiatok pridajte tieto tri komentárové riadky (s vašim menom a dátumom):

# 3. zadanie: hashmap
# autor: Alan Turing
# datum: 1.11.2018

Súbor riesenie3.py odovzdávajte na úlohový server L.I.S.T. najneskôr do 23:00 9. novembra. Môžete zaň získať 10 bodov.



© Copyright 2018-2019, Andrej Blaho.
Naposledy aktualizované 14. feb. 2019.
Vytvorené pomocou Sphinx 1.8.4.

Creative Commons License This work is licensed under a Creative Commons Attribution 4.0 International License.