Optimalizované vyhľadávanie v poli - princíp dier

Funguje na princípe dier. Z daného slova sa vypočíta hash - číslo indikujúce index v poli. Ak je na danej pozícii diera (null) zapíše sa daná hodnota. Ak je už obsadené, ide na ďalšiu pozíciu dovtedy, kým nie je voľná.

Ak v slovníku hľadám, vypočítam hash slová. Nájdem si ho v poli a skontrolujem, či zodpovedá hľadanému slovu. Ak áno, vráti ho. Ak nie pozrie sa na ďalšiu pozíciu. A hľadá do tej doby, než narazí na dieru.

Toto optimalizuje rýchlosť vyhľadávania.

Príkladné použitie - trieda Slovník.

Zdrojový kód je v jazyku Java

public class Dictionary
{
    // pole pro ukládání slovíček
    String[][] dictionary;
    // kapacita pole
    int capacity;

    /**
     * Konstruktor slovníku. Vytvoří slovník o dané kapacitě.
     * @param capacity Velikost slovníku - počet slov, které se do něj vejdou
     */
    public Dictionary(int capacity)
    {
        this.capacity = capacity;
        dictionary = new String[capacity][2];
    }

    /**
     * Vrátí hash daného slova. Sečte jednotlivá písmena (jejich ascii hodnoty) číslo je v rozmezí kapacity - hash mod kapacita.
     * @param word Slovo, jehož hash chceme získat
     * @return Celočíselný Hash daného slova
     */
    private int hash(String word)
    {
        int hash = 0;
        for (char letter : word.toCharArray())
        {
            hash += (int)letter;
        }
        return hash % capacity;
    }

    /**
     * Přidá slovo do slovníku. Pokud tam již není a pokud je ve slovníku místo.
     * @param czech České slovo
     * @param english Anglický ekvivalent
     * @return Úspěch při ukládání
     */
    public boolean addWord(String czech, String english)
    {
        int position = hash(czech);

        while (dictionary[position][0] != null)
        {
            if ((dictionary[position][0]).equals(czech)) return false;

            position = ++position % capacity;
        }

        dictionary[position][0] = czech;
        dictionary[position][1] = english;

        return true;
    }

    /**
     * Najde ve slovníku pomocí hashe daný ekvivalent slova. Pokud tam není vrátí "Not found" - "Nenalezeno"
     * @param czech České slovo, které chceme přeložit
     * @return Anglický ekvivalent zadaného slova
     */
    public String translate(String czech)
    {
        int position = hash(czech);

        while (dictionary[position][0] != null)
        {
            if (dictionary[position][0].equals(czech)) return dictionary[position][1];

            position = ++position % capacity;
        }

        return "Nenalezeno";
    }
}

Ukážka použitia vyššie uvedenej triedy:

Zdrojový kód je v jazyku Java

Dictionary dic = new Dictionary(5);
System.out.println("úspěch při vložení: " + dic.addWord("pes", "dog"));
System.out.println("úspěch při vložení: " + dic.addWord("kočka", "cat"));
System.out.println("úspěch při vložení: " + dic.addWord("kůň", "horse"));

System.out.println(dic.translate("kočka"));
System.out.println(dic.translate("kůň"));
System.out.println(dic.translate("davos"));

Pozn. aby bola zachovaná rýchlosť vyhľadávania, treba vždy mať pole o dostatočnej veľkosti. Tzn. s dostatočným počtom voľných dier. Teda z uvedenej kapacity poľa by sa malo zaplniť maximálne okolo 75%. Ak sa použije viac, bude málo dier, tým pádom pri vyhľadávaní prvku, ktorý v poli nie je alebo koliduje (má rovnaký hash a preto bol posunutý) sa bude musieť prehľadať väčšia časť poľa (pokiaľ bude plné, tak i celé pole) a algoritmus potom nebude mať zmysel.