-
The basic idea of cuckoo hashing is to resolve collisions by using two hash functions instead of only one.
Основная идея кукушкиного хеширования заключается в разрешении коллизий путём использования двух хеш-функций вместо одной.
-
Moreover, the same theory also proves that the expected size of a connected component of the cuckoo graph is small, ensuring that each insertion takes constant expected time.
Более того, та же теория доказывает, что ожидаемый размер компонент связности кукушкиного графа мал, что обеспечивает постоянное ожидаемое время вставки.
-
Generalizations of cuckoo hashing that use more than two alternative hash functions can be expected to utilize a larger part of the capacity of the hash table efficiently while sacrificing some lookup and insertion speed.
От обобщения кукушкиного хеширования, использующего более двух хеш-функций, можно ожидать лучшего использования хеш-таблицы, жертвуя некоторой скоростью выборки и вставки.
-
The analysis of cuckoo hashing with a stash extends to practical hash functions, not just to the random hash function model commonly used in theoretical analysis of hashing.
Анализ кукушкиного хеширования с запасом распространился и на практические хеш-функции, не только случайные модели хеш-функций, используемые в теоретическом анализе хеширования.
-
With high probability, for a random graph in which the ratio of the number of edges to the number of vertices is bounded below 1/2, the graph is a pseudoforest and the cuckoo hashing algorithm succeeds in placing all keys.
С высокой степенью вероятности для случайного графа, в котором отношение числа рёбер к числу вершин ограничено сверху 1/2, граф является псевдолесом и алгоритм кукушкиного хеширования располагает успешно все ключи.
