Wikiszótár

hash tábla

Magyar

Kiejtés

  • IPA: [ ˈhɒʃhtaːblɒ]

Főnév

hash tábla

  1. (matematika, algoritmusok)

Hash tábla

Definíció

A hash tábla egy adatszerkezet, amely kulcs-érték párokat tárol, és rendkívül hatékony az adatkeresés, beszúrás és törlés szempontjából. A hash tábla egy kulcshoz tartozó értéket egy hash függvény segítségével egy adott indexre térképez egy tömbben vagy egy másik adatszerkezetben.


Fő Jellemzők

  1. Hash függvény:
    • Olyan függvény, amely egy kulcsot egy indexhez rendel.
    • Például: ( h(k) = k n ), ahol ( k ) a kulcs, és ( n ) a hash tábla mérete.
  2. Ütközések kezelése:
    • Két különböző kulcs ugyanarra az indexre kerülhet (ütközés).
    • Ütközési megoldások:
      • Nyílt láncolás: Az indexhez tartozó értékeket egy láncba (például láncolt listába) mentjük.
      • Nyílt címzés: Ütközés esetén a hash függvény egy másik indexet keres (például lineáris próbálkozás).
  3. Hatékonyság:
    • Az átlagos időkomplexitás keresésre, beszúrásra és törlésre: ( O(1) ).
    • Legrosszabb esetben (pl. sok ütközés): ( O(n) ).


Hash Tábla Műveletek

  1. Beszúrás (Insert):
    • Egy kulcsot és annak értékét beszúrjuk a hash táblába.
    • Példa: ( ).
  2. Keresés (Search):
    • Megkeressük egy kulcs értékét.
    • Példa: ( ).
  3. Törlés (Delete):
    • Eltávolítjuk a kulcs-érték párt a táblából.
    • Példa: ( ).


Python Implementáció

Nyílt láncolású hash tábla

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(size)]

    def hash_function(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        index = self.hash_function(key)
        # Ellenőrizzük, hogy a kulcs már létezik-e
        for pair in self.table[index]:
            if pair[0] == key:
                pair[1] = value
                return
        # Ha nem létezik, beszúrjuk
        self.table[index].append([key, value])

    def search(self, key):
        index = self.hash_function(key)
        for pair in self.table[index]:
            if pair[0] == key:
                return pair[1]
        return None  # Kulcs nem található

    def delete(self, key):
        index = self.hash_function(key)
        for pair in self.table[index]:
            if pair[0] == key:
                self.table[index].remove(pair)
                return True
        return False  # Kulcs nem található

    def __str__(self):
        return str(self.table)

# Példa használat
hash_table = HashTable(10)
hash_table.insert("alma", 5)
hash_table.insert("körte", 7)
hash_table.insert("szilva", 12)

print("Hash tábla tartalma:", hash_table)
print("Keresés (alma):", hash_table.search("alma"))
hash_table.delete("alma")
print("Hash tábla alma törlése után:", hash_table)

Kimenet
Hash tábla tartalma: [[['alma', 5]], [['körte', 7]], [['szilva', 12]], [], [], [], [], [], [], []]
Keresés (alma): 5
Hash tábla alma törlése után: [[], [['körte', 7]], [['szilva', 12]], [], [], [], [], [], [], []]

Nyílt címzésű hash tábla

class OpenAddressingHashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

    def hash_function(self, key):
        return hash(key) % self.size

    def probe(self, index):
        return (index + 1) % self.size  # Lineáris próbálkozás

    def insert(self, key, value):
        index = self.hash_function(key)
        original_index = index
        while self.table[index] is not None and self.table[index][0] != key:
            index = self.probe(index)
            if index == original_index:
                raise Exception("Hash tábla tele")
        self.table[index] = (key, value)

    def search(self, key):
        index = self.hash_function(key)
        original_index = index
        while self.table[index] is not None:
            if self.table[index][0] == key:
                return self.table[index][1]
            index = self.probe(index)
            if index == original_index:
                break
        return None

    def delete(self, key):
        index = self.hash_function(key)
        original_index = index
        while self.table[index] is not None:
            if self.table[index][0] == key:
                self.table[index] = None
                return True
            index = self.probe(index)
            if index == original_index:
                break
        return False

    def __str__(self):
        return str(self.table)

# Példa használat
hash_table = OpenAddressingHashTable(10)
hash_table.insert("alma", 5)
hash_table.insert("körte", 7)
hash_table.insert("szilva", 12)

print("Hash tábla tartalma:", hash_table)
print("Keresés (alma):", hash_table.search("alma"))
hash_table.delete("alma")
print("Hash tábla alma törlése után:", hash_table)

Kimenet
Hash tábla tartalma: [('alma', 5), None, None, None, ('körte', 7), None, None, ('szilva', 12), None, None]
Keresés (alma): 5
Hash tábla alma törlése után: [None, None, None, None, ('körte', 7), None, None, ('szilva', 12), None, None]

Előnyök és Hátrányok

Előnyök:

  • Gyors keresés, beszúrás és törlés (( O(1) ) átlagosan).
  • Egyszerű implementáció és rugalmasság.

Hátrányok:

  • Ütközések kezelése komplex lehet.
  • Rossz hash függvény vagy túl sok elem esetén a teljesítmény romlik.
  • Hash táblák memóriaigénye nagyobb lehet, mint más adatszerkezeteké.


Alkalmazások

  1. Gyors keresés:
    • Adatok gyors előkeresése például adatbázisokban.
  2. Kulcs-érték tárolás:
    • Használják például Pythonban a szótárak és Java-ban a HashMap-ek.
  3. Hálózatok:
    • Címek gyors keresése például DNS-rendszerekben.
  4. Adatindexelés:
    • Gyors adatkeresés indexelési algoritmusokban.


Összegzés

A hash tábla hatékony és széles körben alkalmazható adatszerkezet. Az ütközések megfelelő kezelése és a hash függvény kiválasztása kulcsfontosságú a teljesítmény maximalizálásában. A Python beépített szótárak is hash táblákon alapulnak, és könnyen használhatók.

Fordítások

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=hash_tábla&oldid=3479815”