一个下标由整数、浮点数甚至字符串、结构体构成的“数组”。
· 对每一个key,通过映射f得到f(key)作为键值对(key, value)的索引,即键值对存放在arr[f(key)]上。
例如:将长度为n的字符串s转换为:x = s0· 1270+ s1· 1271+ ··· + sn· 127n,x对264取模得到索引。
即不同的键值转换后得到相同索引的情况。
解决方案一:开散列法将同一个索引处的多个(key, value)用链表储存,查询时需要扫描整个链表。注意,每个存放数据的地方都会开一个链表。c++代码如下:
const int SIZE = 1000000;
const int M = 999997;
struct HashTable
{//数组模拟链表
struct Node
{int next, value, key;
} data[SIZE];
// head[M] 存放 f(key)=M 的第一个节点在 data 数组里的下标,即头结点的下标
int head[M], size;
//哈希函数
int f(int key) {return key % M; }
//查找
int get(int key)
{for (int p = head[f(key)]; p; p = data[p]next)
if (data[p].key == key) return data[p].value;
return -1;
}
//修改
int modify(int key, int value)
{for (int p = head[f(key)]; p; p = data[p]next)
if (data[p].key == key) return data[p].value = value;
}
//添加
int add(int key, int value)
{//判断键值对是否已经存储过
if (get(key) != -1) return -1;
data[++size] = (Node){head[f(key), value, key};
head[f(key)] = size;
return value;
}
};
另一种封装好的模板代码如下:
struct hash_map
{//前向星结构
struct data
{long long u;
int v, nex;
};
data e[SZ<< 1]; // SZ 是 const int,表示大小
int h[SZ], cnt; //cnt记录当前e中存入键值对的个数
//哈希函数,用 (u % SZ + SZ) % SZ 是为了将结果转化为正数
int hash(long long u) {return (u % SZ + SZ) % SZ; }
//查找,若找到则返回value,否则返回-1(不太懂这个函数的语法)
int& operator[](long long u)
{int hu = hash(u);
for (int i = h[hu]; i; i = e[i].nex)
if (e[i].u == u) return e[i].v;
return e[++cnt] = (data){u, -1, h[hu]}, h[hu] = cnt, e[cnt].v;
}
hash_map()
{cnt = 0;
memset(h, 0, sizeof(h));
}
};
解决方案二:闭散列法把所有记录直接存储在散列表中,如果发生冲突则用某种方法(如线性探查法)继续探查。代码如下:
const int N = 360007;
class Hash
{private:
int keys[N];
int values[N];
public:
Hash() {memset(values, 0, sizeof(values)); }
int& operator[](int n)
{ int idx = (n % N + N) % N, cnt = 1;
while (keys[idx] != n && values[idx] != 0)
{ idx = (idx + cnt * cnt) % N;
++cnt;
}
keys[idx] = n;
return values[idx];
}
};
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
分享题目:【自学笔记001】哈希表(一)-创新互联
当前网址:https://www.cdcxhl.com/article14/epede.html
成都网站建设公司_创新互联,为您提供服务器托管、做网站、网站建设、品牌网站建设、网站策划、建站公司
声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联