如果在不用C++内置的哈希表时, 你会怎么构造一个哈希表呢? 当然, 此时键值是有限的, 即有上界和下界. 有一个这么好的条件限制, 我自然而然地想到了用一个vector顺序访问, 代码如下:
class MyHashMap {
private:
vector<int> hash;
public:
/** Initialize your data structure here. */
MyHashMap() {
hash.resize(1000001,-1);
}
/** value will always be non-negative. */
void put(int key, int value) {
hash[key]=value;
}
/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
int get(int key) {
return hash[key];
}
/** Removes the mapping of the specified value key if this map contains a mapping for the key */
void remove(int key) {
hash[key]=-1;
}
};
/**
* Your MyHashMap object will be instantiated and called as such:
* MyHashMap obj = new MyHashMap();
* obj.put(key,value);
* int param_2 = obj.get(key);
* obj.remove(key);
*/
但我跑了33个案例以后, 发现耗时高达80ms, 这实在是令我有点难以接受, 按理说都是O(1)的操作, 耗时不应该这么高才对…… 看到一个大神用链表构造哈希表的代码, 耗时仅60ms, mark一下先:
const static auto io_speed_up=[](){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
return NULL;
}();
class MyHashMap {
public:
/** Initialize your data structure here. */
list<pair<int, int>> buckets[1000];
MyHashMap() {
}
/** value will always be non-negative. */
void put(int key, int value) {
bool flag = false;
int hash = (key*1031)%1000;
//printf("%s: key,value,hash(%d %d %d)\n", __func__, key, value, hash);
list<pair<int, int>> &li = buckets[hash];
for (auto it = li.begin(); it != li.end(); it++) {
if (it->first == key) {
flag = true;
it->second = value;
}
}
if (!flag) {
li.push_back(make_pair(key, value));
}
}
/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
int get(int key) {
int hash = (key*1031)%1000;
//printf("%s: key,hash(%d %d)\n", __func__, key, hash);
list<pair<int, int>> li = buckets[hash];
for (auto it = li.begin(); it != li.end(); it++) {
//printf("key, value(%d %d)\n", it->first, it->second);
if (it->first == key) return it->second;
}
return -1;
}
/** Removes the mapping of the specified value key if this map contains a mapping for the key */
void remove(int key) {
int hash = (key*1031)%1000;
list<pair<int, int>> &li = buckets[hash];
for (auto it = li.begin(); it != li.end(); it++) {
if (it->first == key) {
li.erase(it);
return;
}
}
}
};
/**
* Your MyHashMap object will be instantiated and called as such:
* MyHashMap obj = new MyHashMap();
* obj.put(key,value);
* int param_2 = obj.get(key);
* obj.remove(key);
*/
他利用质数1031去计算出一个哈希值, 同时再取除以1000的余数. 这样可以得到1000个桶, 用以处理哈希冲突的问题, 在取值时, 先定位数据放在了哪个桶, 再遍历链表, 相比较直接遍历整个链表而言, 大大减少了耗时, 不能不说实在是妙…… (虽然我最后还是没想明白这么复杂的操作为何耗时比我低就是了QAQ……)
下面给出de神对于为何能用$(key*1031)%1000$来作为一个哈希函数的原因: 从同余方程的角度来理解, 若要使得$p*(key1-key2)\equiv 0 mod M,M=1000$成立，那么$p*(key1 – key2) = t* M$, 由于$(p,M)=1$, 那么必有$M|(key1-key2)$. 也就是说, 若同余方程要成立的话, $key1 = key2 + M*h$, 这些数是很少的, 对于连续的$[1,n]$, 这样的数里面, 每隔$M$个数才有一个, 也就是这个哈希每隔$M$个数才有可能冲突. 此处由于1031>1000, 那么用$(key*1031)%1000$来作为一个哈希函数也就不会产生冲突了~
PS: 这个技巧还可以用于Dijkstra算法效率的提升~