企业宣传网站方案,做网站书籍,网站假设教程,东莞网络建设推广1. 哈希表的相关概念
1.1 哈希表的定义
哈希表#xff0c;又称为散列表#xff0c;是根据关键字直接进行访问的数据结构。
它通过一个哈希函数#xff08;Hash Function#xff09;#xff0c;建立了一种关键字和存储地址间的直接映射关系#xff0c;将每个关键字映射…1. 哈希表的相关概念
1.1 哈希表的定义
哈希表又称为散列表是根据关键字直接进行访问的数据结构。
它通过一个哈希函数Hash Function建立了一种关键字和存储地址间的直接映射关系将每个关键字映射到一个固定大小的数组中的一个位置这个位置被称为哈希地址或索引。理想情况下散列表的查找的时间复杂度为O(1)和表中元素数量无关
1.2 哈希冲突
1.2.1 哈希冲突的定义
哈希表可能把两个或两个以上的不同关键字映射到同一个地址这种情况就叫哈希冲突也加散列冲突起冲突的不同关键字称为同义词
1.2.2 处理哈希冲突的方法
1. 线性探测法
从冲突位置开始依次线性向后探测直到找到下一个没有存储数据的位置如果走到哈希表尾则返回哈希表头
2. 链地址法
所有元素不直接存储到哈希表中哈希表存储指针每数据时指针为空当有多个关键字映射到同一个位置将这些数据串成链表挂在该位置下面
1.3 哈希函数
1.3.1 哈希函数的定义
将关键字映射成对应地址的函数就是哈希函数也叫散列函数记为 Hashkey Addr
1.3.2 常见的哈希函数
1. 直接定址法
直接取关键字的某个线性函数值作为散列地址散列函数是 Hashkey a * key ba和b为常数
2. 除留余数法
假设哈希表的大小为 M 通过 key 除以 M 的余数作为映射位置的下标散列函数是 Hashkey key % M
注意
1. M 取不太接近 2 的整数次幂的一个质数。 一般来讲将关键字范围扩大 2 倍取大于这个范围的质数即可
2. key 有可能为负数取模之后也会有负数。负数补正加上模数即可但这样的活正数和负数的操作就不同一为了方便同一为 模加模
无论key是正数还是负数 key % N N % N
3. 其他方法
数学分析法、平方取中法、折叠法、随机数法......这些方法相对局限
2. 哈希表的具体实现
案例维护一个数据结构初始为空有以下操作 1 x插入元素 x 2 x查询元素是否在数据结构中
输入描述第一行一个整数 n 表示操作次数 假设插入操作次数小于10次 之后 n 行第 i 行两个整数 op、x表示第 op 个操作和元素 x
2.1 除留取余法哈希函数 线性探测法处理哈希冲突 #includeiostream
#includecstring
using namespace std;
//根据题目的插入操作次数的范围找到一个合适的模数创建哈希表
//范围扩大两倍N 是质数
const int N 23;
int h[N];//将哈希表的所有元素初始化为一个不会取到的值
//如果初始化为0或其他数那可能无法辨别该数是初始数还是放入的数
//一般这个取不到的值为0x3f3f3f3f
const int INF 0x3f3f3f3f;
void Init()
{memset(h, 0x3f, sizeof(h));
}//哈希函数返回映射位置
int h_f(int x)
{//模加模int id (x % N N) % N;//线性探测法处理哈希冲突while (h[id] ! INF h[id] ! x){id;if (id N) id 0;}return id;
}//插入元素
void insert(int x)
{int id h_f(x);h[id] x;
}//查找元素
bool find(int x)
{int id h_f(x);return h[id] x;
}
int main()
{Init();int n; cin n;while (n--){int op, x; cin op x;if (op 1){insert(x);}else{if (find(x))cout yes endl;else cout no endl;}}return 0;
}
2.2 除留取余法哈希函数 链地址法处理哈希冲突
该实现方法和用数组实现树的遍历存储中的链式前向星方法一样本质是数组模拟链表
#includeiostream
using namespace std;
#includecstring
//根据题目的插入操作次数的范围找到一个合适的模数创建哈希表
//范围扩大两倍N 是质数
const int N 23;
int h[N];//数组模拟链表
int e[N], ne[N],id;//除留取余法
int f(int x)
{return (x % N N) % N;
}//查找元素
bool find(int x)
{//得到 x 对应的哈希值int idx f(x);//遍历链表for (int i h[idx]; i; i ne[i]){if (e[i] x) return true;}return false;
}//插入元素
void insert(int x)
{//先判断该元素是否存在if (find(x)) return;int idx f(x);//头插id;e[id] x;ne[id] h[idx];h[idx] id;
}int main()
{int n; cin n;while (n--){int op, x; cin op x;if (op 1){insert(x);}else{if (find(x)) cout yes endl;else cout no endl;}}return 0;
}
3. unordered_set/unordered_multiset
unordered_set 和 set(红黑树和STL——set/map的区别是前者使用哈希表实现而后者使用红黑树实现。导致的结果就是存储和查找的速率不一样以及前者无序后者有序其他的使用方式完全一样。
而unordered_set 和 unordered_multiset 的区别unordered_set 不能存相同的元素而unordered_multiset 可以存相同元素
#includeiostream
#includeunordered_set
using namespace std;int main()
{int arr[] { 3,5,6,8,9,2,10,1 };unordered_setint mp;//begin/end:迭代器可以用范围for遍历哈希表//和红黑树实现的 set 不同遍历出来的结果是无序的for (auto e : arr){//insert:插入时间复杂度近似为O(1)mp.insert(e);}//find:查找一个元素返回迭代器//count:查询一个元素出现的次数一般用来判断该元素是否在哈希表中//时间复杂度都近似为O(1)if (mp.count(3)) cout yes endl;else cout no endl;//erase:删除元素时间复杂度近似为O(1)mp.erase(3);if (mp.count(3)) cout yes endl;else cout no endl;//size:返回哈希表中元素个数时间复杂度O(1)cout mp.size() endl;//empty:判断哈希表是否为空时间复杂度O(1)if (mp.empty()) cout 空 endl;else cout 非空 endl;return 0;
}
4. unordered_map/unordered_multimap
unordered_map 和 map红黑树和STL——set和map的区别是前者使用哈希表实现而后者使用红黑树实现。导致的结果就是存储和查找的速率不一样以及前者无序后者有序其他的使用方式完全一样。
而unordered_map 和 unordered_multimap 的区别unordered_map 不能存相同的元素而unordered_multimap 可以存相同元素
还有一点无论是 map 还是 unordered_map 都可以存图但 map 的查找速率较低而 unordered_map 的查找速率较高
#includeiostream
#includeunordered_map
#includevector
using namespace std;void test()
{unordered_mapint, vectorint mp;mp[1].push_back(2);mp[2] { 3, 4, 5 };mp[3].push_back(1);mp[3].push_back(2);for (auto p : mp){cout p.first :;for (auto b : mp[p.first]) cout b ;cout endl;}
}int main()
{unordered_mapstring, int mp;//insert:插入元素时间复杂度近似O(1)//用{}将元素括起来mp.insert({ lili,1 });mp.insert({ kiki,2 });mp.insert({ vivi,3 });//c17的结构化绑定for (auto [k,v] : mp){cout k 编号 v endl;}//operator[]:重载[],让unordered_map可以像数组一样使用//但operator[]可能会向 map 插入意料外的元素//插入时第一个关键字为[]里内容第二个关键字为默认值//会把hihi,0放入if (mp[hihi] 4) cout hihi4 endl;else cout no endl;//begin/end:迭代器用范围for遍历for (auto [k, v] : mp){cout k 编号 v endl;}//erase:删除时间复杂度近似O(1)mp.erase(hihi);//find:查找元素返回迭代器//count查询元素出现次数一般用来判断元素是否在哈希表中//时间复杂度都近似O(1)if(mp.count(lili)) cout yes endl;else cout no endl;//size:求哈希表元素个数//empty:判断哈希表是否为空//时间复杂度都近似O(1)cout mp.size() endl;if (mp.empty()) cout 空 endl;else cout 非空 endl;//存图test();
}
