22 (1106259), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Указатели вообще не используются, что приводит ксохранению места и ускорению поиска.Таким образом, коэффициент заполнения α = n/m не больше 1.Поиск (search): мы определенным образом просматриваемэлементы таблицы, пока не найдем искомый или не убедимся,что искомый элемент отсутствует.Просматриваются не все элементы (иначе это был быпоследовательный поиск), а только некоторые согласнозначению хеш-функции, которая в этом случае имеет двааргумента – ключ и «номер попытки»:hash: U × {0, 1, …, m – 1} → {0, 1, …, m – 1}.Функцию hash нужно выбрать такой, чтобы в последовательностипроб 〈hash(k, 0), hash(k, 1), …, hash(k, m – 1)〉 каждый номерячейки 0, 1, …, m – 1 встретился только один раз.Если при поиске мы добираемся до ячейки, содержащей NULL,можно быть уверенным, что элемент с данным ключом18отсутствует (иначе он попал бы в эту ячейку).Хеширование с открытой адресацией: программы#define m 1999struct htype {int key;int val;} *index[m];/* ключ *//* значение элемента данных *//* Поиск элемента */struct htype *search (int k) {int i = 0, j;do {j = hash (key, i);if (index[j] && index[j]->key == k)return index[j];} while (!index[j] || ++i == m);return NULL;}19Хеширование с открытой адресацией: программы/* Добавление элемента */int insert (int k, int v) {int i = 0, j;do {j = hash (key, i);if (index[j] && index[j]->key == k) {index[j]->val = v;return j;}} while (!index[j] || ++i == m);/* Таблица может оказаться заполненной */if (i == m)return -1; /* Или расширим index */index[j] = new ();index[j]->key = k, index[j]->val = v;return j;}20Хеширование с открытой адресацией: программы/* Внутренний поиск: вернем индекс массива */static int search_internal (int k) {int i = 0, j;do {j = hash (key, i);if (index[j] && index[j]->key == k)return j;} while (!index[j] || ++i == m);return -1;}/* Внешний поиск легко реализуется через внутренний */struct htype *search (int k) {int j = search_internal (k);return j >= 0 ? index[j] : NULL;21}Хеширование с открытой адресацией: программы/* Удаление элемента */void delete (int k) {int j;j = search_internal (k);if (j < 0)return;/* Нельзя писать index[j] = NULL!Будут потеряны ключи, возможно, находящиесяза удаляемым ключом (с тем же хешем).

*/???}22Хеширование с открытой адресацией: программы#define SHADOW ((void *) (intptr_t) 1)/* Удаление элемента */void delete (int k) {int j;j = search_internal (k);if (j < 0)return;/* Нельзя писать index[j] = NULL! */free (index[j]);index[j] = SHADOW;}23Хеширование с открытой адресацией: программы#define SHADOW ((void *) (intptr_t) 1)#define ISEMPTY(el) ((el) || (el) == SHADOW)static int search_internal (int k) {int i = 0, j;do {j = hash (key, i);if (!ISEMPTY (index[j]) && index[j]->key == k)return j;} while (!index[j] || ++i == m);return -1;}24Хеширование с открытой адресацией: программы#define SHADOW ((void *) (intptr_t) 1)#define ISEMPTY(el) ((el) || (el) == SHADOW)/* Добавление элемента */int insert (int k, int v) {int i = 0, j;do {j = hash (key, i);if (!ISEMPTY (index[j]) && index[j]->key == k) {index[j]->val = v;return j;}} while (! ISEMPTY (index[j]) || ++i == m);/* Таблица может оказаться заполненной (много вставок/удалений) */if (i == m)return -1; /* Или расширим index */index[j] = new ();index[j]->key = k, index[j]->val = v;return j;25}Хеш-функции для открытой адресацииЛинейная последовательность проб.Пусть hash′: U → {0, 1, …, m – 1} – обычная хеш-функция.Функция hash(k, i) = (hash′(k) + i) mod mопределяет линейную последовательность проб.При линейной последовательности проб начинают с ячейкиindex[h′(k)], а потом перебирают ячейки таблицы подряд:index[h′(k) + 1], index[h′(k) + 2], … (после index[m – 1] переходят кindex[0]).Cуществует лишь m различных последовательностей проб,т.к.

каждая последовательность однозначно определяетсясвоим первым элементом.26Хеш-функции для открытой адресацииСерьезный недостаток – тенденция к образованию кластеров(длинных последовательностей занятых ячеек, идущих подряд),что удлиняет поиск:Если в таблице все четные ячейки заняты, а нечетныеячейки свободны, то среднее число проб при поискеотсутствующего элемента равно 1,5.Если же те же m/2 занятых ячеек идут подряд, тосреднее число проб равно (m/2)/2 = m/4.Причины образования кластеров: если k заполненных ячеек идутподряд, то:вероятность того, что при очередной вставке в таблицубудет использована ячейка, непосредственно следующаяза ними, есть (k +1)/m ( пропорционально «толщине слоя»),вероятность использования конкретной ячейки,предшественница которой тоже свободна, всего лишь 1/m.Таким образом, хеширование с использованием линейнойпоследовательности проб далеко не равномерное.Возможное улучшение: добавляем не 1, а константу с, взаимно27простую с m (для полного обхода таблицы).Хеш-функции для открытой адресацииКвадратичная последовательность проб:hash(k, i) = (hash′(k) + c1⋅i + c2⋅i2) mod m,c1 и c2 ≠ 0 – константы.Пробы начинаются с ячейки index[h′(k)], а потом ячейкипросматриваются не подряд, а по более сложному закону.Метод работает значительно лучше, чем линейный.Чтобы при просмотре таблицы index использовались все ееячейки, значения m, c1 и c2 следует брать не произвольными, аподбирать специально.

Если обе константы равны единице:находим i ← hash′(k); полагаем j ← 0;проверяем index[i]:если она свободна, заносим в неезапись и выходим из алгоритма,если нет – полагаем j ← (j + 1) mod m,i ← (i + j) mod m и повторяем текущий шаг.28Хеш-функции для открытой адресацииДвойное хеширование – один из лучших методов открытойадресации.hash(k, i) = (h1(k) + i h2(k)) mod m,где h1(k) и h2(k) – обычные хеш-функции.Дополнительная хеш-функция h2(k) генерирует хеши, взаимнопростые с m.Если основная и дополнительная функция существеннонезависимы (т.е.

вероятность совпадения их хешей обратнопропорциональна квадрату m), то скучивания не происходит,а распределение ключей по таблице близко к случайному.Оценки. Среднее число проб для равномерного хеширования11.1−αоценивается при успешном поиске как αПри коэффициенте заполнения 50% среднее число проб дляуспешного поиска ≤ 1,387, а при 90% – ≤ 2,559.При поиске отсутствующего элемента и при добавлении новогоln1элемента оценка среднего числа проб 1 − α .29Хеширование других данныхХеширование идентификаторов в компилятореhashval_thtab_hash_string (const PTR p){const unsigned char *str = (const unsigned char *) p;hashval_t r = 0;unsigned char c;while ((c = *str++) != 0)r = r * 67 + c - 113;return r;}Хеширование ключа переменной длины: в GCC используетсяhttp://burtleburtle.net/bob/hash/evahash.html30.

Характеристики

Список файлов лекций