W tablicach skrótów, które rozwiązują kolizje za pomocą sondowania liniowego, w celu zapewnienia oczekiwanej wydajności , zarówno konieczne, jak i wystarczające jest, aby funkcja skrótu pochodziła z 5-niezależnej rodziny. (Wystarczalność: „Sondowanie liniowe ze stałą niezależnością”, Pagh i in. , Konieczność: „O k-niezależności wymaganej przez sondowanie liniowe i niezależność minutową”, Pătraşcu i Thorup )
Rozumiem, że najszybsze znane 5-niezależne rodziny korzystają z tabel. Wybranie funkcji z takiej rodziny może być kosztowne, dlatego chciałbym zminimalizować liczbę takich działań, jednocześnie zapobiegając atakom złożoności algorytmicznej, jak opisano w Crosby i Wallach's „Odmowa usługi za pośrednictwem ataków złożoności algorytmicznej” . Mniej martwię się atakami w czasie (tj. Przeciwnikami z stoperami). Jakie są konsekwencje ponownego użycia tej samej funkcji:
- Kiedy rośnie zbyt duży stół mieszający?
- Podczas zmniejszania tabeli mieszania, która nie jest wystarczająco pełna?
- Podczas odbudowywania tabeli skrótów, w której ustawiono zbyt wiele „usuniętych” bitów?
- W różnych tabel hash, które mogą zawierać pewne klucze wspólnego?
- W inny hash tabel, które zawierają żadnych klawiszy ze sobą wspólnego?
Odpowiedzi:
źródło