Jak powinienem zrobić optymalizację tabeli mieszania dla danej populacji?

Question

Powiedz, że mam populację par klucz-wartość, które planuję przechowywać w tabeli mieszania. Populacja jest stała i nigdy się nie zmieni. Jakie optymalizacje są dostępne, aby tablica asocjacyjna była tak szybka, jak to tylko możliwe? Na których optymalizacjach powinienem się skoncentrować? Zakładam, że mam dużo przestrzeni. Będzie rozsądna liczba par (powiedzmy nie więcej niż 100 000).

EDIT: Chcę zoptymalizować wyszukiwanie. Nie obchodzi mnie, ile czasu zajmuje zbudowanie.

Answer 1

Upewnię się, że hasz klucza jest unikalny. Zapewni to, że każde wyszukiwanie będzie stałym czasem, a więc tak szybko jak to możliwe.

Ponieważ nigdy nie można mieć więcej niż 100 000 kluczy, możliwe jest uzyskanie 100 000 wartości skrótu.

Upewnij się również, że używasz konstruktora, który pobiera int, aby określić początkową pojemność (ustawiono na 100 000) i wartość zmiennoprzecinkową, aby ustawić współczynnik obciążenia. (Użyj 1) Ponadto, wykonanie tego wymaga posiadania idealnej funkcji skrótu dla kluczy. Ale spowoduje to najszybsze wyszukiwanie, przy jak najmniejszej ilości pamięci.

Answer 2

Upewnij się, że nie ma kolizji. Jeśli nie ma kolizji, masz zagwarantowany stały czas patrzenia O (1). Następną optymalizacją byłoby wówczas wyszukiwanie.

Użyj profilera, aby zoptymalizować kawałek po kawałku. Bez tego trudno jest.

Answer 3

Optymalizację należy wykonać w metodzie hashCode klucza . Należy pamiętać o tym, aby zaimplementować tę metodę, aby uniknąć kolizji.

Answer 4

Ogólnie rzecz biorąc, aby zoptymalizować tabelę skrótów, należy zminimalizować kolizje podczas określania wartości mieszania, aby w zasobnikach nie było więcej niż jednego elementu, a wyszukiwanie haszowania natychmiast powróci.

W większości przypadków oznacza to, że należy zmierzyć wyjście funkcji mieszania w obszarze problemu. Więc myślę, że polecam zajrzeć do tego

Answer 5

Jeśli jest możliwe, aby duży stół mieszania, tak, że nie ma żadnych kolizji, będzie idealny. Ponieważ twoje wstawienia i wyszukiwania będą wykonywane w stałym czasie.

Ale jeśli nie jest to możliwe, spróbuj wybrać funkcję skrótu, aby klucze były rozdzielane równomiernie na stole mieszającym.

Answer 6

Perfect hashing algorithms radzi sobie z problemem, ale nie może skalować do 100 tys. Obiektów. Znalazłem Java MPH package, ale go nie wypróbowałem.

Answer 7

Jeśli populacja jest znana podczas kompilacji, optymalnym rozwiązaniem jest użycie minimalnej idealnej funkcji skrótu (MPH). The Wikipedia page na ten temat łączy się z kilkoma narzędziami Java, które mogą je wygenerować.

Answer 8

Uzyskanie idealnego algorytmu mieszającego, który da całkowicie unikalne wartości obiektom 100K, będzie prawdopodobnie niemożliwe. Weźmy pod uwagę paradoks urodzin. Data, w której ludzie się urodzili, może być uważana za idealny algorytm haszowania, ale jeśli masz więcej niż 23 osoby, prawdopodobieństwo kolizji jest większe niż w tabeli z 365 datami.

Jak duży stół nie potrzebuje kolizji w 100K?

Jeśli twoje klucze są łańcuchami, twoja optymalna strategia to drzewo, a nie binarne, ale n-rozgałęzione dla każdej postaci. Jeśli klawisze są pisane małymi literami, jest to jeszcze łatwiejsze, ponieważ potrzebujesz tylko 26 razy, gdy tworzysz oddział.

Zaczynamy od 26 klawiszy. Podążaj za pierwszym znakiem, powiedzmy, że f f może mieć przypisaną wartość. I może mieć pod-drzewa. Wyszukaj podtekst o. Prowadzi to do kolejnych podtktów, a następnie do następnego o. (Wiedziałeś, dokąd to prowadzi!). Jeśli nie ma ona powiązanej z nim wartości lub po drodze trafimy na puste drzewo podrzędne, wiemy, że wartość nie została znaleziona.

Możesz zoptymalizować przestrzeń na drzewie, w której trafiłeś w punkt wyjątkowości. Powiedzmy, że masz kluczowy styczeń i staje się wyjątkowy na 4. znaku. W tym momencie, w którym przypisujesz wartość, przechowujesz również rzeczywisty ciąg związany z tym. W naszym przykładzie może być jedna wartość związana z foo, ale klucz, do którego się odnosi, może być pożywieniem, a nie foo.

Myślę, że wyszukiwarki google używają techniki podobnej do tej.

Answer 9

Kluczowym pytaniem jest klucz. (Żadna gra słów nie jest przeznaczona.) Jak wskazali inni, celem jest zminimalizowanie liczby kolizji mieszania. Jeśli możesz uzyskać liczbę konfliktów mieszania do zera, tj. Twoja funkcja mieszająca generuje unikalną wartość dla każdego klucza, który jest do niej przekazywany, otrzymasz doskonały skrót.

Należy zauważyć, że w języku Java funkcja mieszania ma naprawdę dwa kroki: Najpierw klucz jest uruchamiany przez funkcję hashCode dla swojej klasy. Następnie obliczyć wartość indeksu do tabeli mieszania, biorąc tej wartości modulo rozmiar tabeli mieszania.

Myślę, że ludzie dyskutujący o idealnej funkcji skrótu zwykle zapominają o tym drugim kroku. Nawet jeśli napisałeś funkcję hashCode, która wygenerowała unikalną wartość dla każdego przekazanego do niej klucza, nadal możesz uzyskać absolutnie straszny hasz, jeśli ta wartość modulo rozmiar tabeli mieszającej nie jest unikalny. Na przykład powiedzmy, że masz 100 kluczy, a funkcja hashCode zwraca wartości 1, 1001, 2001, 3001, 4001, 5001, ... 99001. Jeśli twój stół hash ma 100 000 miejsc, będzie to doskonały skrót. Każdy klucz ma swój własny slot. Ale jeśli ma 1000 slotów, wszystkie mają hash do tego samego gniazda. Byłby to najgorszy możliwy haszysz.

Należy więc rozważyć skonstruowanie dobrej funkcji skrótu. Weź ekstremalne przypadki. Załóżmy, że kluczem jest data. Wiesz, że wszystkie daty będą w styczniu tego samego roku. Następnie użyj dnia miesiąca, ponieważ wartość mieszania powinna być tak dobra, jak to będzie: wszystko będzie mieszało się z unikalną liczbą całkowitą w małym zakresie. Z drugiej strony, jeśli twoje daty byłyby pierwszymi miesiącami przez wiele lat i wiele miesięcy, przyjęcie dnia miesiąca byłoby okropnym haszyszem, ponieważ każdy rzeczywisty klucz zamieniłby się na "1".

Chodzi mi o to, że jeśli naprawdę chcesz zoptymalizować swój hash, musisz znać charakter swoich danych. Jaki jest rzeczywisty zakres wartości, które otrzymasz?