/* @链表法解决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 = ;
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;
}