数据结构之哈希表

你的名字 2021-12-23 23:11 465阅读 0赞

头文件：HashTable.h

#define _INT_MIN (0x80000000)
    class HashTable
    {
    public:
    	HashTable(int hashLen);
    	HashTable(int ary[], int n, int hashLen);
    	HashTable(int *start,int *end,int hashLen);
    	//获取哈希码
    	int HashCode(int key, int *cPtr );
    	//冲突处理
    	int Collision(int H, int key, int *cPtr );
    	//初始化哈希表
    	void Initial(int hashLen);
    
    	int ToArray(int ary[]);
    
    	int AddRange(int ary[], int n);
    
    	int Add(int key);
    private:
    	CirSeqList csl;
    	int len;
    	
    	int SqrtSearchHashes(int H, int key, int *cPtr );
    };
    
    void HashTable::Initial(int hashLen)
    {
    	len = hashLen;
    	//初始化 循环表
    	int *a = new int[hashLen];
    	for (int i = 0; i < hashLen; i++)
    	{
    		//int的最小值
    		a[i] = _INT_MIN;
    	}
    	csl.Initial(a, hashLen);
    	delete[] a;
    }
    
    HashTable::HashTable(int hashLen)
    {
    	Initial(hashLen);
    }
    
    HashTable::HashTable(int ary[], int n, int hashLen)
    {
    	Initial(hashLen);
    	AddRange(ary, n);
    }
    
    HashTable::HashTable(int *start, int *end, int hashLen)
    {
    	Initial(hashLen);
    	AddRange(start, end - start + 1);
    }
    
    int HashTable::Add(int key)
    {
    	int count = 0, H = HashCode(key, &count);
    	if (H != -1)
    	{
    		csl.Set(H, key);
    	}
    	else
    	{
    		//printf("\n*****哈希表溢出！*****\n");
    	}
    	return count;
    }
    
    int HashTable::AddRange(int ary[], int n)
    {
    	int count = 0;
    	for (int i = 0; i < n; i++)
    	{
    		count+=Add(ary[i]);
    	}
    	return count;
    }
    
    //获取哈希码
    int HashTable::HashCode(int key, int *cPtr = NULL)
    {
    	int H = key%7, count = 1;
    
    
    	//如果是的，就直接返回。防止重复元素出现。
    	if (csl.Get(H) == key)
    	{
    		return H;
    	}
    	else if (csl.Get(H) != _INT_MIN)
    	{
    		//寻找空位
    		H = Collision(H, _INT_MIN, &count);
    		if (H == -1)
    		{
    			//printf("\n*****哈希表溢出！*****\n");
    			return -1;
    		}
    	}
    	(*cPtr) = count;
    	return H;
    
    }
    //冲突处理
    int HashTable::Collision(int H, int key, int *cPtr = NULL)
    {
    	bool noway=false;
    	int method = 0, tar = -1;
    
    	//遍历处理冲突的方法表
    	while (noway == false && method++, tar == -1)
    	{
    		switch (method)
    		{
    		case 1:
    			//方法一：二次探测再散列
    			tar = SqrtSearchHashes(H, key, cPtr);
    			break;
    		case 2:
    			//方法二：。。。。。。
    			tar = -1;
    			break;
    		default:
    			//方法表已穷尽
    			noway = true;
    			break;
    		}
    	}
    
    	return tar;
    }
    
    //1^2 2^2 3^3
    int HashTable::SqrtSearchHashes(int H, int key = _INT_MIN, int *cPtr = NULL)
    {
    	int i = 1, tar = H, d;
    	while (csl.IsLegal(tar) && csl.Get(tar) != key)
    	{
    		if (i > len / 2)
    		{
    			return -1;
    		}
    		d = i * i;
    		tar = (H + d) % len;
    		if (cPtr != NULL)
    		{
    			(*cPtr)++;
    		}
    		i++;
    	}
    	return tar;
    }
    
    int HashTable::ToArray(int ary[])
    {
    	csl.SetCurNum(len-1);
    	for (int i = 0; i < len; i++)
    	{
    		ary[i] = csl.Next();
    	}
    	return len;
    }

转载于:https://www.cnblogs.com/tinyjian/p/6550713.html