hash map
Főnév
- (informatika) A hash map (más néven hash table, magyarul gyakran hasító tábla vagy kulcs–érték páros tároló) egy olyan adatszerkezet, amely kulcsokat (key) és a hozzájuk tartozó értékeket (value) tárol. A hatékonyságának kulcsa egy hash függvény, amely a kulcsot egy memóriacímre (indexre) képezi le.
🔧 Alapötlet
A hash map célja, hogy:
- egy értéket gyorsan megtaláljunk egy kulcs alapján,
- új párokat gyorsan be tudjunk illeszteni,
- törlést is hatékonyan végezhessünk.
A tipikus műveletek:
insert(key, value)get(key)vagyfind(key)remove(key)
Mindegyik átlagosan O(1) időben történik – vagyis konstans idő alatt.
🧠 Hogyan működik?
1. Hash függvény
A kulcsot (pl. "alma", vagy 42) egy hash függvény leképezi egy egész számra (az ún. hash kódra), pl.:
hash("alma") → 18239123
2. Tárolás egy tömbben
Egy fix méretű tömbben tároljuk az adatokat, a hash alapján kiválasztott indexre:
index = hash(key) % table_size
⚠️ Ütközések (collisions)
Mivel sok kulcsot kevés indexre kell leképezni, előfordulhat, hogy két különböző kulcs ugyanarra az indexre kerül. Ez ütközés. Két gyakori kezelési módja:
1. Láncolás (chaining)
Minden indexhez egy lista tartozik, így több kulcs is ott lehet:
table[5] = { ("kutya",3), ("macska",4) }
2. Nyílt címzés (open addressing)
Ha egy hely foglalt, másik szabad indexet keresünk pl. lineárisan vagy kvadratikusan.
📦 Használat különböző nyelvekben
C++ (std::unordered_map)
#include <unordered_map>
std::unordered_map<std::string, int> gyumolcs;
gyumolcs["alma"] = 5;
gyumolcs["banán"] = 3;
std::cout << gyumolcs["alma"]; // 5
Python (dict)
gyumolcs = {"alma": 5, "banán": 3}
print(gyumolcs["alma"]) # 5
Java (HashMap)
import java.util.HashMap;
HashMap<String, Integer> gyumolcs = new HashMap<>();
gyumolcs.put("alma", 5);
gyumolcs.put("banán", 3);
System.out.println(gyumolcs.get("alma")); // 5
📊 Teljesítmény
| Művelet | Átlagos idő | Legrosszabb eset |
|---|---|---|
insert() |
O(1) | O(n) |
get() |
O(1) | O(n) |
delete() |
O(1) | O(n) |
Legrosszabb eset akkor fordul elő, ha minden kulcs ugyanoda kerül, de jól megválasztott hash függvény mellett ez ritka.
🧮 Példa működésre
Tegyük fel, hogy table_size = 10 és a hash így működik:
hash("kutya") % 10 → 3hash("macska") % 10 → 3(ütközés)
Ekkor:
Index | Tartalom
------|--------------------------
3 | [ ("kutya", 5), ("macska", 9) ]
✅ Előnyök
- Gyors keresés, beszúrás, törlés (átlagosan O(1))
- Könnyen használható kulcs–érték viszonyokhoz
- Támogatja string, szám vagy más típusú kulcsokat (ha van hash-függvény)
❌ Hátrányok
- Hash függvényt nehéz jól megválasztani
- Nem rendezett (ellentétben pl.
std::mapvagyTreeMap) - Memóriaigényes (sok üres hely lehet)
- Ütközések kezelése komplexitást visz a rendszerbe
🧪 Haladó témák
- Rehashing: ha a táblázat túl telített, újra kell osztani (dupla méret).
- Custom hash: C++-ban saját hash függvény készítése
- Load factor: tényleges elem/tábla méret arány → 0.7 fölött érdemes újratárazni
🎓 Összefoglalás
A hash map:
- egy hatékony adatszerkezet kulcs–érték párok tárolására,
- a kulcsot hash függvénnyel indexeli,
- gyors műveleteket biztosít,
- és elengedhetetlen sok modern algoritmus és program számára (pl. cache-k, szótárak, leképezések, duplikátum ellenőrzés, stb.).