Содержание
- 2. Хеширование Функция хеширования Сокращение времени поиска можно осуществить путем локализации (уменьшения) области просмотра. Например, отсортировать данные
- 3. Хеширование В рассмотренных ранее методах поиска число итераций в лучшем случае было пропорционально O(log n). Поставим
- 4. Хеширование Основные понятия Пространством ключей называется множество всех теоретически возможных значений ключей записи. Пространством записей называется
- 5. Хеширование Функцией хеширования (функцией перемешивания, функцией рандомизации) называется функция, обеспечивающая отображение пространства ключей K в пространство
- 6. Хеширование Основные свойства хеш-функции Необратимость. Если хеш-функция, преобразующая ключ в адрес, может порождать коллизии, то однозначной
- 7. Хеширование К хеш-функции в общем случае предъявляются следующие требования: –она не должна отображать какую-либо связь между
- 8. Хеширование Если хеш-функция распределяет совокупность отображений возможных ключей равномерно по множеству индексов, то хеширование эффективно разбивает
- 9. Хеширование Хеш-таблица Хеш-таблица – это обычный массив с необычной адресацией, задаваемой хеш-функцией. Хеш-таблица – это массив,
- 10. Хеширование Основные правила использования хеш-таблиц 1. Выполнение операции в хеш-таблице начинается с вычисления хеш-функции от ключа.
- 11. Хеширование Области применения Хэш-таблицы часто применяются в базах данных, в языковых процессорах типа компиляторов и ассемблеров,
- 12. Хеширование Типы функций хеширования, их преимущества и недостатки Приведем анализ некоторых наиболее простых из применяемых на
- 13. Хеширование Метод деления Если ключей больше, чем элементов массива, то в качестве хеш-функции можно использовать деление
- 14. Хеширование Рекомендации для символьной строки Ключом может являться остаток от деления, например, суммы кодов символов строки
- 15. Хеширование Метод умножения (мультипликативный метод) Построение хеш-функции методом умножения выполняется в два этапа. 1. Сначала ключ
- 16. Хеширование Метод умножения (мультипликативный метод) Описанный метод вычисления хеш-функции по формуле h(k) =[m (kA mod 1)]
- 17. Хеширование Метод умножения (мультипликативный метод) Реализация умножения простым сдвигом h(k) =[m (kA mod 1)], m выбирается
- 18. Хеширование Схема метода умножения Реализация умножения простым сдвигом
- 19. Хеширование Метод умножения (мультипликативный метод) Реализация умножения простым сдвигом Пример 1 Пусть k=123 456; р=14; m=16384
- 20. Хеширование Мультипликативный метод /* 8-bit index */ typedef unsigned char HashIndexType; static const HashIndexType K =
- 21. Хеширование Мультипликативный метод Пример. Пусть размер таблицы hashTableSize равен 1024 (2^10). Тогда нам достаточен 16-битный индекс
- 22. Хеширование Аддитивный метод для строк переменной длины (Размер таблицы равен 256). Для строк переменной длины хорошие
- 23. Хеширование Исключающее ИЛИ для строк переменной длины (Размер таблицы равен 256). Этот метод аналогичен аддитивному, но
- 24. Хеширование Исключающее ИЛИ для строк переменной длины (Размер таблицы Логическая операция исключающее ИЛИ выполняется с двумя
- 25. Хеширование Метод свертки Еще одной хеш-функцией можно назвать функцию свертки. Цифровое представление ключа разбивается на части,
- 26. Хеширование Методы разрешения коллизий С помощью хеш-функций ключи преобразуются в адреса таблицы в заданном диапазоне. После
- 27. Хеширование Открытое (внешнее) хеширование или метод цепочек – это технология разрешения коллизий, которая состоит в том,
- 28. Хеширование Технология сцепления элементов состоит в том, что элементы множества, которым соответствует одно и то же
- 29. Хеширование Пример На рисунке hashTable – массив из 7 элементов. Каждый элемент представляет собой указатель на
- 30. Хеширование Чтобы вставить в таблицу новый элемент, хешируем ключ, чтобы определить список, в который его нужно
- 31. Хеширование Пример. Как определить размер хеш-таблицы Предположим, мы хотим создать хеш-таблицу с разрешением коллизий методом цепочек
- 32. Хеширование Чем меньше таблица, тем больше среднее время поиска ключа в ней (при фиксированном количестве элементов).
- 33. Хеширование Если можно оценить величину n и выбрать В как можно ближе к этой величине, то
- 34. Хеширование Каждая ячейка массива (хеш-таблицы) является указателем на связанный список (цепочку) пар ключ-значение, соответствующих одному и
- 35. Хеширование Преимущества и недостатки связывания Одно из преимуществ этого метода состоит в том, что при его
- 36. Хеширование Блочное хеширование Другой способ разрешения коллизий заключается в том, чтобы выделить ряд блоков, каждый из
- 37. Хеширование Чтобы реализовать схему блочного хеширования, можно использовать массив указателей на блоки (массивы фиксированной длины), которые
- 38. Хеширование Связывание блоков Вместо того, чтобы хранить все лишние элементы в одних и тех же дополнительных
- 39. Хеширование Преимущества и недостатки применения блоков Вставка и добавление элемента в хеш‑таблицу с блоками выполняется достаточно
- 40. Хеширование Закрытое (внутреннее) хеширование или метод открытой адресации – это технология разрешения коллизий, которая предполагает хранение
- 41. Хеширование Пример. На рисунке разрешение коллизий осуществляется методом открытой адресации. Пусть два значения претендуют на ключ
- 42. Хеширование Методика повторного хеширования Добавление элемента При закрытом хешировании применяется методика повторного хеширования. Если осуществляется попытка
- 43. Хеширование Поиск элемента При поиске элемента k необходимо просмотреть все местоположения h(k),h1(k),h2(k),..., пока не будет найден
- 44. Хеширование Второй подход. Чтобы увеличить эффективность данной реализации, необходимо в сегмент, который освободился после операции удаления
- 45. Хеширование Но если невозможно непосредственно сразу после удаления элементов пометить освободившиеся сегменты, то следует предпочесть закрытому
- 46. Хеширование Повторное хеширование – это поиск местоположения для очередного элемента таблицы с учетом шага перемещения. Методы
- 47. Хеширование Квадратичное опробование Отличается от линейного тем, что шаг перебора сегментов нелинейно зависит от номера попытки
- 48. Хеширование Двойное хеширование Основано на нелинейной адресации, достигаемой за счет суммирования значений основной и дополнительной хеш-функций:
- 49. Хеширование Методы повторного хеширования
- 50. Хеширование Реструктуризация хеш-таблиц Чтобы выход за пределы адресного пространства таблицы происходил реже, можно увеличить длину таблицы
- 51. Хеширование Циклический переход к началу таблицы В случае многократного превышения адресного пространства и, соответственно, многократного циклического
- 52. Хеширование Анализ скорости выполнения операций вставки и других операций при закрытом хешировании В случае применения схемы
- 53. Хеширование Преимущества и недостатки закрытого хеширования Используется массив определенной длины, превышающей количество данных, требующий больше памяти,
- 54. Хеширование При любом методе разрешения коллизий необходимо ограничить количество операций при поиске элемента. Если для поиска
- 55. Хеширование Задания 1. Применить повторное хеширование для вставки элементов 18, 14, 9, 20, 19, 12, 5,
- 56. Хеширование Идеальное хеширование Идеальным хешированием называется метод, который в наихудшем случае выполняет поиск за O(1) обращений
- 57. Хеширование Идея хеширования впервые была высказана Г.П. Ланом (Hans Peter Luhn (July 1, 1896 – August
- 58. Хеширование Андре́й Петро́вич Ершо́в (19 апреля 1931 - 8 декабря 1988) — советский учёный, один из
- 59. Хеширование Пример. Программная реализация закрытого хеширования. C.1. #include "stdafx.h" #include #include using namespace std; typedef int
- 60. Хеширование Пример. Программная реализация закрытого хеширования. C.2. int _tmain(int argc, _TCHAR* argv[]){ int i, *a, maxnum;
- 61. Хеширование Пример. Программная реализация закрытого хеширования. C.3. // заполнение хеш-таблицы элементами массива for (i = 0;
- 62. Хеширование Пример. Программная реализация закрытого хеширования. C.4. // очистка хеш-таблицы for (i = maxnum-1; i >=
- 63. Хеширование Пример. Программная реализация закрытого хеширования. C.5. // функция поиска местоположения и вставки величины в таблицу
- 64. Хеширование Пример. Программная реализация закрытого хеширования. C.6. //функция удаления величины из таблицы void deleteData(T data){ int
- 65. Хеширование Пример. Программная реализация закрытого хеширования. C.7. else { used[gap] = true; hashTable[gap] = hashTable[bucket]; used[bucket]
- 66. Хеширование Пример. Программная реализация открытого хеширования. С.1. #include "stdafx.h" #include #include using namespace std; typedef int
- 67. Хеширование Пример. Программная реализация открытого хеширования. С.2. int _tmain(int argc, _TCHAR* argv[]){ int i, *a, maxnum;
- 68. Хеширование Пример. Программная реализация открытого хеширования. С.3. // поиск элементов массива по хеш-таблице for (i =
- 69. Хеширование Пример. Программная реализация открытого хеширования. С.4. // сохранение хеш-таблицы в файл HashTable.txt out.open("HashTable.txt"); for (i
- 70. Хеширование Пример. Программная реализация открытого хеширования. С.5. // хеш-функция размещения вершины hashTableIndex myhash(T data) { return
- 71. Хеширование Пример. Программная реализация открытого хеширования. С.6. //функция удаления вершины из таблицы void deleteNode(T data) {
- 73. Скачать презентацию