Содержание
- 2. Словарные операции поиск элемента х; добавление нового элемента х; удаление элемента х. Структуры данных для выполнения
- 3. Абстрактный тип данных: множество (set) Абстрактный тип данных: ассоциативный массив (map) Структуры данных на основе хеш-таблиц
- 4. Для простоты будем считать, что ключи являются целыми числами из диапазона [0, N). Обозначим через K
- 5. 1. Прямая адресация Если достаточно памяти для массива, число элементов которого равно числу всех возможных ключей,
- 6. размер таблицы с прямой адресацией не зависит от того, сколько элементов реально содержится в множестве; если
- 7. 2. Хеш-функция (англ. hash function) Введём некоторую функцию, называемую хеш-функцией, которая отображает множество ключей в некоторое
- 8. является вполне годной для практики хеш-функцией и часто применяется; любая пара различных ключей будет давать коллизию;
- 9. Велика ли вероятность коллизий? Пусть осуществляется хеширование для n различных ключей, т.е. мы строим вектор длины
- 11. или
- 12. Разработано несколько стратегий разрешения коллизий Разрешение коллизий методом цепочек (англ. separate chaining) Разрешение коллизий методом открытой
- 13. Разрешение коллизий методом цепочек (англ. separate chaining)
- 14. Хеш-функция h раскладывает исходные ключи x по корзинам (англ. bins, buckets) или слотам (англ. slots). ключ
- 15. Операция вставки элемента
- 16. Сначала вычисляется хеш-значение h(x) для ключа x, а затем происходит обращение к соответствующему связному списку. Если
- 17. Операция удаления элемента
- 18. Вычисляем сначала хеш-значение для ключа x: h(45)=5. В общем случае из односвязного списка удалить элемент из
- 19. Таким образом, производительность всей конструкции связана с таким параметром, как длина цепочки. ВНИМАНИЕ Даже если цепочка
- 20. Разрешение коллизий методом открытой адресации (англ. open addressing)
- 21. В линейном массиве хранятся непосредственно ключи, а не заголовки связных списков. В каждой ячейке массива разрешено
- 22. Последовательность проб (англ. probe sequence) Обозначим через h(x,i) номер ячейки в массиве, к которой следует обращаться
- 23. Для успешной работы алгоритмов поиска последовательность проб должна быть такой, чтобы в результате M проб все
- 24. Линейное пробирование Ячейки хеш-таблицы последовательно просматриваются с некоторым фиксированным интервалом c между ячейками: h(x, i) =
- 25. h(x,i)=(x+2·i) mod 10 Например, при x = 5, подставляя i от 0 до 9, будем получать
- 26. Теорема Для того чтобы в ходе M проб все ячейки таблицы оказались просмотренными по одному разу,
- 27. Доказательство. Воспользуемся сведениями из элементарной теории чисел. Докажем необходимость Пусть h(x, i) пробегает все значения от
- 28. Недостаток линейного пробирования проявляется в том, что на реальных данных часто образуются кластеры из занятых ячеек
- 29. Номер ячейки квадратично зависит от номера попытки, расстояние между ячейками с каждой итерацией увеличивается на константу
- 30. Двойное хеширование: h(x,i) = (h'(x) + h"(x) ·i) mod M Последовательность проб при работе с ключом
- 31. Операция вставки элемента
- 32. Перед вставкой ключа x выполняется поиск этого ключа. Если такой элемент x уже есть в таблице,
- 33. Например, при линейном пробировании: h(x,i) = (x+i) mod M, М=10 7, 29, 67, 38, 25, 27,
- 34. Операция поиска элемента Случай 1. Предположим, сначала что в таблице операция удаления элемента НЕ поддерживается.
- 35. Ячейки массива проверяются, в соответствии с той же функцией последовательности проб, которая использовалась при добавлении элементов
- 36. Операция поиска элемента Случай 2. Предположим, что в хеш-таблице поддерживается операция удаления элемента.
- 37. h(x,i)=(x+i) mod M, 7 29 25 67 38 27 18 M=10 Затем выполнили поиск элемента x=18.
- 38. h(x, i) = (x + i) mod M, 7 29 25 67 38 27 18 M=10
- 39. Недостатки открытой адресации
- 40. 1. Нетрудно видеть, что при разрешении коллизий методом открытой адресации наличие большого числа deleted-ячеек отрицательно сказывается
- 41. 2. Число хранимых ключей не может превышать размер хеш-массива (при заполнении на 70% производительность падает и
- 42. Преимущества открытой адресации
- 43. экономия памяти, если размер ключа невелик по сравнению с размером указателя в методе цепочек приходится хранить
- 44. Хеш-таблицы на практике Любой подход к реализации хеш-таблицы может работать достаточно быстро на реальных нагрузках. Время,
- 45. Критически важным показателем для хеш-таблицы является коэффициент заполнения— отношение числа ключей, которые хранятся в хеш-таблице, к
- 46. Реализация хеш-таблицы общего назначения обязана поддерживать операцию изменения размера. На практике часто используемым приёмом является автоматическое
- 47. Объединение хеш-значений Предположим, что координаты точек на плоскости хранятся в виде пар целых чисел (x,y), и
- 48. Пусть для простоты верхняя граница возможных значений хеш-функции не фиксирована (где-то дальше в реализации хеш будет
- 49. Хеширование строк. Полиномиальное хеширование
- 50. Предположим, что на вход поступает строка: S= ‘аbcdb’ → 1,2,3,4,2.
- 51. Прямой полиномиальный хеш (хеширование слева направо) Обратный полиномиальный хеш (хеширование справа налево) Две одинаковые строки будут
- 54. …
- 55. Так как хеш - это значение многочлена, то для многих строковых операций можно быстро пересчитывать хеш
- 58. Для реализации математической формулы ? ?
- 59. Применение хеширования строк Т S Т Т
- 60. Проход по содержимому хеш-таблицы В процессе программирования может возникнуть необходимость выполнить обход всех элементов структуры данных
- 61. В большинстве реализаций проход по хеш-множествам выполняется в произвольном порядке, не гарантируется какой-либо отсортированности ключей. В
- 62. Хеш-таблицы в C++
- 63. Долгое время в языке C++ не было стандартных реализаций структур данных на основе хеш-таблиц. Контейнеры std::set
- 64. Наконец, в стандарте C++11 в STL официально были добавлены хеш-таблицы. Стандарт предусматривает четыре контейнера на основе
- 65. В качестве хеш-значения в C++ используется число типа size_t. Все хеш-контейнеры предоставляют метод rehash(), который позволяет
- 66. Рассмотрим более подробно реализацию в компиляторе GCC (GNU Compiler Collection) Пусть ключи добавляются в std::unordered_set по
- 67. Хеш-таблицы в JAVA
- 68. Коллекции HashSet и HashMap реализуются как хеш-таблицы, для разрешения коллизий используется метод цепочек. Для хеширования целых
- 69. В версии Java 8 разработчики озаботились вопросом устойчивости коллекций, использующих хеширование, к коллизиям. В исходном коде
- 70. Хеш-таблицы в PYTHON
- 71. Встроенный тип dict — ассоциативный массив, словарь —широко используется в языке. Он реализован в виде хеш-таблицы,
- 72. Криптографические хеш-функции В криптографии множество K возможных ключей бесконечно, и любой блок данных является ключом (в
- 73. За годы развития вычислительной техники сформировалась наука о том, как практически строить хеш-функции. Разработаны всевозможные правила
- 74. Универсальное хеширование (англ. universal hashing)
- 75. Добавить рандомизацию: внести элемент случайности, чтобы не было фиксированного «плохого» случая. Идея не брать какую-либо одну
- 77. p·(p-1) способ выбрать хеш-функцию из семейства добавление элемента – усреднённо O(1); поиск элемента – математичекое ожидание
- 78. Совершенное хеширование (англ. perfect hashing)
- 79. Пусть S — фактическое множество ключей в хеш-таблице, и у этого множества размер n, где n
- 80. Таким образом, подход заключается в построении хеш-функции, которая является: простой, т.е. достаточно константного объёма памяти, чтобы
- 81. Совершенное двухуровневое хеширование
- 82. Уровень 2 для каждой цепочки строится небольшая вторичная хеш-таблица, чтобы гарантировать отсутствие коллизий на этом уровне
- 83. Общие задачи в iRunner для закрепления навыков 0.5. Хеш-таблица (разрешение коллизий метом открытой адресации)
- 85. Скачать презентацию