ハッシュマップ - yanprog @ ウィキ

hash_map<V,N> で値の型がV,keyがlong longでメモリNのハッシュマップを作成する。
Nは、メモリと計算時間のバランスを考えて決定する。大体、入れたいサイズと同じぐらいならOK。
newで確保した領域の開放は書いていないので注意。[key]でアクセスし、clear()で要素を全削除。have(key)は、keyを持っているかどうか。
key%Nがちゃんと一様に分布していないと実行速度が遅くなるので注意。

template <typename V, int N> struct hash_map{
	struct element{
		ll key;
		V value;
		element* next;
		element(ll _key){
			key=_key;
			value=777;
			next=0;
		}
	};
	vector<element*> table;
	hash_map(){
		table=vector<element*>(N);
	}
	void clear(){
		REP(i,N) table[i]=0;
	}
	V& operator[](const ll key){
		int idx=( (unsigned long long)(key) ) %N;
		if(table[idx]==0){
			element *e=new element(key);
			table[idx]=e;
			return e->value;
		}
		element *e=table[idx];
		while(true){
			assert(e!=0);
			if(e->key==key)return e->value;
			if(e->next==0){
				element *e2=new element(key);
				e->next=e2;
				return e2->value;
			}
			e=e->next;
		}
	}
	bool have(const ll key){
		int idx=( (unsigned long long)(key) ) %N;
		if(table[idx]==0){
			return false;
		}
		element *e=table[idx];
		while(true){
			assert(e!=0);
			if(e->key==key)return true;
			if(e->next==0){
				return false;
			}
			e=e->next;
		}
	}
};