.NET Początkowa moc obliczeniowa ConcurrentDictionary dla arbitralnej liczby pierwszej zamiast oczekiwanej w przykładowej dokumentacji MSDN. Czemu?

Question

właśnie patrząc na MSDN documentation for ConcurrentDictionary i widziałem to w „przykład” Kod:

// We know how many items we want to insert into the ConcurrentDictionary. 
// So set the initial capacity to some prime number above that, to ensure that 
// the ConcurrentDictionary does not need to be resized while initializing it. 
int NUMITEMS = 64; 
int initialCapacity = 101; 

odsyłającym słownika na przykład MSDN jest inicjowany w następujący sposób:

ConcurrentDictionary<int, int> cd = new ConcurrentDictionary<int, int>(Environment.ProcessorCount * 2, initialCapacity); 
for (int i = 0; i < NUMITEMS; i++) cd[i] = i * i; 

W przykład, słownik nigdy nie będzie zawierał więcej niż 64 elementy. Dlaczego nie ustawić początkowej pojemności na 64, zamiast na pozornie arbitralną liczbę pierwszą większą niż 64? Komentarz mówi, że ma to zapewnić, że słownik nie będzie wymagał zmiany rozmiaru podczas inicjalizacji, ale dlaczego należy zmienić rozmiar podobnego słownika o wartości initialCapacity = 64? Dlaczego wybrano tę liczbę pierwszą?

Answer 1

Słownik lub tabela mieszania polega na haszowaniu klucza, aby uzyskać mniejszy indeks do znalezienia odpowiedniego sklepu (tablicy). Tak więc wybór funkcji hash jest bardzo ważny. Typowym wyborem jest uzyskanie kodu skrótu klucza (tak, aby uzyskać dobrą dystrybucję losową), a następnie podzielenie kodu przez liczbę pierwszą i użycie przypomnienia w celu zindeksowania do ustalonej liczby segmentów. Pozwala to na przekształcenie dowolnie dużych kodów skrótu w ograniczony zestaw małych liczb, dla których możemy zdefiniować tablicę, na którą będziemy patrzeć. Dlatego ważne jest, aby rozmiar tablicy w liczbie pierwszej, a następnie najlepszy wybór dla rozmiaru stał się liczbą pierwszą, która jest większa niż wymagana pojemność. I to jest właśnie implementacja słownika.

W zasadzie każdy implementacja słownika Modulo N (n będącego liczbą pierwszą) będzie potrzebował swojej pojemności, aby być liczbą pierwszą. Więc jeśli powiesz, wymagana pojemność to X, wówczas te implementacje zazwyczaj wybiorą następny większy numer startera niż wymagana pojemność.