Co to jest Hashtable?
W informatyce hashtable to struktura danych do przechowywania danych, która składa się z listy wartości, zwanych kluczami, które są łączone z odpowiednią listą wartości, zwaną tablicą. Na przykład nazwa firmy może zostać sparowana z jej adresem. Zazwyczaj każda wartość w tablicy ma numer pozycji określany jako skrót. Funkcja skrótu to na ogół zestaw instrukcji lub algorytm, który odwzorowuje każdą wartość klucza na skrót - łącząc nazwę firmy z jej adresem, numerem telefonu i kategorią biznesową. Celem funkcji skrótu jest przypisanie każdego klawisza do unikalnej odpowiadającej wartości w tablicy; jest to powszechnie nazywane skrótem. Funkcje skrótu muszą być odpowiednio sformatowane, aby tablica skrótów działała poprawnie.
Wydajność tablicy mieszającej na zestawie danych zależy od wydajności jej funkcji mieszającej. Dobra funkcja skrótu zazwyczaj zapewnia jednolite wyszukiwanie kluczy i równomierny rozkład odwzorowań w odpowiedniej tablicy. Zderzenie mieszania występuje, gdy dwa klucze są przypisane do tej samej odpowiedniej wartości. Kiedy występuje kolizja skrótu, funkcja skrótu jest zwykle wykonywana ponownie, dopóki nie zostanie znaleziona unikalna odpowiadająca jej wartość; zwykle skutkuje to dłuższym czasem mieszania. Chociaż liczba kluczy w tablicy mieszającej jest zwykle ustalona, czasem mogą występować duplikaty kluczy. Mimo to dobrze zaprojektowana tablica skrótów ma skuteczne funkcje skrótu, które odwzorowują każdy klucz na unikalną odpowiadającą mu wartość w tablicy.
Czasami nieefektywne funkcje skrótu w tablicy skrótów mogą również powodować tworzenie się klastrów odwzorowań. Jeśli funkcja skrótu tworzy klaster odwzorowań dla istniejących kluczy, może to wydłużyć czas potrzebny na wyszukanie odpowiednich wartości. Może to spowolnić haszowanie przyszłych kluczy, ponieważ większość funkcji haszujących zazwyczaj szuka następnej dostępnej pozycji w tablicy. Jeśli przypisano już duży klaster wartości, zwykle szukanie nieprzypisanej wartości dla nowego klucza zajęłoby znacznie więcej czasu.
Współczynnik obciążenia to kolejna koncepcja związana z wydajnością funkcji skrótu; współczynnik obciążenia to ilość już istniejących skrótów w stosunku do całkowitego rozmiaru odpowiedniej tablicy w tablicy skrótów. Zwykle jest definiowany przez podzielenie liczby już przypisanych kluczy przez rozmiar odpowiedniej tablicy. Wraz ze wzrostem współczynnika obciążenia dobra funkcja skrótu normalnie nadal utrzymuje stałą liczbę kolizji i skupień do pewnego momentu. Często ten próg może być wykorzystywany do określania wydajności funkcji skrótu przy danej liczbie kluczy i kiedy może być potrzebna nowa funkcja skrótu.
Wielu naukowców zajmujących się informatyką dążyło do stworzenia idealnej funkcji skrótu - takiej, która nie powoduje kolizji ani skupień, biorąc pod uwagę rosnący współczynnik obciążenia. Teoretycznie kluczem do stworzenia idealnej tablicy hashującej jest stworzenie idealnej funkcji skrótu. Ogólnie rzecz biorąc, naukowcy uważają, że idealna funkcja skrótu powinna mieć stałą wydajność - liczbę kolizji i skupień - przy rosnącym współczynniku obciążenia. W najgorszych przypadkach idealna funkcja skrótu nadal umożliwia ciągłe mieszanie bez osiągania progu.