哈希表复习

Aki 发布于 2023-02-25 248 次阅读

开散列哈希表。。。。。。

#include<iostream>
#include<memory>
#include<vector>
#include<string>
#include<cassert>


using std::vector, std::cout, std::endl, std::cin;
using std::string, std::destroy_at,std::construct_at;


//哈希表使用的类的声明
template<class Key, class Value>
class Hash_Table;

template<class Key, class Value>
struct pair;

template<class Key, class Value>
struct _hash_node_;

template<class Key, class Value>
class iterator;


//下面三个是哈希函数
//int版本
size_t BKDHash(const int& key) noexcept
{
	return static_cast<size_t>(key);
}

//string版本
size_t BKDHash(const string& key) noexcept
{
	size_t seed = 131, hash = 0, siz = key.size();
	for (size_t i = 0; i < siz; ++i)
	{
		hash = hash * seed + key[i];
	}
	return hash;
}

//char版本
size_t BKDHash(const char& key) noexcept
{
	return static_cast<size_t>(key);
}


//素数表
const size_t PRIME_COUNT = 28;
const size_t prime_list[PRIME_COUNT] = { 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 };



//pair类型，存放键值对
template<class Key, class Value>
struct pair
{
	Key key;
	Value value;
};


//哈希结点类型
template<class Key, class Value>
struct _hash_node_
{
	pair<Key, Value>  _data;
	_hash_node_<Key, Value>* _next;
};



//哈希迭代器类型
template<class Key, class Value>
class iterator
{
public:

	using _pnode = _hash_node_<Key, Value>*;
	using _node = _hash_node_<Key, Value>;
	using _ptable = Hash_Table<Key, Value>*;

	iterator(const _pnode p , const _ptable t )noexcept :_p(p), _t(t) {}

	iterator(const iterator& rhs)noexcept :_p(rhs._p), _t(rhs._t) {}

	const iterator& operator=(const iterator& rhs) noexcept
	{
		if (this != &rhs)
		{
			_p = rhs._p;
			_t = rhs._t;
		}
		return *this;
	}

	~iterator()noexcept {}

	//对迭代器解引用返回pair类型
	pair<Key, Value>& operator*()const noexcept
	{
		assert(_p);
		return _p->_data;
	}

	//对迭代器使用指针操作符返回pair指针
	pair<Key, Value>* operator->()const noexcept
	{
		assert(_p);
		return &(_p->_data);
	}

        //自增函数
	iterator& operator++()noexcept
	{
		assert(_t);
		if (!_p)
		{
			return *this;
		}
		if (_p->_next)
		{
			_p = _p->_next;
			return *this;
		}
		else
		{
			size_t siz = _t->_table.size();
			size_t index = (BKDHash(_p->_data.key) % siz) + 1;
			for (; index < siz; ++index)
			{
				if (_t->_table[index])
				{
					_p = _t->_table[index];
					return *this;
				}
			}
			_p = nullptr;
			return *this;
		}	
	}

	const iterator operator++(int)noexcept
	{
		iterator tmp(*this);
		++(*this);
		return tmp;
	}

	bool operator==(const iterator& rhs) const noexcept
	{
		return _p == rhs._p && _t == rhs._t;
	}

	bool operator!=(const iterator& rhs) const noexcept
	{
		return !(*this == rhs);
	}

private:
	_pnode _p;
	_ptable _t;
};


//哈希表
template<class Key, class Value>
class Hash_Table
{
public:

	friend class iterator<Key,Value>;

	using _pnode = _hash_node_<Key, Value>*;


	Hash_Table()noexcept :_n(0) {}

	~Hash_Table()noexcept
	{
		clear();
	}

	void clear()noexcept
	{
		size_t siz = _table.size();
		_pnode pt = nullptr, pre = nullptr;
		for (size_t i = 0; i < siz; ++i)
		{
			pt = _table[i];
			for (; pt; )
			{
				pre = pt;
				pt = pt->_next;
				_destroy_(pre);
			}
			_table[i] = nullptr;
		}
		_table.resize(0);
		_n = 0;
	}

	void insert(const pair<Key, Value>& val) noexcept
	{
		if (_find(val))
		{
			return;
		}

		if (_table.empty())
		{
			_table.resize(53ul, nullptr);
		}

		if ((static_cast<double>(_n) / static_cast<double>(_table.size())) > 0.75)
		{
			size_t siz = _table.size();
			size_t nxt = _get_next_prime(siz);
			if (nxt == 0)
			{
				return;
			}
			vector<_pnode> new_table(nxt, nullptr);
			_pnode pt = nullptr;
			for (size_t i = 0; i < siz; ++i)
			{
				pt = _table[i];
				if (pt)
				{
					new_table[BKDHash(pt->_data.key) % nxt] = pt;
					_table[i] = nullptr;
				}
			}
			_table.swap(new_table);
		}

		size_t index = BKDHash(val.key) % _table.size();
		_pnode new_node = static_cast<_pnode>(calloc(1, sizeof(_hash_node_<Key, Value>)));
		if (new_node)
		{
			construct_at(&new_node->_data.key, val.key);
			construct_at(&new_node->_data.value, val.value);
			new_node->_next = _table[index];
			_table[index] = new_node;
			++_n;
		}
	}

	size_t bucket_size()const noexcept
	{
		size_t count = 0, siz = _table.size();
		for (size_t i = 0; i < siz; ++i)
		{
			if (_table[i])
			{
				++count;
			}
		}
		return count;
	}

	void remove(const pair<Key, Value>& val) noexcept
	{
		if (_n == 0)
		{
			return;
		}
		size_t index = BKDHash(val.key) % _table.size();
		_pnode pt = _table[index];
		if (pt == nullptr)
		{
			return;
		}
		if (pt->_data.value == val.value)
		{
			_table[index] = pt->_next;
			_destroy_(pt);
			--_n;
		}
		else
		{
			_pnode prev = nullptr;
			for (; pt;)
			{
				prev = pt;
				pt = pt->_next;
				if (pt && pt->_data.value == val.value)
				{
					break;
				}
			}
			if (pt)
			{
				prev->_next = pt->_next;
				_destroy_(pt);
				--_n;
			}
		}
	}

	size_t size() const noexcept
	{
		return _n;
	}

	iterator<Key,Value> begin() noexcept
	{
		size_t siz = _table.size();
		for (size_t i = 0; i < siz; ++i)
		{
			if (_table[i])
			{
				return iterator<Key,Value>(_table[i], this);
			}
		}
		return iterator<Key,Value>(nullptr, this);
	}

	iterator<Key,Value> end() noexcept
	{
		return iterator<Key,Value>(nullptr, this);
	}

	void for_each() const noexcept
	{
		if (_n == 0)
		{
			return;
		}
		_pnode pt = nullptr;
		size_t siz = _table.size();
		for (size_t i = 0; i < siz; ++i)
		{
			pt = _table[i];
			if (pt)
			{
				for (; pt; pt = pt->_next)
				{
					cout << pt->_data.key << "  " << pt->_data.value << endl;
				}
			}
		}
	}

	const vector<Value*> at(const Key& key)const noexcept
	{
		vector<Value*> tmp;
		_pnode pt = _table[BKDHash(key) % _table.size()];
		for (;pt;pt = pt->_next)
		{
			tmp.push_back(&pt->_data.value);
		}
		return tmp;
	}

	iterator<Key,Value> find(const pair<Key, Value>& pair) noexcept
	{
		return iterator<Key,Value>(_find(pair), this);
	}

	const vector<Value*> operator[](const Key& key)const noexcept
	{
		return at(key);
	}


protected:

	_pnode _find(const pair<Key, Value>& pair)const noexcept
	{
		if (_n == 0)
		{
			return nullptr;
		}
		size_t index = BKDHash(pair.key) % _table.size();
		_pnode pt = _table[index];
		for (; pt; pt = pt->_next)
		{
			if (pt->_data.value == pair.value)
			{
				return pt;
			}
		}
		return nullptr;
	}

	size_t _get_next_prime(size_t cur)const noexcept
	{
		for (size_t i = 0; i < PRIME_COUNT; ++i)
		{
			if (prime_list[i] > cur)
			{
				return prime_list[i];
			}
		}
		return 0;
	}

	void _destroy_(_pnode pt) noexcept
	{
		if (pt)
		{
			destroy_at(&pt->_data.key);
			destroy_at(&pt->_data.value);
			free(pt);
		}
	}

private:

	vector<_pnode> _table;
	size_t _n;
};

int main()
{


	Hash_Table<char, int> t;

	int a = 10;

	for (char i = 'a'; i <= 'z'; ++i)
	{
		t.insert(pair<char, int>{i, a});
	}

	for (char i = 'A'; i <= 'Z'; ++i)
	{
		t.insert(pair<char, int>{i,a});
	}

	for (char i = 'A'; i <= 'Z'; ++i)
	{
		t.remove(pair<char, int>{i, a});
	}

	for (char i = 'a'; i <= 'z'; ++i)
	{
		t.remove(pair<char, int>{i, a});
	}
	for (char i = 'A'; i <= 'Z'; ++i)
	{
		t.insert(pair<char, int>{i, a});
	}
	for (char i = 'a'; i <= 'z'; ++i)
	{
		t.insert(pair<char, int>{i, a});
	}
	for (auto i = t.begin(); i != t.end(); ++i)
	{
		cout << i->key << "  " << i->value << endl;
	}
	
	cout << t.size() << endl;
	cout << t.bucket_size() << endl;


	return 0;
}