layout: post title: 散列查找 (哈希表) date: 2017-05-20 tag: 数据结构和算法 ---
①以关键字 key 为自变量,通过一个确定的函数 h(散列函数),计算出对应的函数值 h(key),作为数据对象的存储地址。
②可能不同的关键字会映射到同一个散列地址上,即 h(keyi) = h(keyj)(当 keyi ≠keyj),称为 "冲突 (Collision)"---- 需要某种冲突解决策略
①计算简单,以便提高转换速度;
②关键词对应的地址空间分布均匀,以尽量减少冲突。
- Eg: 56793542
- 542
- 793
- + 056
- ———
- 1391
- h(56793542) = 391
- Eg: 56793542
- 56793542
- x 56793542
- —————————
- 3225506412905764
- h(56793542) = 641
- Eg:h("abcde")='a'*324+'b'*323+'c'*322+'d'*32+'e'
- Index Hash (const char*Key,intTableSize )
- {
- unsignedinth =0;/* 散列函数值,初始化为0 */while ( *Key != '\0')/* 位移映射 */h = ( h <<5) + *Key++;
- return h % TableSize;
- }
- //哈希表平方探测法
- #include < stdio.h > #include < stdlib.h > #include < math.h > #define MAXTABLESIZE 100000
- /* 允许开辟的最大散列表长度 */
- typedef int ElementType;
- /* 关键词类型用整型 */
- typedef int Index;
- /* 散列地址类型 */
- typedef Index Position;
- /* 数据所在位置与散列地址是同一类型 */
- /* 散列单元状态类型,分别对应:有合法元素、空单元、有已删除元素 */
- typedef enum {
- Legitimate,
- Empty,
- Deleted
- }
- EntryType;
- typedef struct HashEntry Cell;
- /* 散列表单元类型 */
- struct HashEntry {
- ElementType Data;
- /* 存放元素 */
- EntryType Info;
- /* 单元状态 */
- };
- typedef struct TblNode * HashTable;
- /* 散列表类型 */
- struct TblNode {
- /* 散列表结点定义 */
- int TableSize;
- /* 表的最大长度 */
- Cell * Cells;
- /* 存放散列单元数据的数组 */
- };
- /* 返回大于N且不超过MAXTABLESIZE的最小素数 */
- int NextPrime(int N) {
- int i,
- p = (N % 2) ? N + 2 : N + 1;
- /*从大于N的下一个奇数开始 */
- while (p <= MAXTABLESIZE) {
- for (i = (int) sqrt(p); i > 2; i--) if (! (p % i)) break;
- /* p不是素数 */
- if (i == 2) break;
- /* for正常结束,说明p是素数 */
- else p += 2;
- /* 否则试探下一个奇数 */
- }
- return p;
- }
- HashTable CreateTable(int TableSize) {
- HashTable H;
- int i;
- H = (HashTable) malloc(sizeof(struct TblNode));
- H - >TableSize = NextPrime(TableSize);
- /* 保证散列表最大长度是素数 */
- H - >Cells = (Cell * ) malloc(H - >TableSize * sizeof(Cell));
- /* 声明单元数组 */
- /* 初始化单元状态为 空单元 */
- for (i = 0; iTableSize; i++) H - >Cells[i].Info = Empty;
- return H;
- }
- Position Hash(ElementType Key, int TableSize) {
- return Key % TableSize;
- }
- /*平方探测法1^2,-1^2,2^2,-2^2 …*/
- Position Find(HashTable H, ElementType Key) {
- Position CurrentPos,
- NewPos;
- int CNum = 0;
- /* 记录冲突次数 */
- NewPos = CurrentPos = Hash(Key, H - >TableSize);
- /* 初始散列位置 */
- /* 当该位置的单元非空,并且不是要找的元素时,发生冲突 */
- while (H - >Cells[NewPos].Info != Empty && H - >Cells[NewPos].Data != Key) {
- /* 字符串类型的关键词需要 strcmp 函数!! */
- /* 统计1次冲突,并判断奇偶次 */
- if (++CNum % 2) {
- /* 奇数次冲突 */
- NewPos = CurrentPos + (CNum + 1) * (CNum + 1) / 4;
- /* 增量为+[(CNum+1)/2]^2 */
- if (NewPos >= H - >TableSize) NewPos = NewPos % H - >TableSize;
- /* 调整为合法地址 */
- } else {
- /* 偶数次冲突 */
- NewPos = CurrentPos - CNum * CNum / 4;
- /* 增量为-(CNum/2)^2 */
- while (NewPos < 0) NewPos += H - >TableSize;
- /* 调整为合法地址 */
- }
- }
- return NewPos;
- /* 此时NewPos或者是Key的位置,或者是一个空单元的位置(表示找不到)*/
- }
- bool Insert(HashTable H, ElementType Key) {
- Position Pos = Find(H, Key);
- /* 先检查Key是否已经存在 */
- if (H - >Cells[Pos].Info != Legitimate) {
- /* 如果这个单元没有被占,说明Key可以插入在此 */
- H - >Cells[Pos].Info = Legitimate;
- H - >Cells[Pos].Data = Key;
- /*字符串类型的关键词需要 strcpy 函数!! */
- return true;
- } else {
- printf("键值已存在");
- return false;
- }
- }
- int main() {
- HashTable hash;
- hash = CreateTable(5); //real size 0 1 2 3 4 5 6
- printf("size = %d\n", hash - >TableSize);
- Insert(hash, 1);
- Insert(hash, 5);
- Insert(hash, 6);
- Insert(hash, 7);
- Insert(hash, 8);
- Insert(hash, 9);
- Insert(hash, 10);
- return 0;
- }哈希表平方探测法
- //分离链接法
- #include < iostream > #include < cstdio > #include < cstdlib > #include < cstring > #include < math.h > using namespace std;#define MAXTABLESIZE 100000
- /* 允许开辟的最大散列表长度 */
- #define KEYLENGTH 15
- /* 关键词字符串的最大长度 */
- typedef char ElementType[KEYLENGTH + 1];
- /* 关键词类型用字符串 */
- typedef int Index;
- /* 散列地址类型 */
- /******** 以下是单链表的定义 ********/
- typedef struct LNode * PtrToLNode;
- struct LNode {
- ElementType Data;
- PtrToLNode Next;
- };
- typedef PtrToLNode Position;
- typedef PtrToLNode List;
- /******** 以上是单链表的定义 ********/
- typedef struct TblNode * HashTable;
- /* 散列表类型 */
- struct TblNode {
- /* 散列表结点定义 */
- int TableSize;
- /* 表的最大长度 */
- List Heads;
- /* 指向链表头结点的数组 */
- };
- int NextPrime(int N) {
- /* 返回大于N且不超过MAXTABLESIZE的最小素数 */
- int i,
- p = (N % 2) ? N + 2 : N + 1;
- /*从大于N的下一个奇数开始 */
- while (p <= MAXTABLESIZE) {
- for (i = (int) sqrt(p); i > 2; i--) if (! (p % i)) break;
- /* p不是素数 */
- if (i == 2) break;
- /* for正常结束,说明p是素数 */
- else p += 2;
- /* 否则试探下一个奇数 */
- }
- return p;
- }
- HashTable CreateTable(int TableSize) {
- HashTable H;
- int i;
- H = (HashTable) malloc(sizeof(struct TblNode));
- H - >TableSize = NextPrime(TableSize);
- /* 保证散列表最大长度是素数 */
- H - >Heads = (List) malloc(H - >TableSize * sizeof(struct LNode));
- /* 以下分配链表头结点数组 */
- /* 初始化表头结点 */
- for (i = 0; iTableSize; i++) {
- H - >Heads[i].Data[0] = '\0';
- H - >Heads[i].Next = NULL;
- }
- return H;
- }
- Index Hash(ElementType Key, int TableSize) {
- return ( * Key - 'a') % TableSize;
- }
- Position Find(HashTable H, ElementType Key) {
- Position P;
- Index Pos;
- Pos = Hash(Key, H - >TableSize);
- /* 初始散列位置 */
- P = H - >Heads[Pos].Next;
- /* 从该链表的第1个结点开始 */
- /* 当未到表尾,并且Key未找到时 */
- while (P && strcmp(P - >Data, Key)) P = P - >Next;
- return P;
- /* 此时P或者指向找到的结点,或者为NULL */
- }
- bool Insert(HashTable H, ElementType Key) {
- Position P,
- NewCell;
- Index Pos;
- P = Find(H, Key);
- if (!P) {
- /* 关键词未找到,可以插入 */
- NewCell = (Position) malloc(sizeof(struct LNode));
- strcpy(NewCell - >Data, Key);
- Pos = Hash(Key, H - >TableSize);
- /* 初始散列位置 */
- /* 将NewCell插入为H->Heads[Pos]链表的第1个结点 */
- NewCell - >Next = H - >Heads[Pos].Next;
- H - >Heads[Pos].Next = NewCell;
- return true;
- } else {
- /* 关键词已存在 */
- printf("键值已存在");
- return false;
- }
- }
- void DestroyTable(HashTable H) {
- int i;
- Position P,
- Tmp;
- /* 释放每个链表的结点 */
- for (i = 0; iTableSize; i++) {
- P = H - >Heads[i].Next;
- while (P) {
- Tmp = P - >Next;
- free(P);
- P = Tmp;
- }
- }
- free(H - >Heads);
- /* 释放头结点数组 */
- free(H);
- /* 释放散列表结点 */
- }
- int main() {
- HashTable hash;
- hash = CreateTable(5); //real size 7: 0 1 2 3 4 5 6
- Insert(hash, "a");
- Insert(hash, "b");
- Insert(hash, "c");
- Insert(hash, "d");
- Insert(hash, "e");
- Insert(hash, "h");
- Insert(hash, "g");
- return 0;
- }分离链接法
来源: http://www.cnblogs.com/ranjiewen/p/6883081.html