欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

【数据结构】c++实现HashTable(开链法)

程序员文章站 2022-04-02 07:53:13
#include #include using namespace std; template struct HashTableNode { K _key; V _va...
#include 
#include 
using namespace std;

template 
struct HashTableNode
{
	K _key;
	V _value;
	HashTableNode* _next;

	HashTableNode(const K&key, const V&value)
		:_key(key)
		, _value(value)
		, _next(NULL)
	{}
};

template 
struct DefaultHashFunc
{
	size_t operator()(const K&key)
	{
		return key;
	}
};

template >
class HashTableBucket
{
	typedef HashTableNode Node;
public:
	HashTableBucket()
		:_size(0)
	{}
	HashTableBucket(size_t size)
		:_size(0)
	{
		_tables.resize(size);
	}

	bool Insert(const K&key, const V&value)
	{
		_CheckExpand();
		size_t index = HashFunc(key, _tables.size());
		Node* begin = _tables[index];
		while (begin)
		{
			if (begin->_key == key)
				return false;
			begin = begin->_next;
		}

		Node* tmp = new Node(key, value);
		tmp->_next = _tables[index];
		_tables[index] = tmp;

		++_size;
		return true;
	}
	size_t HashFunc(const K&key, size_t capacity)
	{
		HashFun hf;
		return hf(key) % capacity;
	}
	void PrintTables()
	{
		for (size_t i = 0; i ",i);
			Node* cur = _tables[i];
			while (cur)
			{
				cout _key _value ";
				cur = cur->_next;

			}
			cout  size)
			{
				return _PrimeList[i];
			}
		}

		return _PrimeList[_PrimeSize - 1];
	}

	void _CheckExpand()
	{
		// 载荷因子到1时进行增容,保证效率
		if (_size == _tables.size())
		{
			size_t newSize = _GetNextPrime(_size);
			if (_size == newSize)
				return;

			vector newTables;
			newTables.resize(newSize);

			for (size_t i = 0; i _next;

					// 头插
					size_t newIndex = HashFunc(tmp->_key, newTables.size());
					tmp->_next = newTables[newIndex];
					newTables[newIndex] = tmp;
				}

				_tables[i] = NULL;
			}

			_tables.swap(newTables);
		}
	}
protected:
	vector*> _tables;
	size_t _size;
};