hashmap的C++实现
按照hashmap的基本原理用C++实现了简单的基本功能，复杂的实现参考C++库的源码。
/* * HashMap.h * * 2012-7-25 * Author: luxiaoxun */#ifndef HASHMAP_H_#define HASHMAP_H_#include <iostream>using namespace std;//List all the integer number no less than 57 total number is 28//And each number is about half of its next numberstatic int prime[28] ={ 57, 97, 193,389,769, 1543, 3079,6151,12289,24593, 49157, 98317,196613,393241,786433, 1572869, 3145739,6291469,12582917,25165843, 50331653, 100663319,201326611, 402653189, 805306457, 1610612741};class HashMapUtil{public: static int find_NextPrimeNumber( int current ) { //Find the next prime number by searching in the prime number list int i = 0; for( ; i < 28 ; i++ ) if ( current < prime[i] )break; return prime[i]; //return the next larger prime. }};template < class Key, class Value, class HashFunc, class EqualKey >class Hash_Map{private: template < class _Key, class _Value> class KeyNode { public: _Value value;//Store the value _Key key;//Store the keyword int used; //if the type of Value/Key is your own class, make sure they can handle copy constructor and operator = KeyNode():used(0){} KeyNode(const KeyNode & kn) { value = kn.value; key = kn.key; used = kn.used; } KeyNode & operator=(const KeyNode & kn) { if(this == &kn) return *this; value = kn.value; key = kn.key; used = kn.used; return *this; } };public: Hash_Map(); void insert( const Key& hashKey , const Value& value ); void remove( const Key& hashKey ); void rehash();//use it when rehashing Value& find( const Key& hashKey ); Value& operator [] ( const Key& hashKey ); ~Hash_Map();private: HashFunc* hf; EqualKey* ek; HashMapUtil* hml; KeyNode <Key ,Value> *table; int size;//current number of itmes int capacity;//capacity of the array const static double loadingFactor = 0.8; int findKey( const Key& hashKey );//find the index of a key};template<class Key , class Value , class HashFunc , class EqualKey>Hash_Map<Key, Value, HashFunc, EqualKey>::Hash_Map(){ hf = new HashFunc; ek = new EqualKey; hml = new HashMapUtil; capacity = hml->find_NextPrimeNumber(0); //initialize the capacity with first primer 57 //resize the table with capacity because an extra one is used //to return the NULL type of Value in the function find table = new KeyNode<Key , Value>[capacity+1]; for( int i = 0 ; i < capacity ; i++ )//initialize the table table[i].used = 0; size = 0;}template<class Key, class Value, class HashFunc, class EqualKey>Hash_Map<Key, Value, HashFunc, EqualKey>::~Hash_Map(){ delete []table; delete hf; delete ek; delete hml;}template<class Key, class Value, class HashFunc, class EqualKey>Value& Hash_Map<Key, Value, HashFunc, EqualKey>::find( const Key& hashKey ){ int index = findKey( hashKey ); if ( index < 0 ) //if index <0 ,not found,else return the index { cout<<"can not find the key!"<<endl; return table[capacity].value; //return NULL } else {return table[index].value; }}template<class Key, class Value, class HashFunc, class EqualKey>void Hash_Map<Key, Value, HashFunc, EqualKey>::insert( const Key& hashKey, const Value& value ){ int hash_value = ( hf->cal_hash( hashKey ) ) % capacity; while( table[hash_value].used ==1 )//search an empty place,and then insert into it { if ( hash_value == capacity - 1 ) hash_value = 0; else hash_value++; } table[hash_value].used = 1;//modify the KeyNode table[hash_value].key = hashKey; table[hash_value].value = value; size++; //if the table's size is too large ,then rehash it if ( size >= capacity * loadingFactor )rehash();}template<class Key, class Value, class HashFunc, class EqualKey>void Hash_Map<Key, Value, HashFunc, EqualKey>::rehash(){ int pastsize = capacity; //create a new array to copy the information in the old table capacity = hml->find_NextPrimeNumber( capacity ); KeyNode<Key,Value>* tmp = new KeyNode<Key,Value>[capacity]; for( int i = 0 ; i < pastsize ; i++ ) if ( table[i].used == 1 )//copy the KeyNode into the tmp array { tmp[i] = table[i]; } delete []table; //release the memory of the old table table = new KeyNode<Key,Value>[capacity+1];//resize the table for( int i = 0 ; i < capacity ; i++ ) //initialize the table { table[i].used = 0; } for( int i = 0 ; i < pastsize ; i++) //insert the item into the table one by one if ( tmp[i].used == 1 ) insert( tmp[i].key, tmp[i].value ); delete []tmp;//delete the tmp array}template<class Key, class Value, class HashFunc, class EqualKey>void Hash_Map<Key, Value, HashFunc, EqualKey>::remove( const Key& hashKey ){ int index = findKey( hashKey );//find the index of the key if ( index < 0 ) //if find modify the flag with 0,else print out "no such key!" { cout<<"No such Key!"<<endl; } else { table[index].used = 0; size--; }}template<class Key, class Value, class HashFunc, class EqualKey>Value& Hash_Map<Key, Value, HashFunc, EqualKey>::operator[](const Key& hashKey){ return find( hashKey );//overload the operation to return the value of the element}template<class Key, class Value, class HashFunc, class EqualKey>int Hash_Map<Key, Value, HashFunc, EqualKey>::findKey( const Key& hashKey ){ int index = ( hf->cal_hash( hashKey ) ) % capacity; //if the "used" flag equals 1 and the key equals to hashkey, find it for(int i = 0 ; (table[index].used == 1) && !(ek->Check_equal(table[index].key,hashKey)) && i <= capacity ; i++ ) { if ( index == capacity - 1 ) //if index>=capacity-1,return to the head of the array index = 0; else index++; } if ( (table[index].used != 1) || !(ek->Check_equal( table[index].key,hashKey )) ) return -1; else return index;}#endif /* HASHMAP_H_ */
C++编译器不支持模板头文件和实现代码分离的编译，如果的类实现和类声明分别放在cpp文件和h头文件里，那么在测试代码里include要加上实现的代码，比如加上#include"HashMap.cpp"。
使用hashmap，需要自己提供针对key的hash仿函数类和equal仿函数类，测试代码：
/* * main.cpp * * 2012-7-25 * Author: luxiaoxun */#include "HashMap.h"#include <string>#include <iostream>using namespace std;//Hash function you provided must be correspond to the type of the Keyclass HashFunc{ public: int cal_hash(const string & key ) { unsigned int hash = 0; for(int i = 0; i < key.length(); ++i) { // equivalent to: hash = 65599*hash + (*str++); hash = key[i] + (hash << 6) + (hash << 16) - hash; } return (hash & 0x7FFFFFFF); }};//Equal function you provided to check whether two Keys are equal//must be correspond to the type of the Keyclass EqualKey{ public: bool Check_equal( string A , string B ) { if ( A == B ) return true;//if equal return true else return false;//else false }};int main(){ Hash_Map<string,string,HashFunc,EqualKey> hm; cout<<"insert"<<endl; hm.insert( "hello" , "you" ); hm.insert( "why" , "dream" ); hm.insert( "java" ,"good" ); hm.insert( "welcome" ,"haha" ); cout<<"after insert"<<endl; cout<<hm.find( "welcome" )<<endl; cout<<hm.find( "java" )<<endl; cout<<hm["why"]<<endl; cout<<hm["hello"]<<endl; hm.remove( "hello" ); //remove is ok cout<<hm.find( "hello" )<<endl; //not exist print NULL cout<<hm[ "why" ]<<endl; return 0;}