Хэш-таблица | это... Что такое Хэш-таблица? (original) (raw)
В программировании хеш-таблица — это структура данных, реализующая интерфейс ассоциативного массива, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу.
Существует два варианта хэш-таблиц: с прямой и открытой адресацией. Хэш-таблица содержит некоторый массив H, элементы которого есть пары (хэш-таблица с открытой адресацией) или списки пар (хэш-таблица с прямой адресацией).
Выполнение операции в хэш-таблице начинается с вычисления хэш-функции от ключа. Получающееся хэш-значение i = hash(k e y) играет роль индекса в массиве 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.