Autor: Joanna, data dodania: 2019-09-30

Czym jest tablica mieszająca (hashtable)?

Autor: Joanna, data dodania: 2019-10-04

0

To tablica, która działa na zasadzie klucz-wartość, dzięki czemu odczytywanie danych jest bardzo szybkie i nie zależy od wielkości tablicy. W tablicy mieszającej stosuje się funkcję mieszającą, która dla danego klucza wyznacza indeks w tablicy. W najprostszym przypadku do każdego indeksu przypisany jest jeden klucz, co sprawia, że czas odczytywania danych jest bardzo szybki i wynosi O(1). Sprawa komplikuje się, kiedy funkcja mieszająca przypisze ten sam indeks w tablicy dwóm kluczom. Wtedy powstaje tzw. kolizja - sytuacja, w której pod jednym indeksem znajduje się kilka kluczy. Szukając odpowiedniego klucza i przypisanej do niego wartości tablica musi przeszukać kilka elementów przypisanych do tego samego indeksu (tak jakby przeszukiwała drugą tablicę - choć niekoniecznie dane zapisane pod jednym indeksem muszą być w formie tablicy). Czas wyszukiwania danych wydłuża się w takiej sytuacji do O(n) - bo pod danym indeksem trzeba przeszukać n elementów, które są tam przypisane.

Zaloguj się, by dodać odpowiedź