Nie do końca rozumiem, jak działa uniwersalny hasz. Na przykład, kiedy wstawiam element do mojego tablicy mieszającej, muszę wybrać funkcję losową z mojej uniwersalnej rodziny funkcji skrótu. Teraz chcę odzyskać przedmiot. W jaki sposób mój tablica asocjacyjna będzie znała funkcję, której ma używać do obliczania wartości mieszania?Powszechne mieszanie
Ponieważ będziesz używać tej samej funkcji mieszania dla wszystkich elementów w tabeli.
Masz na myśli, że (losowy) wybór funkcji mieszającej jest dokonywany w czasie budowy, a nie w każdej operacji wstawiania? –
@iuliux: Prawidłowo. Sól, jeśli jest używana, może się różnić (i będzie przechowywana wraz z wkładką), ale algorytm będzie taki sam. –
Nadal nie rozumiem, jak odzyskać numer, który zahaczyliśmy za pomocą losowej funkcji skrótu. – user65165
Która funkcja hash jest używana jest losowa tylko w tym sensie, że nie jest przewidywalna przez przeciwnika, ale wybór jest funkcją klucza. Jest miło napisać pod adresem http://www.cs.ucsb.edu/~suri/cs130a/Hashing.txt Metoda macierzowa jest łatwiejsza do zrozumienia niż inne metody ...
Dowolny nowszy link? Jest teraz zepsuty. –
Jakiego języka używasz? – Gerben
@ Gerben: Brak. To jest pytanie koncepcyjne. – ryyst