哈希
key->value,借助离散化的思想对数据进行映射,可视为用value代表原本的key
在C++中,可使用map当做哈希表使用,将std::hash
当做哈希函数使用
hash<Typename>name;
size_t value=name(key);
数字哈希
哈希函数的设计
- 方法:直接定址法(a*key+b)、平方取中法(key^2且取中间几位)、除留余数法(key%p,p为质数,数字哈希常用)、随机数法…
- 除留余数法中p为质数的原因:为保证周期不减小
- 常用的p:31、131、1313、1313、13131、131313…(具体问题具体分析)
字符串哈希
- 进制哈希:借用位权展开的思想,将字符串中每一位乘以p进制下的指数(例: a b c d abcd abcd: a ∗ p 3 + b ∗ p 2 + c ∗ p 1 + d ∗ p 0 a*p^3+b*p^2+c*p^1+d*p^0 a∗p3+b∗p2+c∗p1+d∗p0)
- 常用的p:31、131、1313、1313、13131、131313…(具体问题具体分析)
- 技巧:设计unsigned类型,能够实现自动取模
- 应用:判断回文串:顺序哈希=反序哈希
哈希冲突
哈希冲突:两个不同的key映射到一个value上,就出现了哈希冲突。
开散列表(拉链法)
采用邻接表结构,但有可能会使哈希表退化成 O ( n ) O(n) O(n)。当$\ge$7时,应采用AVL、红黑树等更高级的数据结构。
闭散列表(开放寻址法)
线性探测法、二次探测法、平方探测法…