Хэш-таблица

В программировании хеш-таблица — это структура данных, реализующая интерфейс ассоциативного массива, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу.

Существует два варианта хэш-таблиц: с прямой и открытой адресацией. Хэш-таблица содержит некоторый массив 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