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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
 
(не показано 14 промежуточных версий 3 участников)
Строка 1: Строка 1:
{{tick}} Написать что делают функции add delete и exists
+
{{tick | ticked = 1}} Написать что делают функции add delete и exists
  
{{tick}} "Вытаскиваем" - плохое слово для научного текста
+
{{tick | ticked = 1}} O(1) - в TeX
  
{{tick}} Объяснить, какое зацикливание может появиться в функции add.
+
{{tick | ticked = 1}} Оформить доказательство того, что добавление работает за O(1) как [[Шаблон:Утверждение | утверждение ]]
  
{{tick}} Не рассмотрен случай заполненной хеш-таблицы
+
{{tick | ticked = 1}} "Вытаскиваем" - плохое слово для научного текста
  
{{tick}} Не понятно, как выбирать новые хеш-функции.
+
{{tick | ticked = 1}} Объяснить, какое зацикливание может появиться в функции add.
  
{{tick}} O(1) - в TeX
+
: {{tick | ticked = 1}} "Если в ходе перемещений элементов в таблице на очередном шаге мы опять хотим переместить элемент <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> то зациклились.
 +
::: Используйте подпись <nowiki>--~~~~</nowiki> и отступы. По делу: ''новый элемент'' <tex>x</tex>, который мы добавляем в таблицу, в любом случае в самом начале работы попадает в <tex>h_1(x)</tex> или <tex>h_2(x)</tex>. Если в начале работы обе ячейки заняты, мы достаем из одной ячейки (обозначим её <tex>h_i(x)</tex>) элемент <tex>y</tex> (заметим, что <tex>h_i(y) = h_i(x)</tex>), в освободившуюся кладем <tex>x</tex>, а <tex>y</tex> кладем в <tex>h_j(y),~ (i \ne j)</tex> и так далее. Зацикливание, это когда для очередного <tex>y</tex>: <tex>h_i(y) = h_i(x)</tex>. --[[Участник:Rybak|Андрей Рыбак]] 21:14, 24 апреля 2012 (GST)
 +
:::: Когда для очередного <tex>y</tex>: <tex>h_i(y) = h_i(x)</tex> у нас <tex>x</tex> пойдет в <tex>h_j(x)(j!=i)</tex> и вот если потом вернулись то зациклились. --[[Участник:Watson|Роскошный Яков]] 22:01, 24 апреля 2012 (GST)
 +
::::: Теперь понял. {{tick | ticked = 1}} Нужно подробней расписать --[[Участник:Rybak|Андрей Рыбак]] 22:24, 24 апреля 2012 (GST)
  
{{tick}} Оформить доказательство того, что добавление работает за O(1) как [[Шаблон:Утверждение | утверждение ]]
+
{{tick | ticked = 1}} Не рассмотрен случай заполненной хеш-таблицы.
 +
: расширяемся в 2 раза?
 +
:: Нужно про это написать. Коэффициент увеличения может быть не 2, лучше просто написать "увеличим размер хеш-таблицы". --[[Участник:Rybak|Андрей Рыбак]] 17:48, 23 апреля 2012 (GST)
  
{{tick}} Оформить раздел "источники" (Требования - Викификация - пункт 9)
+
{{tick | ticked = 1}} Не понятно, как выбирать новые хеш-функции.
 +
: с помощью универсального хэширования (из универсального семейства хэш функций)
 +
:: Так и напиши это. --[[Участник:Rybak|Андрей Рыбак]] 17:48, 23 апреля 2012 (GST)
  
{{tick}} Добавить категории (Требования - Викификация - пункт 8)
+
{{tick | ticked = 1}} Оформить раздел "источники" (Требования - Викификация - пункт 9)
 +
: Добавь название для второй ссылки
 +
 
 +
 
 +
{{tick | ticked = 1}} Добавить категории (Требования - Викификация - пункт 8)
 +
 
 +
----
 +
 
 +
{{tick}} Добавить вики-ссылки
 +
 
 +
{{tick}} "Проверяем, если хэш-таблица заполнена увеличиваем её размер." - эта строчка зря повторяется

Текущая версия на 22:08, 6 июня 2012

Написать что делают функции 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)


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

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