当前位置 博文首页 > CrazyCatJack：《数据结构与算法分析》学习笔记-第五章-散列
散列表只支持二叉查找树所允许的一部分操作。散列是一种用于以常数平均时间执行插入、删除和查找的技术。但是，那些需要元素间任何排序信息的操作将不会得到有效的支持，例如FindMin、FindMax以及以线性时间将排过序的整个表进行打印的操作都是散列所不支持的
Index
Hash(const char *Key, int TableSize)
{
unsigned int HashVal = 0;
while (*Key != '\0')
//HashVal = (HashVal << 5) + *Key++;
HashVal = (HashVal << 5) ^ *Key++;
return HashVal % TableSize;
}
如果关键字特别长，那么散列函数计算起来会花过多的时间，而且前面的字符还会左移出最终的结果。因此这样情况下，不使用所有的字符。此时关键字的长度和性质会影响选择。例如只取奇数位置上的字符来实现散列函数。这里的思想是用计算散列函数省下来的时间来补偿由此产生的对均匀分布函数的轻微干扰
。
#define MINTABLESIZE 11
struct HashTbl;
typedef struct HashTbl *HashTable;
typedef Stack List;
struct HashTbl
{
int TableSize;
List *TheLists;
};
HashTable
InitializeTable(int TableSize)
{
if (TableSize < MINTABLESIZE) {
printf("TableSize too small\n");
return NULL;
}
HashTable H = NULL;
H = (HashTable)malloc(sizeof(struct HashTbl));
if (H == NULL) {
printf("HashTable malloc failed\n");
return NULL;
}
memset(H, 0, sizeof(struct HashTbl));
H->TableSize = GetNextPrime(TableSize);
H->TheLists = (List *)malloc(sizeof(List) * H->TableSize);
if (H->TheLists == NULL) {
printf("HashTable TheLists malloc failed\n");
free(H);
H = NULL;
return NULL;
}
memset(H->TheLists, 0, sizeof(List) * H->TableSize);
int cnt, cnt2;
for (cnt = 0; cnt < H->TableSize; cnt++) {
H->TheLists[cnt] = CreateStack();
if (H->TheLists[cnt] == NULL) {
printf("H->TheLists[%d]malloc failed\n", cnt);
for (cnt2 = 0; cnt2 < cnt; cnt2++) {
if (H->TheLists[cnt2] != NULL) {
DistroyStack(H->TheLists[cnt2]);
H->TheLists[cnt2] = NULL;
}
}
if (H->TheLists != NULL) {
free(H->TheLists);
H->TheLists = NULL;
}
if (H != NULL) {
free(H);
H = NULL;
}
return NULL;
}
}
return H;
}
PtrToNode
Find(ElementType Key, HashTable H)
{
if (H == NULL) {
printf("ERROR: H is NULL\n");
return NULL;
}
PtrToNode tmp = NULL;
tmp = H->TheLists[GetHashSubmit(Key, H->TableSize)]->Next;
while (tmp != NULL && tmp->Element != Key) {
tmp = tmp->Next;
}
return tmp;
}
void
Insert(ElementType Key, HashTable H)
{
if (H == NULL) {
printf("HashTable is NULL\n");
return;
}
if (0 != Push(Key, H->TheLists[GetHashSubmit(Key, H->TableSize)])) {
printf("Insert Key failed\n");
}
}
证明：
令表的大小TableSize是一个大于3的素数。我们证明，前[TableSize / 2]个备选位置是互异的。
h(X) + i^2(mod TableSize)和h(X) + j^2(mod TableSize)是这些位置中的两个，其中0 < i, j <= [TableSize / 2]。为推出矛盾，假设这两个位置相同，但i != j，于是
1) h(X) + i^2 = h(X) + j^2 (mod TableSize)
2) i^2 - j^2 = 0
3) (i + j)(i - j) = 0
所以i = -j或者i = j，因为i != j，且i,j都大于0,所以前[TableSize / 2]个备选位置是互异的
HashTable
ReHash(HashTable H)
{
if (H == NULL) {
printf("H is NULL!\n");
return NULL;
}
int cnt;
int OldTableSize = H->TableSize;
Cell *OldCells = H->TheCells;
HashTable newTable = InitializeTable(2 * OldTableSize);
for (cnt = 0; cnt < OldTableSize; cnt++) {
if (OldCells[cnt].Info == Legitimate) {
Insert(newTable, OldCells[cnt].Element);
}
}
DestroyTable(H);
return newTable;
}
本文作者: CrazyCatJack
本文链接: https://www.cnblogs.com/CrazyCatJack/p/13340018.html
版权声明:本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
关注博主:如果您觉得该文章对您有帮助，可以点击文章右下角推荐一下，您的支持将成为我最大的动力！
