HashTable (poj2785)
3560 ワード
//by zxfx100
//(positive int # < maxN = 9999997) && (elements' range is int)
#define maxN 9999997
int HashTablea[maxN];
int HashTablecnt[maxN];
class HashTable
{
public:
void init()
{
memset(HashTablecnt, 0, sizeof(HashTablecnt));
}
int find(int n)
{
int index = n % maxN;
index = (index + maxN) % maxN;
while(HashTablea[index] != n)
{
if(!HashTablecnt[index])
return -1;
index = (index + 1) % maxN;
}
return index;
}
void insert(int n)
{
int index = find(n);
if(index >= 0)
{
HashTablecnt[index]++;
return;
}
index = n % maxN;
index = (index + maxN) % maxN;
while(HashTablecnt[index])
index = (index + 1) % maxN;
HashTablea[index] = n;
HashTablecnt[index] = 1;
}
int cnt(int n)
{
int index = find(n);
if(index >= 0)
return HashTablecnt[index];
else
return 0;
}
};