朝花夕拾-哈希表(hashTable)

复习一下常见的数据结构与算法

一、走进哈希表(hashTable)

1.哈希表的目的

实现数据的快速查找

2.哈希表的设计原理

image.png

二、哈希表的设计要素

• 哈希函数-hash function
• 冲突解决方案-collision solution
• 重哈希-rehashing

1.哈希函数-hash function

基本概念

一个哈希函数需要具备如下特征：

• 确定性
• 不可逆

其输入为: 任意二进制数据，输出为:整数(Buckets的位置)

优秀的哈希函数

如何评价一个哈希函数是否优秀了？这里我们主要看：

• 尽可能少的发生碰撞
• 计算复杂度不要太高

常见的哈希函数包括:

• 除余法modulo division
• 平方取中法 mid square
• 基数转换法 radix transformation

Java中字符串的hash函数

实现逻辑:

for(char c : str){
    hashCode = 31 * hashCode + c;
}

所以在Aa,BB、Ab,BC时会出现碰撞。通过如下测试代码可以发现，他们的hashCode是相同的。

 System.out.println("Aa".hashCode());
 System.out.println("BB".hashCode());

2.冲突解决方案-collision solution

开散列

open hashing, 又称拉链法 separate chaining

一言以蔽之，每个Bucket放的都是一个链表头结点的引用，假如冲突了就在这个链表后面加一个结点即可。（链表，往下拉）

闭散列

closed hashing，又称开址法 open addressing

当前位置已有其他元素后，再通过新算法为其找新的位置，(如这个位置的下一个空位).

(有哪些常见的查找新位置的算法呢？线性探查，待补充！)

3.重哈希-rehashing

哈希表扩缩容时，需要对已有数据的位置进行重新编排，这个就是常说的重哈希。

负载因子

负载因子load factor，等于哈希表元素的个数/哈希表容量，用于描述哈希表当前的负载。

一般当负载因子大于0.5的时候，检索性能急剧下降，冲突概率变高，此时一般就要进行哈希表扩容与重哈希了。

重哈希的描述

• 调整哈希表的大小，并将元素重新摆放。
• 当哈希表过于稀疏，进行重哈希可以节省空间
• 当哈希表过于稠密，进行哈希可以加速查找（ 空间换时间）

三、简易实现

四、参考资料

九章算法

算法导论

MIT-算法导论课程