Хеширование (hashing) - это процесс получения индекса элемента массива непосредственно в результате операций, производимых над ключом, который хранится вместе с элементом или даже совпадает с ним. Генерируемый индекс называется хеш-адресом (hash). Изъясняясь проще: есть у нас одномерный массив, который мы назовем хеш-таблицей. Эта хеш-таблица будет нужна для хранения в ней данных. Собственно, как обычный массив. Но у хеш-таблицы есть существенное преимущество: элементы в ней будут располагаться в ячейках с уникальными адресами (хеш-адресами), выдаваемыми хеш-функцией. Хеш-функция – это такая функция, которая выдает адреса (ну, или индексы) добавляемым элементам исходя из какого-то условия. Т.е. в простом массиве как обычно задается адресация? Что-то типа этого:
| Pascal | 1
2
3
4
| ………….
For i:=0 to n do
A[i]:=”добавляемое значение”;
…………. |
|
//данные в хеш-таблице
В хеш-функции же по выбору задается метод выдачи адреса, причем разница между индексами добавленных по очереди элементов может быть ощутимо большой. Все зависит лишь от выбора хеш-функции. Выбирают ее обычно исходя из уместности. К примеру, адрес добавляемым элементам можно задать следующим образом: у добавляемого в таблицу значения (предположим, строкового типа) сначала берется ascii код нескольких символов, коды суммируются, и на выходе функция выдает индекс элемента – это его уникальный ключ, по которому можно будет без особых проблем отыскать этот элемент в таблице.
Пример:
Пусть хеш-функция будет следующей: код второго и последнего символа добавляемого в таблицу элемента.
На входе: ‘Example’ – претендент на получение адреса в таблице, он же добавляемый в хеш-таблицу элемент типа «строка».
- Берем второй символ – символ “x”, его ascii код = 120;
- Берем последний символ – символ “e”, его ascii код = 101;
- Складываем: 120+101=221 – это индекс, выданный хеш-функцией;
- В ячейку хеш-таблицы с индексом 221 заносим элемент со значением ‘Example’.
Аналогичные действия проводятся со всеми добавляемыми элементами.
Стоит отметить, что если в таблицу вносятся элементы с одинаковыми значениями, они все будут содержать одинаковый, вернее, один и тот же адрес.
Удобна такая адресация с точки зрения поиска элементов в таблице. В обычном массиве мы бы перебрали кучу не нужных нам элементов, прежде чем отыскать нужный. Будь то хоть один из самых эффективных методов поиска – результат все равно оставляет желать лучшего. В хеш-функции же все намного проще: вводится элемент для поиска, вычисляется его адрес с помощью той же хеш-функции, заглядываем в ячейку с выданным адресом и видим, что он там спокойно себе хранится. В итоге задача как бы решилась в одно действие. Но это в лучшем случае. Ведь всегда может случиться ситуация, когда при желании добавить в таблицу очередной элемент по выданному хеш-функцией адресу ячейка уже занята. Например: два элемента ‘123’ и ‘223’ вроде бы с разными значениями, но так выходит, что с одинаковыми адресами в таблице: суммы ascii кодов второго и последнего символа у обоих элементов совпадают. В этом случае можно конечно сменить хеш-функцию и забыть об этом неприятном случае. Проблема в том, что и другой хеш-функции могут тоже выйти подобного рода не состыковки. Называются они коллизиями.
Стандартное определение:
Цитата:
Ситуация, когда два или более ключа ассоциируются с одной и той же ячейкой в таблице, называется коллизией при хешировании.
Эту проблему нужно решать. Как говорится, совершенная хеш-функция – это функция, не порождающая коллизий. Насколько мне известно, таких функций пока не изобрели (или, может, я сам это упустил). Если вообще убрать коллизии невозможно, то вполне возможно хотя бы минимизировать их количество. Тут на помощь и приходят всяческие методы их разрешения.
Существует несколько таких способов. К примеру, метод цепочек или метод открытой адресации.
Здесь будет рассмотрен метод открытой адресации, а также одна из его последовательностей проб – линейное пробирование (или апробирование, везде по-разному).
Суть «Открытой адресации»
В массиве H хранятся сами пары ключ-значение. Алгоритм вставки элемента проверяет ячейки массива H в некотором порядке до тех пор, пока не будет найдена первая свободная ячейка, в которую и будет записан новый элемент. Этот порядок вычисляется на лету.
Суть «Линейного пробирования»
Ячейки хеш-таблицы последовательно просматриваются с некоторым фиксированным интервалом k между ячейками (обычно, k = 1), то есть i-й элемент последовательности проб — это ячейка с номером (hash(x) + ik) mod N. Для того, чтобы все ячейки оказались просмотренными по одному разу, необходимо, чтобы k было взаимно-простым с размером хеш-таблицы. Т.е. стоит иметь в виду, что нерационально выбранный шаг (интервал) может привести не только к неудачному поиску, но и вовсе к зацикливанию.
По сути, тот или иной метод – это та же функция, которая будет выдавать добавляемым элементам новые адреса. Если же приобретенный адрес вновь не подошел – функция подыщет еще один  . И так пока не достигнет конца таблицы. Это опять же в лучшем случае, т.к. все зависит от шага (интервала k, см. выше), который пользователь задаст в начале.
Вернемся к примеру: два элемента: ‘123’ и ‘223’. У обоих одинаковый адрес ячеек. В таком случае его займет тот элемент, который ввели раньше. К адресу второго применится метод разрешения коллизий и ему выдастся новый адрес, туда и будет помещен элемент.
С точки зрения поиска «таких» элементов в таблице: опять же хеш-функцией выдается адрес. Если по этому адресу не нужный нам элемент – применяем метод, получаем новый адрес и, наверняка по этому адресу и находится искомый элемент. Если нет – применяем метод еще раз.
Пора перейти к реализации.
Формирование хеш-таблицы:
| Pascal | 1
2
3
4
5
6
7
8
9
10
11
12
13
| const
MAXn = 7000; { размерность таблицы }
{ формирование типа хеш-таблицы }
type
arr = record
mas: string[7]; { элемент в таблице }
flag: boolean; { флаг для пометки просмотров }
end;
var
table: array [0..mAxN] of arr; { таблица представлена массивом записей }
.............. |
|
Процедура инициализации таблицы:
| Pascal | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
| procedure initArray;
{
Процедура инициализации массива (хеш-таблицы).
Массив типа string, '' - пустая ячейка.
}
var
j: integer;
begin
for j := 0 to maxn do
begin
table[j].mas := '';
table[j].flag := true;
end;
end; |
|
Та самая хеш-функция, выдающая адреса элементам:
| Pascal | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| function hash(str: string): integer;
{
Хеш-функция. Задает адрес для элемента в массиве.
str - элемент, которому необходимо назначить адрес
}
begin
{
Хеш-функция описана ниже, для занесения элемента
в таблицу нам нужно, чтобы элемент был как минимум из двух символов.
Поэтому дописываем пробелов для получения корректного адреса.
Само значение добавляемого элемента при этом не изменится.
}
if length(str) = 1 then
str := ' ' + str + ' ';
{ к примеру, сумма кодов второй и последней букв элемента }
hash := ord(str[2]) + ord(str[length(str)]);
end; |
|
Функция-метод для разрешения коллизий. Выдает новые адреса «нуждающимся» элементам:
| Pascal | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
| function rhash(ii: integer; var c: integer; str: string): integer;
{
Разрешение коллизий. Подбирает новый адрес для элемента,
если место, которое ему определила хеш-функция, занято.
ii - ii-й элемент последовательности проб;
c - фиксированный шаг;
str - текущий элемент.
Прим. Для того, чтобы все ячейки оказались просмотренными по одному разу,
необходимо, чтобы "с" было взаимно-простым с размером хеш-таблицы (maxn).
}
begin
{ например, такой метод - линейное пробирование }
rhash := (hash(str) + c * ii) mod maxn;
end; |
|
Процедура добавления элемента в хеш-таблицу:
| Pascal | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| procedure AddHash(var j, c, n: integer; var str: string);
{
Процедура добавления элемента в таблицу. Здесь с - шаг,
j - cчетчик элементов, str - вводимая строка
}
var
i, ii: integer;
begin
{
В случае, если потребуется подбирать свободное
место для элемента в таблице, начинать всегда
нужно с начала. Поэтому i=0
}
i := 1; { переменная для rhash }
if c = 0 then { шаг не введен, значит таблица пуста }
begin
repeat
write('Размерность таблицы (<=7000): ');
readln(n);
until n <= 7000;
write('Введите шаг: ');
readln(c);
end;
if n = 0 then
writeln('Таблица заполнена')
else
begin
inc(j); { счетчик для элементов }
writeln('Элемент # ', j);
readln(str);
ii := hash(str); { получения адреса для хранения элемента в хеш-таблице }
while true do
begin
{ ячейка по определенному хеш-функцией адресу пуста }
if ii <= maxn then
begin
if (table[ii].mas = '') or (table[ii].flag = true) then
begin
table[ii].mas := str; { добавляем элемент в ячейку }
table[ii].flag := false; { помечаем как занятую }
dec(n);
break; { выходим для дальшейших операций }
end;
{ по указанному адресу лежит элемент-клон}
if ((table[ii].mas <> '') and (table[ii].mas = str)) or
(table[ii].flag = true) then
begin
table[ii].mas := str; { заменяем его (они ведь одинаковы) }
table[ii].flag := false; { помечаем ячейку как занятую }
dec(j); { элемент заменился, значит счетчик не увеличиваем }
break; { выходим для дальшейших операций }
end;
{ по указанному адресу уже есть элемент, отдичный от текущего }
if ((table[ii].mas <> '') and (table[ii].mas <> str)) or
(table[ii].flag = true) then
ii := rhash(i, c, str); { меняем адрес элементу во избежание коллизии }
{ проверяем таблицу на наличие свободного места }
end
else
ii := rhash(i, c, str);
inc(i); { в случае, если адрес, выданный rhash, тоже занят, продолжаем поиск }
end;
end;
end; |
|
| Pascal | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| procedure DeleteHash(var j, n: integer; c: integer; var str: string);
{
Процедура удаления элемента по адресу в таблице.
Здесь j - номер вводимого элемента, c - шаг
}
var
i, ii: integer;
begin
i := 1; { переменная для rhash }
writeln('Введите элемент для удаления:');
readln(str); { вводим элемент }
ii := hash(str); { вычисляем его адрес }
while true do
begin
if ii <= maxn then
begin
{ ищем в таблице }
if (table[ii].mas = '') or ((table[ii].mas = str) and (table[ii].flag = true)) then
begin
writeln('Элемент не найден');
break;
end;
{ находим }
if (table[ii].mas = str) and (table[ii].flag = false) then
begin
{
Помечаем ячейку как свободную. Элемент при этом не удаляем.
Добавляемый в нее элемент просто перезапишет пред. значение
}
table[ii].flag := true;
writeln('Элемент удален');
inc(n);
dec(j); { элемент удален, уменьшаем счетчик }
break;
end;
end;
{
Поиск другого адреса. Это значит, что элемент был
добавлен в таблицу с применением функции rhash, т.е. выдачей
ему нового адреса из-за конфликта с другим элементом.
}
ii := rhash(i, c, str);
inc(i); { переменная для rhash }
end;
end; |
|
| Pascal | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| procedure SearchHash(c: integer; var str: string);
{
Процедура для поиска элемента в таблице по хеш-адресу.
Здесь c - шаг
}
var
i, ii: integer;
begin
i := 1; { переменная для rhash }
write('Введите элемент для поиска: ');
readln(str); { вводим элемент для поиска }
ii := hash(str); { вычисляем его адрес в таблице }
while true do
begin
if ii <= maxn then
begin
{ ищем }
if (table[ii].mas = '') or (table[ii].flag = true) then
begin
writeln('Элемент не найден');
break;
end;
{ нашли }
if (table[ii].mas = str) and (table[ii].flag = false) then
begin
writeln('Адрес: ', ii, ' сравнений: ', i);
break; { прекращаем поиск }
end;
end; {
Поиск другого адреса. Это значит, что элемент был
добавлен в таблицу с применением функции rhash, т.е. выдачей
ему нового адреса из-за конфликта с другим элементом.
}
ii := rhash(i, c, str);
{
rhash присвоил недопустимый адрес
для ячейки или ячейка со стандартным адресом пуста
}
inc(i); { переменная для rhash }
end;
end; |
|
| Pascal | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
| uses
crt;
const
MAXn = 7000; { размерность таблицы }
{ формирование типа хеш-таблицы }
type
arr = record
mas: string[7]; { элемент в таблице }
flag: boolean; { флаг для пометки просмотров }
end;
var
table: array [0..mAxN] of arr; { таблица представлена массивом записей }
str: string;
q: char;
j, c, n: integer;
procedure initArray;
{
Процедура инициализации массива (хеш-таблицы).
Массив типа string, '' - пустая ячейка.
}
var
j: integer;
begin
for j := 0 to maxn do
begin
table[j].mas := '';
table[j].flag := true;
end;
end;
{--------------------------------------------------------------------}
function hash(str: string): integer;
{
Хеш-функция. Задает адрес для элемента в массиве.
str - элемент, которому необходимо назначить адрес
}
begin
{
Хеш-функция описана ниже, для занесения элемента
в таблицу нам нужно, чтобы элемент был как минимум из двух символов.
Поэтому дописываем пробелов для получения корректного адреса.
Само значение добавляемого элемента при этом не изменится.
}
if length(str) = 1 then
str := ' ' + str + ' ';
{ к примеру, сумма кодов второй и последней букв элемента }
hash := ord(str[2]) + ord(str[length(str)]);
end;
{--------------------------------------------------------------------}
function rhash(ii: integer; var c: integer; str: string): integer;
{
Разрешение коллизий. Подбирает новый адрес для элемента,
если место, которое ему определила хеш-функция, занято.
ii - ii-й элемент последовательности проб;
c - фиксированный шаг;
str - текущий элемент.
Прим. Для того, чтобы все ячейки оказались просмотренными по одному разу,
необходимо, чтобы "с" было взаимно-простым с размером хеш-таблицы (maxn).
}
begin
{ например, такой метод - линейное пробирование }
rhash := (hash(str) + c * ii) mod maxn;
end;
{--------------------------------------------------------------------}
procedure AddHash(var j, c, n: integer; var str: string);
{
Процедура добавления элемента в таблицу. Здесь с - шаг,
j - cчетчик элементов, str - вводимая строка
}
var
i, ii: integer;
begin
{
В случае, если потребуется подбирать свободное
место для элемента в таблице, начинать всегда
нужно с начала. Поэтому i=0
}
i := 1; { переменная для rhash }
if c = 0 then { шаг не введен, значит таблица пуста }
begin
repeat
write('Размерность таблицы (<=7000): ');
readln(n);
until n <= 7000;
write('Введите шаг: ');
readln(c);
end;
if n = 0 then
writeln('Таблица заполнена')
else
begin
inc(j); { счетчик для элементов }
writeln('Элемент # ', j);
readln(str);
ii := hash(str); { получения адреса для хранения элемента в хеш-таблице }
while true do
begin
{ ячейка по определенному хеш-функцией адресу пуста }
if ii <= maxn then
begin
if (table[ii].mas = '') or (table[ii].flag = true) then
begin
table[ii].mas := str; { добавляем элемент в ячейку }
table[ii].flag := false; { помечаем как занятую }
dec(n);
break; { выходим для дальшейших операций }
end;
{ по указанному адресу лежит элемент-клон}
if ((table[ii].mas <> '') and (table[ii].mas = str)) or
(table[ii].flag = true) then
begin
table[ii].mas := str; { заменяем его (они ведь одинаковы) }
table[ii].flag := false; { помечаем ячейку как занятую }
dec(j); { элемент заменился, значит счетчик не увеличиваем }
break; { выходим для дальшейших операций }
end;
{ по указанному адресу уже есть элемент, отдичный от текущего }
if ((table[ii].mas <> '') and (table[ii].mas <> str)) or
(table[ii].flag = true) then
ii := rhash(i, c, str); { меняем адрес элементу во избежание коллизии }
{ проверяем таблицу на наличие свободного места }
end
else
ii := rhash(i, c, str);
inc(i); { в случае, если адрес, выданный rhash, тоже занят, продолжаем поиск }
end;
end;
end;
{--------------------------------------------------------------------}
procedure DeleteHash(var j, n: integer; c: integer; var str: string);
{
Процедура удаления элемента по адресу в таблице.
Здесь j - номер вводимого элемента, c - шаг
}
var
i, ii: integer;
begin
i := 1; { переменная для rhash }
writeln('Введите элемент для удаления:');
readln(str); { вводим элемент }
ii := hash(str); { вычисляем его адрес }
while true do
begin
if ii <= maxn then
begin
{ ищем в таблице }
if (table[ii].mas = '') or ((table[ii].mas = str) and (table[ii].flag = true)) then
begin
writeln('Элемент не найден');
break;
end;
{ находим }
if (table[ii].mas = str) and (table[ii].flag = false) then
begin
{
Помечаем ячейку как свободную. Элемент при этом не удаляем.
Добавляемый в нее элемент просто перезапишет пред. значение
}
table[ii].flag := true;
writeln('Элемент удален');
inc(n);
dec(j); { элемент удален, уменьшаем счетчик }
break;
end;
end;
{
Поиск другого адреса. Это значит, что элемент был
добавлен в таблицу с применением функции rhash, т.е. выдачей
ему нового адреса из-за конфликта с другим элементом.
}
ii := rhash(i, c, str);
inc(i); { переменная для rhash }
end;
end;
{--------------------------------------------------------------------}
procedure SearchHash(c: integer; var str: string);
{
Процедура для поиска элемента в таблице по хеш-адресу.
Здесь c - шаг
}
var
i, ii: integer;
begin
i := 1; { переменная для rhash }
write('Введите элемент для поиска: ');
readln(str); { вводим элемент для поиска }
ii := hash(str); { вычисляем его адрес в таблице }
while true do
begin
if ii <= maxn then
begin
{ ищем }
if (table[ii].mas = '') or (table[ii].flag = true) then
begin
writeln('Элемент не найден');
break;
end;
{ нашли }
if (table[ii].mas = str) and (table[ii].flag = false) then
begin
writeln('Адрес: ', ii, ' сравнений: ', i);
break; { прекращаем поиск }
end;
end; {
Поиск другого адреса. Это значит, что элемент был
добавлен в таблицу с применением функции rhash, т.е. выдачей
ему нового адреса из-за конфликта с другим элементом.
}
ii := rhash(i, c, str);
{
rhash присвоил недопустимый адрес
для ячейки или ячейка со стандартным адресом пуста
}
inc(i); { переменная для rhash }
end;
end;
{--------------------------------------------------------------------}
begin
clrscr;
initArray; { инициализируем хеш-таблицу }
while true do
begin
writeln('----------------------------------------');
writeln('1-Добавить; 2-Удалить; 3-Найти; 4-Выход');
writeln('----------------------------------------');
readln(q);
case q of
'1': AddHash(j, c, n, str);
'2': DeleteHash(j, n, c, str);
'3': SearchHash(c, str);
'4': break;
end;
end;
end. |
|
Обо всех ошибках и неточностях в описании прошу уведомить в комментариях, либо в ЛС. |
. И так пока не достигнет конца таблицы. Это опять же в лучшем случае, т.к. все зависит от шага (интервала k, см. выше), который пользователь задаст в начале. 
