哈希表

一、哈希表

哈希的应用主要分成两类：一类是哈希表，用于查找；另一类是字符串哈希，用于匹配。

• 顺序查找，这个方式的时间复杂度为 $O（n）$。如果序列是有序的，借助二分查找，能达到 $O（log n）$ 的效率。但若序列是无序的，又遇到稍大的数据量如 $10^9$，将面临时间超限的问题。
• 桶排。输入x后做出标记，a[x]=x。查找即是对a[x]的值进行判断，如等于x则存在，时间复杂度为 $O（1）$。该处理方式虽然快但涉及到空间问题，若序列中的数值相对较稀疏时，空间的开销会较大。 如面临大数据量的查找时，我们能将这两种方式的有点相结合，综合时空优势，无疑是一个有效的解决 途径。而哈希表，便是处于这两种方式的中间点，平衡时空问题，有效进行查找。
• 构造哈希函数有三个注意的要点：
  • 1、构造哈希函数有两个标准：简单和均匀。
  • 2、哈希函数的关键字一般要选用元素中的整数或字符串。
  • 3、最常用的哈希函数：除留余数法，即 $h(key)=key$ $mod$ $p$ 。其中 $p$ 必须为素数， 可以使得元素在数据结构中均匀分布，减少冲突。

二、容器$vector$

• 函数：

• 元素的插入：

inline void insert(int x)
{
	h[has(x)].push_back(x);
}

• 元素查找：

inline bool find(int x)
{
	for(int i = 0; i < h[has(x)].size(); i++){
		if(h[has(x)][i] == x)return true;
	}
	return false;
}

三、$map$

$map$ 是 $STL$ 标准库中提供的一个关联容器，可以实现元素一对一的映射 想要调用 $map$ 则必须引用头文件<map>

• 如下：

#include <map>

• 或万能头：

#include <bits/stdc++.h>

• 底层：

$map$ 是使用 红黑树 来实现的， 因此 $map$ 中的元素默认按照键的 升序 进行排序。