哈希表（hash）
哈希表
一、哈希表
哈希的应用主要分成两类：一类是哈希表，用于查找；另一类是字符串哈希，用于匹配。
- 顺序查找，这个方式的时间复杂度为
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
- 函数：
| 函数名 | 操作功能 | 调用方式 |
|---|---|---|
| begin() | 获取vector中首元素的地址，即g[0]的地址 | g.begin() |
| end() | 获取vector中尾元素的下一地址(空) | g.end() |
| size() | 调用size()函数可以获得vector中保存的元素个数 | g.size() |
| push_back(x) | 在vector的最后面添加一个元素x | g.push_back(x) |
| pop_back() | 删除vector的末尾元素 | g.pop_back() |
| clear() | 用于清空vector中所有的元素 | g.clear() |
- 元素的插入：
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;
}