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.
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 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 výhody a nevýhody a kedy je vhodné 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.
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:
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.
