Optimalizované vyhledávání v poli - princip děr

Funguje na principu děr. Z daného slova se vypočítá hash - číslo indikující index v poli. Pokud je na dané pozici díra (null) zapíše se daná hodnota. Pokud je již obsazeno, jde na další pozici do té doby, dokud není volná.

Pokud ve slovníku hledám, vypočítám hash slova. Najdu si jej v poli a zkontroluji, zda odpovídá hledanému slovu. Pokud ano, vrátí ho. Pokud ne podívá se na další pozici. A hledá do té doby, než narazí na díru.

Tento výukový obsah pomáhají rozvíjet následující firmy, které dost možná hledají právě tebe!

Toto optimalizuje rychlost vyhledávání.

Příkladné použití - třída Slovník.

Zdrojový kód je v jazyce 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ázka použití výše uvedené třídy:

Zdrojový kód je v jazyce 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 byla zachována rychlost vyhledávání, je třeba vždy mít pole o dostatečné velikosti. Tzn. s dostatečným počtem volných děr. Tedy z uvedené kapacity pole by se mělo zaplnit maximálně kolem 75%. Pokud se použije více, bude málo děr, tím pádem při vyhledávání prvku, který v poli není nebo koliduje (má stejný hash a proto byl posunut) se bude muset prohledat větší část pole (pokud bude plné, tak i celé pole) a algoritmus pak nebude mít smysl.