C++实现基于 int 键的哈希表
对int的HashTable实现
C++实现对以int
为键的hashTable
。
目前值为int
,但可变;
const int N=1e3; // 设计的hashTable大小
// assume data range: -intINF~+intINF
struct _hash_data
{
int sym,data;
_hash_data *nxt;
_hash_data(){
sym=-1;data=-1;nxt=nullptr;
}
};
class hash_table{
public:
int& operator[](int key){
unsigned short idx=(key%MOL+MOL)%MOL;
_hash_data *result=&data[idx];
while (result->nxt!=nullptr&&result->sym!=key)
result=result->nxt;
if (result->sym==key) return result->data;
_hash_data *newData=new _hash_data();
if (!newData) throw bad_alloc();
result->nxt=newData;
newData->sym=key;
return newData->data;
}
~hash_table(){
// release all the pointers
for (int i=0;i<N;i++){
_hash_data *current=&data[i];
while (current-> nxt!=nullptr){
_hash_data *tmp=current;
current=current->nxt;
if (tmp!=&data[i])
delete tmp;
}
}
}
private:
const unsigned short int MOL=997; // 一个接近N的大质数
_hash_data data[N+10];
};
解释
哈希表
哈希表又称散列表,一种以「key-value」形式存储数据的数据结构。所谓以「key-value」形式存储数据,是指任意的键值 key 都唯一对应到内存中的某个位置。只需要输入查找的键值,就可以快速地找到其对应的 value。可以把哈希表理解为一种高级的数组,这种数组的下标可以是很大的整数,浮点数,字符串甚至结构体。
哈希函数
要让键值对应到内存中的位置,就要为键值计算索引,也就是计算这个数据应该放到哪里。这个根据键值计算索引的函数就叫做哈希函数,也称散列函数。举个例子,如果键值是一个人的身份证号码,哈希函数就可以是号码的后四位,当然也可以是号码的前四位。生活中常用的「手机尾号」也是一种哈希函数。在实际的应用中,键值可能是更复杂的东西,比如浮点数、字符串、结构体等,这时候就要根据具体情况设计合适的哈希函数。哈希函数应当易于计算,并且尽量使计算出来的索引均匀分布。
冲突解决
类似开散列法
拉链法是在每个存放数据的地方开一个链表,如果有多个键值索引到同一个地方,只用把他们都放到那个位置的链表里就行了。查询的时候需要把对应位置的链表整个扫一遍,对其中的每个数据比较其键值与查询的键值是否一致。如果索引的范围是 $1\ldots M$,哈希表的大小为 N,那么一次插入/查询需要进行期望 $O(\frac{N}{M})$ 次比较。
代码中用指针的形式实现链表。
评论
匿名评论
隐私政策
你无需删除空行,直接评论以获取最佳展示效果