Dopuszczalne typy używane jako klucze w HashTable

Question

Muszę przyznać, że posiadam tylko podstawowe wiadomości na temat działania HashTables, chociaż z tego, co wiem, wydaje mi się to dość proste. Moje pytanie brzmi właśnie tak: wydaje się, że konwencjonalna mądrość polega na używaniu prostych, podstawowych typów wartości, takich jak liczby całkowite dla kluczy w HashTable. Ciągi są jednak często używane, chociaż w wielu językach są one implementowane jako typy odniesienia. To, co uważam za ogólnie zalecane, nie jest zalecane przy użyciu złożonych typów referencyjnych; Zgaduję, że to dlatego, że wymagałoby to wolniejszej funkcji skrótu? Ale dlaczego tak powszechnie używane są struny? W końcu nie jest wewnętrznie ciągiem tablicy char [] (znowu w większości języków)?

W końcu, jakie typy wartości są ogólnie uważane za "najlepsze" (lub nawet po prostu "dopuszczalne") wybory do użycia jako klucze w HashTable? A czy są jakieś powszechnie stosowane wybory, które są faktycznie uważane za "złe" (jak na przykład ciągi)?

Answer 1

Najlepszym hash keys są te, które

1. mają dobre (jak w niskich collisions) skrótów (patrz Object.GetHashCode dla .NET Object.hashcode dla Javy)
2. mieć szybki porównań (bo gdy istnieją kolizje hash) .

Wszystko, co powiedzieliśmy, myślę, że łańcuchy są w większości przypadków dobrymi klawiszami skrótów, ponieważ istnieje wiele doskonałych implementacji skrótów dla ciągów.

Answer 2

Tak długo, jak jest zapewniona odpowiednia funkcja skrótu, wszystkie typy będą działały jak klucze. Pamiętaj, że po wszystkim tablica asocjacyjna jest po prostu tablicą liniową. Funkcja hash pobiera klucz określonego typu i oblicza indeks w tablicy tablicy mieszającej (zwanej bucket), w której wartość jest zapisywana (ale występują pewne problemy z kolizjami).

Tak naprawdę trudną częścią jest znalezienie funkcji skrótu. Oczywiście powinien on posiadać pewne właściwości, takie jak proste do obliczenia, chaotyczne (prawie identyczne klucze powinny być odwzorowane na kompletnie różne łyżki tabeli mieszania), deterministyczne (te same klucze oznaczają to samo tablice tablicy mieszającej), jednolitość (wszystkie możliwe klucze są odwzorowywane równomiernie na wiaderka), lub surektywność (wszystkie wiadra tabeli hash powinny być użyte).

Wydaje się, że łatwiej jest zdefiniować taką funkcję dla prostych typów, takich jak liczby całkowite.

Answer 3

Większość implementacji ciągów, chociaż mogą one wyglądać jako typy odniesień w zarządzanych środowiskach, ich implementacja jest zwykle typu niezmiennego.

Funkcja skrótu polega na mapowaniu bardzo dużej liczby stanów na mniejszą liczbę stanów.

Dlatego mieszanie łańcuchów jest dobre do testowania równości łańcuchów. Możesz odwzorować wartość na indeks tablicy i szybko wyszukać informacje o tej wartości. Nie musisz porównywać każdego znaku z każdym innym znakiem w każdym innym ciągu. I możesz powiedzieć dokładnie to samo o wszystkim. Chodzi o zmniejszenie lub pobranie odcisków palców dowolnej liczby bajtów w jakiś użyteczny sposób.

W tym miejscu dyskusja na temat typu klucza używanego w tablicy mieszającej staje się nieważna, ponieważ jest mapowaniem tej wartości na mniejszą przestrzeń stanów i sposobem, w jaki jest ona wykorzystywana wewnętrznie, co czyni ją użyteczną. Liczba całkowita jest zwykle przyjazna sprzętowo, ale 32-bitowe nie jest tak naprawdę dużą przestrzenią, a kolizje są prawdopodobnie w obrębie tej przestrzeni dla dowolnych danych wejściowych.

W końcu, jeśli użyjesz tabeli mieszania, koszt obliczenia wartości skrótu jest nieistotny w porównaniu do czasu, jaki zajęłoby porównanie każdej wartości z każdą inną wartością w każdej innej możliwej pozycji (zakładając, że twój hash tabela zawiera setki pozycji).

Answer 4

Jeśli było użyć typu złożonego jako klucz następnie:

• byłoby trudne do wdrożenia tabeli hash do pozycji grupy w wiadrach do szybkiego odzyskania; w jaki sposób zdecydować, jak pogrupować zakres skrótów w wiadrze?
• Tabela mieszania może wymagać dokładnej znajomości typu, aby wybrać wiadro.
• Istnieje ryzyko zmiany właściwości obiektu, co powoduje, że przedmioty kończą się w niewłaściwych segmentach. Hashy muszą być niezmienne.

Liczby całkowite często używane, ponieważ można je łatwo podzielić na zakresy odpowiadające segmentom, są to typy wartości, a zatem niezmienne i są dość łatwe do wygenerowania.

Answer 5

To nie jest kwestia ciągów porównaniu liczb całkowitych, lub wartości kontra odniesienia, ale modyfikowalnych klawiszy porównaniu kluczy niezmiennych. Tak długo, jak klucze są niezmienne (a tym samym ich wartość mieszania nigdy się nie zmienia), są one w stanie indeksować tablicę asocjacyjną. Na przykład ciągi znaków w języku Java są niezmienne i dlatego doskonale nadają się jako klucze hashtable.

Nawiasem mówiąc, jeśli typ danych jest na tyle prosty, aby zawsze był przekazywany przez wartość (np. Skalary), to oczywiście będzie w porządku.

Ale teraz wyobraź sobie, że używasz zmiennego typu; jeśli podasz mi odniesienie do jednego z tych obiektów jako klucza, wyliczę jego wartość hash, a następnie umieścisz ją w jednym z moich zasobników hashtable. Ale kiedy później zmodyfikujesz obiekt, nie będę miał możliwości powiadomienia; i obiekt może teraz znajdować się w niewłaściwym wiadrze (jeśli jego wartość mieszania jest inna).

Mam nadzieję, że to pomoże.