一、C 哈希表模板
template
class HashTable{
private:
struct Node{
Key key;
Value val;
Node* next;
Node(Key key,Value val,Node* next){
this->key=key;
this->val=val;
this->next=next;
}
};
int M;
int size;
Node** table;
int hash(Key key){
return (std::hash()(key) & 0x7fffffff) % M;
}
public:
HashTable(int M){
this->M=M;
this->size=0;
table=new Node*[M];
for(int i=0;i<M;i++){
table[i]=NULL;
}
}
~HashTable(){
for(int i=0;inext;
delete temp;
}
}
delete[] table;
}
int getSize(){
return size;
}
void add(Key key,Value val){
int index=hash(key);
Node* cur=table[index];
while(cur){
if(cur->key==key){
cur->val=val;
return;
}
cur=cur->next;
}
Node* newNode=new Node(key,val,table[index]);
table[index]=newNode;
size++;
}
bool contains(Key key){
int index=hash(key);
Node* cur=table[index];
while(cur){
if(cur->key==key)
return true;
cur=cur->next;
}
return false;
}
Value* get(Key key){
int index=hash(key);
Node* cur=table[index];
while(cur){
if(cur->key==key)
return &(cur->val);
cur=cur->next;
}
return NULL;
}
void set(Key key,Value val){
int index=hash(key);
Node* cur=table[index];
while(cur){
if(cur->key==key){
cur->val=val;
return;
}
cur=cur->next;
}
throw std::invalid_argument("Key not exist");
}
Value remove(Key key){
int index=hash(key);
Node* cur=table[index];
Node* prev=NULL;
while(cur){
if(cur->key==key){
if(!prev)
table[index]=cur->next;
else
prev->next=cur->next;
Value res=cur->val;
delete cur;
size--;
return res;
}
prev=cur;
cur=cur->next;
}
throw std::invalid_argument("Key not exist");
}
};
該哈希表支持泛型，其中 key 和 value 類型可以自行指定。哈希表使用鏈表解決哈希衝突問題，因為鏈表解決衝突的時間複雜度低，實現簡單。哈希表中的元素個數如果超出數組大小的一半，就調整數組大小，使數組大小成為原來大小的兩倍。如果元素個數小於數組大小的四分之一，就將數組大小減小到原來的一半，以防止浪費空間。在哈希表中最重要的是哈希函數，它決定了元素的分布情況，哈希函數的設計要盡量高效，盡量不會出現過多的衝突。
二、C 哈希表 遍歷
可以使用哈希表中的 getKeySet 和 getValueSet 函數，獲取哈希表中所有 key 和 value 的集合，然後遍歷一個個輸出。
int main(){
HashTable table(10);
table.add("a",1);
table.add("b",2);
table.add("c",3);
std::unordered_set keySet;
table.getKeySet(keySet);
for(std::string key : keySet){
std::cout<<key<<":"<<*(table.get(key))<<std::endl;
}
return 0;
}
三、C 哈希表介面
C++ 的哈希表介面跟 Java 的哈希表介面不一樣，在 C++ 中沒有實現 Map 介面。C++ 的 unordered_map 可以作為 Map，提供了 Map 的基本介面，不過其底層實現使用了哈希表。除了 Map 介面外，C++ 標準庫里還定義了 unordered_set 和 unordered_multiset、 unordered_multimap 等不同類型的哈希表。
四、C 哈希表頭文件
使用哈希表需要包含 C++ 標準庫中的unordered_map 頭文件，如下：
#include <unordered_map> using namespace std;
五、哈希表在c中怎麼用
C 語言中沒有哈希表的數據類型，但是可以用鏈表實現一個哈希表來解決鍵值對的存儲和查找。C 語言的哈希表中的關鍵就是哈希函數，對於同一個鍵值，必須總是得出相同的哈希地址，否則無法找到該值。
六、哈希表C語言示例代碼
#include <stdio.h>
#include <string.h>
#define HASH_TABLE_SIZE 1024
struct hashtable_t {
char* key;
char* val;
struct hashtable_t* next;
};
unsigned int hashtable_hash(struct hashtable_t* const hashtable, char* const key) {
unsigned long int hashval = 0;
unsigned int i = 0;
while (hashval < ULONG_MAX && i < strlen(key)) {
hashval = hashval << 8;
hashval += key[i];
i++;
}
return hashval % HASH_TABLE_SIZE;
}
struct hashtable_t* hashtable_newpair(char* key, char* value) {
struct hashtable_t* newpair;
if ((newpair = malloc(sizeof(struct hashtable_t)))==NULL) {
return NULL;
}
if ((newpair->key = strdup(key))==NULL) {
return NULL;
}
if ((newpair->val = strdup(value))==NULL) {
return NULL;
}
newpair->next = NULL;
return newpair;
}
void hashtable_set(struct hashtable_t* const hashtable, char* const key, char* const value) {
int bin = 0;
struct hashtable_t* newpair = NULL;
struct hashtable_t* next = NULL;
struct hashtable_t* last = NULL;
bin = hashtable_hash(hashtable, key);
next = hashtable->table[bin];
while (next!=NULL && next->key!=NULL && strcmp(key, next->key) > 0) {
last = next;
next = next->next;
}
if (next!=NULL && next->key!=NULL && strcmp(key, next->key)==0) {
free(next->val);
next->val = strdup(value);
} else {
newpair = hashtable_newpair(key, value);
if (next==hashtable->table[bin]) {
newpair->next = next;
hashtable->table[bin] = newpair;
} else if (next==NULL) {
last->next = newpair;
} else {
newpair->next = next;
last->next = newpair;
}
}
}
char* hashtable_get(struct hashtable_t* const hashtable, char* const key) {
int bin = 0;
struct hashtable_t* pair;
bin = hashtable_hash(hashtable, key);
pair = hashtable->table[bin];
while (pair!=NULL && pair->key!=NULL && strcmp(key, pair->key) > 0) {
pair = pair->next;
}
if (pair==NULL || pair->key==NULL || strcmp(key, pair->key)!=0) {
return NULL;
} else {
return pair->val;
}
}
int main(int argc, char **argv) {
struct hashtable_t* hashtable = NULL;
char* str = NULL;
hashtable = calloc(1, sizeof(struct hashtable_t*));
hashtable->table = calloc(HASH_TABLE_SIZE, sizeof(struct hashtable_t*));
hashtable_set(hashtable, "key1", "inky");
hashtable_set(hashtable, "key2", "pinky");
hashtable_set(hashtable, "key3", "blinky");
hashtable_set(hashtable, "key4", "floyd");
printf("%s\n", hashtable_get(hashtable, "key1"));
printf("%s\n", hashtable_get(hashtable, "key2"));
printf("%s\n", hashtable_get(hashtable, "key3"));
printf("%s\n", hashtable_get(hashtable, "key4"));
return 0;
}
本文詳細介紹了哈希表在C++中的應用，包括C++哈希表模板、C++哈希表遍歷、C++哈希表頭文件、C++哈希表介面等方面的內容。同時，本文還介紹了如何用C語言實現哈希表，並給出了示例代碼，可以幫助讀者更好地理解哈希表的原理和應用。哈希表是一個非常重要的數據結構，廣泛應用於各種演算法和程序設計中。希望讀者通過本文的學習，能夠對哈希表有更深入的認識，進一步提高自己的程序設計能力。
原創文章，作者：STMQX，如若轉載，請註明出處：https://www.506064.com/zh-tw/n/370781.html
微信掃一掃 
支付寶掃一掃 