基于散列表(线性探查的哈希表和链式散列)的字典实现

字典的另一种表示是散列。它用一个散列函数（也称哈希函数）把字典的数对映射到一个散列表（也称哈希表）的具体位置。与跳表相比，它把操作的时间提高到渐近等于1，但最坏情况下依然是渐近等于N。但是如果经常输出所有元素或按照顺序查找元素（如查找第10个最小元素之类），跳表的执行效率将优于散列。相较于线性表，一个良好的散列函数得到的散列表，其查找、插入、删除的平均时间复杂度渐近等于1，即使是最坏情况下（所有元素都哈希到同一个桶），它的性能也和线性表相同。
基于跳表的字典实现

散列函数和散列表

1.桶和起始桶

当关键字范围太大，不能用理想方法表示时，可以采用并不理想的散列表和散列函数：散列表位置的数量比关键字的个数少，散列函数把若干个不同的关键字映射到散列表的同一个位置，也叫哈希冲突，将带来哈希溢出。散列表的每个位置叫作一个桶（bucket）；对关键字k的数对，f(k)是起始桶；桶的数量等于散列表的长度或大小。本文考虑两种极端情况：每个桶只能存储一个数对和每个桶都是可以容纳全部数对的线性表（哈希链表）。

2.除法散列函数

在多种散列函数中，最常用的是散列函数：f(k)=k%D 其中k是关键字，D是散列的长度（桶的数量）。

3.冲突和溢出

当两个不同的关键字通过散列函数后，对应的起始桶相同时，就发生了冲突。当该桶没有空间多存储一个元素时，将带来溢出。当映射到散列表中任何一个桶里的关键字数量大致相等时，冲突和溢出的平均数最少。均匀散列函数就是这样的函数。我们需要选择一个良好的散列函数，那么就需要选择一个好的散列函数的除数D。这也就是为什么一般哈希桶数（散列函数除数）一般都是良好的素数，如果是合数，当我们的数据满足一定特点时（如偶数居多、元素多为2的幂等待情况），这时的D不是一个好的散列函数除数，得到的也是一个不良的散列函数。

4.解决冲突和溢出

1.线性探查
最简单的方法就是找到下一个可用的桶，本文第一种情况就选择这种方法。因此，这种方法的搜索过程如下：首先搜索起始桶f(k)，然后把散列表当作环表继续搜索下一个桶，直到以下情况之一发生：1.存在关键字k的桶已找到；2.到达要给空桶；3.又回到起始桶。后两种情况说明关键字k不存在。因此这种情况下，删除操作除了需要删除指定的元素，还要从该元素的下一个桶开始，逐个检查每个桶，以确定要移动的元素，直到到达一个空桶或回到删除位置为止，然后依次将这些桶的元素向前移动。
2.使用链式哈希表
如果散列表的每一个桶都可以容纳无限多个记录，那么溢出问题就不存在了。实现这个目标的一个方法就是给散列表的每一个位置配置一个线性表。本文的第二种情况就是使用这种方法，为每个桶配置一个有序链表。
3.其他解决方法
如再哈希、设置公共溢出区等方法。

具体的C++实现

字典的ADT描述

#pragma once
//字典结构的抽象描述
template <typename K,typename V>
class dictionary {
public:
	virtual ~dictionary(){ }
	virtual bool empty() const = 0;
	//返回字典中数对的数目
	virtual size_t size() const = 0;
	//返回匹配数对的指针
	virtual std::pair<const K, V>* find(const K& _key) const = 0;
	virtual void erase(const K& _key) = 0;
	virtual void insert(const std::pair<const K, V>& _pair) = 0;
};

1.线性探查的哈希表

哈希表满异常

#pragma once
#include <string>
using std::string;
#include <iostream>
using std::cin; using std::cout; using std::ends; using std::endl;
class fullHashTable
{
public:
	fullHashTable(const std::string& _msg="The hash table is full!"):msg(_msg){ }
	std::string what()const { return msg; }
	void output()const { cout << msg << endl; }
private:
	std::string msg;
};

线性探查的哈希表实现

#pragma once
#ifndef hashTable_H
#define hashTable_H

#include "dictionaryADT.h"
#include "fullHashTable.h"

//使用先行探查来解决移出 每个桶只装一个元素
//散列表的平均性能远优于线性表(如查找、插入、删除) 即使在最坏情况(也就是所有元素hash到所有同一个起始桶)也和线性表相同
template <typename K, typename V>
class hashTable {
public:
	hashTable(int _divisor=11);
	~hashTable();

	bool empty()const { return dict_size == 0; }
	size_t size()const { return dict_size; }
	std::pair<const K, V>* find(const K& _Key)const;
	void insert(const std::pair<const K, V>& _pair);
	void erase(const K& _Key);
	void output(std::ostream& os)const;
private:
	std::pair<const K, V>** table;	//保存指向堆中pair对象的数组
	size_t dict_size;				//字典大小
	int divisor;					//散列函数除数

	int search(const K& _Key)const;	//查找给定的key所在的位置
};


template <typename K, typename V>
hashTable<K, V>::hashTable(int _divisor){
	divisor = _divisor;
	dict_size = 0;
	//分配并初始化table
	table = new std::pair<const K, V>* [divisor]();
}


template <typename K,typename V>
hashTable<K, V>::~hashTable() {
	for (size_t i = 0; i < divisor;++i) {
		if (table[i] != nullptr)
			delete table[i];
	}
	delete[] table;
}


template <typename K,typename V>
int hashTable<K, V>::search(const K& _Key)const {
	//搜索关键字为指定key的数对 如果存在则返回桶的位置
	//利用std::hash生成函数对象进行hash
	//返回结果只有三种：
	//1.从哈希值桶处开始寻找，找到该关键字的数对
	//2.从哈希值桶处开始寻找，中途遇到空桶，即相同哈希值的桶没有该数对
	//3.从哈希值桶处开始寻找，遍历，回到起始处，说明没有该数对
	int bucket = std::hash<K>()(_Key) % divisor;	//桶的原始位置
	int start = bucket;	//需要寻找的key对应的数对的位置
	int end = start;	//循环结束标识 防止在没有该key的情况下死循环
	do
	{
		if (table[start] == nullptr || table[start]->first == _Key)//如果为空或者找到了相等的数对
			return start;//返回桶的位置
		start = (++start) % divisor;
	} while (start!=end);
	return bucket;//桶满 返回桶的原始位置
}

template <typename K,typename V>
std::pair<const K, V>* hashTable<K, V>::find(const K& _Key)const {
	int bucket = search(_Key);
	//如果为空或者不等于_Key(即桶满但是没有找到)
	if (table[bucket] == nullptr || table[bucket]->first!=_Key)
		return nullptr;
	return table[bucket];
}

template <typename K,typename V>
void hashTable<K, V>::insert(const std::pair<const K,V>& _pair) {
	int bucket = search(_pair.first);
	if (table[bucket] == nullptr) {	//得到空指针 直接插入
		table[bucket] = new std::pair<const K, V>(_pair);
		++dict_size;
	}
	else{	//指针非空
		if (table[bucket]->first == _pair.first)//得到原表中Key值相同的数对 覆盖该数对的值
			table[bucket]->second = _pair.second;
		else //哈希表已满
			throw fullHashTable("Can not insert into full hash table!");
	}
}


template <typename K,typename V>
void hashTable<K, V>::erase(const K& _Key) {
	int bucket = std::hash<K>()(_Key) % divisor;//该_key的桶的原始位置
	int start = search(_Key);//该key的起始位置
	if (table[start] == nullptr || table[start]->first!=_Key) {//哈希表中没有该Key值对应的数对
		cout << "Key = " << _Key << " is not in the dictionary!" << endl;
		return;
	}
	else {//进行删除并移动后续相同hash%divisor值的元素
		//寻找相同hash%divisor的元素
		delete table[start];
		table[start] == nullptr;
		//寻找相同桶的元素
		int end = start;	//end表示需要移动的最末位置
		while (table[(end + 1) % divisor] != nullptr &&	//下个位置不为空
			std::hash<K>()(table[(end + 1) % divisor]->first) % divisor == bucket) {	//且和bucket相同
			end = (end + 1) % divisor;
		}
		while (start !=end) {
			table[start] = table[(start + 1) % divisor];
			start = (start + 1) % divisor;
		}
		table[start] = nullptr;	//相同桶的元素的最后一个位置置为空
	}
}


template <typename K,typename V>
void hashTable<K, V>::output(std::ostream& os) const{
	for (size_t i = 0; i < divisor;++i) {
		if (table[i] == nullptr)
			cout << "nullptr  ";
		else
			cout << "(" << table[i]->first << "," << table[i]->second << ")  ";
	}
	cout << endl;
}

template <typename K,typename V>
std::ostream& operator<<(std::ostream& os, const hashTable<K, V>& table) {
	table.output(os);
	return os;
}
#endif

2.链式散列

有序链表的节点

#pragma once
//一个突然的思考：为什么在skipNode和pairNode以及dictionaryADT文件中 
//即使不包含头文件<utility>也可以使用std::pair并且不报错？
//1.首先我们需要知道，类似<vector>或者<iostream>这些标准库文件中都有包含<utility>文件。
//2.最主要的是我们在这几个头文件中使用了模板 而模板的编译是发生在实例化的过程的。
//	所以我们在skipList.h和srotedChain.h中包含了<iostream> 并且在hash.cpp中实例化了模板，所以毫无问题。
//事实是，如果我们在本文件或者其他模板文件中为VS2019提供模板参数的样本来模拟实例化，编译器会发现这个错误并且报错。
//因为我们提供了模板实参，模板的实例化编译就会发生在本文件中，类似普通的编译，编译器找不到std::pair的定义也就自然会报错了。
//这也就解释了为什么模板最好不要分离编译的原因，因为没有在模板文件中给定模板实参来实例化模板的话，该模板文件不会进行编译，
//在其他.cpp文件中也就找不到编译后的模板定义(二进制文件)，也就导致了编译器出现链接错误的问题。如果我们不得不让模板分离编译
//那么必须在该模板文件中提供显示的模板实参来实例化它，然而往往我们必须提供多个模板实参，导致文件冗余庞大，干脆不要分离编译了。


template <typename K, typename V>
struct pairNode
{
	std::pair<const K, V> element;
	pairNode<K, V>* next;

	pairNode(const std::pair<const K, V>& _element, pairNode<K, V>* _next = nullptr)
		:element(_element), next(_next) { }
};

存在桶中的有序链表

#pragma once
#ifndef sortedChain_H
#define sortedChain_H
//是一个字典的有序链表实现，包含了字典的基本操作。可以存放在hashChain的哈希桶中 
#include <iostream>
using std::cout; using std::cin; using std::ends; using std::endl;

#include "dictionaryADT.h"
#include "pairNode.h"

template <typename K,typename V>
class sortedChain : public dictionary<K,V>
{
public:
	sortedChain():dict_size(0),firstNode(nullptr){  }
	~sortedChain();

	bool empty() const { return dict_size == 0; }
	size_t size() const { return dict_size; }
	std::pair<const K,V>* find(const K& _Key) const;
	void insert(const std::pair<const K,V>& _pair);
	void erase(const K& _Key);
	void output(std::ostream& os=cout)const;
private:
	size_t dict_size;
	pairNode<K, V>* firstNode;
};

template <typename K, typename V>
sortedChain<K,V>::~sortedChain()
{
	while (firstNode!=nullptr) {
		auto next = firstNode->next;
		delete firstNode;
		firstNode = next;
	}
	//cout << "chain deleted" << endl;
}


template <typename K, typename V>
std::pair<const K, V>* sortedChain<K, V>::find(const K& _Key) const {
	auto node = firstNode;
	while (node != nullptr && node->element.first != _Key)
		node = node->next;
	if (node != nullptr && node->element.first == _Key)//找到
		return &node->element;
	return nullptr;	//没找到
}


template <typename K,typename V>
void sortedChain<K, V>::insert(const std::pair<const K,V>& _pair) {
	auto node = firstNode;
	pairNode<K, V>* preNode = nullptr;
	while (node != nullptr && node->element.first < _pair.first){
		preNode = node;
		node = node->next;
	}
	if (node != nullptr && node->element.first == _pair.first){//如果存在相同key的pair则更新值
		node->element.second = _pair.second;
		return;
	}
	if (preNode == nullptr)	//插入位置为首节点
		firstNode = new pairNode<K, V>(_pair, node);
	else
		preNode->next = new pairNode<K, V>(_pair, node);
	++dict_size;
	return;
}

template <typename K, typename V>
void sortedChain<K, V>::erase(const K& _Key) {
	auto node = firstNode;
	pairNode<K,V>* preNode = nullptr;//删除节点的前驱节点
	while (node!=nullptr && node->element.first<_Key) {
		preNode = node;
		node = node->next;
	}
	if (node!=nullptr && node->element.first==_Key) {//找到
		if (preNode == nullptr)//要删除首节点
			firstNode = node->next;
		else
			preNode->next = node->next;
		delete node;
		--dict_size;
	}
	else {
		cout << _Key << " is not in dictionary" << endl;
	}
	return;
}

template <typename K,typename V>
void sortedChain<K, V>::output(std::ostream& os)const {
	auto node = firstNode;
	while(node!=nullptr){
		os << "(" << node->element.first << "," << node->element.second << ")  ";
		node = node->next;
	}
	os << endl;
}

template <typename K,typename V>
std::ostream& operator<<(std::ostream& os, const sortedChain<K, V>& chain) {
	chain.output(os);
	return os;
}
#endif // !sortedChain_H

链式散列的实现

#pragma once
#ifndef hashChain_H
#define hashChain_H

//以链表存在桶里的哈希链表，一个桶可以存任意多个元素，不用像线性探查法那样担心溢出
#include "dictionaryADT.h"
#include "sortedChain.h"

template <typename K,typename V>
class hashChain :public dictionary<K,V>
{
public:
	hashChain(int _divisor=11)
		:divisor(_divisor), dict_size(0),table(new sortedChain<K,V>[divisor]()) {  }
	~hashChain() { delete[]table; }

	bool empty()const { return dict_size == 0; }
	size_t size()const { return dict_size; }

	std::pair<const K,V>* find(const K& _Key)const;
	void erase(const K& _Key);
	void insert(const std::pair<const K, V>& _pair);
	void output(std::ostream& os=cout)const;
private:
	int divisor;			//散列哈希除数
	size_t dict_size;		//字典元素数量	
	sortedChain<K, V>* table;//哈希表
};


template <typename K,typename V>
std::pair<const K, V>* hashChain<K,V>::find(const K& _Key)const {
	return table[std::hash<K>()(_Key) % divisor].find(_Key);
}

template <typename K, typename V>
void hashChain<K,V>::erase(const K& _Key) {
	table[std::hash<K>()(_Key) % divisor].erase(_Key);
}

template <typename K, typename V>
void hashChain<K, V>::insert(const std::pair<const K, V>& _pair) {
	size_t bucket = std::hash<K>()(_pair.first) % divisor;
	size_t originalSize = table[bucket].size();
	table[bucket].insert(_pair);
	if (table[bucket].size() > originalSize)
		++dict_size;
}

template <typename K,typename V>
void hashChain<K, V>::output(std::ostream& os)const {
	for (int i = 0; i < divisor;++i) {
		os << "bucket[" << i << "] : ";
		table[i].output(os);
		os << endl;
	}
}

template <typename K,typename V>
std::ostream& operator<<(std::ostream& os, const hashChain<K, V>& hc) {
	hc.output(os);
	return os;
}
#endif // !hashChain_H