- Хэш-таблица
-
В программировании хеш-таблица — это структура данных, реализующая интерфейс ассоциативного массива, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу.
Существует два варианта хэш-таблиц: с прямой и открытой адресацией. Хэш-таблица содержит некоторый массив H, элементы которого есть пары (хэш-таблица с открытой адресацией) или списки пар (хэш-таблица с прямой адресацией).
Выполнение операции в хэш-таблице начинается с вычисления хэш-функции от ключа. Получающееся хэш-значение i = hash(key) играет роль индекса в массиве H. Затем выполняемая операция (добавление, удаление или поиск) перенаправляется объекту, который хранится в соответствующей ячейке массива H[i].
Ситуация, когда для различных ключей получается одно и то же хэш-значение, называется коллизией (collision).
Число хранимых элементов делённое на размер массива H (число возможных значений хэш-функции) называется коэффициентом заполнения хэш-таблицы (load factor) и является важным параметром, от которого зависит среднее время выполнения операций.
Содержание
Свойства хэш таблицы
Важное свойство хэш-таблицы состоит в том, что все три операции в среднем выполняются за время O(1). Но при этом не гарантируется, что время выполнения отдельной операции мало. Это связано с тем, что при достижении некоторого значения коэффициента заполнения необходимо осуществлять перестройку индекса хэш-таблицы: увеличить значение размера массива H и заново добавить в пустую хэш-таблицу все пары.
Разрешение коллизий
Существует несколько способов разрешения колизий.
Прямая адресация
В массиве H хранятся списки пар. Коллизии просто приводят к тому, что появляются списки длиной более одного элемента.
Среднее время выполнения операций в хэш-таблице с прямой адресацией равно коэффициенту заполнения.
Открытая адресация
В массиве H хранятся сами пары. В случае возникновения коллизии, алгоритм поиска (удаления, добавления) объекта просто перемещается на ячейку вправо до момента разрешения коллизии. Разрешение коллизии происходит при достижении пустой ячейки или ячейки, в котором хранится пара с заданным ключом.
Размер шага смещения вправо может зависеть от значения ключа и вычисляться с помощью второй хэш-функции. Данная техника называется двойным хэшированием с открытой адресацией.
Ниже представлен простой код её демонстрирующий.
/* P должно быть простым числом! */ #define P 30011 char *dict[P]; char dict_size = 0; int hash_index[P]; // необходимо инициализировать элементы значением -1 /* Функция get_id возвращает индекс слова word в массиве dict. * При этом происходит добавление слова word в словарь dict, если его там нет. */ int get_id(const char *word) { unsigned int len = 0, h1 = 0, h2 = 0; const char *p = word; // Вычислим две хэш-функции от слова word: // h1 лежит в [0..P-1], h2 лежит в [1..P-1] do { h1 *= 17; h1 += 13*(*p); h2 *= 13; h2 += 17*(*p); len++; } while ( *(p++) ); h1 %= P; h2 %= (P-1); h2 += 1; while ( hash_index[h1] != -1 ) { if ( strcmp (word, dict[ hash_index[h1] ] ) == 0 ) { return hash_index[h1]; } h1 += h2; h1 %= P; } len++; dict[dict_size] = (char*) malloc ( len * sizeof(char) ); strcpy ( dict[dict_size], word ); hash_index[h1] = dict_size; return dict_size++; }
Пример полной реализации
unit Unit1; interface uses Dialogs; type PStudent = ^TStudent; TRStudent = record id: Integer; Family: string; Name: string; Patronymic: string; end; TStudent = record Data: TRStudent; Next: PStudent; end; TProc = procedure (Student: TRStudent; Row, Col: Integer); TProcList = procedure (Student: TRStudent; N: Integer); TProcData = procedure (Student: PStudent); THashTable = class; TLList = class; TMas = array of TLList; TLList = class private First: PStudent; public constructor Create(); destructor Destroy(); override; procedure Add(Student: TRStudent); function Delete(id: Integer): Boolean; procedure Clear(); function Search(id: Integer): PStudent; procedure Process(Proc: TProc; Row: Integer); procedure ProcessData(Proc: TProcData); procedure ProcessHelp(var H: THashTable); end; THashTable = class private List, ListHelp: array of TLList; CountEL: Integer; FirstCount: Integer; aCount: Integer; procedure setValue(Value: Integer); public constructor Create(iCount: Integer = 1); destructor Destroy(); override; procedure Clear(); procedure Insert(Student: TRStudent); procedure Delete(id: Integer); function Search(id: Integer): PStudent; procedure Help(); procedure Process(Proc: TProc); procedure ProcessData(Proc: TProcData); property Count: Integer read aCount write setValue default 0; end; implementation uses Math; procedure TLList.Add(Student: TRStudent); var current: PStudent; begin New(current); current.Data:= Student; current^.Next:= First; First:= current; end; procedure TLList.Clear; var P: PStudent; begin while First <> nil do begin P:= First^.Next; Dispose(First); First:= P; end; end; constructor TLList.Create(); begin inherited Create; First:= nil; end; function TLList.Delete(id: Integer): Boolean; var back, current: PStudent; begin Result:= false; back:= nil; current:= First; while (current <> nil) and (current.Data.id <> id) do begin back:= current; current:= current^.Next; end; if current <> nil then begin if back <> nil then back^.Next:= current^.Next else First:= current^.Next; Dispose(current); Result:= True; end; end; destructor TLList.Destroy; begin Clear(); inherited Destroy; end; procedure TLList.Process; var current: PStudent; n: Integer; begin n:= -1; current:= First; while current <> nil do begin inc(n); Proc(current.Data, Row, n); current:= current^.Next; end; end; procedure TLList.ProcessData(Proc: TProcData); var current: PStudent; begin current:= First; while current <> nil do begin Proc(current); current:= current^.Next; end; end; procedure TLList.ProcessHelp(var H: THashTable); var current: PStudent; begin current:= First; while current <> nil do begin H.Insert(current.Data); current:= current^.Next; end; end; function TLList.Search(id: Integer): PStudent; var current: PStudent; begin current:= First; while (current <> nil) and (current.Data.id <> id) do current:= current^.Next; Result:= current; end; { THashTable } procedure THashTable.Clear; var i: Integer; begin for i := 0 to Count - 1 do List[i].Clear; CountEL:= 0; Count:= FirstCount; end; constructor THashTable.Create; var i: Integer; begin inherited Create; Count:= iCount; FirstCount:= iCount; CountEL:= 0; List:= nil; SetLength(List, Count); for i:= 0 to Count - 1 do List[i]:= TLList.Create; end; procedure THashTable.Delete(id: Integer); begin if List[id mod Count].Delete(id) then Dec(CountEL); end; destructor THashTable.Destroy; begin Clear; List:= nil; inherited Destroy(); end; procedure THashTable.Help; var i: Integer; begin i:= Count*2; if CountEL > i then begin ListHelp:= List; List:= nil; Count:= i + 1; CountEL:= 0; SetLength(List, Count); for i:= 0 to Count - 1 do List[i]:= TLList.Create; for i:= 0 to High(ListHelp) do ListHelp[i].ProcessHelp(Self); ListHelp:= nil; end; end; procedure THashTable.Insert(Student: TRStudent); var n: Integer; P: PStudent; begin if Student.id >= 0 then begin n:= Student.id mod Count; if List[n].Search(Student.id) = nil then begin List[n].Add(Student); Inc(CountEL); end; end; Help; end; procedure THashTable.Process; var i: Integer; begin for i:= 0 to Count - 1 do List[i].Process(Proc, i); end; procedure THashTable.ProcessData; var i: Integer; begin for i:= 0 to Count - 1 do List[i].ProcessData(Proc); end; function THashTable.Search(id: Integer): PStudent; begin Result:= List[id mod Count].Search(id); end; procedure THashTable.setValue(Value: Integer); begin aCount:= Value; end; end.
См. также
Ссылки
- Кормен, Т., Лейзерсон, Ч., Ривест, Р. Алгоритмы: построение и анализ = Introduction to Algorithms / Пер. с англ. под ред. А. Шеня. — М.: МЦНМО, 2002. — 960 с. — ISBN 5-900916-37-5
- Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд.. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4
Wikimedia Foundation. 2010.