哈希算法

​ 大家好,今天我就为大家介绍一下哈希算法,在我的理解里:哈希算法本质上就是通过 一种"空间换时间"的算法来实现快速的查找,它规定每一个值都有一个"编号",每个编号都是不相同的,它通过分组每一组,而每组是通过这个编号值 % 他的分组大小来确定的,这样的来分组的话,在以后查找一个数的时候,只要知道它的"编号值",通过"编号值" % 分配的数组大小就能确定在哪一个分组中,之后在在这一组里面查找对应的"编号值"就能找到对应该数.

//比如说,有 从 1 - 24的编号值,把他们分成6组来排列,通过他自己的编号值 % (分的6组)来进行存放到哪一组中.

编号除 6 余数为 0 的为第一组：6121824编号除 6 余数为 1 的为第二组：171319编号除 6 余数为 2 的为第三组：281420编号除 6 余数为 3 的为第四组：391521编号除 6 余数为 4 的为第五组：4101622编号除 6 余数为 5 的为第六组：5111723

以这种编号的方式就是高效的散列，我们俗称“哈希”！

以上过程是通过把关键码值 key（编号）映射到表中一个位置(数组的下标)来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

//以下是通过"哈希算法"单链表实现的代码:

#include #include <Windows.h> #include “_Hash.h”

using namespace std;

typedef int ElemType;

typedef struct _LinkNode { int key; ElemType data; struct _LinkNode *next; }_LinkNode;

typedef struct _Hash { _LinkNode* *Thelists; int TableSize; }_Hash;

//哈希表的初始化 _Hash* HashInit(int TableSize);

//根据key查找位置 _LinkNode* FindKey(_Hash *hash, int key);

//哈希表的前插法 bool HashInsert_front(_Hash *hash, int key, ElemType data);

//哈希表的后插法 bool HashInsert_back(_Hash *hash, int key, ElemType data);

//哈希表的删除 bool HashDelete(_Hash *hash, int key);

//哈希表的输出 void HashPrint(const _Hash *hash);

//哈希表的释放 void HashDestory(_Hash *hash);

//哈希算法 int Hash(int key, int TableSize) { return (key % TableSize); }

//根据key查找位置 _LinkNode* FindKey(_Hash *hash, int key) { assert(hash != NULL && hash->Thelists != NULL);

int index = Hash(key, hash->TableSize); _LinkNode *L = hash->Thelists[index]; _LinkNode *p = L->next; while (p != NULL && key != p->key) { p = p->next; } //p:NULL 没有找到key true:找到key return p;

}

//哈希表的初始化 _Hash* HashInit(int TableSize) { if (TableSize < 1) return NULL;

_Hash *hash = new _Hash; if (!hash) return NULL; //分配哈希桶 hash->TableSize = TableSize; //哈希桶分配空间 hash->Thelists = new _LinkNode * [TableSize]; if (!hash->Thelists) { delete hash; return NULL; } int i = -1; while (++i < TableSize) { hash->Thelists[i] = new _LinkNode; if (!hash->Thelists[i]) { delete[] hash->Thelists; delete hash; return NULL; } hash->Thelists[i]->data = -1; hash->Thelists[i]->key = 0; hash->Thelists[i]->next = NULL; } return hash;

}

//哈希表的前插法 bool HashInsert_front(_Hash *hash, int key, ElemType data) { if (!hash || !hash->Thelists) return false;

//true:有对应的key if (FindKey(hash, key)) return false; //没有找到key可以插入key值 int index = Hash(key, hash->TableSize); _LinkNode *L = hash->Thelists[index]; if (!L) return false; //分配新空间的值 _LinkNode *node = new _LinkNode; if (!node) return false; node->key = key; node->data = data; node->next = L->next; L->next = node; return true;

}

//哈希表的后插法 bool HashInsert_back(_Hash *hash, int key, ElemType data) { if (!hash || !hash->Thelists) return false;

//true:有对应的key if (FindKey(hash, key)) return false; //没有找到key可以插入key值 int index = Hash(key, hash->TableSize); _LinkNode *L = hash->Thelists[index]; if (!L) return false; while (L->next != NULL) { L = L->next; } //分配新空间的值 _LinkNode *node = new _LinkNode; if (!node) return false; node->key = key; node->data = data; node->next = NULL; L->next = node; return true;

}

//哈希表的删除 bool HashDelete(_Hash *hash, int key) { if (!hash || !hash->Thelists) return false;

int index = Hash(key, hash->TableSize); _LinkNode *L = hash->Thelists[index]; _LinkNode *last = L; _LinkNode *p = last->next; while (p != NULL && key != p->key) { last = p; p = p->next; } if (p == NULL) return false; //p != NULL last->next = p->next; delete p; return true;

}

//哈希表的输出 void HashPrint(const _Hash *hash) { if (!hash || !hash->Thelists) return;

cout << "哈希表一共分配了" << hash->TableSize << "组\n"; int i = -1; while (++i < hash->TableSize) { _LinkNode *p = hash->Thelists[i]->next; printf("第%d组(余数为)[%d]: ", i + 1, i); while (p != NULL) { printf("[key:%d] ", p->key); cout << "data:" << p->data << " "; p = p->next; } printf("\n"); } printf("\n");

}

//哈希表的释放 void HashDestory(_Hash *hash) { if (!hash) return;

int i = -1; while (++i < hash->TableSize) { _LinkNode *L, *q; L = q = hash->Thelists[i]; while (q != NULL) { L = L->next; delete q; q = L; } hash->Thelists[i] = NULL; } delete[] hash->Thelists; delete hash;

}

int main(void) { _Hash *hash = HashInit(5);

int data[] = { 19,30,50,60,18,19,31,41,12,44,132,13,32,534,56,66,123,64,123,213 }; int size = sizeof(data) / sizeof(data[0]); for (int i = 0; i < size; i++) { HashInsert_back(hash, i + 1, data[i]); } HashPrint(hash); system("pause"); return 0;

}