Обсуждение:Хеширование кукушки — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 5: Строка 5:
 
{{tick | ticked = 1}} Объяснить, какое зацикливание может появиться в функции add.
 
{{tick | ticked = 1}} Объяснить, какое зацикливание может появиться в функции add.
 
: {{tick}} "Если в ходе перемещений элементов в таблице на очередном шаге мы опять хотим переместить элемент <tex>x</tex> в ячейку <tex>h_1(x)</tex> то значит произошло зацикливание." - элемент <tex>x</tex> уже лежит в <tex>h_1(x)</tex>, тут, вроде, нужно сказать про элемент <tex>y</tex> такой, что <tex>h_1(y) = h_1(x)</tex>. --[[Участник:Rybak|Андрей Рыбак]] 17:48, 23 апреля 2012 (GST)
 
: {{tick}} "Если в ходе перемещений элементов в таблице на очередном шаге мы опять хотим переместить элемент <tex>x</tex> в ячейку <tex>h_1(x)</tex> то значит произошло зацикливание." - элемент <tex>x</tex> уже лежит в <tex>h_1(x)</tex>, тут, вроде, нужно сказать про элемент <tex>y</tex> такой, что <tex>h_1(y) = h_1(x)</tex>. --[[Участник:Rybak|Андрей Рыбак]] 17:48, 23 апреля 2012 (GST)
 
+
Вроде правильно, потому что <tex>x</tex> мог переместиться в <tex>h_2(x)</tex>, и вот если он вернулся в <tex>h_1(x)</tex> то зациклились.
 
{{tick}} Не рассмотрен случай заполненной хеш-таблицы.
 
{{tick}} Не рассмотрен случай заполненной хеш-таблицы.
 
: расширяемся в 2 раза?
 
: расширяемся в 2 раза?

Версия 11:17, 24 апреля 2012

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

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

Объяснить, какое зацикливание может появиться в функции 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] то зациклились. Не рассмотрен случай заполненной хеш-таблицы.

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

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

с помощью универсального хэширования (из универсального семейства хэш функций)
Так и напиши это. --Андрей Рыбак 17:48, 23 апреля 2012 (GST)

O(1) - в TeX

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

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

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