Лекция 5 (стр. 4 )

Эффективность доступа и хранения данного метода зависит от того, насколько проектировщик выполняет требования, предъявляемые к хеш-функции.

Пример. Требуется для заданной последовательности значений ключа: 36, 26, 12, 5, 95 и адресного пространства от 1 до 10 построить функцию хеширования, не приводящую к коллизиям.

1. Пусть в качестве хеш-функции выбрана H(x)=x mod10 +1. Соответствие значений ключа физическим адресам представлено в табл.:

	36	26	12	5	95
H(x)	7	7	3	6	6

При такой hash-функции будет две коллизии.

2. Пусть в качестве хеш-функции выбрана H(x)=(a+b) mod 10 + 1, где a – количество десятков в x, а b – количество единиц в x. Соответствие значений ключа физическим адресам представлено в табл.

	36	26	12	5	95
H(x)	10	9	4	6	5

Данная хеш-функции не приводит к коллизиям.

Задания

Задание 1. В качестве ключей некоторой БД используются числовые поля целого типа. Имеется следующая последовательность ключей:

111 51 48 22 14 31 28 56 19 7 30 95 23 15 49

Размер хеш-таблицы – 20 строк. Строки нумеруются с 0. Нарисовать состояние хэш-таблицы при использовании случайного рехеширование с числами r=3, 8, 5,1

Хеш-функция: h(ai)=ai mod N

Формула для рехеширования: (h(ai)+r) mod N

Номер строки	Ключ
0
1
2	22
3	23
4	56
5
6
7	19
8	48
9	49
10	7
11	111
12
13	30
14	51
15	95
16	28
17	14
18	15
19	31

Попробуем выполнить поиск числа 56.

h(a)=56 mod 20=16 – неудачно

h(a)=(56+3) mod 20=19 - неудачно

h(a)=(56+8) mod 20=4 – удачно

Задание 2

Решим ту же задачу с использованием метода цепочек для рехеширования:

111  51 48 22 14 31 28 56 19 7 30 95 23 15 49

С использованием линейных списков		С использованием 2-х таблиц
Номер строки	Ключ		Таблица объектов		Хеш-таблица
0					Chain[2]
1			1	111	2		0
2	22		2	51	6		1
3	23		3	48	7		2	4
4			4	22			3	13
5			5	14			4
6			6	31			5
7	7		7	28			6
8	48->28		8	56			7	10
9	49		9	19			8	3
10	30		10	7			9	15
11	111->51->31		11	30			10	11
12			12	95	14		11	1
13			13	23			12
14	14		14	15			13
15	95->15		15	49			14	5
16	56						15	12
17							16	8
18							17
19	19						18
							19	9

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

Задание 3

Пусть коды букв имеют значения: A-1, B-2, C-3, D-4, E-5, F-6, G-7, H-8, I-9, J-10, K-11, L-12, M-13, N-14, O-15, P-16, Q-17, R-18, S-19, T-20, U-21, V-22, W-23, X-24, Y-25, Z-26. Размер хеш-таблицы N=24. Строки нумеруются с 0. Нарисовать состояние таблицы после записи в нее последовательно идентификаторов: HOME, PLACE, FACE, TABLE, KINO, RENO, PEN, MAN, GO, TRACE, EDIT, COPY, CUT, PUT, DOWN, PAGE, END, если используется случайное рехеширование с числами ri=5,3,9,7. Хеш-функция равна сумме кодов букв.

№		Сумма кодов букв (Sum)	Sum mod 24
1	HOME	41	17
2	PLACE	37	13
3	FACE	15	15
4	TABLE	40	16
5	KINO	49	1
6	RENO	52	4
7	PEN	35	11
8	MAN	28	4
9	GO	22	22
10	TRACE	47	23
11	EDIT	38	14
12	COPY	59	11
13	CUT	44	20
14	PUT	57	9
15	DOWN	56	8
16	PAGE	29	5
17	END	23	23

При случайном рехешировании получаем:

0
1	КINO
2	END
3
4	RENO
5	CUT
6
7
8	DOWN
9	MAN
10	PAGE
11	PEN
12	PUT
13	PLACE
14	EDIT
15	FACE
16	TABLE
17	HOME
18
19
20	COPY
21
22	GO
23	TRACE

При линейном рехешировании таблица выглядит так:

0	END
1	KINO
2
3
4	RENO
5	MAN
6	PAGE
7
8	DOWN
9	PUT
10
11	PEN
12	COPY
13	PLACE
14	EDIT
15	FACE
16	TABLE
17	HOME
18
19
20	CUT
21
22	GO
23	TRACE

Попробуем выполнить поиск идентификатора PAGE:

h(PAGE)=5 – неудачно.

h(PAGE)=(5+1) mod 24=6 – удачно.

Задание 4

Напишите программу на языке Паскаль, в которой для заданных текстовых файлов, содержащих идентификаторы, производится хеширование тремя разными способами и сравнение эффективности этих трех хеш-функций (функции вы выбираете сами, их можно взять из лекций, литературы или придумать самим). Размер хеш-таблицы равен размеру файла. Использовать метод случайного рехеширования. (подбирать randomом). Для каждого файла и для каждой функции нужно подсчитать среднее и максимальное количество попыток при включении значения в хеш-таблицу и сделать выводы о том, какая хеш-функция является более эффективной. Результаты эксперимента оформить в виде таблицы примерно следующего вида:

Имя и размер файла	метод	Среднее кол-во попыток	Максимальное кол-во попыток
inp1.txt 67 элементов	1
2
3
inp2.txt 117 элементов	1
2
3
inp3.txt 178 элементов	1
2
3

[1] С хешированием мы сталкиваемся едва ли не на каждом шагу: при работе с браузером (список Web-ссылок), текстовым редактором и переводчиком (словарь), языками скриптов (Perl, Python, PHP и др.), компилятором (таблица символов).

[2] Цепочки.