本文主要是介绍【数据结构】哈希表(hashTable)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
复习一下常见的数据结构与算法
文章目录
- 一、走进哈希表(hashTable)
- 1.哈希表的目的
- 2.哈希表的设计原理
- 二、哈希表的设计要素
- 1.哈希函数-hash function
- 基本概念
- 优秀的哈希函数
- Java中字符串的hash函数
- 2.冲突解决方案-collision solution
- 开散列
- 闭散列
- 3.重哈希-rehashing
- 负载因子
- 重哈希的描述
- 三、简易实现
- 四、参考资料
一、走进哈希表(hashTable)
1.哈希表的目的
实现数据的快速查找
2.哈希表的设计原理
二、哈希表的设计要素
- 哈希函数-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-算法导论课程
这篇关于【数据结构】哈希表(hashTable)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
