散列表（哈希表）的实现

刺骨的言语ヽ痛彻心扉 2022-08-04 12:36 202阅读 0赞

散列函数直接用key%size的形式，size为散列表的大小。

冲突处理采用平方探测法，为保证可以探测到整个散列表空间，散列表大小设置为4k+3形式的素数。

当散列表中的元素过多时会造成性能下降，这时应该倍增散列表的大小，重新计算原来散列表中每个元素在新的散列表中的位置。

散列表的实现

<span style="font-size:18px;">// HashTable.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include<iostream>
    using namespace std;
    
    enum state{
    	empty,
    	deleted,
    	busy,
    };
    
    template<typename T>
    struct HashNode
    {
    	T key;
    	state sta;
    	HashNode()
    	{
    		sta = empty;
    	}
    };
    const int prime_size = 5;
    const static int prime[prime_size] //素数表，形式为4k+3，保证可以探测到整个散列表空间
    ={
    	31, 59, 127, 263, 547
    };
    template<typename T>
    class HashTable
    {
    private:
    	HashNode<T>*hashtable;
    	double alpha;//当前散列表的充满程度
    	int size;//当前散列表的大小
    	int current_busy;
    	double max_alpha;
    	int hash_func(T key)
    	{
    		return key%size;
    	}
    
    	int find_next_prime()
    	{
    		for (int i = 0; i < prime_size; i++)
    		{
    			if (prime[i]>size)
    				return prime[i];
    		}
    		return size;
    	}
    
    	void reHash()//alpha>max_alpha时调整散列表大小
    	{
    		int newsize = find_next_prime();
    		if (newsize == size)
    			return;
    		HashNode<T>*newhashtable = new HashNode<T>[newsize];
    		for (int i = 0; i < size; i++)
    		{
    			if (hashtable[i].sta == busy)
    			{
    				newhashtable[hashtable[i].key % newsize].key = hashtable[i].key;
    				newhashtable[hashtable[i].key % newsize].sta = busy;
    			}
    		}
    		delete[]hashtable;
    		hashtable = newhashtable;
    		size = newsize;
    		alpha =get_alpha();
    	}
    public:
    	
    	HashTable()
    	{
    		max_alpha = 0.80;
    		size = prime[0];
    		alpha = 0;
    		hashtable = new HashNode<T>[size];
    	}
    
    	bool insert(T key)
    	{
    		int count = 0;
    		while (true)
    		{
    			int index = (key + count*count) % size;
    			if (hashtable[index].sta != busy)
    			{
    				hashtable[index].sta = busy;
    				hashtable[index].key = key;
    				current_busy++;
    				alpha = get_alpha();
    				if (alpha > max_alpha)
    					reHash();
    				return true;
    			}
    			if (hashtable[index].sta == busy&&hashtable[index].key == key)
    			{
    				cout<<"HashTable中已经有"<<key<<endl;
    				return false;
    			}
    			index = (key - count*count) % size;
    			while (index < 0)
    			{
    				index += size;
    			}
    			if (hashtable[index].sta != busy)
    			{
    				hashtable[index].sta = busy;
    				hashtable[index].key = key;
    				current_busy++;
    				alpha = get_alpha();
    				if (alpha > max_alpha)
    					reHash();
    				return true;
    			}
    			if (hashtable[index].sta == busy&&hashtable[index].key == key)
    			{
    				cout << "HashTable中已经有" << key << endl;
    				return false;
    			}
    			count++;
    		}
    		
    	}
    
    	int find(T key)
    	{
    		int count = 0;
    		while (true)
    		{
    			int index = (key + count*count) % size;
    			if (hashtable[index].sta != busy)
    			{
    				return -1;
    			}
    			if (hashtable[index].key== key)
    			{
    				return index;
    			}
    			index = (key - count*count) % size;
    			while (index < 0)
    			{
    				index += size;
    			}
    			if (hashtable[index].sta != busy)
    			{
    				return -1;
    			}
    			if (hashtable[index].key == key)
    			{
    				return index;
    			}
    			count++;
    				if (count > size / 2 + 1)
    					return -1;
    		}
    	}
    
    	bool erase(T key)
    	{
    		int index = find(key);
    		if (index >= 0)
    		{
    			hashtable[index].sta = deleted;
    			current_busy--;
    			alpha = get_alpha();
    			return true;
    		}
    		return false;
    	}
    
    	double get_alpha()
    	{
    		return double(current_busy) / double(size);
    	}
    
    
    	~HashTable()
    	{
    		delete[]hashtable;
    	}
    
    };
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	HashTable<int>aa;
    	aa.insert(1);
    	aa.insert(2);
    	aa.insert(11);
    	aa.insert(3);
    	aa.insert(5);
    	aa.insert(36);
    	aa.insert(5);
    	cout << aa.find(36) << endl;
    	aa.erase(5) ;
    	//cout << -7 % 4 << endl;
    	system("pause");
    	return 0;
    }
    </span>