Добавил:
ПОИТ 2016-2020 Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Пустовалова 2 сем / Лекции / Лекция 9_Хэш.ppt
Скачиваний:
51
Добавлен:
29.04.2018
Размер:
1.49 Mб
Скачать

ХЭШ-ТАБЛИЦЫ

хэш-таблица — это динамическое

множество, поддерживающее словарные операции: добавление, поиск и удаление элемента, использующее специальные методы адресации. Основное отличие таблиц от других динамических множеств – вычисление адреса элемента по значению ключа.

хэш-таблица — это структура данных,

реализующая интерфейс ассоциативного

массива, а именно, она позволяет хранить пары (ключ или индекс, значение)

Назначение

символьная таблица – словарь в базах данных

компилятор для управления

информацией о переменных, ассемблер

Web-браузер для хранения адресов

страниц, (cache — кэширования) недавно использованных доменных

имен и их IP-адресов.

поиск в хэш

Первый шаг – вычисление хэш- функции, которая преобразует ключ поиска в адрес в таблице.

Второй шаг – процесс разрешения конфликтов, который обрабатывает такие ключи.

Среднее время поиска элемента O(1) времядля наихудшего случая - O(n)

Хэш-функции

Преобразование ключей в адреса в таблице

или

Разбиение множества на подмножества

Множество M разбивается на N непересекающихся подмножеств, занумерованных индексами от 0 до N - 1. Подмножество Mi с индексом i

содержит все элементы x из M,

значения хеш-функции для которых

равняются i:

Mi ={x € M : h(x) = i}

При поиске элемента x вычисляется значение его хеш-функции: t = h(x). Затем ищем x в подмножестве Mt .

свойства хэш-функций

определена на элементах множества и принимает целые неотрицательные значения

1) легко вычислять;

2)принимать всевозможные различные значения приблизительно с равной вероятностью (минимизация коллизий);

3) на близких значениях аргумента она принимала далекие друг от друга значения (свойство, противоположное

математическому понятию непрерывности)

Модульное хэширование

hashTableSize - простое число

h(key) key%hashTableSize

0 до (hashTableSize-1)

// модульное хэширование

typedef int HashIndexType;

HashIndexType Hash(int Key)

{return Key % HashTableSize; }

Соседние файлы в папке Лекции