数据结构与算法详解——散列表篇（附c++实现代码）

• • 散列表
  • 散列函数
  • 哈希冲突
  • • 开放地址法
    • • 线性探测
      • 二次探测
      • 双重散列
    • 链表法
    • 两种方法优缺点比较
  • 装载因子
  • 动态扩容
  • 实现
  • • 类的定义
    • 插入
    • 查找
    • 删除
    • operator[]
    • 完整代码

  前面数组、链表、栈、队列都是序列式容器，存储的都是一个元素。而散列表又叫哈希表(hash table)，是一种关联式容器，存储的是一对值，一般是一个key对应一个value(又叫键值对)。
  c++ stl中的map就是一个散列表，举个例子：

std::map m;
m["小明"]=170;
std::cout<<"小明的身高是"< 
  m是一个key是字符串类型，value是整型的哈希表，这里我们用来存储人名和身高，(“小明”,170)就是一对键值对，访问m[“小明”]得到的就是一个int类型的数字170。
 
散列函数 
  上述例子中m[“小明”]的形式看起来是不是很像数组，只不过数组的下标是非负整数，而散列表的下标可以是任意类型。我们可以用数组来实现散列表，那就可以用到数组支持随机访问时间复杂度为O(1)的特性了。
   那么我们就需要将key转换成数组的下标，这里就用到了散列函数，散列函数的要求：
 
hash(key)的结果是非负整数(数组下标)
if key1==key2，hash(key1)==hash(key2)
if key1!=key2，hash(key1)!=hash(key2)
 
  这三条规则应该都比较好理解，然而实际情况中，第三点是基本做不到的，就算是著名的哈希算法MD5,SHA都难以避免会有不同key算出相同的hash值的情况，又称为哈希冲突。
   哈希算法有很多种，但是好的哈希算法应该尽量少地出现哈希冲突。举个例子，上面key为"小明"，我们可以将中文转换成GB2312编码，相加然后取余数组的空间大小capacity，就能转换成[0,capacity)的数组下标了，但是这样简单的算法会出现很多哈希冲突，只要任意n个中文字的GB2312编码相加的结果相同，就会得到相同的哈希值，造成哈希冲突。
 
哈希冲突 
  前面说到哈希冲突是无法避免的，假设hash(“小明”)=hash(“小红”)=x，那么我们在存储时就会发生错误：
 
//a是数组
a["小明"]=170;	//实际执行a[x]=170
a["小红"]=160;	//实际执行a[x]=160
 
  小红的数据把小明的数据覆盖了，当访问a[“小明”]时就会得到160，显然是错误的。
   那如何解决哈希冲突呢？一般有两种方法：开放地址法和链表法。
 
开放地址法 
线性探测 
  线性探测的思想很简单，当我要插入数据时，如果这个下标已经有数据就往后找，找到一个没有数据的位置就可以插入。
   插入：上述例子中，当我们想要插入小红的数据时，我们发现a[x]已经有数据了(已经插入了小明的170)，那我们可以往后找一个空的位置插入160，如果x+1的位置是空的就插入a[x+1]=160，如果x+1有数据了就看x+2的位置有没有数据，以此类推。如果超过了capacity，就循环回到0的位置。
   查找：查找的过程和插入一样，我们可以让定义一个含有key和value的类，然后创建一个存储该类对象指针的数组。如果我们要访问a[“小红”]，计算hash(“小红”)=x，然后对比a[x]->key是否等于"小红"，如果不是就往后继续对比，直到遇到第一个空闲的位置。
   如果要查找160是否在a中存在，也是一样的做法，只不过对比的是a[x]->value。
   删除：这里要注意的是，删除的时候不能直接把元素设置为空或者初始值。为什么？我们来看一个例子：
 
数组下标
数组存储的值
0
(小明，170)
1
(小红，160)
2
(小陈，180)
3
空
  现在我们要删除(小红,160)，如果把元素设为空：
 
数组下标
数组存储的值
0
(小明，170)
1
空
2
(小陈，180)
3
空
  那我们现在要查找小陈的数据的时候，就找不到了，而小陈的数据确实是存在的。因此删除的时候不能直接设置为空或者初始值，我们可以设置一个flag标志这个元素已经删除，查找的时候遇到删除标志继续往下探测，查找到这个数据的时候再查看这个标志来确定这个元素是否已经删除。
   当散列表插入的数据越来越多的时候，哈希冲突发生的概率越来越大，线性探测需要的时间也越来越久，最坏的情况下探测需要遍历整个数组，时间复杂度为O(n)，同理查找和删除也是。
 
二次探测 
  假设hash(key)=x，线性探测就是按x,x+1,x+2,x+3的步长进行探测，而二次探测是按x,x+11,x+22,x+3*3的步长进行探测。
 
双重散列 
  双重散列的思路就是使用多个哈希函数，当hash1(key)的位置已经有数据的时候，计算hash2(key),hash3(key)…，直到找到一个空闲位置插入数据。
 
链表法 
  链表法在数组的每个槽都维护一个链表，当发生散列冲突的时候，存储在链表的结点里，插入查找删除的时间复杂就是链表插入查找删除的时间复杂度。
 
两种方法优缺点比较 
开放地址法：
 
优点：
 
所有数据都存在数组里，可以有效利用CPU缓存
所有数据都存在数组里，便于序列化
 
缺点：
 
删除需要使用特殊标志
发生冲突时插入查找删除都需要探测，代价较高
装载因子不能太大，需要提前申请好内存，这也导致了比链表法更加浪费内存
 
适用情况：
 
数据量小，装载因子小
 
链表法：
 
优点：
 
需要的时候才申请结点而不是一开始就申请好，内存利用率更高
对装载因子容忍度高，就算装载因子很大，只要哈希函数分布比较平均，链表长度虽然变长，但是相当于均摊到每一条链表了，所以比起纯数组还是要快。
当数据量大时，可以使用红黑树或者跳表代替链表实现优化，使得查找效率从O(n)变成O(logn)。
 
缺点：
 
链表结点在内存中不连续，对CPU缓存不友好
需要存储额外的指针，如果存储小的对象会消耗更多的内存，如果存储较大的对象的话指针的消耗可以忽略不计。
 
适用情况：存储大对象，大数据量
 
装载因子 
装载因子loadfactor = 填入表中的元素个数 / 散列表的长度
 
  装载因子越大，说明散列表越满，哈希冲突的概率越大，开放地址法的探测次数增加，链表法的链表长度会增大，导致散列表的性能会下降。
   一般我们会为装载因子设置一个阈值，当到达或者超过这个阈值后散列表进行动态扩容。
   装载因子的阈值设置需要权衡时间，空间的需求。如果对内存充足，对执行效率性能要求比较高，可以将阈值设置小一点；如果内存紧张，对执行效率性能要求不敏感，可以将阈值设置大一些，甚至可以超过1。Java的HashMap中默认的最大装载因子是0.75。
 
动态扩容 
  上面说到装载因子达到某个阈值时，散列表需要动态扩容以减小散列冲突：申请更大的数组空间，旧数据重新计算哈希值，搬移到新的空间上。
   在实际中，如果我们提供对外服务，在插入某个数据后启动动态扩容，一次性将所有旧数据计算哈希值并搬移到新空间上，可能会导致某一段时间无法响应用户的请求。
   因此，在动态扩容时，我们可以先申请空间，但是先不计算哈希值和搬移数据。在需要插入新数据时，我们将新数据插入新的空间，然后从旧散列表中取一个数据计算哈希值插入新的空间里。这样的话在查找的时候也需要兼顾新旧两个散列表，先从新散列表里找，如果找不到再到旧散列表里找。
   这种做法我们将动态扩容均摊到插入操作中，每次插入操作的时间复杂度是O(1)，这样的做法会更加地柔和，避免了一次性动态扩容耗时过高。
 
实现 
类的定义 
  这里我们使用链表法解决哈希冲突，我们定义链表的结点，需要存储键值对和next指针：
 
template 
class Entry {
public:
	K key;
	V value;
	Entry* next;
	Entry(Entry* next) {
		this->next = next;
	}
	Entry(K key, V value, Entry* next) {
		this->key = key;
		this->value = value;
		this->next = next;
	}
};
 
  哈希表类的定义：
   注意table是一个二维指针，因为table是一个指针数组，存储的是链表结点的指针。
 
template 
class hashtable {
private:
	const int default_init_capacity = 8;		//初始化大小
	const float load_factor = 0.75f;		//装载因子的阈值
	Entry** table;
	int capacity = default_init_capacity;		//容量
	int size=0;			//实际数量
	int used=0;			//已经使用的索引的数量，也就是table的下标已经使用了的数量
	const std::hash _hasher;
public:
	hashtable() {
		table = new Entry*[default_init_capacity];
		for (int i = 0; i < default_init_capacity; i++)
			table[i] = nullptr;
	}
	~hashtable();
	void put(K key, V value);
	void remove(K key);
	V& get(K key);
	V& operator[](K key);
	void print();
private:
	size_t hash(K key);
	void resize();			//扩容
};
 
  哈希函数使用了std::hash()：
 
template 
size_t hashtable::hash(K key) {
	size_t h = _hasher(key);
	return h % capacity;
}
 
插入 
template 
void hashtable::put(K key, V value) {
	size_t index = hash(key);
	if (table[index] == nullptr)			//如果index这个位置未使用，创建哨兵
		table[index] = new Entry(nullptr);

	if (table[index]->next == nullptr) {
		table[index]->next = new Entry(key, value, nullptr);
		++size;
		++used;
		std::cout << "used " << used << std::endl;
		if (used  >= load_factor*capacity)	//如果装载因子大于阈值就扩容
			resize();
	}
	else {		// 可能是key相同，也可能是不同key计算出相同的hash值(散列冲突)
		Entry* tmp = table[index]->next;
		while (tmp != nullptr) {
			if (tmp->key == key) {	//如果是key相同，那么更新value
				tmp->value = value;
				return;
			}
			tmp = tmp->next;
		}
		//上面遍历了一遍链表，key都没有相同的，这里就是散列冲突的情况了
		tmp = table[index]->next;
		table[index]->next = new Entry(key, value, tmp);
		++size;
	}
}
 
  这里需要注意的是，数组的槽里的结点是不存储数据的，也就是table[i]这个结点是不存储数据的，可以理解成是一个哨兵，table[i]->next所指向的结点才是第一个存储数据的。
   当我们计算出哈希值index时，如果table[index]这个槽是空指针，说明还没有数据插入过这个槽的链表里，直接插入即可；如果table[index]这个槽不是空指针，有可能这个key在哈希表里已经存在，也有可能不存在，所以要遍历这个槽的链表查看这个key是否存在，存在就更新value，不存在就插入新的。
   还有在插入时要判断装载因子是否过大，这里采用的是一次性动态扩容。
 
查找 
template 
V& hashtable::get(K key) {
	size_t index = hash(key);
	Entry* e = table[index];
	if (e == nullptr || e->next == nullptr) {
		std::cout << "cant find key == " << key << std::endl;
		throw "get(K key):cant find key";
	}
	while (e->next != nullptr) {
		e = e->next;		//table[index]是哨兵，不存数据的，第一个next才开始存数据，所以这里要先e=e->next;
		if (e->key == key)
			return e->value;
	}
	std::cout << "get(K key) : cant find key == " << key << std::endl;
	throw "get(K key) : cant find key";
}
 
  查找就比较简单了，计算哈希值，然后遍历链表。
 
删除 
template 
void hashtable::remove(K key) {
	size_t index = hash(key);
	Entry* e = table[index];
	if (e == nullptr || e->next == nullptr) {
		std::cout << "remove(K key) : cant find key == " << key << std::endl;
		throw "remove(K key) : cant find key";
	}
	Entry* pre;
	while (e->next != nullptr) {
		pre = e;
		e = e->next;				//table[index]是哨兵，不存数据的，第一个next才开始存数据，所以这里要先e=e->next;
		if (e->key == key) {
			pre->next = e->next;
			--size;
			if (table[index]->next == nullptr)
				--used;
			delete e;
			return;
		}
	}
	std::cout << "remove(K key) : cant find key == " << key << std::endl;
	throw "remove(K key) : cant find key";
}
 
  删除也比较简单，先找这个结点，找到了就删除这个结点。
 
operator[] 
template 
V& hashtable::operator[](K key) {
	size_t index = hash(key);
	Entry* e = table[index];
	if (e == nullptr || e->next == nullptr) {
		put(key, V());		//如果找不到key就创建一个值，这样用户才可以使用hashtable[x]=y进行创建一个值（x原本在table中没有）
		return get(key);
	}
	while (e->next != nullptr) {
		e = e->next;		//table[index]是哨兵，不存数据的，第一个next才开始存数据，所以这里要先e=e->next;
		if (e->key == key)
			return e->value;
	}
	put(key, V());	//如果找不到key就创建一个值
	return get(key);
}
 
  这里想要实现的功能是能用hashtable[x]=y这样的赋值，如果原来x这个key在哈希表中不存在就创建一个。因为可以赋值，所以函数返回值是引用。注意在表里找不到key的情况有两种，第一种就是index这个槽未使用过，就插入；第二种就是在链表中找不到key，也是插入。
 
完整代码 
#ifndef HASHTABLE_H
#define HASHTABLE_H

#include 

template 
class Entry {
public:
	K key;
	V value;
	Entry* next;
	Entry(Entry* next) {
		this->next = next;
	}
	Entry(K key, V value, Entry* next) {
		this->key = key;
		this->value = value;
		this->next = next;
	}
};

template 
class hashtable {
private:
	const int default_init_capacity = 8;		//初始化大小
	const float load_factor = 0.75f;		//装载因子的阈值
	Entry** table;
	int capacity = default_init_capacity;		//容量
	int size=0;			//实际数量
	int used=0;			//已经使用的索引的数量，也就是table的下标已经使用了的数量
	const std::hash _hasher;
public:
	hashtable() {
		table = new Entry*[default_init_capacity];
		for (int i = 0; i < default_init_capacity; i++)
			table[i] = nullptr;
	}
	~hashtable();
	void put(K key, V value);
	void remove(K key);
	V& get(K key);
	V& operator[](K key);
	void print();
private:
	size_t hash(K key);
	void resize();			//扩容
};

template 
hashtable::~hashtable() {
	for (int i = 0; i < capacity; i++) {
		if (table[i] == nullptr || table[i]->next == nullptr) {
			delete table[i];
			continue;
		}
		Entry* n = table[i]->next;
		while (n != nullptr) {
			Entry* tmp = n;
			n = n->next;
			delete tmp;
		}
	}
	delete[] table;
}

template 
size_t hashtable::hash(K key) {
	size_t h = _hasher(key);
	return h % capacity;
}

template 
void hashtable::resize() {
	std::cout << "resize()n";
	Entry** oldtable = table;
	int oldcapacity = capacity;
	capacity *= 2;
	table = new Entry*[capacity];

	for (int i = 0; i < oldcapacity; i++) {
		if (oldtable[i] == nullptr || oldtable[i]->next == nullptr) {
			table[i] = nullptr;
			continue;
		}
		Entry* e = oldtable[i];
		while (e->next != nullptr) {
			e = e->next;			//oldtable[index]是哨兵，不存数据的，第一个next才开始存数据，所以这里要先e=e->next;
			size_t index = hash(e->key);		//重新计算hash
			if (table[index] == nullptr) {		//如果index这个位置未使用，创建一个哨兵
				table[index] = new Entry(nullptr);
				++used;
			}
			
			table[index]->next = new Entry(e->key, e->value, table[index]->next);
		}
	}
}

template 
void hashtable::put(K key, V value) {
	size_t index = hash(key);
	if (table[index] == nullptr)			//如果index这个位置未使用，创建哨兵
		table[index] = new Entry(nullptr);

	if (table[index]->next == nullptr) {
		table[index]->next = new Entry(key, value, nullptr);
		++size;
		++used;
		std::cout << "used " << used << std::endl;
		if (used  >= load_factor*capacity)	//如果装载因子大于阈值就扩容
			resize();
	}
	else {		// 可能是key相同，也可能是不同key计算出相同的hash值(散列冲突)
		Entry* tmp = table[index]->next;
		while (tmp != nullptr) {
			if (tmp->key == key) {	//如果是key相同，那么更新value
				tmp->value = value;
				return;
			}
			tmp = tmp->next;
		}
		//上面遍历了一遍链表，key都没有相同的，这里就是散列冲突的情况了
		tmp = table[index]->next;
		table[index]->next = new Entry(key, value, tmp);
		++size;
	}
}

template 
void hashtable::remove(K key) {
	size_t index = hash(key);
	Entry* e = table[index];
	if (e == nullptr || e->next == nullptr) {
		std::cout << "remove(K key) : cant find key == " << key << std::endl;
		throw "remove(K key) : cant find key";
	}
	Entry* pre;
	while (e->next != nullptr) {
		pre = e;
		e = e->next;				//table[index]是哨兵，不存数据的，第一个next才开始存数据，所以这里要先e=e->next;
		if (e->key == key) {
			pre->next = e->next;
			--size;
			if (table[index]->next == nullptr)
				--used;
			delete e;
			return;
		}
	}
	std::cout << "remove(K key) : cant find key == " << key << std::endl;
	throw "remove(K key) : cant find key";
}

template 
V& hashtable::get(K key) {
	size_t index = hash(key);
	Entry* e = table[index];
	if (e == nullptr || e->next == nullptr) {
		std::cout << "cant find key == " << key << std::endl;
		throw "get(K key):cant find key";
	}
	while (e->next != nullptr) {
		e = e->next;		//table[index]是哨兵，不存数据的，第一个next才开始存数据，所以这里要先e=e->next;
		if (e->key == key)
			return e->value;
	}
	std::cout << "get(K key) : cant find key == " << key << std::endl;
	throw "get(K key) : cant find key";
}

template 
V& hashtable::operator[](K key) {
	size_t index = hash(key);
	Entry* e = table[index];
	if (e == nullptr || e->next == nullptr) {
		put(key, V());		//如果找不到key就创建一个值，这样用户才可以使用hashtable[x]=y进行创建一个值（x原本在table中没有）
		return get(key);
	}
	while (e->next != nullptr) {
		e = e->next;		//table[index]是哨兵，不存数据的，第一个next才开始存数据，所以这里要先e=e->next;
		if (e->key == key)
			return e->value;
	}
	put(key, V());	//如果找不到key就创建一个值
	return get(key);
}

template 
void hashtable::print() {
	for (int i = 0; i < capacity; i++) {
		if (table[i] == nullptr || table[i]->next == nullptr) {
			std::cout << "index " << i << " : no data" << std::endl;
			continue;
		}
			
		Entry* n = table[i]->next;
		std::cout << "index " << i << " : ";
		while (n != nullptr) {
			std::cout << "<" << n->key << "," << n->value << ">" << " ";
			n = n->next;
		}
		std::cout << std::endl;
	}
}

#endif