散列表的定义与实现

发表于 | 分类于

散列基础知识

散列（hashing）是指散列表的实现，散列是一种用于以常数平均时间进行插入、删除、查找的的数据结构。但是散列表并不包含任何元素之间的排序信息，因此散列表不支持诸如查找最大元素、最小元素等需要排序的操作。散列表一般的实现中是采用一个固定大小的数组以及一个散列函数将关键字映射到数组的某一个位置，由于数组的大小是有限的而关键字数量却无限制，因此自然会发生多个关键字经过散列函数的映射到同一位置，此时就需要解决这种称为冲突的情况，因此可以认为散列是一种由散列函数和一系列冲突解决方案组成的抽像数据结构。

散列表中有一个概念称为装填因子λ，其定义为散列表元素的个数除以散列表大小的比值。

散列函数

散列函数又称为哈希函数（Hash Function），散列函数具有如下性质：

  • 同一散列函数计算出的散列值不同，则原始输出必定不同，称为散列函数的确定性
  • 散列函数的输入输出不一定是唯一对应关系，如果两个输入散列值相同，两个输入可能不同，称为散列碰撞

散列函数的选取将会极大影响散列的性能，如果散列函数选取失败，不能将大量的关键字均匀地进行分配，则会产生大量的冲突。使得散列性能下降。因此构建散列函数的目标就是均匀的分布在连续的内存空间中，常用的散列函数构造方法有如下几种：

直接定址法

即以关键字加上某个常数作为散列值，比如对于26个小写字母的散列函数可以直接是H(X) = X - ‘a’，这种哈希函数计算简单，一般适用于关键字值连续的情况，否则将会浪费大量的空间。

数字分析法

对于关键字中存在一定规律且分布比较均匀的数字作为计算散列值的依据，数据分析方法比较适用于关键字基本已知的情况，比如对于学生学号为关键字的散列函数，由于学号中一般包含学生编号序列，因此在计算学号的散列值可以提取出这部分编号计算出散列值。

除留余数法

用关键字除以某个不大于哈希表容量大小的数（一般直接关键字%散列表大小），余数作为散列值，即H(x) = X mod SizeOfTable。这种方法计算简单，通常适用于关键字分布均匀的情况

分段叠加法

根据散列表地址情况将关键字分为几个大小相同的段（最后一个段大小可较短），然后将这几部分叠加，丢弃进位部分，余下的即为散列值，分段叠加可以分为折叠发和位移法两种，折叠法是将奇数段正序偶数段逆序相加，位移法是将分割后的每部分地位对齐后相加。

平方取中法

如果关键字的各个部分分布不够均匀，可以先求出关键字的平方值然后按需求取中间的几位作为散列值，由于平方值和关键字的每一位都有关系，因此平方值的随机性比较高。

伪随机数法

在计算机中计算随机数时，得到的数不能称为正真的随机数，因为其值是通过一个确定性的算法计算出来，因此如果计算伪随机数的开始值不变的话，计算出的随机数也保持相同，这就是伪随机数法的基础。伪随机数散列函数结构为H(X) = random(X)。

散列冲突解决

一个好的散列函数尽量避免冲突的产生，但是一旦冲突发生，必须给予消除，一下为几种常用的冲突解决方法：

分离链接法（又称链地址法、拉链法）

其基本思想是把散列到同一个散列值的所有元素保存到一个链表中。在执行删除、插入查找时，需要遍历该表已确定元素是否在链表中，然后执行下一步操作。

分离链接法有如下优缺点：

- 优点
    1. 处理简单，无堆积现象
    2. 链表元素是动态申请内存的，因此对于无法事前了解散列表长度的情况非常合适
    3. 该方法对装填因子没有很高的要求，甚至装填因子λ可以大于1
    4. 删除操方便
- 缺点
    1. 指针占用内存空间，导致空间利用率下降

开放定址法

在分离链接法中，需要增加一个指针，同时可能需要分配新的单元，因此分离链接法的速度会受到申请内存开销的影响，而开放定址法则在发生冲突时尝试选择其他的单元直到找到一个空闲单元，在寻找空闲单元时，hi(X)=(Hash(X)+F(i)) mod SizeOfTable, i=0,1,2…依次被尝试，由于开放定址的特点，其不能进行标准的删除操作，只能采用惰性删除，否则可能将使查找操作失败，既元素已存在却返回不存在。开放定址法装填因子应该低于0.5。根据F(i)计算方式的不同开放定址法可分为：

  • 线性探测法：在该方法中，F(i)是i的线性函数，一般取F(i)=i，即出现冲突则依次探测下一个单元（可回绕）。在该冲突解决方法中，因为依次探测下一个，在散列表比较空的时候占据的单元会开始形成区块，称为一次聚集，导致散列到区块中的元素需要进行多次探测才能找到合适的空闲单元。使用线性探测方法预期的探测次数对于插入和不成功的查找为1/2*（1+(1/(1-λ)2))，对于成功的查找则为1/2*（1+(1/(1-λ))。线性探测法插入平均时间可用1/λ*ln(1/(1-λ))，计算方法为对1/(1-λ)从0~λ积分。

  • 平方探测：F(i)是i的二次函数，常用F(i)=i2，在使用平方探测时，如果表的大小是一个素数，当表至少有一半是空闲时，保证总能够插入一个新元素。如果表有比一半多一个的位置被填满，则插入操作可能失败。平方探测存在二次聚集的情况.

  • 双散列：双散列F(i)=i*hash2(X)。第二个散列函数值不能为0，否则原地死循环。另外尽量保证所有的单元都能被探测到。

再散列法

如果表的元素天的过满，则直接新建一个是原来约两倍的表，同时采用一个新的散列函数并把原始数据移入新表中，这既是再散列的含义。再散列可以用平方探测以多种方式实现，主要有以下做法：

1. 表满一半就再散列
2. 插入失败立刻再散列，这种方式比较极端
3. 即途中策略，当表装填因子达到某一值再散列

分离链接法的实现

根据分离链接法的基本定义，该ADT可以包含以下操作：

  • 插入一个元素InsertElement
  • 删除一个元素DeleteElement
  • 查找一个元素Find
  • 清空所有元素MakeEmpty

仿照《数据结构与算法分析-C语言描述》，有如下数据结构：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
template <typename DataType>
struct Node
{
	DataType data;
	Node *next;
	Node(): next(nullptr) {}
};

template <typename DataType>
class HashTable
{
public:
	HashTable(int inTableSize);
	~HashTable();
	void InsertElement(DataType inKey);
	void DeleteElement(DataType inKey);
	DataType *Find(DataType inKey);
	void MakeEmpty();
private:
	int Hash(DataType inKey); //具体的哈希函数，采用除余留法
	int tableSize; //哈希表大小
	Node<DataType> *tableArray; //哈希表指针
};

如上所示，tableSize用来保存使用者指定的下一个素数，tableArray用来保存元素，采用哑节点的方式方便进行删除操作，以下为具体实现。

  • 构造函数
1
2
3
4
5
template <typename DataType>
HashTable<DataType>::HashTable(int inTableSize): tableSize(inTableSize), tableArray(nullptr) 
{
	tableArray = new Node<DataType>[inTableSize];
}
  • 插入节点函数，采用头插法实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <typename DataType>
void HashTable<DataType>::InsertElement(DataType inKey)
{
	int position = Hash(inKey);
	Node<DataType> *cycleIter = tableArray[position].next;
	while (cycleIter != nullptr) {
		if (cycleIter->data == inKey) {
			return;
		}
		cycleIter = cycleIter->next;
	}
	Node<DataType> *newNode = new Node<DataType>;
	newNode->next =  tableArray[position].next;
	newNode->data = inKey;
	tableArray[position].next = newNode;
}
  • 删除一个元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template <typename DataType>
void HashTable<DataType>::DeleteElement(DataType inKey)
{
	int position = Hash(inKey);
	Node<DataType> *preCycleIter = &tableArray[position];

	while (preCycleIter->next != nullptr && preCycleIter->next->data !=inKey) {
		preCycleIter = preCycleIter->next;
	}

	if (preCycleIter->next == nullptr) {
		return;
	}

	Node<DataType> * toBeDelete = preCycleIter->next;
	preCycleIter->next = toBeDelete->next;
	delete toBeDelete;
}
  • 找到节点，返回该节点在内存中的地址
1
2
3
4
5
6
7
8
9
10
11
12
template <typename DataType>
DataType * HashTable<DataType>::Find(DataType inKey)
{
	int position = Hash(inKey);
	Node<DataType> *cycleIter = tableArray[position].next;

	while (cycleIter != nullptr && cycleIter->data !=inKey) {
		cycleIter = cycleIter->next;
	}

	return cycleIter == nullptr ? nullptr : &cycleIter->data;
}
  • 清空散列表中的链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <typename DataType>
void HashTable<DataType>::MakeEmpty()
{
	for (int i = 0; i < tableSize; i++) {
		if (tableArray[i].next != nullptr) {
			Node<DataType> *pre = &tableArray[i];
			while (pre->next != nullptr) {
				Node<DataType> *tmp = pre->next;
				pre->next = tmp->next;
				delete tmp;
			}
		}
		
	}
}
  • 析构函数，清空散列表
1
2
3
4
5
6
7
template <typename DataType>
HashTable<DataType>::~HashTable()
{
	MakeEmpty();
	delete [] tableArray;
	tableArray = nullptr;
}
  • 散列函数，简单起见，直接除余留法，假设键值为数值类型
1
2
3
4
5
template <typename DataType>
int HashTable<DataType>::Hash(DataType inKey)
{
	return int(inKey)%tableSize;
}

开放定址法平方探测的实现

开放地址法与分离链接法最大的区别就是在没找到位置时需要继续探测直到找到空位，而且可能会出现插入失败的情况，而且删除只能采用惰性删除，因此需要在节点域中添加标记当前节点状态，主要有三种状态空闲、占用、已删除。仿照《数据结构与算法分析-C语言描述》，有如下数据结构：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
enum State
{
	EMPTY,
	DELETED,
	OCCUPY
};

template <typename DataType>
struct Node
{
	DataType data;
	State nodeState;
	Node(): nodeState(State::EMPTY) {}
};

template <typename DataType>
class HashTable
{
public:
	HashTable(int inTableSize);
	~HashTable();
	void InsertElement(DataType inKey);
	void DeleteElement(DataType inKey);
	DataType *Find(DataType inKey);
private:
	int Hash(DataType inKey); //具体的哈希函数，采用除余留法
	int FindCore(DataType inKey); //查找核心函数，如果没找到返回插入位置
	int tableSize; //哈希表大小
	Node<DataType> *tableArray; //哈希表指针
};

以上数据成员和分离链接法基本类似，以下为各函数实现：

  • 构造函数
1
2
3
4
5
template <typename DataType>
HashTable<DataType>::HashTable(int inTableSize): tableSize(inTableSize), tableArray(nullptr) 
{
	tableArray = new Node<DataType>[inTableSize];
}
  • 插入节点函数，调用核心查找函数，如果找到则不做任何处理，否则插入返回位置（如果可以插入）
1
2
3
4
5
6
7
8
9
template <typename DataType>
void HashTable<DataType>::InsertElement(DataType inKey)
{
	int position = FindCore(inKey);
	if (tableArray[position].nodeState != State::OCCUPY) {
		tableArray[position].nodeState = State::OCCUPY;
		tableArray[position].data = inKey;
	}
}
  • 删除一个元素
1
2
3
4
5
6
7
8
template <typename DataType>
void HashTable<DataType>::DeleteElement(DataType inKey)
{
	int position = FindCore(inKey);
	if (tableArray[position].nodeState == State::OCCUPY) {
		tableArray[position].nodeState = State::DELETED;
	}
}
  • 找到节点核心函数，如果找到则返回下标，否则返回下一个可供插入的位置
1
2
3
4
5
6
7
8
9
10
11
12
template <typename DataType>
int HashTable<DataType>::FindCore(DataType inKey)
{
	int position = Hash(inKey);
	int i = 1;
	while (tableArray[position].nodeState != State::EMPTY 
			&& tableArray[position].data != inKey) {
		position += 2*i-1; ++i; //采用书上公式
		position = position >= tableSize ? position - tableSize : position;
	}
	return position;
}
  • 找到节点，返回该节点在内存中的地址
1
2
3
4
5
6
7
8
9
template <typename DataType>
DataType * HashTable<DataType>::Find(DataType inKey)
{
	int position = FindCore(inKey);
	if (tableArray[position].nodeState == State::OCCUPY) {
		return &tableArray[position].data;
	}
	return nullptr;
}
  • 析构函数，清空散列表
1
2
3
4
5
6
template <typename DataType>
HashTable<DataType>::~HashTable()
{
	delete [] tableArray;
	tableArray = nullptr;
}
  • 散列函数，简单起见，直接除余留法，假设键值为数值类型
1
2
3
4
5
template <typename DataType>
int HashTable<DataType>::Hash(DataType inKey)
{
	return int(inKey)%tableSize;
}

以上代码没有进行错误检测，如果核心查找函数失败的话可能会陷入死循环，因此可添加一个计数值，循环次数大于该值就停止寻找。