各类判重方案比较 (各路神犇别看，熟悉 wordpress 写的) —— By boshi

方案一：直接使用 STL map

方案二：取模分组再使用 STL map

方案三：直接使用取模哈希

方案四：链式哈希表

下面统计了各种方案在 5*10⁶ 级别的用时（ubuntu, 无 O2 优化, 3.30GHz）及判重错误的数据量 (数据随机生成)

Insert:
STL Map Use Time:4490ms
HASH + Map Use Time:1245ms
Origin Hash Use Time:67ms
List Hash Use Time:728ms
Read:
STL Map Use Time:5812ms, 0 Mistakes
HASH + Map Use Time:1983ms , 0 Mistakes
Origin Hash Use Time:58ms , 4847252 Mistakes
List Hash Use Time:407ms , 0 Mistakes

部分代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <map>
#include <ctime>
#include <vector>

#define MX 5000001
#define MY 10001
#define MD 1423333

using namespace std;

map<int,int> origin;
map<int,int> origin_plus[MX];
int origin_hash[MX];
vector<int> list_hash[MD+1];

inline void insrt1(int x){
    origin[x]=x;
}

inline void insrt2(int x){
    origin_plus[x%MD][x]=x;
}

inline void insrt3(int x){
    origin_hash[x%MD]=x;
}

inline void insrt4(int x){
    int mx=x%MD;
    for(register unsigned int j=0; j<list_hash[mx].size(); j++)
        if(list_hash[mx][j]==x)
            return;
    list_hash[mx].push_back(x);
}

inline int check1(int x){
    return origin[x];
}

inline int check2(int x){
    return origin_plus[x%MD][x];
}

inline int check3(int x){
    return origin_hash[x%MD];
}