第99篇 C++数据结构（九）散列表

• 1.散列表简介
• • 1.1.散列函数
  • 1.2.散列冲突解决方案
• 2.数据节点
• 3.实现
• • 3.1.变量
  • 3.2.方法
• 4.测试
• • 4.1.测试代码
  • 4.2.输出结果
• 5.实现代码
• 6.总结

详细介绍：
大佬文章链接1
大佬文章链接2

散列表也叫哈希表（Hash table），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

散列函数设计的基本要求：
散列函数计算得到的散列值是一个非负整数；
如果 key1 = key2，那 hash(key1) == hash(key2)；
如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)。（往往这个条件很难办到，key不同可能出现相同的散列值，于是出现散列冲突）

大佬文章链接1
大佬文章链接2

为了方便操作，把数据和属性封装起来。因为存储数据，所以不好用某个值来判断散列表某个位置是否有数据，因此添加一个hasValue属性，用于判断某个位置是否有值，添加remove属性，用于删除某个值之后，出现表断裂的情况（查找的时候，是遇到没有值的地方就停止，如果这个地方被删除，那还可以继续查找）。

struct Node
{
	int m_value;
	bool m_hasValue;
	bool m_remove;

	Node() : m_value(0), m_remove(false), m_hasValue(false) {}
	Node(int value) : m_value(value), m_remove(false), m_hasValue(true) {}
};

#include 

#include "hashtable.h"

int main()
{
	HashTable hashtable(8);

	std::cout << "n添加8个数据：" << std::endl;
	for (int i = 0; i < 8; i++)
	{
		hashtable.add(i * 7 + 1);
	}
	hashtable.print();

	std::cout << "n添加34：" << std::endl;
	hashtable.add(34);
	hashtable.print();

	std::cout << "n添加45：" << std::endl;
	hashtable.add(45);
	hashtable.print();

	std::cout << "n删除100：" << std::endl;
	hashtable.remove(100);
	hashtable.print();

	std::cout << "n查找34：" << std::endl;
	if (hashtable.serch(34))
	{
		std::cout << "34在表里" << std::endl;
	}
	else
	{
		std::cout << "34不在表里" << std::endl;
	}

	std::cout << "n查找35：" << std::endl;
	if (hashtable.serch(35))
	{
		std::cout << "35在表里" << std::endl;
	}
	else
	{
		std::cout << "35不在表里" << std::endl;
	}

	return 0;
}

添加8个数据：
8, 1, 50, 43, 36, 29, 22, 15,

添加34：
36, 1, 29, 34, 22, 50, 15, 43, 8,

添加45：
50, 1, 22, 43, 34, 15, 36, 45, 8, 29,

删除100：
50, 1, 22, 43, 34, 15, 36, 45, 8, 29,

查找34：
34在表里

查找35：
35不在表里

#pragma once
#ifndef _HASHTABLE_H_
#define _HASHTABLE_H_

#include 
#include 

struct Node
{
	int m_value;
	bool m_hasValue;
	bool m_remove;

	Node() : m_value(0), m_remove(false), m_hasValue(false) {}
	Node(int value) : m_value(value), m_remove(false), m_hasValue(true) {}
};

class HashTable
{
public:
	HashTable(int size)
	{
		if (size > 0)
		{
			m_hashTable = std::vector(size);
			m_size = size;
		}
		else
		{
			m_size = 0;
		}
	}

	int size() const
	{
		return m_size;
	}

	bool add(int value)
	{
		if (full())
		{
			m_size++;
			std::vector newHashTable(m_size);

			for (int i = 0; i < m_size - 1; i++)
			{
				int index = hashFunc(m_hashTable[i].m_value);
				while (newHashTable[index].m_hasValue)
				{
					index = (index + 1) % m_size;
				}

				newHashTable[index].m_hasValue = true;
				newHashTable[index].m_remove = false;
				newHashTable[index].m_value = m_hashTable[i].m_value;
			}

			m_hashTable = newHashTable;
		}

		int index = hashFunc(value);
		while (m_hashTable[index].m_hasValue)
		{
			index = (index + 1) % m_size;
		}

		m_hashTable[index].m_hasValue = true;
		m_hashTable[index].m_remove = false;
		m_hashTable[index].m_value = value;

		return true;
	}

	bool remove(int value)
	{
		int index = hashFunc(value);
		int count = 0;
		while ((m_hashTable[index].m_hasValue || m_hashTable[index].m_remove) && m_hashTable[index].m_value != value && count < m_size)
		{
			index = (index + 1) % m_size;
			count++;
		}

		if (index < m_size && m_hashTable[index].m_hasValue && m_hashTable[index].m_value == value)
		{
			m_hashTable[index].m_hasValue = false;
			m_hashTable[index].m_remove = true;
			return true;
		}

		return false;
	}

	bool serch(int value)
	{
		int index = hashFunc(value);
		int count = 0;
		while ((m_hashTable[index].m_hasValue || m_hashTable[index].m_remove) && m_hashTable[index].m_value != value && count < m_size)
		{
			index = (index + 1) % m_size;
			count++;
		}

		if (index < m_size && m_hashTable[index].m_hasValue && m_hashTable[index].m_value == value)
		{
			return true;
		}

		return false;
	}

	bool full() const
	{
		for (int i = 0; i < m_size; i++)
		{
			if (!m_hashTable[i].m_hasValue)
			{
				return false;
			}
		}

		return true;
	}

	void print() const
	{
		for (Node node : m_hashTable)
		{
			if (node.m_hasValue)
			{
				std::cout << node.m_value << ", ";
			}
			else
			{
				std::cout << " " << ", ";
			}
		}
		std::cout << std::endl;
	}

protected:
	int hashFunc(int key)
	{
		return abs(key % m_size);
	}

private:
	std::vector m_hashTable;
	int m_size;
};

#endif // !_HASHTABLE_H_

只是简单的实现，初次接触，如有错误，还望谅解。