Обсуждение:Хеширование кукушки

☑ Написать что делают функции add delete и exists

☑ O(1) - в TeX

☑ Оформить доказательство того, что добавление работает за O(1) как утверждение

☑ "Вытаскиваем" - плохое слово для научного текста

☑ Объяснить, какое зацикливание может появиться в функции add.

☑ "Если в ходе перемещений элементов в таблице на очередном шаге мы опять хотим переместить элемент [math]x[/math] в ячейку [math]h_1(x)[/math] то значит произошло зацикливание." - элемент [math]x[/math] уже лежит в [math]h_1(x)[/math], тут, вроде, нужно сказать про элемент [math]y[/math] такой, что [math]h_1(y) = h_1(x)[/math]. --Андрей Рыбак 17:48, 23 апреля 2012 (GST)

Вроде правильно, потому что [math]x[/math] мог переместиться в [math]h_2(x)[/math], и вот если он вернулся в [math]h_1(x)[/math] то зациклились.

Используйте подпись --~~~~ и отступы. По делу: новый элемент [math]x[/math], который мы добавляем в таблицу, в любом случае в самом начале работы попадает в [math]h_1(x)[/math] или [math]h_2(x)[/math]. Если в начале работы обе ячейки заняты, мы достаем из одной ячейки (обозначим её [math]h_i(x)[/math]) элемент [math]y[/math] (заметим, что [math]h_i(y) = h_i(x)[/math]), в освободившуюся кладем [math]x[/math], а [math]y[/math] кладем в [math]h_j(y),~ (i \ne j)[/math] и так далее. Зацикливание, это когда для очередного [math]y[/math]: [math]h_i(y) = h_i(x)[/math]. --Андрей Рыбак 21:14, 24 апреля 2012 (GST)

Когда для очередного [math]y[/math]: [math]h_i(y) = h_i(x)[/math] у нас [math]x[/math] пойдет в [math]h_j(x)(j!=i)[/math] и вот если потом вернулись то зациклились. --Роскошный Яков 22:01, 24 апреля 2012 (GST)

Теперь понял. ☑ Нужно подробней расписать --Андрей Рыбак 22:24, 24 апреля 2012 (GST)

☑ Не рассмотрен случай заполненной хеш-таблицы.

расширяемся в 2 раза?

Нужно про это написать. Коэффициент увеличения может быть не 2, лучше просто написать "увеличим размер хеш-таблицы". --Андрей Рыбак 17:48, 23 апреля 2012 (GST)

☑ Не понятно, как выбирать новые хеш-функции.

с помощью универсального хэширования (из универсального семейства хэш функций)

Так и напиши это. --Андрей Рыбак 17:48, 23 апреля 2012 (GST)

☑ Оформить раздел "источники" (Требования - Викификация - пункт 9)

Добавь название для второй ссылки

☑ Добавить категории (Требования - Викификация - пункт 8)

---

☐ Добавить вики-ссылки

☐ "Проверяем, если хэш-таблица заполнена увеличиваем её размер." - эта строчка зря повторяется