【数据结构】c++实现HashTable（开链法）

左手的ㄟ右手 2022-08-22 03:46 16阅读 0赞

#include <iostream>
    #include <vector>
    using namespace std;
    
    template <class K, class V>
    struct HashTableNode
    {
    	K _key;
    	V _value;
    	HashTableNode<K, V>* _next;
    
    	HashTableNode(const K&key, const V&value)
    		:_key(key)
    		, _value(value)
    		, _next(NULL)
    	{}
    };
    
    template <class K>
    struct DefaultHashFunc
    {
    	size_t operator()(const K&key)
    	{
    		return key;
    	}
    };
    
    template <class K, class V, class HashFun = DefaultHashFunc<K>>
    class HashTableBucket
    {
    	typedef HashTableNode<K, V> 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 < _tables.size(); ++i)
    		{
    			printf("Tables[%d]->",i);
    			Node* cur = _tables[i];
    			while (cur)
    			{
    				cout << "[" << cur->_key << ":" << cur->_value << "]"<<"->";
    				cur = cur->_next;
    
    			}
    			cout << "NULL"<<endl;
    		}
    		cout << endl;
    	}
    protected:
    	size_t _GetNextPrime(size_t size)
    	{
    		static const int _PrimeSize = 28;
    		static const unsigned long _PrimeList[_PrimeSize] =
    		{
    			53ul, 97ul, 193ul, 389ul, 769ul,
    			1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
    			49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
    			1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
    			50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
    			1610612741ul, 3221225473ul, 4294967291ul
    		};
    
    		for (size_t i = 0; i < _PrimeSize; ++i)
    		{
    			if (_PrimeList[i] > 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<Node*> newTables;
    			newTables.resize(newSize);
    
    			for (size_t i = 0; i < _tables.size(); ++i)
    			{
    				Node* cur = _tables[i];
    				while (cur)
    				{
    					// 取节点
    					Node* tmp = cur;
    					cur = cur->_next;
    
    					// 头插
    					size_t newIndex = HashFunc(tmp->_key, newTables.size());
    					tmp->_next = newTables[newIndex];
    					newTables[newIndex] = tmp;
    				}
    
    				_tables[i] = NULL;
    			}
    
    			_tables.swap(newTables);
    		}
    	}
    protected:
    	vector<HashTableNode<K, V>*> _tables;
    	size_t _size;
    };