hashmap的C++實(shí)現(xiàn)

1、 按照hashmap的基本原理用C實(shí)現(xiàn)了簡(jiǎn)單的基本功能，復(fù)雜的實(shí)現(xiàn)參考C 庫(kù)的源碼。 /* * 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 number static int prime28

2、 = 57, 97, 1543, 193, 3079, 389, 6151, 12289, 769, 24593, 98317, 3145739, 6291469, 49157, 1572869, 50331653, 100663319, 196613, 393241, 12582917, 786433, 25165843, 201326611, 402653189, 805306457, 1610612741 ; class HashMapUtil public: static int find_NextPrimeNumber( int current ) /Find the next pr

3、ime number by searching in the prime number list int i = 0; for( ; i 28 ; i+ ) if ( current primei ) break; return primei; /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 /Store t

4、he value /Store the keyword public: _Value value; _Key key; int used; of Value/Key is your own class, make sure they can handle copy /if the type constructor and operator = KeyNode():used(0) KeyNode(const KeyNode kn) value = kn.value; key = kn.key; used = kn.used; KeyNode operator=(const KeyNode kn)

5、 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 clear(); /use it when rehashing Value find( const Key hashKey ); Value operator ( const Key ha

6、shKey ); Hash_Map(); private: HashFunc* hf; EqualKey* ek; HashMapUtil* hml; KeyNode Key ,Value *table; int size;/current number of itmesint capacity; /capacity of the array const static double loadingFactor = 0.8; /find the index of a key int findKey( const Key hashKey ); ; templateclass Key , class

7、 Value , class HashFunc , class EqualKey Hash_MapKey, Value, HashFunc, EqualKey:Hash_Map() /initialize the capacity with hf = new HashFunc; ek = new EqualKey; hml = new HashMapUtil; capacity = hml-find_NextPrimeNumber(0); first primer 57 /resize the table with capacity because an extra one is used /

8、to return the NULL type of Value in the function find table = new KeyNodeKey , Valuecapacity+1; for( int i = 0 ; i capacity ; i+ )/initialize the table tablei.used = 0; size = 0; templateclass Key, class Value, class HashFunc, class EqualKey Hash_MapKey, Value, HashFunc, EqualKey:Hash_Map() delete t

9、able; delete hf; delete ek; delete hml; templateclass Key, class Value, class HashFunc, class EqualKey Value Hash_MapKey, Value, HashFunc, EqualKey:find( const Key hashKey ) int index = findKey( hashKey ); if ( index 0 ) /if index 0 ,not found,else return the index coutcan not find the key!endl; ret

10、urn tablecapacity.value; /return NULL else return tableindex.value; templateclass Key, class Value, class HashFunc, class EqualKey void Hash_MapKey, Value, HashFunc, EqualKey:insert( const Key hashKey, const Value value ) int hash_value = ( hf-cal_hash( hashKey ) ) % capacity; while( tablehash_value

11、.used =1 )/search an empty place,and then insert into it if ( hash_value = capacity - 1 ) hash_value = 0; else hash_value+; /modify the KeyNode tablehash_value.used = 1; tablehash_value.key = hashKey; tablehash_value.value = value; size+; /if the tables size is too large ,then rehash it if ( size =

12、capacity * loadingFactor ) clear(); templateclass Key, class Value, class HashFunc, class EqualKey void Hash_MapKey, Value, HashFunc, EqualKey:clear() int pastsize = capacity; /create a new array to copy the information in the old table capacity = hml-find_NextPrimeNumber( capacity ); KeyNodeKey,Val

13、ue* tmp = new KeyNodeKey,Valuecapacity; /copy the KeyNode into the tmp array for( int i = 0 ; i pastsize ; i+ ) if ( tablei.used = 1 ) tmpi = tablei; delete table; /release the memory of the old table /resize the table table = new KeyNodeKey,Valuecapacity+1; for( int i = 0 ; i capacity ; i+ ) /initi

14、alize the table tablei.used = 0; for( int i = 0 ; i pastsize ; i+) /insert the item into the table one by one if ( tmpi.used = 1 ) insert( tmpi.key, tmpi.value ); delete tmp;/delete the tmp array templateclass Key, class Value, class HashFunc, class EqualKey void Hash_MapKey, Value, HashFunc, EqualK

15、ey: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! coutNo such Key!endl; else tableindex.used = 0; size-; templateclass Key, class Value, class HashFunc, class EqualKey Value Hash_MapKey

16、, Value, HashFunc, EqualKey:operator(const Key hashKey) return find( hashKey ); /overload the operation to return the value of the element const Key templateclass Key, class Value, class HashFunc, class EqualKey int Hash_MapKey, Value, HashFunc, EqualKey:findKey( hashKey ) int index = ( hf-cal_hash(

17、 hashKey ) ) % capacity; /if the used flag equals 1 and the key equals to hashkey, find it for(int i = 0 ; (tableindex.used = 1) !(ek-Check_equal(tableindex.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 (

18、(tableindex.used | !(ek-Check_equal( tableindex.key,hashKey ) ) return -1; else return index; != 1) #endif /* HASHMAP_H_ */ C 編譯器不支持模板頭文件和實(shí)現(xiàn)代碼分離的編譯， 如果的類實(shí)現(xiàn)和類聲明分別放 在 cpp 文件和 h 頭文件里，那么在測(cè)試代碼里 include 要加上實(shí)現(xiàn)的代碼，比如加上 #includeHashMap.cpp 。 使用hashmap,需要自己提供針對(duì) key的hash仿函數(shù)類和equal仿函數(shù)類，測(cè)試代碼： /* * main.cpp * 201

19、2-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 Key class 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 = keyi + (hash 6) + (hash 16) - hash; return (hash 0 x7FFFFFFF); ;