Zgodnie z this question słownik .Net zmienia wielkość przydzielonego miejsca na liczby pierwsze, które są co najmniej dwa razy większe od bieżącego. Dlaczego ważne jest używanie liczb pierwszych, a nie tylko dwukrotność obecnego rozmiaru? (Próbowałem użyć moich mocy google-fu, aby znaleźć odpowiedź, ale bez skutku)Dlaczego słowniki .Net zmieniają się na liczby pierwsze?
Jest to szczegół implementacji algorytmu związany z choosing a good hashing function i zapewnia jednolity rozkład. Niejednolita dystrybucja zwiększa liczbę kolizji i koszty ich rozwiązania.
Wybór liczby początkowej nie ** nie ** zapewnia jednolitą dystrybucję, nie trzeba upraszczać. Z 'hashsize = prime_number', masz absolutnie taką samą szansę na zderzenie, jak w' hashsize = 2^k' lub jakiejkolwiek innej. Po prostu niektóre rozmiary krzyży sprawiają, że kolizje wyglądają na "nieprzewidywalne", "losowe" lub "jednolicie rozproszone". Z drugiej strony posiadanie 'hashsize = 2^k' oznaczałoby, że każda funkcja mieszająca oparta na Xor będzie ssała. –
Z powodu matematyki liczb pierwszych. Nie można ich uwzględnić w różnych mniejszych liczbach. Kiedy podzielisz liczbę haszującą z przechowywanych przedmiotów, otrzymasz równą dystrybucję. Jeśli nie masz liczby pierwszej, w zależności od obiektów, rozkład może nie być równy.
Łyżka, w której umieszczony jest element, jest określana przez (hash & 0x7FFFFFF) % capacity. To musi być równomiernie rozłożone. Z tego wynika, że jeśli wiele wpisów, które są wielokrotnością pewnej podstawy (hash1 = x1 * base, hash2 = x2 * base, ...) gdzie base i capacity nie są koprime (największy wspólny dzielnik> 1) niektóre gniazda są nadużywane, a niektóre nigdy nie są używane używany. Ponieważ liczby pierwsze są coprime do dowolnej liczby oprócz siebie, mają stosunkowo dobre szanse na osiągnięcie dobrej dystrybucji.
Jedną szczególnie miłą właściwością jest to, że dla capacity > 30 udział każdego bitu w hashcode jest inny. Więc jeśli zmiana wartości skrótu jest skoncentrowana tylko w kilku bitach, nadal będzie to prowadzić do dobrej dystrybucji. To wyjaśnia, dlaczego moce, które są potęgami dwóch, są złe: maskują wysokie bity. Zestaw liczb, w których tylko wysokie bity są różne, nie jest mało prawdopodobny.
Osobiście uważam, że źle wybierają tę funkcję. Zawiera on kosztowną operację modulo i jeśli wpisy są wielokrotnościami pojemności pierwotnej, jej wydajność ulega rozkładowi. Ale wydaje się być wystarczająco dobre dla większości aplikacji.
jako jedno z pomysłów na drugie pytanie, czy ktokolwiek zna zrównoważoną strukturę danych, która zmienia rozmiar na pierwotne? Może powinienem wysłać kolejne pytanie –
jaka jest struktura danych drzewa za słownikiem .Net? –
Zadałem pytanie tutaj http://stackoverflow.com/questions/4639122/balanced-tree-like-data-structure-that-resizes-to-prime-sizes –