W jaki sposób tabele hash są implementowane wewnętrznie w popularnych językach?

Perl używa tablicy z połączonymi listami do przechowywania kolizji. Ma prostą heurystykę, która automatycznie podwaja rozmiar tablicy w razie potrzeby. Istnieje również kod do udostępniania kluczy między hashami, aby zaoszczędzić trochę pamięci. Możesz o tym przeczytać w datowanym, ale wciąż istotnym Perl pod "HV". Jeśli jesteś naprawdę żądny przygód, możesz kopać w hv.c .

Algorytm haszujący kiedyś był dość prosty, ale teraz jest pewnie o wiele bardziej skomplikowany z Unicode. Ponieważ algorytm był przewidywalny, doszło do ataku DoS, w wyniku którego atakujący generował dane, które powodowały kolizje hashów. Na przykład ogromna lista kluczy wysyłanych do witryny sieci Web jako dane POST. Program Perla prawdopodobnie podzieliłby go i wrzucił do hasha, który następnie wepchnął wszystko do jednego wiadra. Otrzymany hash był O (n), A nie o (1). Wrzuć całą masę żądań POST na serwer i możesz zatkać procesor. W rezultacie Perl zakłóca teraz funkcję hash z bitem losowych danych.

Możesz też przyjrzeć się jak Parrot implementuje Basic hashes, co jest znacznie mniej przerażające niż implementacja Perla 5.

Jeśli chodzi o "najbardziej wydajny i praktyczny", użyj cudzej biblioteki hashów. Na litość boską, nie pisz żadnego na użytek produkcji. Jest już hojlion solidnych i wydajnych.

Tabele Lua używają całkowicie pomysłowej implementacji , która dla dowolnych kluczy zachowuje się jak 'tablica z wiadrami', ale jeśli używasz kolejnych liczb całkowitych jako kluczy, ma taką samą reprezentację i spację jak tablica. W implementacji każda tabela zawiera część hashową oraz część array.

Myślę, że to jest bardzo fajne: -)

Attractive Chaos ma porównanie bibliotek tabel Hashowych i update . Kod źródłowy jest dostępny i jest w C i C++

Zbalansowane drzewa w pewnym sensie nie spełniają celu tabel hash, ponieważ tabela hash może zapewnić wyszukiwanie w (amortyzowanym) stałym czasie, podczas gdy średnie wyszukiwanie w zrównoważonym drzewie to o (log (n)).

Separate chaining (array with linked list) naprawdę działa całkiem dobrze, jeśli masz wystarczającą ilość buckets, a twoja implementacja linked list używa alokatora poolingu, a nie malloc()ing każdy węzeł ze sterty osobno. Uważam, że jest tak samo wydajna jak każda inna technika, gdy odpowiednio dostrojony, bardzo łatwy i szybki w pisaniu. Spróbuj zacząć od 1/8 tyle łyżek, ile danych źródłowych.

Możesz również użyć open addressingz sondowaniem kwadratowym lub wielomianowym, tak jak robi to Python.

Jeśli możesz przeczytać Java, Możesz sprawdzić kod źródłowy dla różnych implementacji map, w szczególności HashMap, TreeMap i ConcurrentSkipListMap. Dwa ostatnie zachowują klucze zamówione.

Java ' s HashMap używa standardowej techniki, o której wspomniałeś o łańcuchowaniu w każdej pozycji kubełka. Używa dość słabych 32-bitowych kodów skrótu i przechowuje klucze w tabeli. Autorzy numerycznych receptur podają również przykład (w C) tabeli hashowej zasadniczo skonstruowanej jak Java, ale w której (a) przydzielasz węzły bucket listy z tablicy, i (b) używasz silniejszy 64-bitowy kod hash i zrezygnować z przechowywania kluczy w tabeli.

Co Crashworks miał na myśli....

Celem tabel Hash jest wyszukiwanie w czasie stałym, dodawanie i usuwanie. Pod względem algorytmu operacja dla wszystkich operacji wynosi O (1). Natomiast w przypadku korzystania z drzewa ...w najgorszym przypadku czas operacji będzie wynosił O (log n)dla zrównoważonego drzewa. N to liczba węzłów. ale czy naprawdę mamy hash zaimplementowany jako drzewo?