Jakie są "nowe funkcje skrótu" w haszu z kukułką?

Question

Czytam o kukułki mieszaja z Pagh i Rodle i nie mogę zrozumieć sens tego ustępu.

może się zdarzyć, że proces ten pętli, jak pokazano na rysunku 1 (b). Dlatego liczba iteracji jest ograniczona przez wartość "MaxLoop" do być określone w rozdziale 2.3. Jeśli zostanie osiągnięta ta liczba iteracji, możemy powtarzać kluczy w tabelach z wykorzystaniem nowych funkcji skrótu, a następnie spróbuj ponownie aby pomieścić klucz nestless. Nie ma potrzeby, aby przeznaczyć nowe tabele dla uporczywie powtarzanym: Możemy po prostu uruchomić poprzez tabelach usunąć i wykonać zwykłe procedury wstawiania na wszystkich kluczy okaże się nie być w ich zamierzonym miejscu w tabeli.

Co to znaczy przy użyciu nowych funkcji skrótu?
W algorytmie wstawiania tabela jest zmieniana. Czy powinniśmy używać "puli" funkcji skrótu do użycia? Jak tworzymy tę pulę?

Answer 1

Tak, oni oczekując nowych funkcji skrótu, tak jak mówią. Na szczęście nie wymagają one stosu nowych algorytmów, tylko nieznacznie innego zachowania hashującego na aktualnym zestawie danych.

Spójrz na sekcji 2.1 papieru, a następnie Dodatek A. Omawia budowę losowej universal hash functions.

Prosty, mam nadzieję, że przykład ilustracyjny, to przypuszczam, że masz jakąś normalną funkcję hash chcesz, który działa na bloki bajtów. Nazwiemy to H(x). Chcesz go użyć do stworzenia rodziny nowych, nieco różnych funkcji skrótu H_n(x). Cóż, jeśli H(x) jest dobre, a twoje wymagania są słabe, możesz po prostu zdefiniować H_n(x) = H(concat(n,x)). Nie masz niezłych silnych gwarancji dotyczących zachowań H_n(x), ale można się spodziewać, że większość z nich będzie inna.