Czy można zaimplementować dobrze rozłożoną tabelę skrótów bez użycia operatora%?

11

Chcę zaimplementować szybką, dobrze rozproszoną tabelę skrótów w języku C #. Mam problem z wybraniem funkcji ograniczenia skrótu, która pobiera dowolny kod skrótu i ​​„ogranicza” go, aby można go było użyć do indeksowania segmentów. Do tej pory widzę dwie opcje:

  • Z jednej strony możesz mieć pewność, że twoje segmenty zawsze mają pierwszą liczbę elementów, a aby ograniczyć hash, po prostu moduluj je według liczby segmentów. Tak właśnie działa Słownik .NET . Problem z tym podejściem polega na tym, że użycie% jest bardzo wolne w porównaniu do innych operacji; jeśli spojrzeć na stołach instrukcji Agner przeciwmgłowe , idiv(który jest kod zespół, który zostanie wygenerowany dla%) ma opóźnienia instrukcji o ~ 25 cykli dla nowszych procesorów Intel. Porównaj to do około 3 do mullub od 1 do OPS bitowe jak and, orlub xor.

  • Z drugiej strony, możesz zawsze mieć liczbę segmentów o wartości 2. Wciąż będziesz musiał obliczyć moduł skrótu, aby nie próbować indeksować poza tablicą, ale tym razem będzie on tańszy . Ponieważ dla mocy 2 % Njest po prostu & (N - 1)ograniczenie jest ograniczone do operacji maskowania, która zajmuje tylko 1-2 cykle. Odbywa się to przez Google Sparsehash . Wadą tego jest to, że liczymy na to, że użytkownicy zapewnią porządny skrót; maskowanie skrótu zasadniczo odcina część skrótu, więc nie uwzględniamy już wszystkich jego fragmentów. Jeśli skrót użytkownika jest nierównomiernie rozłożony, na przykład wypełniane są tylko wyższe bity lub niższe bity są niezmiennie takie same, wówczas podejście to ma znacznie większą częstotliwość kolizji.

Szukam algorytmu, którego mogę użyć, który ma to, co najlepsze z obu światów: bierze pod uwagę wszystkie części skrótu, a także jest szybszy niż użycie%. Nie musi to być moduł, tylko coś, co gwarantuje, że będzie w zakresie 0..N-1(gdzie N jest długością segmentów) i ma równomierny rozkład dla wszystkich gniazd. Czy taki algorytm istnieje?

Dzięki za pomoc.

James Ko
źródło
1
Sprawdź efekt lawiny , a także wyjaśnienie w murmurhash3 (smhasher) . Jednak podstawowa kwestia twojego pytania nie została rozwiązana poprzez przyjęcie lepszej funkcji skrótu. Zamiast tego chodzi o pytanie, dlaczego użytkownicy nie przyjmują tej samej lepszej funkcji skrótu, i prośbę o środki zaradcze (tak, jakby użytkownicy byli złośliwie leniwi).
rwong
Aby uzyskać szybki modulo (2^N +/- 1), patrz stackoverflow.com/questions/763137/…
rwong
@rwong Przykro mi, ale nie jestem pewien, co twój komentarz ma wspólnego z moim postem. Nie kontroluję skrótu udostępnianego przez użytkownika, więc nie szukam lepszej funkcji skrótu. Nie rozumiem również, co rozumiesz przez „złośliwie leniwych użytkowników”.
James Ko
4
Jeśli funkcja skrótu jest słaba, implementator tabeli skrótów nie może nic zrobić, aby „naprawić” słabą dystrybucję. Modulo liczba pierwsza nie naprawia złego skrótu. Rozważmy funkcję skrótu, która daje jako wynik wielokrotności liczby pierwszej. Widziałem taki problem w prawdziwym kodzie produkcyjnym.
Frank Hileman,

Odpowiedzi:

9

Nowoczesne implementacje tabeli skrótów nie używają funkcji modulo. Często używają mocy dwóch rozmiarów stołów i odcinają niepotrzebne bity. Idealna funkcja skrótu pozwoliłaby na to. Zastosowanie modulo w połączeniu z rozmiarami tablic liczb pierwszych pojawiło się w czasach, gdy funkcje haszujące były na ogół słabe, ponieważ często są one rozwijane .net. Polecam przeczytać o SipHash , nowoczesnej funkcji mieszającej, a następnie o innych współczesnych funkcjach, takich jak xxHash .

Powinienem wyjaśnić, dlaczego funkcje skrótu .net są często słabe. W .net programiści są często zmuszeni do implementacji funkcji skrótu, zastępując GetHashcode. Ale .net nie zapewnia narzędzi potrzebnych do zapewnienia wysokiej jakości funkcji tworzonych przez programistę, a mianowicie:

  • enkapsulacja stanu skrótu w strukturze lub klasie
  • funkcje dodawania skrótu, które dodają nowe dane do stanu skrótu (na przykład dodaj tablicę bajtów lub podwójną)
  • funkcja „finalizacji” skrótu, aby wytworzyć lawinę
  • enkapsulacja wyniku skrótu - w .net dostajesz jeden wybór, 32-bitową liczbę całkowitą ze znakiem.

Aby uzyskać więcej informacji na temat używania wyniku funkcji skrótu jako indeksu tabeli skrótów, zobacz definicje uniwersalnych form mieszania w tym dokumencie: Szybsze 64-bitowe uniwersalne mieszanie przy użyciu mnożenia bez przenoszenia

Frank Hileman
źródło
3

Aby użyć ORAZ zachowując wszystkie bity, użyj również XOR.

Na przykład temp = (hash & 0xFFFF) ^ ( hash >> 16); index = (temp & 0xFF) ^ (temp >> 8);.

W tym przykładzie nie ma modulo i wszystkie 32 bity hashefektu są 8-bitowe index. Jednak to, czy jest szybsze niż DIV, zależy od zbyt wielu czynników, aw niektórych przypadkach może być wolniejsze niż DIV (np. Duży skrót i mały indeks).

Brendan
źródło
To zawsze będzie szybsze niż DIV / IDIV, jednak nie sądzę, że odpowiada na moje pytanie - indexbędzie w zasięgu [0..255]. Potrzebuję czegoś w zakresie [0..n-1], w którym njest liczba wiader.
James Ko
@JamesKo Ale jeśli wdrażasz słownik, kontrolujesz również liczbę segmentów (do pewnego stopnia). Zamiast liczb pierwszych można wybrać potęgi dwóch. (Nie wiem, czy to byłoby dobrym pomysłem.)
svick
@svick Dla mocy 2 moglibyśmy wykonać prostą operację maski. Jak wspomniano w pytaniu, szukam taniego sposobu na zrobienie tego z liczbami pierwszymi, aby nawet źle rozłożone hasze były dostępne.
James Ko
1

Możesz skorzystać z faktu, że wiele liczb pierwszych ma modułową multiplikatywną odwrotność. Zobacz ten artykuł . Spełniliście jedno z ograniczeń, ustawiając indeks łyżki na pierwszą i moduł 2 ^ n, które są z natury względnie pierwsze.

W artykule opisano algorytm znajdowania liczby takiej, że pomnożenie przez tę liczbę i zignorowanie przepełnienia da taki sam wynik, jak gdybyś podzielił się przez rozmiar indeksu segmentu.

BobDalgleish
źródło