HashTable – Java dátové štruktúry

Java HashTable (tabuľka) je dátová štruktúra, ktorá ti umožní bezpečne pracovať s dátami aj vo viacvláknových aplikáciách. Hoci ide o staršiu, no stále spoľahlivú implementáciu, jej používanie má svoje špecifiká. V nasledujúcich riadkoch sa pozrieme na to, ako trieda HashTable funguje, aké sú jej výhody a obmedzenia a tiež na to, kedy ju má zmysel použiť namiesto modernejších alternatív, ako je napríklad HashMap.

HashTable – Java dátové štruktúry
HashTable – Java dátové štruktúry

Trieda HashTable je jednou zo starších implementácií hashovacích tabuliek v Jave.

HashTable kolekcia – hierarchia dedičnosti (zdroj: media.geeksforgeeks.org/wp-content/uploads/20201124183400/HierarchyofHashtable.png)

HashTable kolekcia – hierarchia dedičnosti (zdroj: media.geeksforgeeks.org/wp-content/uploads/20201124183400/HierarchyofHashtable.png)

Odporúčame ti...

HashTable je jednou z množstva dátových štruktúr na jednoduchšiu prácu s dátami. V našom seriáli si postupne predstavíme aj rôzne ďalšie dátové štruktúry. Ukážeme si, ako s nimi pracovať, aké operácie sa s nimi dajú robiť, aké sú najčastejšie používané metódy. Spomenieme spomenieme výhody a nevýhody a kedy je vhodne konkrétnu dátovú štruktúru použiť.

HashTable v Java – predstavenie dátovej štruktúry

Trieda HashTable je implementáciou rozhrania Map, ktorá ukladá páry kľúč-hodnota a využíva hashovaciu tabuľku pre rýchle operácie. Každý kľúč musí byť jedinečný a nikdy nesmie byť null, rovnako ani hodnota, teda v HashTable nie sú povolené null hodnoty.

Na rozdiel od modernejších kolekcií, ako je HashMap, je HashTable synchronizovaná, čo znamená, že je bezpečná pre použitie vo viacvláknových aplikáciách, ale zároveň jej operácie môžu byť pomalšie.

6 min.Laptop s programovacím kódom na obrazovke

HashMap – Java dátové štruktúry

Zoznám sa s dátovou štruktúrou HashMap v Jave – prehľad metód, operácií, výhod, nevýhod či praktické príklady jej použitia.

HashTable využíva hashCode() metódu objektov na rovnomerné rozdelenie párov do interných „vedier“. To umožňuje vykonávať operácie pridávania, vyhľadávania a odstraňovania v konštantnom čase (O(1)) pri ideálnom rozložení.

HashTable – konštruktory

Pre vytvorenie inštancie HashTable máme k dispozícií niekoľko konštruktorov:

1. Prázdna HashTable

Vytvorí prázdnu hashovaciu tabuľku s predvolenou kapacitou (11) a load faktorom (0.75).

Hashtable<Integer, String> table = new Hashtable<>();

2.HashTable s definovanou kapacitou

Vytvorí novú, prázdnu hašovaciu tabuľku so zadanou počiatočnou kapacitou a predvoleným faktorom zaťaženia (0.75).

Hashtable<Integer, String> table = new Hashtable<>(20);

3. HashTable s definovanou kapacitou a load faktorom

Vytvorí novú, prázdnu hašovaciu tabuľku so zadanou počiatočnou kapacitou a zadaným faktorom zaťaženia.

Hashtable<Integer, String> table = new Hashtable<>(20, 0.82f);

4. HashTable skonštruovaný z Map

Vytvorí novú hašovaciu tabuľku s rovnakým mapovaním ako daná Map.

Hashtable(Map<? extends K,? extends V> t)

Initial capacity, Load Factor (faktor zaťaženia)

Inštancia Hashtable má dva parametre, ktoré ovplyvňujú jej výkon: počiatočnú kapacitu a faktor zaťaženia. Kapacita je počet segmentov v hašovacej tabuľke a počiatočná kapacita je jednoducho kapacita v čase vytvorenia hašovacej tabuľky. V prípade rovnakého hash hódu (tzv. kolízie) je v jednom segmente uložených viacero záznamov, ktoré je potrebné postupne prehľadávať. Koeficient zaťaženia udáva, ako veľmi sa môže hašovacia tabuľka naplniť, kým sa automaticky zvýši jej kapacita.

Vo všeobecnosti predvolený faktor zaťaženia (0.75) ponúka dobrý kompromis medzi nákladmi na čas a priestor. Vyššie hodnoty znižujú réžiu priestoru, ale zvyšujú časové náklady na vyhľadanie záznamu (čo sa odráža vo väčšine operácií hashtable vrátane get a put). Počiatočná kapacita riadi kompromis medzi premárneným priestorom a potrebou opakovaných operácií, ktoré sú časovo náročné.

Ak je počiatočná kapacita väčšia ako maximálny počet záznamov, ktoré bude hashovacia tabuľka obsahovať, vydelený jej koeficientom zaťaženia, nikdy sa nevyskytnú žiadne prehashovacie operácie. Nastavenie príliš vysokej počiatočnej kapacity však môže plytvať miestom. Pri konštruovaní HashTable preto odporúčame, čo najlepšie odhadnúť, koľko elementov budeme ukladať do kolekcie a zvoliť si správne počiatočnú kapacitu (a prípadne aj load factor).

Ak sa má do hashtable vytvoriť veľa záznamov, jeho vytvorenie s dostatočne veľkou kapacitou môže umožniť vkladanie záznamov efektívnejšie, ako nechať ho vykonávať automatické prehashovanie podľa potreby na zväčšenie kapacity tabuľky.

Hash Function

Dobre navrhnutá hashovacia funkcia pre objekty (hashCode) je nesmierne dôležitá, pretože práve ona rovnomerne rozdistribuuje elementy do správnych vedier (buckets), pričom znižuje pravdepodobnosť kolízií a udržiava efektívnosť a výkon kolekcie.

Pri vkladaní prvku do kolekcie sa vypočíta jeho hašovacia hodnota a určí sa segment, do ktorého by sa mal prvok uložiť. To samozrejme nestačí, pretože dva objekty s rovnakým hashCode nemusia byť rovnaké,  preto v rámci toho istého vedra sa objekty porovnávajú pomocou metódy equals(), aby sa zabezpečila jedinečnosť vložených elementov.

HashTable – základné operácie

Medzi základné operácie, ktoré môžeme vykonávať s HashTable, patria:

  • Pridávanie párov
    Metóda put(key, value) vloží nový pár do tabuľky. Ak sa vloží nový pár so zhodným kľúčom, stará hodnota sa prepíše.
  • Odstraňovanie párov
    Metóda remove(key) odstráni pár s daným kľúčom.
  • Test prázdnosti
    Metóda isEmpty() nám zistí, či HashTable vôbec obsahuje nejaký pár.
  • Test prítomnosti
    Metódy containsKey(key), containsValue(value) zisťujú, či sa v tabuľke nachádza daný kľúč alebo hodnota.
  • Zistenie veľkosti
    Metóda size() vráti počet párov v tabuľke.
  • Vyprázdnenie tabuľky
    Metóda clear() odstráni všetky páry z tabuľky.
  • Iterácia
    Pomocou metód keySet(), values() alebo entrySet() môžeme iterovať cez kľúče, hodnoty alebo celé páry.

HashTable – dokumentácia

Kompletný prehľad metód triedy HashTable, nájdeš v oficiálnej dokumentácii.

HashTable – výhody a nevýhody

Výhody HashTable

  • Synchronizácia
    HashTable je synchronizovaná, takže je bezpečná pre použitie vo viacvláknových aplikáciách bez ďalšej synchronizácie.
  • Rýchle operácie
    V ideálnych podmienkach poskytuje operácie pridávania, vyhľadávania a odstraňovania v konštantnom čase (O(1)).
  • Jednoduchosť použitia
    API je prehľadné a intuitívne, čo uľahčuje prácu s mapovacími dátovými štruktúrami.

Nevýhody HashTable

  • Zastaralosť
    HashTable je považovaná za staršiu implementáciu. Moderné kolekcie ako HashMap ponúkajú lepší výkon a viac možností.
  • Bez null hodnôt
    Na rozdiel od niektorých kolekcií HashTable neumožňuje null kľúče ani null hodnoty, čo môže byť obmedzujúce.
  • Citlivosť na implementáciu hashCode a equals
    Ak trieda, ktorú ukladáme ako prvok, nemá správne implementované metódy hashCode() a equals(), môže to viesť k neočakávanému správaniu a zníženiu výkonu.
  • Výkon v prípade kolízií
    Pri veľkom počte kolízií (keď viaceré prvky majú rovnaký hash kód) môže dôjsť k zníženiu výkonu, pretože operácie sa môžu správať pomalšie.

HashTable – kedy ju použiť a kedy nie?

HashTable je vhodná v nasledovných prípadoch:

  • Potrebujeme synchronizovanú mapu bez potreby explicitnej synchronizácie.
  • Netreba ukladať null hodnoty.

Naopak, ak nepotrebujeme synchronizáciu alebo chceme podobnú kolekciu s vyšším výkonom, odporúča sa používať HashMap.

Príklad použitia HashTable v Jave

HashTable vyniká efektívnym ukladaním párov kľúč-hodnota a ich rýchlym vyhľadaním vďaka hashovacej metóde, keď ich potrebujeme načítať a použiť. Preto majú hashovacie tabuľky všestranné použitie.

Teraz si to predvedieme v programe, v ktorom najskôr HashTable vytvoríme pomocou konštruktora a uložíme do nej štáty susediace so Slovenskom. Následne si ešte ukážeme použitie niektorých základných metód pre prácu s HashTable.

Main.java

import java.util.Hashtable;
import java.util.Enumeration;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        // Hashtable creation
        Hashtable<String, String> skNeighbors = new Hashtable<>();

        // Adding country codes and country names
        skNeighbors.put("SK", "Slovakia");
        skNeighbors.put("CZ", "Czech Republic");
        skNeighbors.put("AT", "Austria");
        skNeighbors.put("HU", "Hungary");
        skNeighbors.put("UA", "Ukraine");
        skNeighbors.put("PL", "Poland");

        // Display all country codes and names using Enumeration
        System.out.println("Neighboring states of Slovakia:");
        Enumeration<String> keys = skNeighbors.keys();
        while (keys.hasMoreElements()) {
            String code = keys.nextElement();
            if(!code.equals("SK"))
                System.out.println(code + " - " + skNeighbors.get(code));
        }

        // Lookup a country by its code
        String searchCode = "DE";
        if (skNeighbors.containsKey(searchCode)) {
            System.out.println("\n✅ Country found for code " + searchCode + ": " + skNeighbors.get(searchCode));
        } else {
            System.out.println("\n❌ No country found for code " + searchCode);
        }

        // Display the total number of countries in the directory
        System.out.println("\nTotal number of countries in the Hashtable (before remove): " + skNeighbors.size());

        // Try to remove a country by its code which is not present
        String removeCode = "DE";
        String removedCountry = skNeighbors.remove(removeCode);
        System.out.println("Removed country: " + removeCode + " - " + removedCountry);

        // Try to remove a country by its code
        removeCode = "SK";
        removedCountry = skNeighbors.remove(removeCode);
        System.out.println("Removed country: " + removeCode + " -> " + removedCountry);

        // Check if a specific country exists in the table
        String searchCountry = "Germany";
        if (skNeighbors.containsValue(searchCountry)) {
            System.out.println("✅ " + searchCountry + " is in the directory.");
        } else {
            System.out.println("❌ " + searchCountry + " is NOT in the directory.");
        }

        // Display the total number of countries in the directory
        System.out.println("\nTotal number of countries in the Hashtable (after remove): " + skNeighbors.size());

        // Clear all country entries
        skNeighbors.clear();
        System.out.println("Country directory cleared. Is it empty? " + skNeighbors.isEmpty());

        // Display all remaining countries using keySet()
        System.out.println("Remaining countries after clearing:");
        Set<String> keySet = skNeighbors.keySet();
        for (String code : keySet) {
            System.out.println(code + " - " + skNeighbors.get(code));
        }
    }
}

Výstup z tohto príkladu je:

HashTable - výstup z tohto príkladu

Pripravili sme pre teba súbory so spomínaným príkladom vo forme kódu, ktorý si môžeš spustiť priamo v Jave. Stiahni si Java kód pre HashTable tu.

O autorovi

Jozef Wagner

Java Developer Senior

Viac ako 10 rokov programujem v Jave, momentálne pracujem v msg life Slovakia ako Java programátor senior a pomáham zákazníkom implementovať ich požiadavky do poistného softvéru Life Factory. Vo voľnom čase si rád oddýchnem v lese, prípadne si zahrám nejakú dobrú počítačovú hru.

Daj nám o sebe vedieť