分离链接法: 其做法就是将散列到同一个值的所有元素保存到一个表中.
这样讲可能比较抽象, 下面看一个图就会很清楚, 图如下
相应的实现可以用分离链接散列表来实现 (其实就是一个 linkedList 数组)
至于基本的增加, 删除和查询的思路都是先根据散列函数来确定遍历哪个链表. 然后再到被确定的链表中执行一次查找, 然后再进行相应的操作.
接下来就讲几个注意点吧
(一) 什么时候需要 rehash 来扩大散列表的大小
讲这个的时候, 先介绍一下什么是装填因子.
装填因子 = 关键字个数 / 表长
当我们使用分离链接法来处理冲突的时候, 我们肯定希望装填因子最好为 1, 因为这个能尽可能将查找代价降到最低, 所以当装填因子大于 1 的时候, 我们会需要 rehash 来扩大散列表的大小.
rehash 函数的具体实现如下 (这是数据结构与算法书上的伪代码):
- private void rehash() {
- List<AnyType>[] oldLists = theLists;
- theLists = new List[nextPrime(2*theLists.length)];
- for(int j=0; j<theLists.length;j++)
- theLists[j] = new LinkedList<>();
- currentSize = 0;
- for(int i=0; i<oldLists.length;i++)
- for(AnyType item : oldLists[i])
- insert(item);
- }
其实大概的思路就是: 将当前表的大小翻倍, 但是表的大小必须是大于翻倍后的素数 (下面贴出了 nextPrime 的具体实现)
这里表的大小必须要是素数是为了保证一个好的分布, 尽可能减少冲突.
(二) 散列函数的大概实现
这里先贴出书上的 myhash() 方法的具体实现
- private int myhash(AnyType x) {
- int hashVal = x.hashCode();
- hashVal %= theLists.length;
- if(hashVal < 0) {
- hashVal += theLists.length;
- }
- return hashVal;
- }
思路也比较简单, 就是先得到插入数据的 hashCode, 然后对表的大小取余; 如果结果是负数的话, 就加上表的大小即可.
工具类:
- nextPrime
- // 返回大于某数的下一个素数
- static int NextPrime (int N) {
- if (N % 2 == 0)
- ++N;
- int i;
- for (; ; N += 2){
- for (i = 3; i*i <= N; i+=2)
- if (N % i == 0)
- goto ContOuter;
- return N;
- ContOuter:;
- }
- }
来源: https://www.cnblogs.com/xtuxiongda/p/10346704.html