Лекция 13. Хеш-таблицы (1107988), страница 2

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

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

Пусть количество хеш-значенийравно m. Выберем и зафиксируем вещественную константу v 0 < v < 1; положимhash(key) = m(key⋅v % 1)key⋅v % 1 – дробная часть числа key⋅v.Достоинство метода умножения в том, что качество хеш-функции слабо зависит отвыбора m. Обычно в качестве m выбирают степень двойки, так как в этом случаеумножение на m сводится к сдвигу.(с) Кафедра системного программирования ф-та ВМК МГУ, 20103Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.годПример. Пусть в используемом компьютере длина слова равна w битам и ключ keyпомещается в одно слово. Тогда, если m = 2p, то вычисление hash(key) можновыполнить следующим образом: умножим key на w-битовое целое число v⋅2w;получится 2w-битовое число:В качестве значения hash(key) возьмем первые p битов r0 (умножение на m = 2p иотбрасываниемладшихразрядов).СогласноД.Кнуту(Искусствопрограммирования, том 3) выбор v = 5 − 1 / 2 = 0.6180339887...

является удачным.13.6. Программы.()#define MAX 2000/* размер хеш-таблицы */struct htype {int key;/* ключ */int val;/* значение элемента данных */struct htype *next; /* указатель на следующий элемент цепочки */struct htype *prvs; /* указатель на предыдущий элемент цепочки */} *p;struct htype *index[MAX];/* инициализация хеш-таблицы */void init(void) {int i;for(i = 0; i < MAX; i++) {index[i] = NULL; /* хеш-таблица (массив начал цепочек) */}}/* Вычисление хеш-адреса и поиск по ключу k: если элемент с ключом k *//* найден, возвращаем указатель на него, если нет возвращаем NULL */struct htype *search(int k) {int h;struct htype *p;/* вычисление хеш-адреса */h = k % 701; /* хеш-адрес *//* поиск ключа k */if(index[h] != NULL) {p = index[h];do {if(p -> key == k) return p;else p = p -> next;} while (p != NULL);return NULL;}/* Порождение нового элемента цепочки и возврат указателя на него */(с) Кафедра системного программирования ф-та ВМК МГУ, 20104Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.годstruct htype *new() {struct htype *p;p = malloc(sizeof(struct htype)); //выделение памятиp -> key = -1;p -> val = 0;p -> next = NULL;p -> prvs = NULL;return p;}13.7.

Дополнения.Insert(key, value)Delete(key, value)(с) Кафедра системного программирования ф-та ВМК МГУ, 20105.

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

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