目录

哈希

概念

哈希函数

代码实现

框架

插入

查找

删除和销毁

哈希

概念

散列法 是一种数据的存储方法，不经过任何比较，一次存取得到元素

设计哈希表

1.确定表的空间范围，确定哈希值域

2.构造哈希函数 （确保元素计算之后返回值在值域内）

3.处理冲突的办法（链式结构）

哈希函数

设计方法：

1. 直接寻址法 -散列地址 键值对
2.  数学分析法 -分析构成
3. 平方取中 - 比较集中的数据
4. 折叠法 12345 -- 12 +34 +5 =散列地址
5. 随机数
6. 保留余数法 %10 桶排

代码实现

框架

struct MyTreeNode
{
	int data; //自身数据域
	MyTreeNode * pParent; //父节点指针
	//MyTreeNode *pChild[10]; //子节点指针
	vector child;
};

//子表
struct MyNode
{
	int data; //数据域
	MyNode * pNext;
};

struct HashTable
{
	MyNode * val[10]; //数据域为10
};

///创建哈希表
HashTable * HashTableCreate()
{
	HashTable * pHead = new HashTable;
	memset(pHead, 0, sizeof(HashTable));
	return pHead;
}

//哈希函数
int HashTableIndex(int data)
{
	return data % 10;
}

插入

//插入数据
bool insertHashTable(HashTable *pHash, int val)
{
	if (pHash == nullptr) //判断主表是否为空
		return false;
	//判断分表是否存在
	MyNode * pNode = new MyNode; //遍历数组的辅助指针
	pNode = pHash->val[HashTableIndex(val)]; //分表头
	if (pNode == nullptr) //如果分表为空 就创建
	{
		pHash->val[HashTableIndex(val)] = new MyNode;		//申请新节点
		pHash->val[HashTableIndex(val)]->data = val;		//新节点赋值
		pHash->val[HashTableIndex(val)]->pNext = nullptr;	//新节点指针域赋值
	}
	else
	{
		while (pNode->pNext)//遍历找到最后一个节点，尾插
		{
			pNode = pNode->pNext;
		}
		//找到了
		pNode->pNext = new MyNode;		//申请新节点
		pNode->pNext->data = val;		//新节点赋值
		pNode->pNext->pNext = nullptr;	//新节点指针域赋值
	}
	return true;
}

查找

//查找数据 -- 返回找到的节点
MyNode* FindHashIndex(HashTable * pHash, int findval)
{
	//判断主表是否为空
	if (pHash == nullptr)
		return nullptr;
	//存在主表
	MyNode * pNode;
	pNode = pHash->val[findval % 10]; //表头
	if (pNode == nullptr)//没有分表
		return nullptr;
	while (pNode)
	{
		if (pNode->data == findval)
		{
			return pNode;
		}
		else
		{
			pNode = pNode->pNext;
		}
	}
	//循环结束 -- 没找到
	return nullptr;
}

删除和销毁

//删除数据
bool DeleteHashTableVal(HashTable * pHash, int deleteVal)
{
	//判空
	if (pHash == nullptr)
		return false;
	//表不为空 ，查找数据 -- 函数复用
	MyNode *pNode;
	pNode = FindHashIndex(pHash, deleteVal);
	//能找到，存在返回值
	if (pNode == nullptr)//找不到
		return false;
	//判断是否在表头
	MyNode * pHead = pHash->val[HashTableIndex(deleteVal)];
	if (pNode == pHead)
	{
		//头删
		pHash->val[HashTableIndex(deleteVal)] = pHead->pNext;
	}
	else{
		//中间删 指向被删除的下一个节点
		//找到被删的前一个人节点
		while (pHead->pNext != pNode)
		{
			pHead = pHead->pNext;
		}
		//第一种写法
		pHead->pNext = pNode->pNext;
	}
	delete pNode;
	return true;
}
//销毁整个表
void clearHashTable(HashTable *& pHash) //需要删除主表加了引用才能将子表内存置空
{
	if (pHash == nullptr)
		return;
	//存在内容 两个指针配合删除
	MyNode * pNode, *pHead;
	//通过不断头删去删除
	for (int  i = 0; i < 10; i++)
	{
		if ((pHead = pHash->val[i]) != nullptr);
		{
			while (pHead)
			{
				pNode = pHead; 
				pHead = pHead->pNext; //头删
				delete pNode;
			}
		}
	}
	delete[] pHash;
	pHash = nullptr;
}