Hash_map 实现源码

#include <stdio.h> #include <iostream> #include <assert.h> using namespace std; //begin HashMap define #define HWINLINE inline struct __ITERATOR { }; typedef __ITERATOR* ITERATOR; #define before_start_pos ((ITERATOR)-1L) #define SIZE_T_MAX UINT_MAX // 容器最大的容量 //End HashMap define // 构造容器的所有成员 template<class TYPE> inline void container_construct(TYPE* pElements, int nCount) { assert(nCount == 0 || NULL != pElements); // 内存区域初始化为0 memset((void*)pElements, 0, nCount * sizeof(TYPE)); // 调用所有的构造函数 for (; nCount--; pElements++) { // 必须包含new.h ::new ((void*)pElements) TYPE; } } // 析构容器的所有成员 template<class TYPE> inline void container_destruct(TYPE* pElements, int nCount) { assert(nCount == 0 || NULL != pElements); // 调用析构函数 for (; nCount--; pElements++) pElements->~TYPE(); } // 比较容器的成员 template<class TYPE, class ARG_TYPE> inline bool container_compare(const TYPE* pElement1, const ARG_TYPE* pElement2) { assert(NULL != pElement1); assert(NULL != pElement2); return *pElement1 == *pElement2; } template<class KEY> inline unsigned int hash_key(KEY key) { KEY iVal = key; unsigned int iRes = ((unsigned int)(void*)(unsigned int)iVal) >> 4; // cout<<" ------------iRes: "<<iRes<<endl; return ((unsigned int)(void*)(unsigned int)key) >> 4; } // 内存块类 struct TMemPlex // warning variable length structure { TMemPlex* pNext; void* data() { return this+1; } static TMemPlex* create(TMemPlex*& head, unsigned int nMax, unsigned int cbElement); void freeDataChain(); // free this one and links }; TMemPlex* TMemPlex::create(TMemPlex*& pHead, unsigned int nMax, unsigned int cbElement) { assert(nMax > 0 && cbElement > 0); TMemPlex* p = (TMemPlex*) new unsigned char[sizeof(TMemPlex) + nMax * cbElement]; p->pNext = pHead; pHead = p; return p; } void TMemPlex::freeDataChain() { TMemPlex* p = this; while (p != NULL) { unsigned char* bytes = (unsigned char*) p; TMemPlex* pNextTemp = p->pNext; delete[] bytes; p = pNextTemp; } } #define assert_valid(x) ((x)->assertValid()) // HASHMAP类 template<class KEY, class VALUE> class CMap { public: // 使用拉地址链算法,当多个主键具有相同的HASH时,将其列入链表 struct TAssoc { TAssoc* pNext; unsigned int nHashValue; KEY key; VALUE value; }; public: CMap(int nBlockSize = 10); int size() const; bool isEmpty() const; bool lookup(KEY key, VALUE& rValue) const; VALUE& operator[](KEY key); void put(KEY key, VALUE newValue); bool removeKey(KEY key); void removeAll(); ITERATOR getFirstPos() const; void getNext(ITERATOR& rNextPosition, KEY& rKey, VALUE& rValue) const; unsigned int capacity() const; void init(unsigned int hashSize, bool bAllocNow = true); protected: TAssoc** m_pHashTable; unsigned int m_nHashTableSize; int m_nCount; TAssoc* m_pFreeList; struct TMemPlex* m_pBlocks; int m_nBlockSize; TAssoc* newAssoc(); void freeAssoc(TAssoc*); TAssoc* getAssocAt(KEY, unsigned int&) const; public: ~CMap(); void assertValid() const; }; // INLINE函数 template<class KEY, class VALUE> inline int CMap<KEY, VALUE>::size() const { return m_nCount; } template<class KEY, class VALUE> inline bool CMap<KEY, VALUE>::isEmpty() const { return m_nCount == 0; } template<class KEY, class VALUE> inline void CMap<KEY, VALUE>::put(KEY key, VALUE newValue) { (*this)[key] = newValue; } template<class KEY, class VALUE> inline ITERATOR CMap<KEY, VALUE>::getFirstPos() const { return (m_nCount == 0) ? NULL : before_start_pos; } template<class KEY, class VALUE> inline unsigned int CMap<KEY, VALUE>::capacity() const { return m_nHashTableSize; } // OUTLINE函数 template<class KEY, class VALUE> inline CMap<KEY, VALUE>::CMap(int nBlockSize) { assert(nBlockSize > 0); m_pHashTable = NULL; m_nHashTableSize = 17; // 默认HASH大小 m_nCount = 0; m_pFreeList = NULL; m_pBlocks = NULL; m_nBlockSize = nBlockSize; } template<class KEY, class VALUE> inline void CMap<KEY, VALUE>::init( unsigned int nHashSize, bool bAllocNow) { assert_valid(this); assert(m_nCount == 0); assert(nHashSize > 0); if (m_pHashTable != NULL) { delete[] m_pHashTable; m_pHashTable = NULL; } if (bAllocNow) { m_pHashTable = new TAssoc* [nHashSize]; memset(m_pHashTable, 0, sizeof(TAssoc*) * nHashSize); } cout<<"^^^^^^^^^^^^^^^^ nHashSize: "<<nHashSize<<endl; m_nHashTableSize = nHashSize; } template<class KEY, class VALUE> inline void CMap<KEY, VALUE>::removeAll() { assert_valid(this); if (m_pHashTable != NULL) { // destroy elements (values and keys) for (unsigned int nHash = 0; nHash < m_nHashTableSize; nHash++) { TAssoc* pAssoc; for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL; pAssoc = pAssoc->pNext) { #ifdef ISO_CPLUSPLUS container_destruct<VALUE>(&pAssoc->value, 1); container_destruct<KEY>(&pAssoc->key, 1); #else container_destruct(&pAssoc->value, 1); container_destruct(&pAssoc->key, 1); #endif } } } delete[] m_pHashTable; m_pHashTable = NULL; m_nCount = 0; m_pFreeList = NULL; m_pBlocks->freeDataChain(); m_pBlocks = NULL; } template<class KEY, class VALUE> inline CMap<KEY, VALUE>::~CMap() { removeAll(); assert(m_nCount == 0); } template<class KEY, class VALUE> inline typename CMap<KEY, VALUE>::TAssoc* CMap<KEY , VALUE>::newAssoc() { if (m_pFreeList == NULL) { //cout<<"******************* m_nBlockSize: "<<m_nBlockSize<<endl; TMemPlex* newBlock = TMemPlex::create(m_pBlocks, m_nBlockSize, sizeof(TAssoc)); TAssoc* pAssoc = (TAssoc*) newBlock->data(); pAssoc += m_nBlockSize - 1; for (int i = m_nBlockSize-1; i >= 0; i--, pAssoc--) { pAssoc->pNext = m_pFreeList; m_pFreeList = pAssoc; } } assert(m_pFreeList != NULL); TAssoc* pAssoc = m_pFreeList; m_pFreeList = m_pFreeList->pNext; m_nCount++; assert(m_nCount > 0); #ifdef ISO_CPLUSPLUS container_construct<KEY>(&pAssoc->key, 1); container_construct<VALUE>(&pAssoc->value, 1); #else container_construct(&pAssoc->key, 1); container_construct(&pAssoc->value, 1); #endif //ISO_CPLUSPLUS return pAssoc; } template<class KEY, class VALUE> inline void CMap<KEY, VALUE>::freeAssoc( typename CMap<KEY, VALUE>::TAssoc* pAssoc) { #ifdef ISO_CPLUSPLUS container_destruct<VALUE>(&pAssoc->value, 1); container_destruct<KEY>(&pAssoc->key, 1); #else container_destruct(&pAssoc->value, 1); container_destruct(&pAssoc->key, 1); #endif //ISO_CPLUSPLUS pAssoc->pNext = m_pFreeList; m_pFreeList = pAssoc; m_nCount--; assert(m_nCount >= 0); if (m_nCount == 0) { removeAll(); } } template<class KEY, class VALUE> inline typename CMap<KEY, VALUE>::TAssoc* CMap<KEY, VALUE>::getAssocAt(KEY key, unsigned int& nHash) const { #ifdef ISO_CPLUSPLUS nHash = hash_key<ARG_KEY>(key) % m_nHashTableSize; #else nHash = hash_key(key) % m_nHashTableSize; #endif //ISO_CPLUSPLUS // cout<<"