Hashovací tabulka (popř. hašovací či hešovací tabulka) je datová struktura pro ukládání dvojic (klíč, hodnota) nabízející dobrý kompromis mezi rychlostí vyhledávání a paměťovou náročností. Princip vyhledávání v hashovací tabulce je podobné vyhledávání dokumentů v uklizené kanceláři: pokud chci například najít určitou fakturu, klíčem bude její číslo 20150715. Z klíče odvodím, že je to faktura z roku 2015, určitě jí tedy najdu v zásuvce nadepsané "faktury 2015". Hashovací tabulka dělá něco podobného - automaticky pro každý klíč určí jeho kategorii a hledá v přihrádkách, ve kterých by se daný klíč mohl nacházet. Tímto způsobem lze ušetřit čas za podmínky, že je kategorizace záznamu dostatečně rychlá a přehledná.

Obecně řečeno, hashovací tabulka je datová struktura se schopností efektivně vkládat, mazat a hledat datové záznamy podle klíče.

Pokud bychom měli celočíselné klíče dlouhé 32 bitů a chtěli bychom maximalizovat rychlost vyhledávání, ukládali bychom všechny záznamy do pole, ve kterém by klíč byl zároveň indexem záznamu. Takto by však docházelo k obrovskému plýtvání pamětí v případě, že by bylo obsazeno jen několik klíčů.

Alternativou by bylo možné použít spojový seznam a uložit všechny záznamy do něho. Takto by se pamětí neplýtvalo, ale každé vyhledávání by znamenalo projít celý seznam.

Bylo by možné použít i binární vyhledávací strom organizovaný podle klíče. U něj je výkon závislý na jeho hloubce a pro dosažení optimální efektivity se musí vyvažovat.

Hashovací tabulka za cenu určitého kompromisu spojuje výhody pole a spojového seznamu a nevýhody minimalizuje. Kromě toho je v obecném případě možné rekurzivně vnořovat hashovací tabulky do sebe a vybudovat hierarchické struktury podobné paměti v počítači.

Princip fungování

Hashovací tabulka uvnitř obsahuje pole tzv. slotů, do kterých lze ukládat záznamy. Hashovací tabulka v podstatě dělá jen to, že na základě klíče vybere vhodný slot a operaci provede v něm. Abychom docílili efektivity, snažíme se, aby všechny sloty byly využity rovnoměrně, tedy aby různé klíče ideálně padaly do různých slotů. Samozřejmě to není zcela možné, protože množina klíčů je mnohem větší než počet slotů. Takové situaci říkáme kolize a existují různé metody, jak tyto kolize řešit:

  • zřetězení záznamů (separate chaining) - každý slot obsahuje spojový seznam, do kterého se postupně řetězí prvky patřící do stejného slotu
  • otevřená adresace (open addressing) - obsah všech slotů je umístěn v jednom poli a tak mohou data z jednoho slotu "přetékat" i do jiných slotů a tím zabírat volné místo pro jejich budoucí prvky, což se minimalizuje různými dalšími technikami (linear probing, double hashing...)
diagram

Převod klíče na index slotu realizuje tzv. hashovací funkce. Toto zobrazení nemusí být injektivní, ale mělo by mít následující vlastnosti:

  • ideálně by mělo vracet různé sloty s rovnoměrnou pravděpodobností
  • mělo by být velmi rychle vypočitatelné

Mezi nejčastěji používané hashovací funkce patří modulo (zbytek po dělení) nebo násobení klíče prvočíslem a následná normalizace na počet slotů, tedy € h(k) = p \cdot k \bmod m €, kde €k€ je celočíselný klíč, €p€ je prvočíslo a €m€ je počet slotů (velikost pole se sloty).

Asymptotická složitost

OperaceTypický případNejhorší případ
vyhledávání podle klíče€ O(1) €€ O(n) €
vkládání záznamu€ O(1) €€ O(n) €
mazání záznamu€ O(1) €€ O(n) €

Implementace

Pomocí pole

hashovací tabulka realizovaná jedním polem

hashovací tabulka realizovaná jedním polem

package ds.hashtable;

public class HashTableBackedByArray<VALUE> implements HashTable<VALUE> {
    private static class HashEntry<DATA> {
        private int key;
        private DATA value;
    }

    private final HashEntry<VALUE>[] table;

    @SuppressWarnings("unchecked")
    public HashTableBackedByArray(final int tableSize) {
        table = new HashEntry[tableSize];
    }

    @Override
    public void add(final int key, final VALUE value) {
        final Integer firstExpectedIndexForKey = scanForNextFreeIndexByKey(key);

        if (firstExpectedIndexForKey == null) {
            throw new IllegalStateException("No free space in table.");
        }

        final HashEntry<VALUE> newEntry = new HashEntry<VALUE>();
        newEntry.key = key;
        newEntry.value = value;
        table[firstExpectedIndexForKey] = newEntry;
    }

    @Override
    public VALUE findByKey(final int key) {
        final Integer index = scanForIndexByKey(key);

        if (index != null) {
            return table[index].value;
        }

        return null;
    }

    @Override
    public boolean removeByKey(final int key) {
        final Integer index = scanForIndexByKey(key);

        if (index != null) {
            if (table[index] != null) {
                table[index] = null;
            }

            return true;
        }

        return false;
    }

    private Integer scanForNextFreeIndexByKey(final int key) {
        int index = getKeyHash(key);

        for (int i = 0; i < table.length; i++) {
            if (table[index] == null) {
                // empty cell found
                return index;
            }

            // continue and wrap around
            index = (index + 1) % table.length;
        }

        return null;
    }

    private Integer scanForIndexByKey(final int key) {
        int index = getKeyHash(key);

        for (int i = 0; i < table.length; i++) {
            if (table[index] != null && table[index].key == key) {
                // non-empty cell with correct key found
                return index;
            }

            // continue and wrap around
            index = (index + 1) % table.length;
        }

        return null;
    }

    private int getKeyHash(final int key) {
        return (key % table.length);
    }
}

Zdrojový kód Pokrytí testy

Pomocí pole a spojového seznamu

hashovací tabulka realizovaná polem a spojovými seznamy

hashovací tabulka realizovaná polem a spojovými seznamy

package ds.hashtable;

public class HashTableWithLinkedListSlots<VALUE> implements HashTable<VALUE> {
    private static class Entry<VALUE> {
        private int innerKey;
        private VALUE innerValue;
        private Entry<VALUE> next;
    }

    private static class Slot<VALUE> {
        private Entry<VALUE> head;

        private void add(final int key, final VALUE value) {
            final Entry<VALUE> newEntry = new Entry<VALUE>();
            newEntry.innerKey = key;
            newEntry.innerValue = value;

            if (head == null) {
                // empty list
                head = newEntry;
            } else {
                Entry<VALUE> temp = head;

                while (temp.next != null) {
                    temp = temp.next;
                }

                temp.next = newEntry;
            }
        }

        private VALUE findByKey(final int key) {
            Entry<VALUE> temp = head;

            while (temp != null) {
                if (temp.innerKey == key) {
                    // value found
                    return temp.innerValue;
                }

                temp = temp.next;
            }

            return null;
        }

        private boolean removeByKey(final int key) {
            Entry<VALUE> temp = head;
            Entry<VALUE> prevOfTemp = null;

            while (temp != null) {
                if (temp.innerKey == key) {
                    if (prevOfTemp == null) {
                        // removing head
                        head = head.next;
                    } else {
                        // general case
                        prevOfTemp.next = temp.next;
                    }
                    return true;
                }

                prevOfTemp = temp;
                temp = temp.next;
            }

            return false;
        }
    }

    private final Slot<VALUE>[] slots;

    @SuppressWarnings("unchecked")
    public HashTableWithLinkedListSlots(final int numberOfSlots) {
        slots = new Slot[numberOfSlots];
    }

    @Override
    public void add(final int key, final VALUE value) {
        final Slot<VALUE> slot = getSlotForKey(key, true);
        slot.add(key, value);
    }

    @Override
    public VALUE findByKey(final int key) {
        final Slot<VALUE> slot = getSlotForKey(key, false);
        if (slot != null) {
            return slot.findByKey(key);
        }
        return null;
    }

    @Override
    public boolean removeByKey(final int key) {
        final Slot<VALUE> slot = getSlotForKey(key, false);
        if (slot != null) {
            return slot.removeByKey(key);
        }
        return false;
    }

    private Slot<VALUE> getSlotForKey(final int key, final boolean createIfMissing) {
        final int bucketIndex = getHash(key);
        Slot<VALUE> slot = slots[bucketIndex];
        if (slot == null && createIfMissing) {
            slot = new Slot<VALUE>();
            slots[bucketIndex] = slot;
        }
        return slot;
    }

    private int getHash(final int key) {
        // simple hash function
        return key % slots.length;
    }
}

Zdrojový kód Pokrytí testy

Reference