Обсуждение:Хеширование кукушки — различия между версиями
Rybak (обсуждение | вклад) м |
|||
| (не показано 5 промежуточных версий 2 участников) | |||
| Строка 8: | Строка 8: | ||
{{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 | 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> то зациклились. | :: Вроде правильно, потому что <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) | ::: Используйте подпись <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) | + | :::: Когда для очередного <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 | ticked = 1}} Не рассмотрен случай заполненной хеш-таблицы. | {{tick | ticked = 1}} Не рассмотрен случай заполненной хеш-таблицы. | ||
: расширяемся в 2 раза? | : расширяемся в 2 раза? | ||
:: Нужно про это написать. Коэффициент увеличения может быть не 2, лучше просто написать "увеличим размер хеш-таблицы". --[[Участник:Rybak|Андрей Рыбак]] 17:48, 23 апреля 2012 (GST) | :: Нужно про это написать. Коэффициент увеличения может быть не 2, лучше просто написать "увеличим размер хеш-таблицы". --[[Участник:Rybak|Андрей Рыбак]] 17:48, 23 апреля 2012 (GST) | ||
| − | {{tick}} Не понятно, как выбирать новые хеш-функции. | + | {{tick | ticked = 1}} Не понятно, как выбирать новые хеш-функции. |
: с помощью универсального хэширования (из универсального семейства хэш функций) | : с помощью универсального хэширования (из универсального семейства хэш функций) | ||
:: Так и напиши это. --[[Участник:Rybak|Андрей Рыбак]] 17:48, 23 апреля 2012 (GST) | :: Так и напиши это. --[[Участник:Rybak|Андрей Рыбак]] 17:48, 23 апреля 2012 (GST) | ||
| − | {{tick}} Оформить раздел "источники" (Требования - Викификация - пункт 9) | + | {{tick | ticked = 1}} Оформить раздел "источники" (Требования - Викификация - пункт 9) |
: Добавь название для второй ссылки | : Добавь название для второй ссылки | ||
| Строка 26: | Строка 29: | ||
{{tick | ticked = 1}} Добавить категории (Требования - Викификация - пункт 8) | {{tick | ticked = 1}} Добавить категории (Требования - Викификация - пункт 8) | ||
| − | + | ---- | |
| + | |||
| + | {{tick}} Добавить вики-ссылки | ||
| + | |||
| + | {{tick}} "Проверяем, если хэш-таблица заполнена увеличиваем её размер." - эта строчка зря повторяется | ||
Текущая версия на 22:08, 6 июня 2012
☑ Написать что делают функции add delete и exists
☑ O(1) - в TeX
☑ Оформить доказательство того, что добавление работает за O(1) как утверждение
☑ "Вытаскиваем" - плохое слово для научного текста
☑ Объяснить, какое зацикливание может появиться в функции add.
- ☑ "Если в ходе перемещений элементов в таблице на очередном шаге мы опять хотим переместить элемент в ячейку то значит произошло зацикливание." - элемент уже лежит в , тут, вроде, нужно сказать про элемент такой, что . --Андрей Рыбак 17:48, 23 апреля 2012 (GST)
- Вроде правильно, потому что мог переместиться в , и вот если он вернулся в то зациклились.
- Используйте подпись --~~~~ и отступы. По делу: новый элемент , который мы добавляем в таблицу, в любом случае в самом начале работы попадает в или . Если в начале работы обе ячейки заняты, мы достаем из одной ячейки (обозначим её ) элемент (заметим, что ), в освободившуюся кладем , а кладем в и так далее. Зацикливание, это когда для очередного : . --Андрей Рыбак 21:14, 24 апреля 2012 (GST)
- Когда для очередного : у нас пойдет в и вот если потом вернулись то зациклились. --Роскошный Яков 22:01, 24 апреля 2012 (GST)
- Теперь понял. ☑ Нужно подробней расписать --Андрей Рыбак 22:24, 24 апреля 2012 (GST)
- Когда для очередного : у нас пойдет в и вот если потом вернулись то зациклились. --Роскошный Яков 22:01, 24 апреля 2012 (GST)
- Используйте подпись --~~~~ и отступы. По делу: новый элемент , который мы добавляем в таблицу, в любом случае в самом начале работы попадает в или . Если в начале работы обе ячейки заняты, мы достаем из одной ячейки (обозначим её ) элемент (заметим, что ), в освободившуюся кладем , а кладем в и так далее. Зацикливание, это когда для очередного : . --Андрей Рыбак 21:14, 24 апреля 2012 (GST)
- Вроде правильно, потому что мог переместиться в , и вот если он вернулся в то зациклились.
☑ Не рассмотрен случай заполненной хеш-таблицы.
- расширяемся в 2 раза?
- Нужно про это написать. Коэффициент увеличения может быть не 2, лучше просто написать "увеличим размер хеш-таблицы". --Андрей Рыбак 17:48, 23 апреля 2012 (GST)
☑ Не понятно, как выбирать новые хеш-функции.
- с помощью универсального хэширования (из универсального семейства хэш функций)
- Так и напиши это. --Андрей Рыбак 17:48, 23 апреля 2012 (GST)
☑ Оформить раздел "источники" (Требования - Викификация - пункт 9)
- Добавь название для второй ссылки
☑ Добавить категории (Требования - Викификация - пункт 8)
☐ Добавить вики-ссылки
☐ "Проверяем, если хэш-таблица заполнена увеличиваем её размер." - эта строчка зря повторяется
