wiki定义

散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

一个通俗的例子是，为了查找电话簿中某人的号码，可以创建一个按照人名首字母顺序排列的表（即建立人名x到首字母F(x)的一个函数关系），在首字母为W的表中查找“王”姓的电话号码，显然比直接查找就要快得多。这里使用人名作为关键字，“取首字母”是这个例子中散列函数的函数法则F()，存放首字母的表对应散列表。关键字和函数法则理论上可以任意确定。

若关键字为k，则其值存放在f(k)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数，按这个思想建立的表为散列表。

对不同的关键字可能得到同一散列地址，即k1 != k2，而f(k1)=f(k2)，这种现象称为冲突（英语：Collision）。

具有相同函数值的关键字对该散列函数来说称做同义词。

综上所述，根据散列函数f(k)和处理冲突的方法将一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便称为散列表，这一映射过程称为散列造表或散列，所得的存储位置称散列地址。

若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数（Uniform Hash function），这就使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。

哈希函数 f(x)

“键” 转换为 “索引”
f(ch)=ch-‘a’
一个班的学生学号 :1 - 30
身份证号: 1101081985121666666
字符串
浮点数
日期
等等~~

 很难保证每一个"键"通过哈希函数的转换对应不同的"索引"
               ⬇产生
            哈希冲突
               ⬇
            解决哈希冲突
               ⬇
           在哈希表上的操作

哈希表充分体现了算法设计领域的经典思想:空间换时间.

假设身份证 110108198512166666
如果我们有9999999999999999的空间，就可以用O(1)的时间操作
如果有1 的空间，就需要O(n)的时间操作

哈希表就是时间和空间之间的平衡

哈希函数的设计

所谓的设计，就是将我们所关心的键通过函数转换存储在数组的索引中.

“键”通过哈希函数得到的“索引”分布越均匀越好

通用的哈希函数

整型

小范围正整数直接使用作为索引

小范围负整数进行偏移例 -100~~100 -> 0~~200

大整数
例如: 身份证号
通常做法: 取模 ,比如取后四位,等同于mod 10000
取后六位: 分布不均匀,因为日期最大只到31
一个简答的解决方法:模一个素数
http://planetmath.org/goodhashtableprimes

浮点数

在计算机都是32位或者64位的二进制表示,只不过计算机解析成了浮点数

字符串：转换成整型处理

166 = 1 * 10^2 + 6*10^1 + 6 * 10^0

code = c 263 + o * 26^2 + d * 26^1 + e * 26^0

code = c B3 + o * B^2 + d * B^1 + e * B^0

hash(code)= (c B3 + o * B^2 + d * B^1 + e * B^0) %M

hash(code)= ((((c *B) + o) * B + d) * B + e) %M

hash(code)= ((((c %M *B) + o) %M * B + d) %M * B + e) %M //避免溢出

int hash=0;
for(int i=0;i<s.length();i++)
{
hash=(hash*B + s.at(i))% ‘M’;

}

复合类型转为整型处理

hash(code)= ((((c %M *B) + o) %M * B + d) %M * B + e) %M //避免溢出

Dtae:year,month,day

hash(data)= ((((data.year %M *B) + data.month) %M * B + data.day) %M //避免溢出

设计原则

一致性: 吐过a==b 则hash(a)== hash(b)
高效性: 计算高效简便
均匀性: 哈希值均匀分布

哈希冲突的处理

链地址法

链路法.jpg

哈希表的动态空间处理

平均每个地址承载的元素多过一定程度,即扩容
N/M >= upperTol

平均每个地址承载的元素少过一定程度,即缩容
N/M < lowerTol

添加动态空间后的复杂度分析

对于哈希表来说,元素数从N增加到upperTol * N ,地址增倍.

平均复杂度O(1)

每个操作都在O(lowerTol)~ O(upperTol) –> O(1)

缩容同理.

更复杂的动态空间处理方法

原本扩容M -> 2M ,扩容 2M 不是素数将会导致哈希冲突增多且哈希值分布不够均匀.

解决方案: 建立一个扩容空间数组存储素数表
http://planetmath.org/goodhashtableprimes

哈希表&平衡树

均摊复杂度

哈希表:O(1)

平衡树:O(log n)

这么来看,平衡树存在的意义在哪里? 事实上,平衡树是维护的是内部数据的有序性,所以牺牲了一部分性能在这上面. 哈希表中存储的内容都是无序的. 所以在前面的平衡树的结构中,所有的key都需要是可比较的,而在哈希表中的key是不需要的。所以当哈希表中底层实现用到了平衡树,则需要Key都是可比较的,否则会出BUG。

基于AVL的Hash代码实现

# pragma once
# include "AVL.hpp"
# include <vector>
using namespace std;
template <class K,class V>
class HashTable
{
private:
	const  static int upperTol = 10;
	const static int lowerTol = 2;
	const static int initCapacity = 7;
public:
	HashTable(int M=97)
	{
		this->M = M;
		size = 0;
		hashtable = new vector<AVL<K, V>*>(M);
		for (int i = 0; i < M; i++)
			hashtable[i] = new AVL<K,V>();
	}

	virtual static int hashCode(K key)
	{
		//传入key值计算出hash值  

	}


	inline int Size() { return size;}
	void add(K key, V value)
	{
		AVL<K,V>* map = hashtable[hash(key)];
		if (!map->contains(key))
		{
			map->add(key, value);
			size++;
			if (size >= upperTol * M)
				resize(2 * M);
		}
	}

	void remove(K key) 
	{
		AVL<K, V>* map = hashtable[hash(key)];
		if (!map->contains(key)) 
		{
			ret = map.remove(key);
			size--;

			if (size <= lowerTol * M && M > initCapacity)
				resize(M / 2);
		}
		return ret;
	}
	 bool contains(K key) {
		return hashtable[hash(key)]->contains(key);
	}

	public V get(K key) {
		return hashtable[hash(key)]->get(key);
	}


private:

	inline int hash(K key)
	{
		return (hashCode(key) & 0x7fffffff) % M;  //取正并取模  得到对应索引值

	}


	void resize(int n)
	{
		vector<AVL<K, V>*>* newHashTable = new vector<AVL<K, V>*>(newM);
		for (int i = 0; i < newM; i++)
			newHashTable[i] = new AVL<K, V>();
		int oldM = M;
		this->M = newM;
		for (int i = 0; i < oldM; i++)
		{
			/*
			这里需要对旧表数据进行迁移
			必须对每个索引值所对应的AVL树进行遍历，将遍历到节点的k值经过新的hash计算
			加入到新表对应的索引中

			由于这里使用的是自己编写的AVL树，这么做的话需要编写属于AVL树的迭代器

			暂时没精力 
			
			留给以后有时间写
			
			*/
		}
		for (int i = 0; i < oldM; i++)
			delete hashtable[i];
		delete hashtable;
		M = newM;
		hashtable = newHashTable;
	}

private:
	vector<AVL<K,V>*>* hashtable;
	int M;
	int size;

};

哈希表Hash 代码尚未完全实现

wiki定义

哈希函数的设计

通用的哈希函数

整型