Ponowne użycie 5 niezależnych funkcji skrótu do sondowania liniowego

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 )$O(1)$

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:

1. Kiedy rośnie zbyt duży stół mieszający?
2. Podczas zmniejszania tabeli mieszania, która nie jest wystarczająco pełna?
3. Podczas odbudowywania tabeli skrótów, w której ustawiono zbyt wiele „usuniętych” bitów?
4. W różnych tabel hash, które mogą zawierać pewne klucze wspólnego?$k$
5. W inny hash tabel, które zawierają żadnych klawiszy ze sobą wspólnego?$k$

$1/2$

• https://issues.cloudera.org/browse/IMPALA-2653
• https://github.com/rust-lang/rust/issues/36481