Czy tablice skrótów naprawdę mogą być O (1)?

Wydaje się, że powszechnie wiadomo, że tablice skrótów mogą osiągnąć O (1), ale to nigdy nie miało dla mnie sensu. Czy ktoś może to wyjaśnić? Oto dwie sytuacje, które przychodzą na myśl:

A. Wartość jest liczbą int mniejszą niż rozmiar tabeli skrótów. Dlatego wartość jest własnym hashem, więc nie ma tabeli skrótów. Ale gdyby tak było, byłoby O (1) i nadal byłoby nieefektywne.

B. Musisz obliczyć skrót wartości. W tej sytuacji kolejność wynosi O (n) dla rozmiaru wyszukiwanych danych. Wyszukiwanie może wyglądać na O (1) po wykonaniu O (n) pracy, ale w moich oczach nadal wychodzi to na O (n).

A jeśli nie masz idealnego haszowania lub dużego stołu do mieszania, prawdopodobnie jest kilka elementów na wiadro. Tak więc w pewnym momencie przekształca się to w małe wyszukiwanie liniowe.

Myślę, że tablice skrótów są niesamowite, ale nie otrzymuję oznaczenia O (1), chyba że ma to być tylko teoria.

Artykuł Wikipedii dotyczący tabel skrótów konsekwentnie odwołuje się do stałego czasu wyszukiwania i całkowicie ignoruje koszt funkcji skrótu. Czy to naprawdę sprawiedliwa miara?

Edycja: podsumowanie tego, czego się nauczyłem:

• Z technicznego punktu widzenia jest to prawda, ponieważ funkcja skrótu nie jest wymagana do wykorzystania wszystkich informacji zawartych w kluczu, a więc może to być stały czas, a wystarczająco duża tabela może sprowadzić kolizje do prawie stałego czasu.

• Jest to prawdą w praktyce, ponieważ z biegiem czasu działa to tak długo, jak długo funkcja skrótu i ​​rozmiar tabeli są wybrane tak, aby zminimalizować kolizje, nawet jeśli często oznacza to niestosowanie funkcji skrótu o stałym czasie.

Masz tutaj dwie zmienne, m i n, gdzie m to długość danych wejściowych, a n to liczba elementów w hashu.

Oświadczenie dotyczące wydajności wyszukiwania O (1) przyjmuje co najmniej dwa założenia:

• Twoje obiekty mogą być równe w czasie O (1).
• Będzie kilka kolizji hash.

Jeśli twoje obiekty mają zmienny rozmiar, a sprawdzenie równości wymaga spojrzenia na wszystkie bity, wydajność osiągnie wartość O (m). Jednak funkcja skrótu nie musi być O (m) - może to być O (1). W przeciwieństwie do kryptograficznego skrótu, funkcja skrótu używana w słowniku nie musi sprawdzać każdego bitu danych wejściowych, aby obliczyć skrót. Implementacje mogą patrzeć tylko na ustaloną liczbę bitów.

Dla dostatecznie wielu elementów liczba elementów stanie się większa niż liczba możliwych haszów, a następnie wystąpią kolizje powodujące wzrost wydajności powyżej O (1), na przykład O (n) dla prostego przeglądania listy połączonej (lub O (n * m), jeśli oba założenia są fałszywe).

W praktyce, chociaż twierdzenie O (1), choć technicznie fałszywe, jest w przybliżeniu prawdziwe w wielu sytuacjach w świecie rzeczywistym, w szczególności w sytuacjach, w których zachodzą powyższe założenia.

Musisz obliczyć hash, więc kolejność wynosi O (n) dla rozmiaru wyszukiwanych danych. Wyszukiwanie może wyglądać na O (1) po wykonaniu O (n) pracy, ale w moich oczach nadal wychodzi to na O (n).

Co? Haszowanie pojedynczego elementu zajmuje stały czas. Dlaczego miałoby to być coś innego? Jeśli wstawiasz nelementy, to tak, musisz obliczyć nhashe, a to zajmuje liniowy czas ... aby wyszukać element, obliczasz pojedynczy hash tego, czego szukasz, a następnie znajdź odpowiedni zasobnik z tym . Nie obliczasz ponownie skrótów wszystkiego, co jest już w tabeli skrótów.

A jeśli nie masz idealnego skrótu lub dużego stołu do mieszania, prawdopodobnie jest kilka elementów na wiadro, więc i tak w pewnym momencie przekształca się to w małe wyszukiwanie liniowe.

Niekoniecznie. Zasobniki niekoniecznie muszą być listami lub tablicami, mogą być dowolnym typem kontenera, takim jak zrównoważony BST. To oznacza O(log n)najgorszy przypadek. Dlatego ważne jest, aby wybrać dobrą funkcję mieszającą, aby uniknąć umieszczania zbyt wielu elementów w jednym wiadrze. Jak zauważył KennyTM, średnio nadal będziesz mieć O(1)czas, nawet jeśli od czasu do czasu będziesz musiał przekopać się przez wiadro.

Kompromisem z tablicami mieszającymi jest oczywiście złożoność przestrzeni. Wymieniasz przestrzeń na czas, co wydaje się być typowym przypadkiem w informatyce.

Wspomniałeś o używaniu łańcuchów jako kluczy w jednym ze swoich komentarzy. Martwisz się, ile czasu zajmuje obliczenie skrótu ciągu, ponieważ składa się on z kilku znaków? Jak ktoś jeszcze raz zauważył, niekoniecznie musisz patrzeć na wszystkie znaki, aby obliczyć hash, chociaż może to dać lepszy hash, jeśli to zrobiłeś. W takim przypadku, jeśli mw twoim kluczu są średnio znaki i użyłeś ich wszystkich do obliczenia skrótu, to przypuszczam, że masz rację, takie wyszukiwanie zajmie O(m). Jeśli m >> nwtedy możesz mieć problem. W takim przypadku prawdopodobnie lepiej by było, gdybyś miał BST. Lub wybierz tańszą funkcję haszowania.

Wartość skrótu ma stały rozmiar - wyszukanie odpowiedniego zasobnika mieszania to operacja o stałym koszcie. Oznacza to, że jest to O (1).

Obliczanie skrótu nie musi być szczególnie kosztowną operacją - nie mówimy tutaj o kryptograficznych funkcjach skrótu. Ale to już niedługo. Samo obliczenie funkcji skrótu nie zależy od liczby n elementów; chociaż może to zależeć od rozmiaru danych w elemencie, nie do tego odnosi się n . Więc obliczenie skrótu nie zależy od n i jest również O (1).

Haszowanie jest O (1) tylko wtedy, gdy w tabeli jest tylko stała liczba kluczy i poczyniono inne założenia. Ale w takich przypadkach ma to przewagę.

Jeśli twój klucz ma reprezentację n-bitową, twoja funkcja skrótu może używać 1, 2, ... n z tych bitów. Myślenie o funkcji skrótu, która używa 1 bitu. Ocena to na pewno O (1). Ale dzielisz tylko przestrzeń kluczy na 2. Więc mapujesz aż 2 ^ (n-1) kluczy do tego samego pojemnika. przy użyciu wyszukiwania BST zlokalizowanie określonego klucza, jeśli jest prawie pełny, zajmuje do n-1 kroków.

Możesz rozszerzyć to, aby zobaczyć, że jeśli twoja funkcja haszująca używa K bitów, twój rozmiar bin wynosi 2 ^ (nk).

więc K-bitowa funkcja skrótu ==> nie więcej niż 2 ^ K efektywnych pojemników ==> do 2 ^ (nK) n-bitowych kluczy na pojemnik ==> (nK) kroki (BST) w celu rozwiązania kolizji. W rzeczywistości większość funkcji skrótu jest znacznie mniej „skuteczna” i potrzebuje / używa więcej niż K bitów do wyprodukowania 2 ^ k pojemników. Więc nawet to jest optymistyczne.

Możesz to zobaczyć w ten sposób - będziesz potrzebować ~ n kroków, aby móc jednoznacznie rozróżnić parę kluczy o długości n bitów w najgorszym przypadku. Naprawdę nie ma sposobu, aby obejść ten limit teorii informacji, niezależnie od tego, czy jest to tabela skrótów, czy nie.

Jednak to NIE jest jak / kiedy używasz tablicy skrótów!

Analiza złożoności zakłada, że ​​dla kluczy n-bitowych w tabeli może znajdować się O (2 ^ n) kluczy (np. 1/4 wszystkich możliwych kluczy). Ale przez większość, jeśli nie przez cały czas, używamy tablicy mieszającej, mamy w niej tylko stałą liczbę kluczy n-bitowych. Jeśli chcesz mieć tylko stałą liczbę kluczy w tabeli, powiedzmy, że C jest Twoją maksymalną liczbą, możesz utworzyć tablicę mieszającą z O (C) bins, która gwarantuje oczekiwaną stałą kolizję (z dobrą funkcją skrótu); oraz funkcję skrótu używającą ~ logC z n bitów klucza. Wtedy każde zapytanie to O (logC) = O (1). W ten sposób ludzie twierdzą, że „dostęp do tablicy skrótów to O (1)” /

Jest tu kilka haczyków - po pierwsze, stwierdzenie, że nie potrzebujesz wszystkich bitów, może być tylko sztuczką rozliczeniową. Po pierwsze, tak naprawdę nie możesz przekazać wartości klucza do funkcji skrótu, ponieważ spowodowałoby to przesunięcie n bitów w pamięci, czyli O (n). Musisz więc zrobić np. Przekazanie referencji. Ale nadal musisz go gdzieś już przechowywać, co było operacją O (n); po prostu nie wystawiasz tego na hasz; ogólne zadanie obliczeniowe nie może tego uniknąć. Po drugie, wykonujesz haszowanie, znajdujesz kosz i znalazłeś więcej niż 1 klucz; Twój koszt zależy od metody rozwiązywania - jeśli korzystasz z porównania (BST lub List), będziesz mieć operację O (n) (klawisz przypomnienia jest n-bitowy); jeśli zrobisz drugi hash, cóż, masz ten sam problem, jeśli drugi hash ma kolizję.

W tym przypadku rozważ alternatywę, np. BST. są klawisze C, więc zbalansowany BST będzie miał głębokość O (logC), więc wyszukiwanie wymaga kroków O (logC). Jednak porównanie w tym przypadku byłoby operacją O (n) ... więc wydaje się, że w tym przypadku lepszym wyborem jest haszowanie.

TL; DR: Tabele skrótu gwarantują O(1)oczekiwany najgorszy czas, jeśli wybierzesz funkcję skrótu równomiernie losowo z uniwersalnej rodziny funkcji skrótu. Oczekiwany najgorszy przypadek nie jest tym samym, co przeciętny przypadek.

Uwaga: formalnie nie udowadniam O(1), że tablice skrótów są , dlatego spójrz na ten film wideo z coursera [ 1 ]. Nie omawiam też amortyzowanych aspektów tabel skrótów. To jest ortogonalne w stosunku do dyskusji o haszowaniu i kolizjach.

Widzę zaskakująco duże zamieszanie wokół tego tematu w innych odpowiedziach i komentarzach i spróbuję poprawić niektóre z nich w tej długiej odpowiedzi.

Rozumowanie o najgorszym przypadku

Istnieją różne rodzaje analizy najgorszego przypadku. Analiza, której dotychczas dokonała większość odpowiedzi, nie jest przypadkiem najgorszym, ale raczej przeciętnym [ 2 ]. Analiza przeciętnego przypadku jest bardziej praktyczna. Może twój algorytm ma jeden zły, najgorszy przypadek, ale w rzeczywistości działa dobrze dla wszystkich innych możliwych danych wejściowych. Najważniejsze jest to, że czas działania zależy od zestawu danych , z którego korzystasz.

Rozważmy następujący pseudokod getmetody tablicy skrótów. Tutaj zakładam, że kolizję rozwiązujemy przez łańcuchowanie, więc każdy wpis w tabeli jest połączoną listą (key,value)par. Zakładamy również, że liczba segmentów mjest stała, ale jest O(n), gdzie njest liczbą elementów w danych wejściowych.

function get(a: Table with m buckets, k: Key being looked up)
  bucket <- compute hash(k) modulo m
  for each (key,value) in a[bucket]
    return value if k == key
  return not_found

Jak wskazywały inne odpowiedzi, jest to przeciętne O(1)i najgorsze O(n). Możemy tutaj zrobić mały szkic dowodu poprzez wyzwanie. Wyzwanie wygląda następująco:

(1) Przekazujesz swój algorytm tablicy mieszającej przeciwnikowi.

(2) Przeciwnik może go przestudiować i przygotować tak długo, jak chce.

(3) W końcu przeciwnik podaje wielkość, nktórą należy wstawić do tabeli.

Pytanie brzmi: jak szybko twoja tablica mieszania jest na wejściu przeciwnika?

Od kroku (1) przeciwnik zna twoją funkcję skrótu; podczas kroku (2) przeciwnik może stworzyć listę nelementów z tym samym hash modulo m, np. przez losowe obliczenie skrótu zbioru elementów; a następnie w (3) mogą dać ci tę listę. Ale spójrzcie, ponieważ wszystkie nelementy są mieszane do tego samego zasobnika, algorytm potrzebuje O(n)czasu, aby przejść przez połączoną listę w tym zasobniku. Bez względu na to, ile razy podejmiemy wyzwanie, przeciwnik zawsze wygrywa i tak zły jest twój algorytm, w najgorszym przypadku O(n).

Dlaczego haszowanie jest O (1)?

Tym, co nas zrzuciło w poprzednim wyzwaniu, było to, że przeciwnik bardzo dobrze znał naszą funkcję skrótu i ​​mógł wykorzystać tę wiedzę do stworzenia jak najgorszego wkładu. A co by było, gdybyśmy zamiast zawsze używać jednej ustalonej funkcji skrótu, mielibyśmy zestaw funkcji skrótu H, z których algorytm może wybierać losowo w czasie wykonywania? Jeśli jesteś ciekawy, Hnazywa się uniwersalną rodziną funkcji skrótu [ 3 ]. W porządku, spróbujmy dodać do tego trochę przypadkowości .

Najpierw załóżmy, że nasza tabela skrótów zawiera również ziarno ri rjest przypisana do liczby losowej w czasie budowy. Przypisujemy go raz, a następnie jest to naprawione dla tej instancji tablicy skrótów. Wróćmy teraz do naszego pseudokodu.

function get(a: Table with m buckets and seed r, k: Key being looked up)
  rHash <- H[r]
  bucket <- compute rHash(k) modulo m
  for each (key,value) in a[bucket]
    return value if k == key
  return not_found

Jeśli spróbujemy jeszcze raz: od kroku (1) przeciwnik może poznać wszystkie funkcje skrótu, w których mamy H, ale teraz zależy od konkretnej funkcji skrótu, której używamy r. Wartość rjest prywatna dla naszej struktury, przeciwnik nie może jej sprawdzić w czasie wykonywania ani przewidzieć z wyprzedzeniem, więc nie może ułożyć listy, która zawsze jest dla nas szkodliwa. Załóżmy, że w etapie (2) przeciwnik wybiera jedną funkcję hashw Hlosowo, potem rzemiosła listę nkolizji wynikających hash modulo mi wysyła je do kroku (3), przejście palce, że przy starcie H[r]będzie taki sam hashwybrali.

To poważny zakład dla przeciwnika, lista, którą stworzył, koliduje z nią hash, ale będzie po prostu losowym wpisem w dowolnej innej funkcji skrótu H. Jeśli wygra ten zakład, nasz czas pracy będzie najgorszy, tak O(n)jak poprzednio, ale jeśli przegra, to cóż, otrzymujemy losowe dane wejściowe, które zajmują średni O(1)czas. I rzeczywiście, w większości przypadków przeciwnik przegrywa, wygrywa tylko raz w każdym |H|wyzwaniu, a my możemy zrobić |H|bardzo duże.

Porównaj ten wynik z poprzednim algorytmem, w którym przeciwnik zawsze wygrywał wyzwanie. Trochę tu macham ręką, ale ponieważ w większości przypadków przeciwnik zawiedzie, a dotyczy to wszystkich możliwych strategii, jakie przeciwnik może wypróbować, wynika z tego, że chociaż jest O(n)to najgorszy przypadek, w rzeczywistości jest to oczekiwany najgorszyO(1) .

Ponownie, nie jest to formalny dowód. Gwarancją, jaką otrzymujemy z tej oczekiwanej analizy najgorszego przypadku, jest to, że nasz czas wykonywania jest teraz niezależny od jakichkolwiek konkretnych danych wejściowych . Jest to prawdziwie przypadkowa gwarancja, w przeciwieństwie do przeciętnej analizy przypadku, w której wykazaliśmy, że zmotywowany przeciwnik może łatwo stworzyć złe dane wejściowe.

Istnieją dwa ustawienia, w których można uzyskać O (1) najgorszych czasów.

1. Jeśli twoja konfiguracja jest statyczna, haszowanie FKS zapewni ci najgorsze gwarancje O (1) . Ale jak wskazałeś, twoje ustawienie nie jest statyczne.
2. Jeśli używasz haszowania Cuckoo, zapytania i usunięcia są w najgorszym przypadku O (1) , ale wstawienie jest oczekiwane tylko O (1) . Haszowanie z kukułką działa całkiem dobrze, jeśli masz górną granicę całkowitej liczby wstawek i ustawisz rozmiar stołu na około 25% większy.

Skopiowano stąd

Wydaje się w oparciu o dyskusję tutaj, że jeśli X jest pułapem (liczba elementów w tabeli / liczba pojemników), to lepszą odpowiedzią jest O (log (X)) przy założeniu wydajnej implementacji wyszukiwania binariów.

A. Wartość jest liczbą int mniejszą niż rozmiar tabeli skrótów. Dlatego wartość jest własnym hashem, więc nie ma tabeli skrótów. Ale gdyby tak było, byłoby O (1) i nadal byłoby nieefektywne.

Jest to przypadek, w którym można by w trywialny sposób odwzorować klucze na różne segmenty, więc tablica wydaje się lepszym wyborem struktury danych niż tablica mieszająca. Jednak nieefektywność nie rośnie wraz z rozmiarem stołu.

(Możesz nadal używać tablicy mieszania, ponieważ nie ufasz, że ints pozostaną mniejsze niż rozmiar tabeli w miarę rozwoju programu, chcesz, aby kod był potencjalnie wielokrotnego użytku, gdy ta relacja nie jest zachowana, lub po prostu nie chcą, aby osoby czytające / utrzymujące kod musiały marnować wysiłek umysłowy na zrozumienie i utrzymanie związku).

B. Musisz obliczyć skrót wartości. W tej sytuacji kolejność wynosi O (n) dla rozmiaru wyszukiwanych danych. Wyszukiwanie może wyglądać na O (1) po wykonaniu O (n) pracy, ale w moich oczach nadal wychodzi to na O (n).

Musimy rozróżnić między rozmiarem klucza (np. W bajtach), a wielkością liczby kluczy przechowywanych w tablicy haszującej. Twierdzenia, że ​​tablice skrótów zapewniają operacje O (1), oznaczają, że operacje (wstawianie / kasowanie / znajdowanie) nie mają tendencji do dalszego spowalniania, ponieważ liczba kluczy rośnie z setek do tysięcy, milionów do miliardów (przynajmniej nie jeśli wszystkie dane jest dostępny / aktualizowany w równie szybkiej pamięci, czy to w pamięci RAM, czy na dysku - efekty pamięci podręcznej mogą pojawić się w grze, ale nawet koszt najgorszego braku pamięci podręcznej jest stałą wielokrotnością trafienia w najlepszym przypadku).

Pomyśl o książce telefonicznej: możesz mieć w niej nazwiska, które są dość długie, ale bez względu na to, czy książka ma 100, czy 10 milionów, średnia długość nazwiska będzie dość spójna, a najgorszy przypadek w historii ...

Rekord Guinnessa dla najdłuższego imienia używanego przez kogokolwiek kiedykolwiek ustanowił Adolph Blaine Charles David Earl Frederick Gerald Hubert Irvin John Kenneth Lloyd Martin Nero Oliver Paul Quincy Randolph Sherman Thomas Uncas Victor William Xerxes Yancy Wolfeschlegelsteinhausenbergerdorff, Senior

... wcmówi mi, że to 215 znaków - to nie jest twarda górna granica długości klucza, ale nie musimy się martwić, że będzie ich znacznie więcej.

Dotyczy to większości rzeczywistych tabel skrótów: średnia długość klucza nie rośnie wraz z liczbą używanych kluczy. Są wyjątki, na przykład procedura tworzenia klucza może zwracać ciągi zawierające zwiększające się liczby całkowite, ale nawet wtedy za każdym razem, gdy zwiększasz liczbę kluczy o rząd wielkości, zwiększasz długość klucza tylko o 1 znak: nie jest to istotne.

Możliwe jest również utworzenie skrótu z ilości kluczowych danych o stałym rozmiarze. Na przykład program Visual C ++ firmy Microsoft jest dostarczany z implementacją biblioteki standardowej, std::hash<std::string>która tworzy skrót zawierający tylko dziesięć bajtów równomiernie rozmieszczonych wzdłuż ciągu, więc jeśli ciągi różnią się tylko w innych indeksach, pojawiają się kolizje (a zatem w praktyce zachowania inne niż O (1) po stronie wyszukiwania po kolizji), ale czas na utworzenie skrótu ma twardą górną granicę.

A jeśli nie masz idealnego haszowania lub dużego stołu do mieszania, prawdopodobnie jest kilka elementów na wiadro. Tak więc w pewnym momencie przekształca się to w małe wyszukiwanie liniowe.

Generalnie prawda, ale niesamowitą rzeczą w tablicach skrótów jest to, że liczba kluczy odwiedzanych podczas tych „małych liniowych wyszukiwań” jest - dla oddzielnego łańcuchowego podejścia do kolizji - funkcją współczynnika obciążenia tablicy skrótów (stosunek kluczy do zasobników).

Na przykład przy współczynniku obciążenia 1,0 długość tych liniowych wyszukiwań wynosi średnio ~ 1,58, niezależnie od liczby kluczy (zobacz moją odpowiedź tutaj ). Dla haszowania zamkniętego jest to nieco bardziej skomplikowane, ale niewiele gorsze, gdy współczynnik obciążenia nie jest zbyt wysoki.

Z technicznego punktu widzenia jest to prawda, ponieważ funkcja skrótu nie jest wymagana do wykorzystania wszystkich informacji zawartych w kluczu, a więc może to być stały czas, a wystarczająco duża tabela może sprowadzić kolizje do prawie stałego czasu.

Ten rodzaj mija się z celem. Każdy rodzaj asocjacyjnej struktury danych ostatecznie musi czasami wykonywać operacje na każdej części klucza (nierówność może czasami być określona tylko na podstawie części klucza, ale równość ogólnie wymaga rozważenia każdego bitu). Jako minimum może raz zaszyfrować klucz i zapisać wartość skrótu, a jeśli używa wystarczająco silnej funkcji skrótu - np. 64-bitowej MD5 - może praktycznie zignorować nawet możliwość zaszyfrowania dwóch kluczy do tej samej wartości (firma Pracowałem dla, zrobiłem dokładnie to dla rozproszonej bazy danych: czas generowania skrótu był nadal nieistotny w porównaniu do transmisji w całej sieci WAN). Nie ma więc sensu obsesja na punkcie kosztu przetwarzania klucza: jest to nieodłączne przy przechowywaniu kluczy niezależnie od struktury danych, i jak wspomniano powyżej - nie.

Jeśli chodzi o wystarczająco duże tabele skrótów, które eliminują kolizje, to też mija się z celem. W przypadku oddzielnego łączenia łańcuchowego nadal masz stałą średnią długość łańcucha kolizji przy dowolnym współczynniku obciążenia - jest ona większa, gdy współczynnik obciążenia jest wyższy, a zależność ta jest nieliniowa. Użytkownik SO, Hans, komentuje moją odpowiedź, również pod linkiem powyżej :

Średnia długość łyżki uwarunkowana niepustymi łyżkami jest lepszą miarą wydajności. Jest to a / (1-e ^ {- a}) [gdzie a jest współczynnikiem obciążenia, e wynosi 2,71828 ...]

Tak więc sam współczynnik obciążenia określa średnią liczbę kolidujących kluczy, które musisz przeszukać podczas operacji wstawiania / usuwania / znajdowania. W przypadku oddzielnego łączenia łańcuchowego nie tylko zbliża się do stałej, gdy współczynnik obciążenia jest niski - jest zawsze stały. W przypadku adresowania otwartego, chociaż roszczenie ma pewną zasadność: niektóre kolidujące elementy są przekierowywane do alternatywnych zasobników i mogą następnie zakłócać operacje na innych klawiszach, więc przy wyższych współczynnikach obciążenia (zwłaszcza> .8 lub .9) długość łańcucha kolizji pogarsza się dramatycznie.

Jest to prawdą w praktyce, ponieważ z biegiem czasu działa to tak długo, jak długo funkcja skrótu i ​​rozmiar tabeli są wybrane tak, aby zminimalizować kolizje, nawet jeśli często oznacza to niestosowanie funkcji skrótu o stałym czasie.

Cóż, rozmiar tabeli powinien skutkować rozsądnym współczynnikiem obciążenia, biorąc pod uwagę wybór bliskiego haszowania lub oddzielnego łączenia, ale także jeśli funkcja skrótu jest nieco słaba, a klucze nie są zbyt losowe, posiadanie pierwszej liczby segmentów często pomaga zmniejszyć również kolizje ( hash-value % table-sizenastępnie zawija się w taki sposób, że zmienia się tylko do jednego lub dwóch bitów wyższego rzędu w wartości skrótu, które nadal są rozwiązywane w celu pseudolosowego rozprzestrzeniania się pojemników w różnych częściach tablicy skrótów).