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

14

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
jbapple
źródło
Jeśli jest to pytanie o praktykę ... prawdopodobnym pragmatycznym podejściem jest zastosowanie kryptograficznej funkcji skrótu, z losowym sekretem zawartym w danych wejściowych, zamiast korzystania ze schematu opartego na tabulacji. Następnie jest mniejsza presja na ponowne użycie tej samej funkcji skrótu; możesz użyć innego sekretu dla każdej tabeli haszującej (i zmienić sekret i powtórzyć wszystko, gdy zmniejszasz / powiększasz / przebudowujesz tabelę haszującą).
DW
Myślę, że nawet szybkie kryptograficzne funkcje skrótu przy krótkich wejściach, takie jak SipHash-2-4, są dość powolne w porównaniu nawet z 5 niezależnymi rodzinami wykorzystującymi wielomiany.
jbapple,

Odpowiedzi: