首页 > 代码库 > 散列表
散列表
散列表是一种ADT。散列表的实现常常叫做散列（hashing），它是一种用于以常数平均时间执行插入、删除、查找的技术。需要元素间任何排序信息的操作将不会得到有效的支持。例如FindMax、FindMax、按序输出等。
散列表的关键是确定散列函数，《数据结构与算法分析》中提到了几种散列函数，但都不是完美的。能解决冲突但有可能散列表占用率不高。字符串中的字符不是随机出现，这也影响到了散列表的利用率。散列函数需要满足的要求：
- 尽量把键值均匀分布
- 散列函数必须容易计算
书中提到了一个好的散列函数，剩下的问题就是对冲突的消除，两种简单的方法：
- 分离链接法（开散列）：将散列到同一个值的所有元素保留到一个链表中。
- 开放定址法（闭散列）：如果发生冲突，选择另外的单元，直到找出空单元。
分离链接法：
插入操作时，一般将新元素插入到对应表的前端，不仅因为方便，而且还因为新近插入的元素最有可能最先被访问。下面是代码：
#include <stdio.h>
typedef int ElementType;
typedef struct ListNode *Position;
struct ListNode
{
ElementType Element;
Position Next;
};
typedef struct HashTbl *HashTable;
struct HashTbl
{
int TableSize;
Position *TheLists; // 指针数组
};
HashTable InitializeTable(int TableSize)
{
HashTable ht;
int i;
ht = malloc(sizeof(struct HashTbl));
if (ht == NULL)
return -1;
ht->TableSize = TableSize;
ht->TheLists = calloc(TableSize, sizeof(Position));
if (ht->TheLists == NULL)
return -1;
return ht;
}
// 散列函数
int Hash(ElementType Key, int TableSize)
{
return Key % TableSize;
}
Position Find(HashTable H, ElementType Key)
{
Position p;
p = H->TheLists[Hash(Key, H->TableSize)];
while (p != NULL && p->Element != Key) // 这里只能对数值型key进行比较
p = p->Next;
return p;
}
// 键值不允许重复
void Insert(HashTable H, ElementType Key)
{
Position *p; // 如果不使用这个双重指针，那么需要计算多次散列函数
Position tmp;
if (Find(H, Key) == NULL) // 元素不存在
{ // 插入链表头部
p = &(H->TheLists[Hash(Key, H->TableSize)]);
tmp = malloc(sizeof(struct ListNode));
tmp->Element = Key;
tmp->Next = *p;
*p = tmp;
}
}
int main(void)
{
HashTable table;
Position p;
table = InitializeTable(100);
Insert(table, 21);
Insert(table, 24);
Insert(table, 43);
Insert(table, 35);
p = Find(table, 43);
if (p != NULL)
printf("Find it!\n");
else
printf("Not found!\n");
return 0;
}这个程序改了我半天，其中有个很隐蔽的问题，就是在插入节点时指针的修改。书中给每个链表都添加了一个头节点，使得插入变得方便，这里我把头节点去掉以节省空间，但为了能够正确插入，我引入了一个双重指针Position *p。
分离链接法的缺陷在于使用了指针，以及需要动态分配空间，造成了速度上的减慢。
开放定址法：
- 线性探测法：发生冲突，顺序查找空闲地址，容易发生一次聚集。
- 平方探测法：排除一次聚集，但散列到同一个位置上的元素将探测相同的备选单元，这称为二次聚集。
- 双散列：用另一个散列函数解决冲突，但计算需要花费代价。
平方探测代码：
#include <stdio.h>
typedef int ElementType;
typedef int Position;
enum KindOfEntry { Legitimate, Empty, Deleted };
struct HashEntry
{
ElementType Element;
enum KindOfEntry Info;
};
typedef struct HashTbl *HashTable;
struct HashTbl
{
int TableSize;
struct HashEntry *array;
};
HashTable InitializeTable(int TableSize)
{
HashTable H;
int i;
H = malloc(sizeof(struct HashTbl));
if (H == NULL)
return -1;
H->TableSize = TableSize;
H->array = malloc(TableSize * sizeof(struct HashEntry));
if (H->array == NULL)
return -1;
for (i = 0; i < TableSize; i++)
H->array[i].Info = Empty;
return H;
}
Position Hash(ElementType Key, int TableSize)
{
return Key % TableSize;
}
Position Find(HashTable H, ElementType Key)
{
Position p;
int num = 0;
p = Hash(Key, H->TableSize);
while (H->array[p].Info != Empty && H->array[p].Element != Key)
{
p += ++num * 2 -1; // 平方操作可以优化
if (p >= H->TableSize)
p -= H->TableSize; // 绕回去
}
return p; // 返回找到的索引或一个正确的插入位置
}
void Insert(HashTable H, ElementType Key)
{
Position p;
p = Find(H, Key);
if (H->array[p].Info != Legitimate) // 如果找到的位置未被占用，则插入
{
H->array[p].Element = Key;
H->array[p].Info = Legitimate;
}
}
void Delete(HashTable H, ElementType Key) // 删除操作采用慵懒删除
{
Position p;
p = Find(H, Key);
if (H->array[p].Info == Legitimate)
H->array[p].Info = Deleted;
}
int main(void)
{
HashTable table;
Position p;
table = InitializeTable(20);
Insert(table, 3);
Insert(table, 1);
Insert(table, 23);
Insert(table, 34);
Insert(table, 8);
p = Find(table, 34);
if (table->array[p].Info == Legitimate)
printf("%d", table->array[p].Element);
return 0;
}这里可以使用一个技巧省略平方操作：
p += ++num * 2 -1;
要求的值是基于前面的结果，避免了重复计算。乘以2相当于移位操作，效率很高。每一个节点HashEntry都保存有实际存储元素和当前状态Info，方便插入和删除操作。
参考：
《数据结构与算法分析》 P111.
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。