Pascal语言的哈希表

Pascal语言中的哈希表

哈希表（Hash Table）是一种常用的数据结构，它通过将键值映射到数组的索引，使得数据的插入、查找和删除操作都能在平均时间复杂度为O(1)的情况下完成。本文将探讨如何在Pascal语言中实现哈希表，包括哈希函数的设计、冲突处理机制以及整体的实现过程。

一、哈希表的基本概念

1.1 哈希表的定义

哈希表是一种用于存储键值对数据的数据结构。它采用哈希函数将数据的键转换为数组的索引，数据可以直接通过索引快速访问。由于哈希表的特点，许多场景中需要快速查找的数据集合都适合使用哈希表来实现。

1.2 哈希函数

哈希函数是一种映射函数，它将输入的键转换为一个固定长度的值（通常是一个非负整数），这个值对应于哈希表中数组的索引。一个好的哈希函数应当具备以下特点： - 高效性：计算速度快。 - 均匀性：能够将输入映射到数组的各个位置，避免冲突。 - 可逆性差：不同的输入应尽量产生不同的输出。

1.3 冲突处理

由于哈希函数的输出范围是有限的，无论哈希函数设计得多么优秀，总是有可能出现不同的键映射到相同的索引，这种现象被称为冲突。常用的冲突处理方法有： - 开放寻址法：当发生冲突时，寻找下一个空闲的插入位置。 - 链地址法：每个数组元素不仅是一个数据项，而是一个链表（或其他数据结构），将冲突的元素存放于同一位置。

二、Pascal语言中的哈希表实现

接下来我们将用Pascal语言实现一个简单的哈希表。以下是代码结构的基本组成部分。

2.1 数据结构定义

首先定义用于存储的节点结构和哈希表的结构：

```pascal type PNode = ^TNode; TNode = record Key: string; Value: integer; Next: PNode; // 处理冲突的链表指针 end;

THashTable = recordTable: array of PNode; // 哈希表数组Size: integer;  // 哈希表大小
end;

```

上述代码定义了节点结构体 TNode，其中 Key 和 Value 用于存储键值对，而 Next 指向下一个节点，形成链表。THashTable 结构体则包含一个动态数组 Table 和哈希表的大小。

2.2 哈希函数

接下来，我们实现一个简单的哈希函数。在这个函数中，我们将根据字符串键的 ASCII 值和表的大小计算索引：

pascal function HashFunction(Key: string; Size: integer): integer; var Hash: integer; i: integer; begin Hash := 0; for i := 1 to Length(Key) do Hash := (Hash + Ord(Key[i])) mod Size; HashFunction := Hash; end;

2.3 初始化哈希表

我们需要一个函数来初始化哈希表：

pascal procedure InitializeHashTable(var HT: THashTable; Size: integer); var i: integer; begin HT.Size := Size; SetLength(HT.Table, Size); for i := 0 to Size - 1 do HT.Table[i] := nil; // 初始化所有位置为空 end;

2.4 插入元素

插入元素需要找到合适的哈希位置并处理冲突：

```pascal procedure Insert(var HT: THashTable; Key: string; Value: integer); var Index: integer; NewNode: PNode; begin Index := HashFunction(Key, HT.Size);

// 创建新节点
New(NewNode);
NewNode^.Key := Key;
NewNode^.Value := Value;
NewNode^.Next := nil;// 插入到链表头部
if HT.Table[Index] = nil then
beginHT.Table[Index] := NewNode;
end
else
beginNewNode^.Next := HT.Table[Index];HT.Table[Index] := NewNode;
end;

end; ```

在这里，首先使用哈希函数计算出索引，如果该位置为空，则直接插入新节点；如果不为空，则将新节点插入到链表的头部。

2.5 查找元素

查找函数需要在链表中遍历节点以查找对应的键：

```pascal function Search(var HT: THashTable; Key: string): integer; var Index: integer; Current: PNode; begin Index := HashFunction(Key, HT.Size); Current := HT.Table[Index];

while Current <> nil do
beginif Current^.Key = Key thenbeginSearch := Current^.Value; // 找到返回值Exit;end;Current := Current^.Next;
end;Search := -1; // 如果未找到，返回-1

end; ```

2.6 删除元素

删除元素的过程与查找类似，需要遍历链表并找到要删除的节点：

```pascal procedure Delete(var HT: THashTable; Key: string); var Index: integer; Current, Prev: PNode; begin Index := HashFunction(Key, HT.Size); Current := HT.Table[Index]; Prev := nil;

while Current <> nil do
beginif Current^.Key = Key thenbeginif Prev = nil thenHT.Table[Index] := Current^.Next // 删除头节点elsePrev^.Next := Current^.Next; // 删除中间节点Dispose(Current);Exit;end;Prev := Current;Current := Current^.Next;
end;

end; ```

三、完整程序示例

将上面的所有部分组合在一起，形成一个完整的哈希表示例程序。

```pascal program HashTableDemo;

type PNode = ^TNode; TNode = record Key: string; Value: integer; Next: PNode; end;

THashTable = recordTable: array of PNode;Size: integer;
end;

function HashFunction(Key: string; Size: integer): integer; var Hash: integer; i: integer; begin Hash := 0; for i := 1 to Length(Key) do Hash := (Hash + Ord(Key[i])) mod Size; HashFunction := Hash; end;

procedure InitializeHashTable(var HT: THashTable; Size: integer); var i: integer; begin HT.Size := Size; SetLength(HT.Table, Size); for i := 0 to Size - 1 do HT.Table[i] := nil; end;

procedure Insert(var HT: THashTable; Key: string; Value: integer); var Index: integer; NewNode: PNode; begin Index := HashFunction(Key, HT.Size); New(NewNode); NewNode^.Key := Key; NewNode^.Value := Value; NewNode^.Next := HT.Table[Index]; HT.Table[Index] := NewNode; end;

function Search(var HT: THashTable; Key: string): integer; var Index: integer; Current: PNode; begin Index := HashFunction(Key, HT.Size); Current := HT.Table[Index]; while Current <> nil do begin if Current^.Key = Key then begin Search := Current^.Value; Exit; end; Current := Current^.Next; end; Search := -1; end;

procedure Delete(var HT: THashTable; Key: string); var Index: integer; Current, Prev: PNode; begin Index := HashFunction(Key, HT.Size); Current := HT.Table[Index]; Prev := nil; while Current <> nil do begin if Current^.Key = Key then begin if Prev = nil then HT.Table[Index] := Current^.Next else Prev^.Next := Current^.Next; Dispose(Current); Exit; end; Prev := Current; Current := Current^.Next; end; end;

var HT: THashTable; Key: string; Value: integer;

begin InitializeHashTable(HT, 10); Insert(HT, 'apple', 1); Insert(HT, 'banana', 2); Insert(HT, 'orange', 3);

WriteLn('查找 apple: ', Search(HT, 'apple')); // 输出 1
WriteLn('查找 cherry: ', Search(HT, 'cherry')); // 输出 -1Delete(HT, 'banana');
WriteLn('查找 banana: ', Search(HT, 'banana')); // 输出 -1

end. ```