Qqqq - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:37:05Z

rollbackEdits.php mass rollback

185.220.101.2 в 03:58, 1 сентября 2022

2022-09-01T03:58:52Z

Nechaev в 16:53, 29 апреля 2012

2012-04-29T16:53:54Z

Nechaev: Удалено содержимое страницы

2012-04-29T16:42:40Z

Удалено содержимое страницы

Nechaev в 15:43, 29 апреля 2012

2012-04-29T15:43:27Z

Nechaev: /* Открытое хеширование с линейным разрешением коллизий */

2012-04-29T15:43:03Z

‎Открытое хеширование с линейным разрешением коллизий

Nechaev: /* Открытое хеширование с линейным разрешением коллизий */

2012-04-29T15:41:25Z

‎Открытое хеширование с линейным разрешением коллизий

Nechaev: /* Разрешение коллизий */

2012-04-29T15:20:14Z

‎Разрешение коллизий

Nechaev: /* Разрешение коллизий */

2012-04-29T15:19:13Z

‎Разрешение коллизий

Nechaev: /* Разрешение коллизий */

2012-04-29T15:17:42Z

‎Разрешение коллизий

← Предыдущая		Версия 16:37, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	== Удалить ==		== Удалить ==

← Предыдущая		Версия 03:58, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	== Удалить ==		== Удалить ==

← Предыдущая	Версия 16:53, 29 апреля 2012
Строка 1:	Строка 1:
−	+	== Удалить ==

← Предыдущая		Версия 16:42, 29 апреля 2012
Строка 1:		Строка 1:
−	'''Хеширование''' - класс методов поиска, идея которого состоит в использовании некоторой частичной информации, полученной из ключа (однозначно характеризующего элемент), в качестве основы поиска. С помощью хеш-функции мы вычисляем хеш-код и используем его для проведения поиска. В общем случае, однозначного соответствия между исходными данными и хеш-кодом нет в силу того, что количество значений хеш-функций меньше, чем вариантов исходных данных, поэтому существуют элементы, имеющие одинаковые хеш-коды — так называемые коллизии, но если два элемента имеют разный хеш-код, то они гарантированно
−	~~различаются. Вероятность возникновения коллизий играет немаловажную роль в оценке качества хеш-функций.~~
−	~~{{Определение~~
−	~~\|id=def1~~
−	\|definition=<tex>] U </tex> {{---}} множество объектов (универсум).<br> <tex>h : U \rightarrow S = \mathcal {f} 0 ... m - 1 \mathcal {g}</tex> называется хеш-функцией, где множество <tex>S</tex> хранит ключи из множества <tex>U</tex>.<br> Если <tex>x \in U</tex> значит <tex>h(x) \in S</tex> <br> Коллизия: <tex>\exists x \neq y : h(x) = h(y)</tex>
−	}}

−
−	~~==== Виды хеширования ====~~
−	* По способу хранения
−	** Статическое {{---}} фиксированное количество элементов. Один раз заполняем хеш-таблицу и осуществляем только проверку на наличие в ней нужных элементов.
−	** Динамическое {{---}} добавляем, удаляем и смотрим на наличие нужных элементов.
−	* По виду хеш-функции
−	** Детерминированная хеш-функция и случайные входные данные
−	** Случайная хеш-функция и произвольные входные данные
−
−	~~== Хеш-таблица ==~~
−
−	'''Хеш-табли́ца''' — структура данных, реализующая интерфейс ассоциативного массива. Представляет собой эффективную структуру данных для реализации словарей, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу.
−
−	~~== Введение ==~~
−	Существует два основных варианта хеш-таблиц: с цепочками и открытой адресацией. Хеш-таблица содержит некоторый массив <tex>H</tex>, элементы которого есть пары (хеш-таблица с открытой адресацией) или списки пар (хеш-таблица с цепочками).
−
−	Выполнение операции в хеш-таблице начинается с вычисления хеш-функции от ключа. Получающееся хеш-значение <tex>i = h(key)</tex> играет роль индекса в массиве <tex>H</tex>. Затем, зная индекс, мы можем выполнить требующуюся операцию (добавление, удаление или поиск).
−
−	Ситуация, когда для различных ключей получается одинаковое хеш-значение (коллизия), встречается не так уж и редко, и зависит от хеш-функции. Чем лучше, используемая хеш-функция, тем меньше вероятность возникновения коллизии. При вставке в хеш-таблицу размером 365 ячеек всего лишь 23-х элементов вероятность коллизии превышает 50 % (при равномерном распределении значений хеш-функции). Способ разрешения коллизий — важная составляющая любой хеш-таблицы.
−
−	Полностью избежать коллизий для произвольных данных невозможно в принципе, и хорошая хеш-функция в состоянии только минимизировать их количество. Но, в некоторых специальных случаях их удаётся избежать. Если все ключи элементов известны заранее, либо меняются очень редко, то можно подобрать хеш-функцию, с помощью которой, все ключи будут распределены по хеш-таблице без коллизий. Это хеш-таблицы с ''прямой адресацией''; в них все операции, такие как: поиск, вставка и удаление {{---}} работают за <tex>O(1)</tex>.
−
−	Если мы поделим число хранимых элементов на размер массива <tex>H</tex> (число возможных значений хеш-функции), то узнаем коэффициент заполнения хеш-таблицы (load factor). От этого параметра зависит среднее время выполнения операций.
−
−	~~== Свойства хеш-таблицы ==~~
−
−	На поиск элемента в хеш-таблице в худшем случае, может потребоваться столько же времени, как и в связанном списке, а именно <tex>\Theta(n)</tex>, но на практике хеширование исключительно эффективно. При некоторых разумных допущениях математическое ожидание времени поиска элемента в хеш-таблице составляет <tex>O(1)</tex>. А все операции (поиск, вставка и удаление элементов) в среднем выполняются за время <tex>O(1)</tex>.
−	При этом не гарантируется, что время выполнения отдельной операции мало́, так как при достижении некоторого значения коэффициента заполнения необходимо увеличить размер массива <tex>H</tex> и заново добавить в новую хеш-таблицу все пары.
−
−	~~== Разрешение коллизий ==~~
−
−	~~=== Хеширование цепочками ===~~
−	~~[[Файл:open_hash.png\|thumb\|380px\|right\|Разрешение коллизий при помощи цепочек.]]~~
−	Каждая ячейка <tex>i</tex> массива <tex>H</tex> содержит указатель на начало списка всех элементов, хеш-значение ключа которых равно <tex>i</tex>, иначе она содержит значение <tex>NIL</tex>. Коллизии приводят к тому, что появляются списки размером больше одного элемента.
−
−	Время, необходимое для вставки в наихудшем случае равно <tex>O(1)</tex>. Это операция выполняет быстро, так как считается, что вставляемый элемент отсутствует в таблице, но если потребуется, то перед вставкой мы может выполнить поиск этого элемента.
−
−	Время работы поиска в наихудшем случае пропорционально длине списка, а если все <tex>n</tex> ключей хешированы в одну и ту же ячейку (создавая список длиной <tex>n</tex>) время поиска будет равно <tex>\Theta(n)</tex> плюс время вычисления хеш-функции, что ничуть не лучше, чем использование связного списка для хранения всех <tex>n</tex> элементов.
−
−	Удаления элемента может быть выполнено за <tex>O(1)</tex>, как и вставка, при использовании двухсвязного списка.<ref>Анализ хеширования с цепочками, вы можете найти в книге Томаса Кормена: «Алгоритмы. Построение и анализ.»</ref>
−
−	~~=== Открытое хеширование с линейным разрешением коллизий ===~~
−	~~[[Файл:close_hash.png\|thumb\|380px\|right\|Пример хеш-таблицы с открытой адресацией и линейным пробированием.]]~~
−	В массиве <tex>H</tex> хранятся сами пары ключ-значение. Алгоритм вставки элемента проверяет ячейки массива <tex>H</tex> в заданном порядке до тех пор, пока не будет найдена первая свободная ячейка, в неё и будет записан новый элемент. Это позволяет сэкономить память на хранение указателей.
−
−	Последовательность, в которой просматриваются ячейки хеш-таблицы, называется последовательностью проб. В общем случае, она зависит только от ключа элемента, то есть это последовательность <tex>h_0(x)</tex>, <tex>h_1(x)</tex>, ...,<tex>h_n</tex><tex>_-</tex><tex>_1</tex><tex>(x)</tex>, где <tex>x</tex> — ключ элемента, а <tex>h_i(x)</tex> — произвольные функции, сопоставляющие каждому ключу ячейку в хеш-таблице. Первый элемент в последовательности, как правило, равен значению некоторой хеш-функции от ключа, а остальные считаются от него каким-нибудь способом. Для успешной работы алгоритмов поиска последовательность проб должна быть такой, чтобы все ячейки хеш-таблицы оказались просмотренными ровно по одному разу.
−
−	Алгоритм поиска просматривает ячейки хеш-таблицы в том же порядке, что и при вставке, пока не найдется элемент с искомым ключом, либо свободная ячейка (что означает отсутствие элемента в хеш-таблице).
−
−	Удаление элементов в такой схеме несколько затруднено. Можно поступить так: будем помечать каждую учейку по признаку, удалили мы из неё элемент, или нет. В этом случаем, удалением является установка метки {{---}} удалён, для соответсвующей ячейки хеш-таблицы, остаётся только модифицировать поиск (если удалён, то занято) и вставку (если удалён, то пусто) элементов.
−
−	~~== Примечания ==~~
−	~~<references/>~~
−
−	~~== Литература ==~~
−	* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. «Алгоритмы. Построение и анализ» {{---}} Издательство: «Вильямс», 2011 г. - 1296 стр. {{---}} ISBN 978-5-8459-0857-5, 5-8459-0857-4, 0-07-013151-1
−	* Дональд Кнут. «Искусство программирования, том 3. Сортировка и поиск» {{---}} Издательство: «Вильямс», 2007 г. — 824 стр. {{---}} ISBN 0-201-89685-0
−	* [http://ru.wikipedia.org/wiki/Хеширование Википедия: Хеширование]
−	* [http://ru.wikipedia.org/wiki/Хеш-таблица Википедия: Хеш-таблица]
−
−	~~[[Категория:Дискретная математика и алгоритмы]]~~
−	~~[[Категория: Хеширование]]~~

← Предыдущая		Версия 15:43, 29 апреля 2012
Строка 1:		Строка 1:
−	~~<tex>q</tex>~~
−
	'''Хеширование''' - класс методов поиска, идея которого состоит в использовании некоторой частичной информации, полученной из ключа (однозначно характеризующего элемент), в качестве основы поиска. С помощью хеш-функции мы вычисляем хеш-код и используем его для проведения поиска. В общем случае, однозначного соответствия между исходными данными и хеш-кодом нет в силу того, что количество значений хеш-функций меньше, чем вариантов исходных данных, поэтому существуют элементы, имеющие одинаковые хеш-коды — так называемые коллизии, но если два элемента имеют разный хеш-код, то они гарантированно		'''Хеширование''' - класс методов поиска, идея которого состоит в использовании некоторой частичной информации, полученной из ключа (однозначно характеризующего элемент), в качестве основы поиска. С помощью хеш-функции мы вычисляем хеш-код и используем его для проведения поиска. В общем случае, однозначного соответствия между исходными данными и хеш-кодом нет в силу того, что количество значений хеш-функций меньше, чем вариантов исходных данных, поэтому существуют элементы, имеющие одинаковые хеш-коды — так называемые коллизии, но если два элемента имеют разный хеш-код, то они гарантированно
	различаются. Вероятность возникновения коллизий играет немаловажную роль в оценке качества хеш-функций.		различаются. Вероятность возникновения коллизий играет немаловажную роль в оценке качества хеш-функций.

@@ Строка 57: / Строка 57: @@
 Алгоритм поиска просматривает ячейки хеш-таблицы в том же порядке, что и при вставке, пока не найдется элемент с искомым ключом, либо свободная ячейка (что означает отсутствие элемента в хеш-таблице).
-Удаление элементов в такой схеме несколько затруднено. Обычно поступают так:  будем помечать каждую учейку по признаку, удалили мы из неё элемент, или нет. В этом случаем, удалением является установка метки {{---}} удалён, для соответсвующей ячейки хеш-таблицы, остаётся только модифицировать поиск (если удалён, то занято) и вставку (если удалён, то пусто) элементов.
+Удаление элементов в такой схеме несколько затруднено. Можно поступить так:  будем помечать каждую учейку по признаку, удалили мы из неё элемент, или нет. В этом случаем, удалением является установка метки {{---}} удалён, для соответсвующей ячейки хеш-таблицы, остаётся только модифицировать поиск (если удалён, то занято) и вставку (если удалён, то пусто) элементов.
 == Примечания ==

@@ Строка 51: / Строка 51: @@
 === Открытое хеширование с линейным разрешением коллизий ===
 [[Файл:close_hash.png|thumb|380px|right|Пример хеш-таблицы с открытой адресацией и линейным пробированием.]]
-В массиве <tex>H</tex> хранятся сами пары ключ-значение. Алгоритм вставки элемента проверяет ячейки массива <tex>H</tex> в некотором порядке до тех пор, пока не будет найдена первая свободная ячейка, в которую и будет записан новый элемент. Этот порядок вычисляется на лету, что позволяет сэкономить на памяти для указателей, требующихся в хеш-таблицах с цепочками.
+В массиве <tex>H</tex> хранятся сами пары ключ-значение. Алгоритм вставки элемента проверяет ячейки массива <tex>H</tex> в заданном порядке до тех пор, пока не будет найдена первая свободная ячейка, в неё и будет записан новый элемент. Это позволяет сэкономить память на хранение указателей.
 Последовательность, в которой просматриваются ячейки хеш-таблицы, называется последовательностью проб. В общем случае, она зависит только от ключа элемента, то есть это последовательность <tex>h_0(x)</tex>, <tex>h_1(x)</tex>, ...,<tex>h_n</tex><tex>_-</tex><tex>_1</tex><tex>(x)</tex>, где <tex>x</tex> — ключ элемента, а <tex>h_i(x)</tex> — произвольные функции, сопоставляющие каждому ключу ячейку в хеш-таблице. Первый элемент в последовательности, как правило, равен значению некоторой хеш-функции от ключа, а остальные считаются от него каким-нибудь способом. Для успешной работы алгоритмов поиска последовательность проб должна быть такой, чтобы все ячейки хеш-таблицы оказались просмотренными ровно по одному разу.
-Алгоритм поиска просматривает ячейки хеш-таблицы в том же самом порядке, что и при вставке, до тех пор, пока не найдется либо элемент с искомым ключом, либо свободная ячейка (что означает отсутствие элемента в хеш-таблице).
+Алгоритм поиска просматривает ячейки хеш-таблицы в том же порядке, что и при вставке, пока не найдется элемент с искомым ключом, либо свободная ячейка (что означает отсутствие элемента в хеш-таблице).
-Удаление элементов в такой схеме несколько затруднено. Обычно поступают так: заводят булевый флаг для каждой ячейки, помечающий, удален ли элемент в ней или нет. Тогда удаление элемента состоит в установке этого флага для соответствующей ячейки хеш-таблицы, но при этом необходимо модифицировать процедуру поиска существующего элемента так, чтобы она считала удалённые ячейки занятыми, а процедуру добавления — чтобы она их считала свободными и сбрасывала значение флага при добавлении.
+Удаление элементов в такой схеме несколько затруднено. Обычно поступают так:  будем помечать каждую учейку по признаку, удалили мы из неё элемент, или нет. В этом случаем, удалением является установка метки {{---}} удалён, для соответсвующей ячейки хеш-таблицы, остаётся только модифицировать поиск (если удалён, то занято) и вставку (если удалён, то пусто) элементов.
 == Примечания ==

@@ Строка 37: / Строка 37: @@
 При этом не гарантируется, что время выполнения отдельной операции мало́, так как при достижении некоторого значения коэффициента заполнения необходимо увеличить размер массива <tex>H</tex> и заново добавить в новую хеш-таблицу все пары.
-== '''[[Открытое и закрытое хеширование | Разрешение коллизий]]''' ==
+== Разрешение коллизий ==
 === Хеширование цепочками ===

@@ Строка 39: / Строка 39: @@
 == Разрешение коллизий ==
-=== Открытое хеширование ===
+=== Хеширование цепочками ===
 [[Файл:open_hash.png|thumb|380px|right|Разрешение коллизий при помощи цепочек.]]
 Каждая ячейка <tex>i</tex> массива <tex>H</tex> содержит указатель на начало списка всех элементов, хеш-значение ключа которых равно <tex>i</tex>, иначе она содержит значение <tex>NIL</tex>. Коллизии приводят к тому, что появляются списки размером больше одного элемента.
@@ Строка 49: / Строка 49: @@
 Удаления элемента может быть выполнено за <tex>O(1)</tex>, как и вставка, при использовании двухсвязного списка.<ref>Анализ хеширования с цепочками, вы можете найти в книге Томаса Кормена: «Алгоритмы. Построение и анализ.»</ref>
-=== Закрытое хеширование ===
+=== Открытое хеширование с линейным разрешением коллизий ===
 [[Файл:close_hash.png|thumb|380px|right|Пример хеш-таблицы с открытой адресацией и линейным пробированием.]]
 В массиве <tex>H</tex> хранятся сами пары ключ-значение. Алгоритм вставки элемента проверяет ячейки массива <tex>H</tex> в некотором порядке до тех пор, пока не будет найдена первая свободная ячейка, в которую и будет записан новый элемент. Этот порядок вычисляется на лету, что позволяет сэкономить на памяти для указателей, требующихся в хеш-таблицах с цепочками.