13.3 Hash table, comparator és ownership

Egy konfigurációs kulcs–érték tárolóban a gyors keresés csak akkor hasznos, ha közben egyértelmű marad, ki birtokolja a kulcsokat, mikor szűnnek meg a visszaadott pointerek érvényes hozzáférést biztosítani, és milyen állapot marad allokációs hiba után. A hash table ezért nem pusztán algoritmus: tárolási, élettartam- és hibakezelési szerződés is.

A dinamikus tömbnél megismert kapacitáskezelésre, a listák csomópont-élettartamára és a callbackek context-szerződésére építünk. Az alábbi modell ISO C17-et használ, egyetlen szálból, konkurens hozzáférés nélkül.

13.3.1 Hash, egyenlőség és comparator

Legyen $H(k)$ a kulcs hashértéke, $E(a,b)$ pedig az egyenlőségi predikátum. A helyes működés szükséges feltétele:

$$E(a,b)\;\Longrightarrow\;H(a)=H(b).$$

A fordított irány nem követelmény: különböző kulcsoknak lehet azonos hashértéke. Ez ütközés, angolul collision; az azonosságot végül az egyenlőségi vizsgálat dönti el.

Az egyenlőségnek ekvivalenciarelációnak kell lennie: reflexívnek, szimmetrikusnak és tranzitívnak. A tárolt kulcs hashértéke és egyenlőségi osztálya nem változhat meg a táblabeli tagság alatt.

Konfigurációs tárolónkban a kulcs és az érték nullterminált karakterlánc, beágyazott nullkarakter nélkül. Az alapváltozat kis- és nagybetűérzékeny: az egyenlőség feltétele strcmp(a, b) == 0. Ez ISO C17 könyvtári viselkedésre épülő, választott API-szerződés, nem minden konfigurációs formátum kötelező szemantikája.

A comparator gyakran háromirányú összehasonlító függvényt jelent: negatív, nulla vagy pozitív eredménnyel. Egy logikai equality callback viszont igaz értéket ad egyenlőségkor. A kettő közvetlen felcserélése megfordíthatja a jelentést.

Ha például az equality figyelmen kívül hagyja az ASCII-kisbetű/nagybetű különbséget, a hashnek is ugyanilyen normalizálással kell dolgoznia. Nem elegendő csak az összehasonlítást módosítani.

Callbackes API-nál a callback contextjének tulajdonosa a hívó; a contextnek minden használatkor élnie kell. A benne tárolt hashmag vagy összehasonlítási szabály megváltoztatása újraépítés nélkül megsérti az invariánst.

13.3.2 Open addressing és chaining: tárolási következmények

Nyílt címzésnél (open addressing) a bejegyzések közvetlenül egy slottömbben helyezkednek el. Ütközéskor egy keresési sorozat, a probe sequence további slotokat vizsgál. Lineáris próbálásnál a kezdőhely:

$$p_0=H(k)\bmod m,$$

ahol $m>0$ a slotok száma; ezután növekvő indexek következnek, a tömb végén körbefordulással.

Láncolásnál (separate chaining) a hash egy bucketet választ, amely például külön allokált csomópontok listáját tartja.

Ezek implementációs következmények, nem univerzális garanciák. A láncolás sem tesz minden iterátort stabillá: a buckethez vagy következő kapcsolathoz kötött bejárási állapot megváltozhat.

13.3.3 Kapacitás, tombstone és keresési invariáns

Nyílt címzésnél három slotállapotot használunk:

• EMPTY: a jelenlegi tábla felépítése óta nem foglalt;
• LIVE: élő bejegyzést tartalmaz;
• DEAD: korábban foglalt, törölt hely, azaz tombstone.

Legyen $n$ az élő, $d$ a törölt slotok száma. Két arány fontos:

$$\alpha=\frac{n}{m}, \qquad \beta=\frac{n+d}{m}.$$

Az $\alpha$ a szokásos terhelési tényező (load factor). A keresést azonban a tombstone-ok is hosszabbítják, ezért az effektív foglaltságot jelző $\beta$ sem hagyható figyelmen kívül.

13.3.3.1 Kidolgozott ütközési példa

Legyen $m=8$, és egy szemléltető hashfüggvény az env, log, port kulcsokhoz egyaránt a 2-es kezdőhelyet adja. Beszúrás után:

A log törlésekor a 3-as slot DEAD lesz. A port keresése megvizsgálja a 2-es slotot, áthalad a 3-ason, majd megtalálja a 4-est. Ha törléskor EMPTY állapotot írnánk, a keresés idő előtt „nincs ilyen kulcs” eredménnyel állna meg.

Beszúráskor megjegyezhetjük az első tombstone helyét, de tovább kell keresnünk egy egyező kulcs vagy egy EMPTY slot eléréséig. Különben már létező kulcsból készíthetnénk második példányt. Minden keresési ciklus legfeljebb $m$ slotot vizsgáljon: ez sérült kapacitáspolitika esetén is kizárja a végtelen körbeforgást.

A példabeli politika az élő elemszámot legfeljebb a kapacitás felére engedi. Sok tombstone esetén azonos kapacitású újraépítés, sok élő elem esetén növelés szükséges. Az újraépítés eltünteti a tombstone-okat.

Növelés előtt két külön határt ellenőrzünk:

$$m\leq\left\lfloor\frac{\mathrm{SIZE\_MAX}}{2}\right\rfloor, \qquad m_{\text{új}}\leq \left\lfloor\frac{\mathrm{SIZE\_MAX}}{\operatorname{sizeof}(\text{slot})}\right\rfloor.$$

Az első a duplázást, a második az allokáció méretszorzását védi. A méret egysége C bájt, nem feltétlenül nyolcbites oktett. Beszúrásnál az n + 1 kiszámítása helyett például az n < m / 2 feltétellel ellenőrizhetjük, hogy elfér-e még egy elem a választott korláton belül.

13.3.4 Ownership és invalidáció

Az owned kulcsot vagy értéket a tábla birtokolja; a borrowed hozzáférés nem jár felszabadítási felelősséggel. A kettőt kulcsra és értékre külön kell eldönteni.

Egy újrahasznált parserbufferre mutató borrowed kulcs tehát akkor is hibás lehet, ha a buffer még nincs felszabadítva: tartalmának módosítása miatt a bejegyzés rossz keresési sorozatban marad.

A következő kód külön allokált, owned kulcsokat és értékeket feltételez. Minden ilyen allokációnak pontosan egy tulajdonosa van; a kulcs- és értékpointerek nem ugyanazt az allokációt birtokolják.

Owned beszúrásnál előbb mindkét szövegmásolatot létrehozzuk, majd biztosítjuk a kapacitást, és csak ezután publikáljuk a bejegyzést. Hiba esetén a részlegesen elkészült másolatokat felszabadítjuk. Értékcserekor is előbb másolunk, és csak siker után szabadítjuk fel a régi értéket.

13.3.5 Tranzakciós rehash C17-ben

Az alábbi cfg.c önállóan objektumfájllá fordítható modulrész: a rehash műveletet tartalmazza, nem teljes hashkönyvtárat.

Előfeltétel: t érvényes, inicializált táblára mutat; live és used pontos; live <= used <= cap. Üres kezdeti állapota struct table t = {0};. A hash mező a teljes hashérték, nem a korábbi kapacitással képzett bucketindex.

#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

enum slot_state { EMPTY, LIVE, DEAD };

struct slot {
    enum slot_state state;
    size_t hash;
    char *key;
    char *value;
};

struct table {
    struct slot *slots;
    size_t cap;
    size_t live;
    size_t used;  /* LIVE + DEAD */
};

enum cfg_status {
    CFG_OK,
    CFG_LIMIT,
    CFG_NOMEM
};

enum cfg_status cfg_rehash(struct table *t, size_t new_cap)
{
    if (new_cap < 8 ||
        t->live > new_cap / 2 ||
        new_cap > SIZE_MAX / sizeof(struct slot)) {
        return CFG_LIMIT;
    }

    struct slot *fresh = malloc(new_cap * sizeof *fresh);
    if (fresh == NULL) {
        return CFG_NOMEM;
    }

    for (size_t i = 0; i < new_cap; ++i) {
        fresh[i] = (struct slot){0};
    }

    for (size_t i = 0; i < t->cap; ++i) {
        if (t->slots[i].state != LIVE) {
            continue;
        }

        size_t p = t->slots[i].hash % new_cap;
        while (fresh[p].state == LIVE) {
            ++p;
            if (p == new_cap) {
                p = 0;
            }
        }
        fresh[p] = t->slots[i];
    }

    free(t->slots);       /* Nem a kulcsokat és értékeket! */
    t->slots = fresh;
    t->cap = new_cap;
    t->used = t->live;
    return CFG_OK;
}

Külön elvégzendő laborprofil: GCC 14.2.0 vagy Clang 19.1.7, Linux x86-64 System V, LP64, glibc 2.39; ISO C17 mód. A példa itt nem végrehajtott fordítási vagy futási mérés.

gcc -std=c17 -Wall -Wextra -Wpedantic -Wconversion \
    -c cfg.c -o cfg-gcc.o

clang -std=c17 -Wall -Wextra -Wpedantic -Wconversion \
    -c cfg.c -o cfg-clang.o

Helyességi bizonyításvázlat. A méretszorzást ellenőrzés előzi meg. Allokációs hiba előtt a régi táblát nem módosítjuk. Sikeres allokáció után legfeljebb new_cap / 2 élő bejegyzést helyezünk át, ezért minden keresés talál üres slotot. Az áthelyezés nem allokál és nem hív hibázható callbacket. A régi tábla a commitig marad tulajdonos; az ideiglenes pointermásolatok nem jelentenek két önálló felszabadítási felelősséget. Végül csak a régi slottömböt szabadítjuk fel.

A rehash várható költsége megfelelő hash-eloszlási modell mellett $O(m_{\text{új}}+n)$, rossz ütközési mintával azonban $O(m_{\text{új}}+n^2)$ is lehet. Átmenetileg mindkét slottömb él.

Korlátos effektív foglaltság és megfelelő hash-eloszlás mellett a keresés várhatóan konstans számú slotot vizsgál; legrosszabb esetben $O(m)$-et. A kulcs hosszát külön számolni kell: a hashképzés egy $k$ hosszú sztringre tipikusan $O(k)$. Geometrikus növelésnél a növelési költség beszúrásonként amortizálható, de ez nem jelent worst-case konstans késleltetést.

13.3.6 Rosszindulatú bemenet és gyakori hibák

A hash DoS lényege, hogy a támadó sok, azonos vagy kedvezőtlenül csoportosuló hashértékű kulcsot választ. Ettől a beszúrások összköltsége négyzetessé válhat. A nagyobb kapacitás nem javítja meg az azonos teljes hashértékeket.

Nem megbízható bemenethez támadásállóságra tervezett, titkos maggal kulcsolt hash, továbbá elemszám-, kulcshossz- és memóriahatár indokolt. A puszta „véletlen só hozzáadása” önmagában nem bizonyít támadásállóságot.

Tipikus hibák:

• hashazonosságot kulcsegyenlőségnek tekinteni;
• borrowed kulcs tartalmát tagság közben módosítani;
• törléskor tombstone helyett EMPTY állapotot írni;
• rehash előtt felszabadítani a régi táblát;
• a kapacitás növelését ellenőrizni, de a méretszorzást nem;
• a slotpointer stabilitását összekeverni a külön allokált payload stabilitásával.

13.3.7 Feladatok

1. Magyarázó: Az equality szerint "PORT" és "port" azonos, a hash viszont az eredeti karaktereket dolgozza fel. Mi hibás, és milyen feltétellel javítható?

2. Kódolási: Egészítsd ki a modult cfg_erase_at függvénnyel. Kapjon indexet, utasítsa el a nem élő slotot, szabadítsa fel a payloadot, és tartsa helyesen a számlálókat.

3. Diagnosztikai: Elmentettél egy slotpointert és az abban tárolt értékre mutató pointert. Mi használható sikertelen rehash, sikeres rehash, majd az adott bejegyzés törlése után?

13.3.8 Megoldások

13.3.8.1 Hash és equality javítása

Sérülhet az $E(a,b)\Rightarrow H(a)=H(b)$ feltétel. Mindkét műveletnek ugyanazt a stabil normalizálást kell alkalmaznia, például explicit ASCII-kisbetűsítést. Ellenőrzési feltétel: minden tesztelt, egyenlőnek minősített kulcspár hashértéke legyen azonos. Ez szükséges teszt, nem teljes bizonyítás.

13.3.8.2 Törlés tombstone-nal

Az alábbi C17-részlet ugyanabba a cfg.c fájlba illeszthető, és az előző parancsokkal fordítható. A tábla tulajdonlási előfeltételei változatlanok.

int cfg_erase_at(struct table *t, size_t i)
{
    if (i >= t->cap || t->slots[i].state != LIVE) {
        return 0;
    }

    free(t->slots[i].key);
    free(t->slots[i].value);
    t->slots[i] = (struct slot){ .state = DEAD };
    --t->live;
    return 1;
}

A used változatlan: egy élő slotból egy tombstone lett. Ellenőrzési feltétel: ütköző kulcsok közül a középső törlése után a később elhelyezett kulcs továbbra is megtalálható legyen. A törölt kulcs és érték borrowed pointerei többé nem használhatók.

13.3.8.3 Pointerek érvényessége

Sikertelen rehash után mindkét pointer használható marad. Sikeres rehash után a régi slotpointer már nem használható hozzáférésre, az értékpointer viszont igen, mert annak allokációját nem mozgattuk.

A bejegyzés későbbi törlése az értékpointert is érvénytelenné teszi. Ellenőrzési feltétel: sikeres rehash után a slotot új kereséssel kell megszerezni; törlés után a régi payloadpointert sem szabad dereferálni.

13.3.9 Összefoglaló

A hash table helyessége a hash/egyenlőség konzisztenciáján, a stabil kulcsszemantikán és az explicit ownershipen alapul. Nyílt címzésnél a tombstone őrzi a keresési útvonalat, a tranzakciós rehash pedig a régi állapotot védi hiba esetén. A kapacitás, az invalidáció és a támadható bemenet kezelése ugyanannak az API-szerződésnek a része.