hashmap的C++实现
［来源］ 达内 ［编辑］ 达内 ［时间］2012-09-08
按照hashmap的基本原理用C++实现了简单的基本功能，复杂的实现参考C++库的源码，C++最新的标准库里已经有以下四种基于hashtable的容器
hashmap的C++实现
< p style="margin: 5px auto; padding: 0px; text-indent: 0px; line-height: 19px; color: rgb(0, 0, 0); font-size: 13px; font-family: verdana, 'ms song', 宋体, Arial, 微软雅黑, Helvetica, sans-serif; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: left; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; background-color: rgb(254, 254, 242); "> 按照hashmap的基本原理用C++实现了简单的基本功能，复杂的实现参考C++库的源码，C++最新的标准库里已经有以下四种基于hashtable的容器： < p style="margin: 5px auto; padding: 0px; text-indent: 0px; line-height: 19px; color: rgb(0, 0, 0); font-size: 13px; font-family: verdana, 'ms song', 宋体, Arial, 微软雅黑, Helvetica, sans-serif; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: left; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; background-color: rgb(254, 254, 242); ">unordered_set (C++11) unordered_multiset (C++11) unordered_map (C++11) unordered_multimap (C++11) 。具体参考：< div style="margin: 5px 0px; padding: 5px; background-color: rgb(245, 245, 245); font-family: 'Courier New'; font-size: 12px; border: 1px solid rgb(204, 204, 204); overflow: auto; color: rgb(0, 0, 0); font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: left; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; " class="cnblogs_code">/* * HashMap.h * 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 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 HashMap { 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: HashMap(); ~HashMap(); bool insert(const Key& hashKey, const Value& value); bool remove(const Key& hashKey); void rehash(); // use it when rehashing Value& find(const Key& hashKey); const Value& operator [](const Key& hashKey) const ; Value& operator [](const Key& hashKey); private : HashFunc hash; EqualKey equal; HashMapUtil hml; KeyNode<Key ,Value> *table; int size; // current number of itmes int capacity; // capacity of the array static const double loadingFactor; int findKey(const Key& hashKey); // find the index of a key}; template <class Key , class Value , class HashFunc , class EqualKey> const double HashMap<Key, Value, HashFunc, EqualKey>::loadingFactor = 0.9 ; template<class Key , class Value , class HashFunc , class EqualKey> HashMap <Key, Value, HashFunc, EqualKey>::HashMap() { hash = HashFunc(); equal = EqualKey(); hml = 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> HashMap <Key, Value, HashFunc, EqualKey>::~HashMap() { delete []table; } template <class Key, class Value, class HashFunc, class EqualKey> bool HashMap<Key, Value, HashFunc, EqualKey>::insert(const Key& hashKey, const Value& value) { int index = hash(hashKey)%capacity; // cout<<"Index is "<<index<<endl; if(table[index].used == 1) // the key-value's hash is unique { // cout<<"The key-value must be unique!"<<endl; return false ; } table[index].used = 1 ; //modify the KeyNode table[index].key = hashKey; table[index].value = value; size++; // if the table's size is too large ,then rehash it if (size >= capacity * loadingFactor) rehash(); return true; } template < class Key, class Value, class HashFunc, class EqualKey> void HashMap<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> bool HashMap<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; return false; } else { table[index].used = 0; size --; return true; } } template <class Key, class Value, class HashFunc, class EqualKey> Value & HashMap<Key, Value, HashFunc, EqualKey>ind(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> const Value& HashMap<Key, Value, HashFunc, EqualKey>::operator [](const Key& hashKey) const { return find(hashKey); // overload the operation to return the value of the element } template<class Key, class Value, class HashFunc, class EqualKey> Value & HashMap<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 HashMap<Key, Value, HashFunc, EqualKey>indKey(const Key& hashKey) { int index = hash(hashKey)% capacity; if ((table[index].used != 1 ) || !equal(table[index].key,hashKey)) return -1; else return index; } #endif /* HASHMAP_H_ */
#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 operator ()(const string & key ) { int hash = 0; for(int i = 0; i < key.length(); ++ i) { hash = hash << 7 ^ key[i]; } return (hash & 0x7FFFFFFF ); } }; // Equal function you provided to check whether two Keys are equal // must be correspond to the type of the Key class EqualKey { public: bool operator ()(const string & A ,const string & B) { if ((B) == 0 ) return true ; //if equal return true else return false ; //else false } }; int main() { HashMap<string ,string,HashFunc,EqualKey> hm; hm.insert( "hello " , " you" ); hm.insert(" why" , "dream "); hm.insert( "java " ,"good "); hm.insert( "welcome " ," haha" ); hm.insert(" welcome" ,"hehe "); // error, key-value must be unique cout<<" after insert:" <<endl; cout<<hm.find( " welcome" )<<endl; cout<<hm.find( " java" )<<endl; cout<<hm[ " why" ]<<endl; cout<<hm[ " hello" ]<<endl; if (hm.remove("hello ")) cout <<"remove is ok "<<endl; // remove is ok cout<<hm.find(" hello")<<endl; // not exist print NULL hm[" why" ] = "love "; // modify the value cout<<hm["why "]<<endl; return 0 ; }
