字典在很多高級語言里都有，比如
- js的物件結構可以當字典來用
- python的字典
- go的map
- ......................
但是你們知道字典是怎么實作的嗎？本文來實作一個簡單的字典，
python的字典
先來看python的字典是怎樣的
d = {}
d["name"]="biningo"
d["age"] = "19"
name = d.get("name")
age = d.get("age")
c語言實作
參考了Redis的字典結構，字典在redis底層應用非常普遍，因為redis是一個K-V資料庫
這里只是實作了string型別的字典，鍵值都是string
用一個Hash Table來存放鍵值，線性探測法解決沖突【redis是用拉鏈法】
dictEntry：存放K-V的結構體
struct dictEntry{
string key;
string val;
};
dict：字典，里面有一個Hash Table
//字典 無序
struct dict{
dictEntry** table; //哈希表陣列
int size; //哈希表大小
int len; //鍵值對計數器
};
根據string來計算Hash Code
//計算str的哈希值 參照java hashCode
int hash(string s){
int h = 0;
for(int i=0;i<s.length();i++){
h = 31 * h + (s[i] & 0xff);
}
return h;
}
創建空字典
dict* dictCreate(int size){
dict* d = (dict*)malloc(sizeof(dict));
d->table = (dictEntry**)calloc(size,sizeof(dictEntry*)); //這里要注意了
for(int i=0;i<size;i++)
d->table[i] = NULL;
d->size = size;//size當作負載因子
d->len=0;
return d;
}
Get、Set
void set(dict* d,string key,string val){
if(d->size==d->len){
cout<<"哈希表滿了"<<endl;
return;
}
int index = hash(key)%d->size;
while(d->table[index]!=NULL){
index = (index+1)%d->size;
}
d->table[index] = (dictEntry*)malloc(sizeof(dictEntry)); //先開辟空間
d->table[index]->val = val;
d->table[index]->key = key;
d->len++;
return;
}
string get(dict* d,string key){
if(d->len==0){
cout<<"哈希表空的"<<endl;
return "";
}
int index = hash(key)%d->size;
int c=1;
while( c<d->size){
if(d->table[index] && d->table[index]->key==key)
break;
index = (index+1)%d->size;
c++;
}
if(c<d->size){
d->len--;
return d->table[index]->val;
}
else{
cout<<"找不到元素"<<endl;
return "";
}
}
洗掉鍵值
//根據鍵查找哈希表的索引
int getIndex(dict* d,string key){
if(d->len==0){
cout<<"哈希表空的"<<endl;
return -1;
}
int index = hash(key)%d->size;
int c=1;
while( c<d->size && d->table[index]->key!=key){
index = (index+1)%d->size;
c++;
}
if(c<d->size)
return index;
else{
cout<<"找不到元素"<<endl;
return -1;
}
}
//根據鍵洗掉鍵值對
void DeleteByKey(dict* d,string key){
int i = getIndex(d,key);
if(i>=0){
d->table[i] = NULL;
d->len--;
}
}
完整代碼以及示例
#include <iostream>
#include<stdint.h>
using namespace std;
struct dictEntry{
string key;
string val;
};
//字典 無序
struct dict{
dictEntry** table; //哈希表陣列
int size; //哈希表大小
int len; //鍵值對計數器
};
dict* dictCreate(int size){
dict* d = (dict*)malloc(sizeof(dict));
d->table = (dictEntry**)calloc(size,sizeof(dictEntry*)); //這里要注意了
for(int i=0;i<size;i++)
d->table[i] = NULL;
d->size = size;//size當作負載因子
d->len=0;
return d;
}
//計算str的哈希值 參照java hashCode
int hash(string s){
int h = 0;
for(int i=0;i<s.length();i++){
h = 31 * h + (s[i] & 0xff);
}
return h;
}
void set(dict* d,string key,string val){
if(d->size==d->len){
cout<<"哈希表滿了"<<endl;
return;
}
int index = hash(key)%d->size;
while(d->table[index]!=NULL){
index = (index+1)%d->size;
}
d->table[index] = (dictEntry*)malloc(sizeof(dictEntry)); //先開辟空間
d->table[index]->val = val;
d->table[index]->key = key;
d->len++;
return;
}
string get(dict* d,string key){
if(d->len==0){
cout<<"哈希表空的"<<endl;
return "";
}
int index = hash(key)%d->size;
int c=1;
while( c<d->size){
if(d->table[index] && d->table[index]->key==key)
break;
index = (index+1)%d->size;
c++;
}
if(c<d->size){
return d->table[index]->val;
}
else{
cout<<"找不到元素"<<endl;
return "";
}
}
//根據鍵查找哈希表的索引
int getIndex(dict* d,string key){
if(d->len==0){
cout<<"哈希表空的"<<endl;
return -1;
}
int index = hash(key)%d->size;
int c=1;
while( c<d->size && d->table[index]->key!=key){
index = (index+1)%d->size;
c++;
}
if(c<d->size)
return index;
else{
cout<<"找不到元素"<<endl;
return -1;
}
}
//根據鍵洗掉鍵值對
void DeleteByKey(dict* d,string key){
int i = getIndex(d,key);
if(i>=0){
d->table[i] = NULL;
d->len--;
}
}
int main(int argc, char *argv[])
{
dict* d = dictCreate(100);
set(d,"age","1");
set(d,"name","biningo");
cout<<get(d,"one");
cout<<get(d,"age")<<" "<<get(d,"name")<<endl;
DeleteByKey(d,"name");
cout<<get(d,"name")<<endl;
return 0;
}
找不到元素
1 biningo
找不到元素
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/69631.html
標籤：其他
上一篇：雙鏈表【參照redis鏈表結構】