散列是一种以常数时间执行插入，删除和查找的技术。
装填因子：插入的值/bucket
每个哈希表槽（bucket）通常包含一个节点，该节点包含键和与之关联的值。

散列函数

1. 最简单的哈希函数

只是将字符值加在一起除以表大小。不能均匀分配
Hash(const char *key,int TableSize){
unsigned int HashVal = 0;
while(*Key != ‘\0’)
HashVal += *Key++;
return HashVal % TableSize;
}

2. 一个好的散列函数

Horner函数

Hash(const char *key ,int TableSize ){
	unsigned int HashVal = 0;
	while( *Key != '\0')
	 HashVal = (HashVal << 5) + *Key++;
  return HashVal % TableSize;
}

解决冲突

1. 分离链表法

struct ListNode{
	ValueType value;
	ListNode* next;
};
struct HashTable{
	int size;
	List valueList[10];
};//这个是有10个空位的哈希表，每个空位都是一个链表的表头。
struct HashTable{
	数量；
	链表数组；（每一个数组都是一个表头）
}

缺点：使用链表，分配空间需要时间

2. 开放定址法

当前位置有内容，那么就去寻找其他地址

线性探测法

如果当前被填充了，就找挨着的下一个位置，直到找到合适的位置。
缺点：会出现聚集现象，查找和插入都会增加耗时。

平方探测法

如果当前被填充了，就找它的平方的位置。
比如，应该插入到2，但是有元素了，那么就插入到4
缺点：二次聚集，但是比线性好

双散列

双散列的主要思想是，当发生冲突时，不仅使用一个散列函数，而是使用两个不同的散列函数来确定新的位置。

双散列的过程如下：

1. 选择两个散列函数，通常称为 hash1(key) 和 hash2(key)。
2. 初始时，使用 hash1(key) 计算键的散列值 h1。
3. 如果在散列表中的位置 h1 已经被占用，即发生冲突，那么使用 hash2(key) 计算另一个偏移值 h2。
   4.尝试在 h1 + h2 处检查下一个位置是否可用。如果仍然发生冲突，继续以 h1 + 2 * h2、h1 + 3 * h2 等方式递增位置，直到找到一个空位置或者遍历整个散列表。
   5. 一旦找到一个空位置，将键值对插入到该位置。