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

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.

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

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).

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.