Co jest hashtable?

W informatyce hashtable to struktura danych do przechowywania danych, która składa się z listy wartości, zwanych klawiszami, które są sparowane 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 jest na ogół zestawem instrukcji lub algorytmem, który mapuje każdą kluczową wartość do skrótu i mdash;Łączenie nazwy firmy z jej adresem, numerem telefonu i kategorii biznesowej.Celem funkcji skrótu jest przypisanie każdego klucza do unikalnej odpowiedniej wartości w tablicy;Jest to powszechnie określane jako mieszanie.Funkcje skrótu muszą być prawidłowo sformatowane, aby hashtable do prawidłowego funkcjonowania.

Wydajność hashtabla na zbiorze danych zależy od wydajności jego funkcji skrótu.Dobra funkcja skrótu zazwyczaj zapewnia jednolite wyszukiwanie klawiszy i równomierny rozkład mapowań w odpowiedniej tablicy.Zderzenie skrótu występuje, gdy dwa klucze są przypisane do tej samej odpowiedniej wartości.Gdy nastąpi kolizja skrótu, funkcja skrótu jest zwykle wykonywana ponownie, aż znajdzie się unikalna odpowiednia wartość;To zwykle powoduje dłuższe czasy mieszania.Chociaż liczba klawiszy w hashcie jest zwykle ustalona, czasami mogą być zduplikowane klucze.Mimo to dobrze zaprojektowana hashtable ma skuteczne funkcje skrótu, które mapują każdy klucz do unikalnej odpowiedniej wartości w tablicy.

Czasami nieefektywne funkcje skrótu w hashcie mogą również wytwarzać klaster mapowań.Jeśli funkcja skrótu tworzy klaster mapowań dla istniejących kluczy, może to zwiększyć czas potrzebny na wyszukiwanie odpowiednich wartości.Może to spowolnić mieszanie dla przyszłych kluczy, ponieważ większość funkcji HASH zazwyczaj szuka kolejnej dostępnej pozycji w tablicy.Jeśli przypisano już dużą klaster wartości, zazwyczaj poszukanie nie przypisanej wartości dla nowego klucza zajęłoby znacznie więcej czasu.

Współczynnik obciążenia jest kolejną koncepcją związaną z wydajnością funkcji skrótu;Współczynnik obciążenia to ilość istniejących machów w stosunku do ogólnej wielkości odpowiedniej tablicy w hashcie.Zazwyczaj jest to definiowane przez podzielenie liczby już przypisanych kluczy według wielkości odpowiedniej tablicy.Wraz ze wzrostem współczynnika obciążenia dobra funkcja skrótu zwykle utrzyma stałą liczbę zderzeń i klastrów do pewnego punktu.Często ten próg można wykorzystać do ustalenia, jak wydajna jest funkcja skrótu z daną liczbą kluczy, a kiedy może być potrzebna nowa funkcja skrótu.

Wielu badaczy informatyki starało się stworzyć idealną funkcję skrótów i mdash;taki, który nie wytwarza zderzeń ani klastrów, biorąc pod uwagę rosnący współczynnik obciążenia.Teoretycznie kluczem do tworzenia idealnej hashtacji jest wykonanie doskonałej funkcji skrótu.Ogólnie rzecz biorąc, naukowcy uważają, że doskonała funkcja skrótu powinna mieć stałą wydajność mdash;liczba zderzeń i klastrów mdash;z rosnącym współczynnikiem obciążenia.W najgorszych scenariuszach idealna funkcja skrótu nadal pozwoliłaby na ciągłe mieszanie bez osiągnięcia progu.