查找----基于散列表(线性探测法)

上一篇:基于散列表(拉链法)的查找

参照数据结构--符号表API实现。

除了拉链法,实现散列表的另一种方式就是用大小为M的数组保存N个键值对。

线性探测法:当碰撞发生时,直接检测散列表中的下一位置。这样线性探测可能发生三种结果:

  • 命中--该位置的键和被查找的键相同
  • 未命中--键为空(该位置没有键)
  • 继续查找--该位置的键和被查找的键不同

开放地址类的散列表的核心思想是与其将其内存用作链表,不如将它们作为散列表中的空元素。这些空元素可以作为查找结束的标志。

使用两个平行数组来保存键值对。

线性探测法的核心方法如下:

private int hash(Key key) {    //散列
    return (key.hashCode()&0x7fffffff)%M;
}
public Value get(Key key) {    //查询方法
    for(int i = hash(key);keys[i]!=null;i=(i+1)%M)
        if(keys[i].equals(key))
            return vals[i];
    return null;
}
public void put(Key key,Value val) {    //插入方法
    int i;
    for(i=hash(key); keys[i]!=null; i=(i+1)%M)
        if(keys[i].equals(key))	{    //已存在键,更新值
            vals[i]=val; return;
        }
    //查询键无果,插入键值对
    keys[i] = key;
    vals[i] = val;
    N++;
}

线性探测法的删除操作

不能直接将找到的位置设为null,这会使得后面的元素无法被找到。所以当我们删除一个元素时,应该将其后的元素重新插入到散列表中。

public void delete(Key key) {
    if(!contains(key))	return;
    int i = hash(key);
    //找到键值对在散列表中的位置
    while(!key.equals(keys[i]))
        i = (i+1)%M;
    //将键值对删除
    keys[i] = null;
    vals[i] = null;
    //将具有相同散列值的排在已删除键值对之后的键值对前移,方法是取出重新插入
    i = (i+1)%M;
    while(keys[i]!=null) {
        //取出后续键值对
        Key keyTo = keys[i];
        Value valTo = vals[i];
        keys[i] = null;
        vals[i] = null;
        N--;
        //重新插入
        put(keyTo,valTo);
        i = (i+1)%M;
    }
    N--;
}

调整数组大小:

private void resize(int cap) {
    //创建一个更大的数组
    LinearProbingHashST<Key,Value> t;
    t = new LinearProbingHashST<Key,Value>(cap);
    //将当前数组中的数据写入新数组
    for(int i=0;i<M;i++) 
        if(keys[i]!=null)
            t.put(keys[i], vals[i]);
    keys = t.keys;
    vals = t.vals;
    M = t.M;
}

当散列表快满时查找所需的探测次数是巨大的,但当使用率在1/2时探测次数只在1.5和2.5之间。

下一篇:基于红黑平衡树的查找

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java思维导图

JAVA容器-自问自答学ArrayList

前言 这次我和大家一起学习HashMap,HashMap我们在工作中经常会使用,而且面试中也很频繁会问到,因为它里面蕴含着很多知识点,可以很好的考察个人基础。但...

3669
来自专栏racaljk

Leetcode 8. String to Integer (atoi) atoi函数实现 (字符串)

这道题的corner cases非常多,请务必确保下面cases都能通过的情况下再提交。

1873
来自专栏机器学习从入门到成神

牛客网刷题汇总(一)附解析

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

4952
来自专栏yl 成长笔记

UML 类图基础

定义:两个类之间的强依赖关系, 可以为单向,亦可为双向。常见表现形式 为 A 类中有 B 类型的成员变量。

1014
来自专栏开发技术

排序之冒泡排序

  本篇博客是在伍迷兄的博客基础上进行的,其博客地址点击就可以进去,里面好博客很多,我的排序算法都来自于此;一些数据结构方面的概念我就不多阐述了,伍迷兄的博客中...

924
来自专栏邵靖的专栏

Python 字符串子串定位性能比较

本文想探讨的是在给定了key字段在字段列表中开始下标和key字段个数后,如何在整行字符串中定位到key字符串的起始位置。

7631
来自专栏阿凯的Excel

Vlookup最高阶应用的全网唯一解决方案

古有烟笼寒水月笼沙的缥缈朦胧,今有查询函数的假模糊匹配的终极应用!今天分享的内容是全网唯一哦~ 为啥是假模糊匹配呢?一会和你说! 嗯嗯,Vlookup函数应该...

2785
来自专栏Petrichor的专栏

tensorflow: Shapes and Shaping 探究

941
来自专栏互联网开发者交流社区

HashMap相关(二)

1145
来自专栏美团技术团队

Java8系列之重新认识HashMap

摘要 HashMap是Java程序员使用频率最高的用于映射(键值对)处理的数据类型。随着JDK(Java Developmet Kit)版本的更新,JDK1.8...

4245

扫码关注云+社区