ВУЗ:
Составители:
Рубрика:
48
ванная таблица называется хеш-таблицей с открытым хешированием. Схемати-
чески она изображена на следующем рисунке:
0
N-1
Заметим, что если в списках находится примерно равное количество элемен-
тов, то поиск одинаково эффективен для всех возможных значений. Например,
пусть N=1001 и в каждом списке максимум 3 элемента, а во всей хеш-таблице –
2048 элементов. Тогда после вычисления хеш-значения элемента последователь-
ный поиск в списке с этим номером потребует максимум
три итерации. Бинарный
же поиск потребует 11 итераций (
20482
11
= ).
Если количество элементов в разных списках отличается значительно, то эф-
фективность хеширования падает. Самый плохой случай – если один список со-
держит все элементы, а остальные списки – пустые. Для поиска в этом случае мо-
жет потребоваться 2048 итераций. Поэтому следует стремиться к тому, чтобы
хеш-функция хорошо перемешивала элементы, заполняя хеш-таблицу
как можно
более равномерно для любых значений (отсюда и название метода – хеширование,
т.е. перемешивание). В частности, именно поэтому число N стремятся выбирать
простым.
Реализуем хеш-таблицу целых в виде класса на основе динамического масси-
ва списков. Поскольку список обеспечивает удаление элемента, наша хеш-
таблица будет также позволять удалять элементы.
uses IntList;
const
sz = MaxInt div sizeof(List);
type
PArr = ^Arr;
Arr = array [0..sz-1] of List;
HashTable = class
private
a: PArr;
N: integer;
public
constructor Create(nn: integer);
destructor Destroy;
