链表法解决hash冲突[亲测有效]

/* @链表法解决hash冲突 * 大单元数组，小单元链表 */ #pragma once  #include <string> using namespace std; template<typename map_t> struct Node { size_t key; map_t content; Node *next; bool isEmpty; Node():next(NULL),isEmpty(true){} }; // 根据hash函数将content添加到hash表中 template<typename map_t> class ListHash { public: ListHash(); ~ListHash(); bool insert(size_t key, const map_t& val); bool find(size_t key, map_t& val); bool erase(size_t key); private: size_t hash(size_t key); private: size_t m_nElementSize; Node<map_t> *m_pNodeArray; }; //////////////////////////实现///////////////////////// template<typename map_t> ListHash<map_t>::ListHash() { m_nElementSize = 3; m_pNodeArray = NULL; m_pNodeArray = new Node<map_t>[m_nElementSize]; } template<typename map_t> ListHash<map_t>::~ListHash() { delete[] m_pNodeArray; m_pNodeArray = NULL; } template<typename map_t> size_t ListHash<map_t>::hash( size_t key ) { return key % m_nElementSize; } template<typename map_t> bool ListHash<map_t>::insert( size_t key, const map_t& val ) { size_t idx = hash(key); Node<map_t> *pNode = &m_pNodeArray[idx]; if (m_pNodeArray[idx].isEmpty) { pNode->key = key; pNode->content = val; pNode->isEmpty = false; pNode->next = NULL; } else { while (pNode->next != NULL) { pNode = pNode->next; } Node<map_t> *pTempNode = new Node<map_t>; pTempNode->key = key; pTempNode->content = val; pTempNode->isEmpty = false; pTempNode->next = NULL; pNode->next = pTempNode; } return true; } template<typename map_t> bool ListHash<map_t>::erase( size_t key ) { size_t idx = hash(key); Node<map_t> *pNode = &m_pNodeArray[idx]; Node<map_t> *pPrepNode = NULL; while (pNode!= NULL) { if (pNode->key == key) { if (pPrepNode) { pPrepNode->next = pNode->next; } delete pNode; return true; } pPrepNode = pNode; pNode = pNode->next; } return false; } template<typename map_t> bool ListHash<map_t>::find( size_t key, map_t& val ) { size_t idx = hash(key); Node<map_t> *pNode = &m_pNodeArray[idx]; while (pNode!= NULL) { if (pNode->key == key) { val = pNode->content; return true; } pNode = pNode->next; } return false; }