散列表

✍ dations ◷ 2024-10-18 22:31:13 #数据结构,搜寻算法

散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存储存位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

一个通俗的例子是，为了查找电话簿中某人的号码，可以创建一个按照人名首字母顺序排列的表（即建立人名 $x {\displaystyle x}$ $x$ 到首字母 $F(x)$ $F(x)$ 的一个函数关系），在首字母为W的表中查找“王”姓的电话号码，显然比直接查找就要快得多。这里使用人名作为关键字，“取首字母”是这个例子中散列函数的函数法则 $F()$ $F()$ ，存放首字母的表对应散列表。关键字和函数法则理论上可以任意确定。

散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快定位。

为了知道冲突产生的相同散列函数地址所对应的关键字，必须选用另外的散列函数，或者对冲突结果进行处理。而不发生冲突的可能性是非常之小的，所以通常对冲突进行处理。常用方法有以下几种：

显示线性探测填装一个散列表的过程：

聚集（Cluster，也翻译做“堆积”）的意思是，在函数地址的表中，散列函数的结果不均匀地占据表的单元，形成区块，造成线性探测产生一次聚集（primary clustering）和平方探测的二次聚集（secondary clustering），散列到区块中的任何关键字需要查找多次试选单元才能插入表中，解决冲突，造成时间浪费。对于开放定址法，聚集会造成性能的灾难性损失，是必须避免的。

在C语言中，实现以上过程的简要程序：

 1 // HashTable 2 InitializeTable(int TableSize) { 3     HashTable H; 4     int i; 5     // 為散列表分配空間 6     // 有些编譯器不支持為struct HashTable 分配空間，聲稱這是一個不完全的結構， 7     // 可使用一个指向HashTable的指針為之分配空間。 8     // 如：sizeof(Probe)，Probe作为HashTable在typedef定義的指針。 9     H = malloc(sizeof(struct HashTable));10     // 散列表大小为一个質数11     H->TableSize = Prime;12     // 分配表所有地址的空間13     H->Cells = malloc(sizeof(Cell) * H->TableSize);14     // 地址初始為空15     for (i = 0; i < H->TableSize; i++)16         H->Cells.info = Empty;17     return H;18 }

查找空单元并插入：

 1 // Position 2 Find(ElementType Key, HashTable H) { 3     Position Current; 4     int CollisionNum; 5     // 冲突次数初始为0 6     // 通過表的大小對關鍵字進行處理 7     CollisionNum = 0; 8     Current = Hash( Key, H->TableSize ); 9     // 不為空時進行查詢10     while (H->Cells.info != Empty &&11             H->Cells.Element != Key) {12         Current = ++CollosionNum * ++CollisionNum;13         // 向下查找超過表範圍時回到表的開頭14         if (Current >= H->TableSize)15             Current -= H->TableSize;16     }17     return Current;18 }

分离连接法

查找效率

散列表的查找过程基本上和造表过程相同。一些关键码可通过散列函数转换的地址直接找到，另一些关键码在散列函数得到的地址上产生了冲突，需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中，产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以，对散列表查找效率的量度，依然用平均查找长度来衡量。

查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。影响产生冲突多少有以下三个因素：

散列表的载荷因子定义为： $\alpha$ $\alpha$ = 填入表中的元素个数 / 散列表的长度

$\alpha$ $\alpha$ 是散列表装满程度的标志因子。由于表长是定值， $\alpha$ $\alpha$ 与“填入表中的元素个数”成正比，所以， $\alpha$ $\alpha$ 越大，表明填入表中的元素越多，产生冲突的可能性就越大；反之， $\alpha$ $\alpha$ 越小，标明填入表中的元素越少，产生冲突的可能性就越小。实际上，散列表的平均查找长度是载荷因子 $\alpha$ $\alpha$ 的函数，只是不同处理冲突的方法有不同的函数。

对于开放定址法，荷载因子是特别重要因素，应严格限制在0.7-0.8以下。超过0.8，查表时的CPU缓存不命中（cache missing）按照指数曲线上升。因此，一些采用开放定址法的hash库，如Java的系统库限制了荷载因子为0.75，超过此值将resize散列表。

Linux操作系统在物理文件系统与块设备驱动程序之间引入了“缓冲区缓存”（BufferCache，简称bcache）。当读写磁盘文件的数据，实际上都是对bcache操作，这大大提高了读写数据的速度。如果要读写的磁盘数据不在bcache中，即缓存不命中（miss），则把相应数据从磁盘加载到bcache中。一个缓存数据大小是与文件系统上一个逻辑块的大小相对应的（例如1KiB字节），在bcache中每个缓存数据块用struct buffer_head记载其元信息：

 1 struct buffer_head { 2     char *b_data;               // 指向缓存的数据块的指针 3     unsigned long b_blocknr;    // 逻辑块号 4     unsigned short b_dev;       // 设备号 5     unsigned char b_uptodate;   // 缓存中的数据是否是最新的 6     unsigned char b_dirt;       // 缓存中数据是否为脏数据 7     unsigned char b_count;      // 这个缓存块被引用的次数 8     unsigned char b_lock;       // b_lock表示这个缓存块是否被加锁 9     struct task_struct *b_wait; // 等待在这个缓存块上的进程10     struct buffer_head *b_prev; // 指向缓存中相同hash值的下一个缓存块11     struct buffer_head *b_next; // 指向缓存中相同hash值的上一个缓存块12     struct buffer_head *b_prev_free; // 缓存块空闲链表中指向下一个缓存块13     struct buffer_head *b_next_free; // 缓存块空闲链表中指向上一个缓存块14 };

整个bcache以struct buffer_head为基本数据单元，组织为一个封闭定址（close addressing，即“单独链表法”解决冲突）的散列表struct buffer_head * hash_table; 散列函数的输入关键字是b_blocknr（逻辑块号）与b_dev（设备号）。计算hash值的散列函数表达式为：

其中NR_HASH是散列表的条目总数。发生“ 冲突”的struct buffer_head，以b_prev与b_next指针组成一个双向（不循环）链表。bcache中所有的struct buffer_head，包括使用中不空闲与未使用空闲的struct buffer_head，以b_prev_free和b_next_free指针组成一个双向循环链表free_list，其中未使用空闲的struct buffer_head放在该链表的前部。

散列表

查找效率

相关