394
правки
Изменения
→Время работы алгоритма
|id = Cuckoo_hashing add
|statement = Добавление в среднем происходит за <tex>O(1)</tex>.
|proof = Один из способов доказательства третьего данного утверждения использует теорию случайных графов. Это делается через неориентированный "кукушкин граф", где каждой ячейке хеш-таблицы соответствует ровно одна вершина, а каждому добавленному элементу — ребро с концами в вершинах, соответствующих ячейкам, в которые указывают хеш-функции элемента. При этом элемент будет добавлен без перехеширования тогда и только тогда, когда после добавления нового ребра граф будет оставаться псевдолесом, то есть каждая его компонента связности будет содержать не более одного цикла.
}}
Таким образом хеширование кукушки является одним из самых быстрых способов хеширования.
