Хэш-таблица | это... Что такое Хэш-таблица? (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.

}

Пример полной реализации

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.

См. также

Ссылки

Wikimedia Foundation.2010.