哈希表详解 (3)

哈希表的初始化：

void HashTableInit(HashTable* ht) //初始化 { size_t i = 0; assert(ht); ht->_size = 0; ht->_N = HashTablePrime(0); ht->_table = (HashNode *)malloc(sizeof(HashNode)*ht->_N); assert(ht->_table); for (i=0; i<ht->_N; i++) ht->_table[i]._status = EMPTY; }

哈希函数：

KeyType HashFunc(KeyType key,size_t n) { return key%n; }

看看哈希表的插入：（这里处理哈希冲突时采用线性探测，二次探测将在下一次博客中写出）
扩容时要特别注意，不能简单的用malloc和realloc开出空间后直接付给哈希表，一定记得扩容之后需要重新映射原表的所有值。

int HashTableInsert(HashTable* ht, KeyType key, ValueType value) //插入 { KeyType index = key; assert(ht); **if (ht->_N == ht->_size) //扩容 { KeyType index; size_t newN = HashTablePrime(ht->_N); HashNode *tmp = (HashNode *)malloc(sizeof(HashNode)*newN); size_t i = 0; assert(tmp); //HashTablePrint(ht); //扩容调试使用 for (i=0; i<newN; i++) tmp[i]._status = EMPTY; for (i=0; i<ht->_N; i++) //扩容之后把以前的表中元素重新映射 { if (ht->_table[i]._status == EXIST) //原表存在时 { index = HashFunc(ht->_table[i]._key,newN); if (tmp[index]._status == EXIST) //发生哈希冲突时 { while (1) { index +=1; if ((size_t)index > newN) index %= newN; if (tmp[index]._status != EXIST) break; } } tmp[index]._key = ht->_table[i]._key; tmp[index]._value = ht->_table[i]._value; tmp[index]._status = EXIST; } else tmp[i]._status = ht->_table[i]._status; } ht->_table = tmp; ht->_N = newN; }** index = HashFunc(key,ht->_N); if (ht->_table[index]._status == EXIST) //发生哈希冲突 { size_t i = 0; for (i=0; i<ht->_N;i++ ) { if (ht->_table[index]._key == key) return -1; index +=i; if ((size_t)index >ht->_N) index %= ht->_N; if (ht->_table[index]._status != EXIST) break; } } ht->_table[index]._key = key; ht->_table[index]._value = value; ht->_table[index]._status = EXIST; ht->_size++; return 0; }

哈希表的查找：

HashNode* HashTableFind(HashTable* ht, KeyType key) //查找 { size_t i = 0; KeyType index = key; assert(ht); index = HashFunc(key,ht->_N); if (ht->_table[index]._key == key) return &(ht->_table[index]); else { for (i=0; i<ht->_N; i++) { index += i; if (ht->_table[index]._key == key) return &(ht->_table[index]); if (ht->_table[index]._status == EMPTY) return NULL; } } return NULL; }

哈希表的删除：

int HashTableRemove(HashTable* ht, KeyType key) //删除 { assert(ht); if(HashTableFind(ht,key)) { HashTableFind(ht,key)->_status = DELETE; return 0; } else return -1; }

哈希表的销毁：（使用了malloc开辟空间必须手动销毁）

void HashTableDestory(HashTable* ht)//销毁 { free(ht->_table); ht->_table = NULL; ht->_size = 0; ht->_N = 0; }

哈希表的打印：

void HashTablePrint(HashTable *ht) //打印hash表 { size_t i = 0; assert(ht); for (i=0; i<ht->_N; i++) { if (ht->_table[i]._status == EXIST) printf("[%d]%d ",i,ht->_table[i]._key); else if (ht->_table[i]._status == EMPTY) printf("[%d]E ",i); else printf("[%d]D ",i); } printf("\n\n"); }

哈希表整个在插入这块会比较ran，要仔细理解，特别是扩容那块。

测试案例：

void TestHashTable() { HashTable ht; HashTableInit(&ht); HashTableInsert(&ht,53,0); HashTableInsert(&ht,54,0); HashTableInsert(&ht,55,0); HashTableInsert(&ht,106,0); HashTableInsert(&ht,1,0); HashTableInsert(&ht,15,0); HashTableInsert(&ht,10,0); HashTablePrint(&ht); printf("%d ",HashTableFind(&ht,53)->_key); printf("%d ",HashTableFind(&ht,54)->_key); printf("%d ",HashTableFind(&ht,10)->_key); printf("%d ",HashTableFind(&ht,15)->_key); printf("%p ",HashTableFind(&ht,3)); printf("\n\n"); HashTableRemove(&ht,53); HashTableRemove(&ht,54); HashTableRemove(&ht,106); HashTableRemove(&ht,10); HashTableRemove(&ht,5); HashTablePrint(&ht); HashTableInsert(&ht,53,0); HashTableInsert(&ht,54,0); HashTableInsert(&ht,106,0); HashTablePrint(&ht); HashTableDestory(&ht); HashTablePrint(&ht); }

测试结果：