HashTable
# 定义
根据关键码值而直接进行访问的数据结构。
给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表M为哈希(Hash)表。函数f(key)称为散列函数。
# 常见的散列函数
# 直接寻址法
取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a·key + b,其中a和b为常数(这种散列函数叫做自身函数)。优点:简单、均匀 缺点:需要事先知道关键字的分布情况 使用场景。
适合查找比较小且连续的情况。
# 数字分析法
设有n个d位数,每一位可能有r种不同的符号,这r种不同的符号在各位上出现的频率不一定相同,可能在某些位上分布比较均匀,每种符号出现的机会均等,在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小,选择其中各种符号分布均匀的若干位作为散列地址。
# 平方取中法
当无法确定关键字中哪几位分布较均匀时,可以先求出关键字的平方值,然后按需要去平方值中间几位作为哈希地址。这是因为平方中间几位和关键字中的每一位都有关联,顾不同关键字会较高的概率产生不同的哈希地址。
适合不知道关键字分布,而位数又不是很大的情况。
# 折叠法
折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些),然后将这几部分叠加求和,并按散列表表长,取后几位作为散列地址。
折叠法适合事先不需要知道关键字的分布,适合关键字位数比较多的情况。
# 随机数字法
使用随机函数,取关键字的随机值作为散列地址,即H(key)=random(key)。
通常用于关键字长度不等的场合。
# 除留余数法
取关键字被某个不大于散列表长度m的数字p作为除数,除后所得的余数作为散列地址,即H(key) = key % p (p<=m)。
# 冲突
散列表的负荷因子定义为:α = 填充表中的元素个数 / 散列表的长度 散列表复合因子应严格限制在0.7-0.8以下,超过0.8,查表时的CPU缓存不命中按照指数曲线上升。
# 冲突解决
解决冲突的两种常见方法是:闭散列和开散列。
# 闭散列
闭散列也叫开放定址法,当发生哈希冲突时,如果哈希表未装满,那么可以把key存放到冲突位置中的"下一个空位置"中去。
函数:Hi=(H(key)+ di) MOD m,i=1,2,…,k(k≤m-1),其中H(key)为散列函数,m为散列表长,di为增量序列。
- 线性探测再散列:从冲突位置开始,依次往后找,知道找到下一个空位置。
- 二次探测再散列:发生冲突时,di增量序列为 di=1^2,-1^2,2^2,-2^2,⑶^2,…,±(k)^2,(km/2) 。
- 伪随机探测再散列:当Hash值p发生冲突时,则从随机序列中取出第一个值j Hash = (p+j)%m,如果还冲突则再次重复上一过程,知道取到空位置。
# 开散列
开散列又称拉链法(哈希桶),首先使用散列函数计算出哈希值,如果冲突,则使用单链表将数据连起来,链表的头存储在哈希表中,这样避免了闭散列中一旦出现冲突就需要侵占其他的位置。
# 其他
# .net 中的HashCode
散列函数
h(key, n) = h1(key) + n*h2(key)
官方对散列函数的说明:
where n is the number of times we've hit a collided bucket and rehashed
(on this particular lookup). Here are our hash functions:
h1(key) = GetHash(key); // default implementation calls key.GetHashCode();
h2(key) = 1 + (((h1(key) >> 5) + 1) % (hashsize - 1));
The h1 can return any number. h2 must return a number between 1 and
hashsize - 1 that is relatively prime to hashsize (not a problem if
hashsize is prime). (Knuth's Art of Computer Programming, Vol. 3, p. 528-9)
If this is true, then we are guaranteed to visit every bucket in exactly
hashsize probes, since the least common multiple of hashsize and h2(key)
will be hashsize * h2(key). (This is the first number where adding h2 to
h1 mod hashsize will be 0 and we will search the same bucket twice).
We previously used a different h2(key, n) that was not constant. That is a
horrifically bad idea, unless you can prove that series will never produce
any identical numbers that overlap when you mod them by hashsize, for all
subranges from i to i+hashsize, for all i. It's not worth investigating,
since there was no clear benefit from using that hash function, and it was
broken.
For efficiency reasons, we've implemented this by storing h1 and h2 in a
temporary, and setting a variable called seed equal to h1. We do a probe,
and if we collided, we simply add h2 to seed each time through the loop.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
之所以不上源代码,是对.net开源的无力吐槽,每到核心问题的时候,总是卡壳。
# java 中的HashCode
/**
* Returns a hash code for this string. The hash code for a
* {@code String} object is computed as
* <blockquote><pre>
* s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
* </pre></blockquote>
* using {@code int} arithmetic, where {@code s[i]} is the
* <i>i</i>th character of the string, {@code n} is the length of
* the string, and {@code ^} indicates exponentiation.
* (The hash value of the empty string is zero.)
*
* @return a hash code value for this object.
*/
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
hash = h = isLatin1() ? StringLatin1.hashCode(value)
: StringUTF16.hashCode(value);
}
return h;
}
/**
* StringLatin1.hashCode(value)
*/
public static int hashCode(byte[] value) {
int h = 0;
for (byte v : value) {
h = 31 * h + (v & 0xff);
}
return h;
}
/**
* StringUTF16.hashCode(value)
*/
public static int hashCode(byte[] value) {
int h = 0;
int length = value.length >> 1;
for (int i = 0; i < length; i++) {
h = 31 * h + getChar(value, i);
}
return h;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43