先引入素數(shù)表，可以有效降低哈希沖突

Common.h #pragma once // 使用素數(shù)表對齊做哈希表的容量，降低哈希沖突unsigned long GetNextPrime(unsigned long num); Common.c #include "Common.h" #define _PrimeSize 28 unsigned long _PrimeList[_PrimeSize] = {53ul, 97ul, 193ul, 389ul, 769ul,1543ul, 3079ul, 6151ul, 12289ul, 24593ul,49157ul, 98317ul, 196613ul, 393241ul, 786433ul,1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,1610612741ul, 3221225473ul, 4294967291ul }; unsigned long GetNextPrime(unsigned long num) {int i = 0;for (; i < _PrimeSize; ++i){if (num <= _PrimeList[i])return _PrimeList[i];}return _PrimeList[_PrimeSize - 1]; } Hash.c #pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> #include<stdlib.h>#include "Common.h"#define MAX_SIZE 10 #define NULL 0 #define DETECTIVE_LINEtypedef char* Datatype; typedef unsigned long (*PHF)(Datatype);typedef enum { EMPYT, EXIST, DELETE }State;typedef struct Elem {Datatype _data;State _state; }Elem;typedef struct Hash {Elem* _arr; //哈希表空間int _Size; //表中有效元素個數(shù)int _capacity; //容量PHF _pToInt; //輸入字符或整形 }HT;void Swap(int *left, int *right); //交換 unsigned long BKDRHash(const char *str); //字符串轉(zhuǎn)整形 void InitHash(HT *ht, unsigned long capacity, PHF pTo); //初始化 int HashFun(HT *ht, Datatype data); //哈希函數(shù) int HashInsert(HT *ht, Datatype data); //插入 int DetectiveLine(HT * ht, int addr); //線性探測 int Detective2(HT * ht, int addr, int i); //二次探測 int Find(HT *ht, Datatype data); //查找 int DeleteHash(HT *ht, Datatype data); //刪除 int EmptyHash(HT *ht); //判空 int SizeHash(HT *ht); //有效元素大小 int CheckHash(HT *ht); //增容 void DestroyHash(HT *ht); //銷毀 ``` Hash.c #include "Hash.h"void Swap(int *left, int *right) {int tmp = *left;*left = *right;*right = tmp; } // int HashEmpty(HT *ht) {assert(ht);return ht->_Size; } // unsigned long BKDRHash(const char *str) //字符串轉(zhuǎn)換為整數(shù) {unsigned int seed = 131;unsigned int hash = 0;while (*str){hash = hash * seed + (*str++);}return (hash & 0x7FFFFFFF); } // void InitHash(HT *ht, unsigned long capacity, PHF pTo) //判斷有效性 - 申請空間 - 狀態(tài) {assert(ht);int i = 0; capacity = GetNextPrime(capacity);ht->_arr = (Elem*)malloc(sizeof(Elem)*capacity);for (; i < capacity; i++){ht->_arr[i]._state = EMPYT;}ht->_Size = 0;ht->_capacity = capacity;ht->_pToInt = pTo; } // int HashFun(HT *ht, Datatype data) {return ht->_pToInt(data) % ht->_capacity; } // int HashInsert(HT *ht, Datatype data) {assert(ht);int addr = 0;int i = 0;if (ht->_capacity == ht->_Size){ht->_capacity = GetNextPrime(ht->_capacity);}addr = HashFun(ht, data);while (EMPYT != ht->_arr[addr]._state){//避免插入重復(fù)元素if (EXIST == ht->_arr[addr]._state && ht->_arr[addr]._data == data)return 0; #ifdef DETECTIVE_LINEaddr = DetectiveLine(ht, addr); #elsei++addr = DetectiveLine2(ht, addr, i); #endif}ht->_arr[addr]._data = data;ht->_Size++;ht->_arr[addr]._state = EXIST; }// //線性探測 int DetectiveLine(HT * ht, int addr) {addr += 1;if (addr > ht->_capacity){addr = 0;}return addr; }//二次探測 int Detective2(HT * ht, int addr, int i) {addr = addr + 2 * i + 1;if (addr > ht->_capacity){addr %= ht->_capacity;}return addr; }int Find(HT *ht, Datatype data) //查找 {assert(ht);int addr = HashFun(ht, data);int count = 0;int addrstart = addr;int i = 0;//如果位置非空，EXIST - 比較 DELEST addr++while (EMPYT != ht->_arr[addr]._state){if (EXIST == ht->_arr[addr]._state && ht->_arr[addr]._data == data){return addr;} #ifdef DETETIVE_LINEaddr = DetectiveLine(ht, data); #elsei++;addr = Detective2(ht, data, i); #endif }return -1; }int DeleteHash(HT *ht, Datatype data) //刪除 {assert(ht);if (0 == EmptyHash(ht)){return 0;}int addr = Find(ht, data);if (addr == -1){return 0;}ht->_arr[addr]._state = DELETE;ht->_Size--;return 1; }int EmptyHash(HT *ht) {assert(ht);return ht->_Size == 0; }int SizeHash(HT *ht) {assert(ht);return ht->_Size; }int CheckHash(HT *ht) {int i = 0;assert(ht);if ((ht->_Size * 10 / ht->_capacity) > 7) //負(fù)載因子0.7{HT tmp;InitHash(&tmp, ht->_capacity, ht->_pToInt);for (; i < ht->_capacity; i++){HashInsert(&tmp, ht->_arr[i]._data);}Swap(&tmp, ht);DestroyHash(&tmp);}return 1; }void DestroyHash(HT *ht) {assert(ht);int i = 0;for (i = 0; i < ht->_capacity; i++){ht->_arr[i]._state = EMPYT;}ht->_Size = 0;ht->_capacity = 0;free(ht->_arr);ht->_arr = NULL; } test.c #include "Hash.h"void main() {HT ht;int tmp = 0;InitHash(&ht, 10, BKDRHash);HashInsert(&ht, "igi");HashInsert(&ht, "godf");tmp = Find(&ht, "ooo");if (-1 == tmp){printf("no\n");}else{printf("yes\n");}system("pause"); }

總結(jié)

以上是生活随笔為你收集整理的闭散列哈希的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。