【数据结构】用Java实现哈希表

这篇具有很好参考价值的文章主要介绍了【数据结构】用Java实现哈希表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

1 概念

2 冲突-概念

3 冲突-避免

4 冲突-避免-哈希函数设计

(1)直接定制法--(常用)

(2)除留余数法--(常用)

(3)平方取中法--(了解)

(4)折叠法--(了解)

(5)随机数法--(了解)

(6)数学分析法--(了解)

5 冲突-避免-负载因子调节(重点掌握)

6 冲突-解决

(1)冲突-解决-闭散列

(2)冲突-解决-开散列/哈希桶(重点掌握)

(3)冲突严重时的解决办法

7 开散列/哈希桶实现

(1)MyHashMap 类

(2)新增 & 修改

(3)扩容

(4)查找是否包含key值

(5)删除指定key值


1 概念

顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过关键码的多次比较顺序查找时间复杂度为O(N),平衡树中为树的高度,即O( ),搜索的效率取决于搜索过程中元素的比较次数。
理想的搜索方法:可以 不经过任何比较,一次直接从表中得到要搜索的元素 如果构造一种存储结构,通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系,那么在查找时通过该函数可以很快找到该元素
当向该结构中:
  • 插入元素:根据待插入元素的关键码,以此函数计算出该元素的存储位置并按此位置进行存放
  • 搜索元素:对元素的关键码进行同样的计算,把求得的函数值当做元素的存储位置,在结构中按此位置取元素比较,若关键码相等,则搜索成功
该方式即为哈希(散列)方法,哈希方法中使用的转换函数称为哈希(散列)函数,构造出来的结构称为哈希表(HashTable)(或者称散列表)
例如:数据集合{1,7,6,4,5,9};
哈希函数设置为:hash(key) = key % capacity; capacity为存储元素底层空间总的大小。
【数据结构】用Java实现哈希表
用该方法进行搜索不必进行多次关键码的比较,因此搜索的速度比较快。问题:按照上述哈希方式,向集合中插入元素44,会出现什么问题?

2 冲突-概念

对于两个数据元素的关键字和 (i != j),有 != ,但有:Hash( ) == Hash( ),即: 不同关键字通过相同哈希哈数计算出相同的哈希地址,该种现象称为哈希冲突或哈希碰撞

 把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”

3 冲突-避免

首先,我们需要明确一点,由于我们哈希表底层数组的容量往往是小于实际要存储的关键字的数量的,这就导致一个问题, 冲突的发生是必然的 ,但我们能做的应该是尽量的降低冲突率

4 冲突-避免-哈希函数设计

引起哈希冲突的一个原因可能是:哈希函数设计不够合理哈希函数设计原则
哈希函数的定义域必须包括需要存储的全部关键码,而如果散列表允许有m个地址时,其值域必须在0到m-1之间,哈希函数计算出来的地址能均匀分布在整个空间中哈希函数应该比较简单
常见哈希函数

(1)直接定制法--(常用)

取关键字的某个线性函数为散列地址:Hash(Key)= A*Key + B 优点:简单、均匀 缺点:需要事先知道关键字的分布情况 使用场景: 适合查找比较小且连续的情况 

(2)除留余数法--(常用)

设散列表中允许的地址数为m,取一个不大于m,但最接近或者等于m的质数p作为除数,按照哈希函数:
Hash(key) = key% p(p<=m),将关键码转换成哈希地址。

(3)平方取中法--(了解)

假设关键字为1234,对它平方就是1522756,抽取中间的3位227作为哈希地址; 再比如关键字为4321,对它平方就是18671041,抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合: 不知道关键字的分布,而位数又不是很大的情况

(4)折叠法--(了解)

 折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些),然后将这几部分叠加求和,并按散列表表长,取后几位作为散列地址。

折叠法适合 事先不需要知道关键字的分布,适合关键字位数比较多的情况

(5)随机数法--(了解)

选择一个随机函数,取关键字的随机函数值为它的哈希地址,即H(key) = random(key),其中random为随机数函数。 通常应用于 关键字长度不等时采用此法

(6)数学分析法--(了解)

设有n个d位数,每一位可能有r种不同的符号,这r种不同的符号在各位上出现的频率不一定相同,可能在某些位上分布比较均匀,每种符号出现的机会均等,在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小,选择其中各种符号分布均匀的若干位作为散列地址。
数字分析法通常适合 处理关键字位数比较大的情况,事先知道关键字的分布且关键字的若干位分布较均匀的情况

【注意】哈希函数设计的越精妙,产生哈希冲突的可能性就越低,但是无法避免哈希冲突

5 冲突-避免-负载因子调节(重点掌握)

【数据结构】用Java实现哈希表
所以当冲突率达到一个无法忍受的程度时,我们需要通过降低负载因子来变相的降低冲突率。
已知哈希表中已有的关键字个数是不可变的,那我们能调整的就只有哈希表中的数组的大小。

6 冲突-解决

解决哈希冲突两种常见的方法是:闭散列开散列

(1)冲突-解决-闭散列

闭散列:也叫开放定址法,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以 key存放到冲突位置中的“下一个” 空位置中去 那如何寻找下一个空位置呢?
1. 线性探测
比如上面的场景,现在需要插入元素44,先通过哈希函数计算哈希地址,下标为4,因此44理论上应该插在该位置,但是该位置已经放了值为4的元素,即发生哈希冲突。
线性探测:从发生冲突的位置开始,依次向后探测,直到寻找到下一个空位置为止。
(1)插入通过哈希函数获取待插入元素在哈希表中的位置
(2)如果该位置中没有元素则直接插入新元素,如果该位置中有元素发生哈希冲突,使用线性探测找到下一个空位置,插入新元素

【数据结构】用Java实现哈希表

采用闭散列处理哈希冲突时,不能随便物理删除哈希表中已有的元素,若直接删除元素会影响其他元素的搜索。比如删除元素4,如果直接删除掉,44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。
2. 二次探测
线性探测的缺陷是产生冲突的数据堆积在一块,这与其找下一个空位置有关系,因为找空位置的方式就是挨着往后逐个去找,因此二次探测为了避免该问题,找下一个空位置的方法为: = (
+ )% m, 或者: = ( - )% m。其中:i = 1,2,3…,是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置,m是表的大小。 对于2.1中如果要插入44,产生冲突,使用解决后的情况为:

【数据结构】用Java实现哈希表

 研究表明:当表的长度为质数且表装载因子a不超过0.5时,新的表项一定能够插入,而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置,就不会存在表满的问题。在搜索时可以不考虑表装满的情况,但在插入时必须确保表的装载因子a不超过0.5,如果超出必须考虑增容。 文章来源地址https://www.toymoban.com/news/detail-410522.html

因此:比散列最大的缺陷就是空间利用率比较低,这也是哈希的缺陷。

(2)冲突-解决-开散列/哈希桶(重点掌握)

开散列法又叫链地址法(开链法),首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中。
【数据结构】用Java实现哈希表
从上图可以看出,开散列中每个桶中放的都是发生哈希冲突的元素。
开散列,可以认为是把一个在大集合中的搜索问题转化为在小集合中做搜索了。

(3)冲突严重时的解决办法

哈希桶其实可以看作将大集合的搜索问题转化为小集合的搜索问题了,那如果冲突严重,就意味着小集合的搜索性能其实也时不佳的,这个时候我们就可以将这个所谓的小集合搜索问题继续进行转化,例如:
  • 1. 每个桶的背后是另一个哈希表
  • 2. 每个桶的背后是一棵搜索树

7 开散列/哈希桶实现

(1)MyHashMap 类

public class MyHashMap {
    private static class Node {
        int key;
        int value;
        Node next;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    // 当前哈希表中有效元素个数
    private int size;
    // 取模数,简单起见,和数组长度保持一致
    private int M;
    // 保存Node元素的数组
    private Node[] data;
    // 负载因子
    private static final double LOAD_FACTOR = 0.75;
    public MyHashMap(){
        this.data = new Node[16];
    }
    public MyHashMap(int c){
        this.data = new Node[c];
        this.M = c;
    }


}

(2)新增 & 修改

//      在当前哈希表中添加一对新元素,返回添加前的值
    public int put(int key,int value){
        // 1.首先计算出当前新元素的下标
        int index = hash(key);
        // 2.在当前的子链表中判断key值是否存在,若存在,只需要更新value即可
        for (Node x = data[index];x != null;x = x.next) {
            if (x.key == key) {
                // 存在,只需要更新value
                int oldValue = x.value;
                x.value = value;
                return oldValue;
            }
        }
        // 3.此时key第一次出现,头插到当前的子链表中
        Node node = new Node(key,value);
        node.next = data[index];
        data[index] = node;
        size ++;
        // 4.判断当前哈希表的冲突情况,是否需要扩容
        if (size >= this.data.length * LOAD_FACTOR) {
            resize();
        }
        return -1;
    }

       // 计算hash值
    private int hash(int key) {
        return key % M;
    }

(3)扩容

private void resize() {
        Node[] newData = new Node[data.length * 2];
        this.M = newData.length;
        // 搬移原数组的所有节点
        for (int i = 0; i < data.length; i++) {

            for (Node x = data[i]; x != null;) {
                Node next = x.next;
                // 当前x搬移到新数组的对应位置
                int index = hash(x.key);
                // 头插到新数组的对应位置
                x.next = newData[index];
                newData[index] = x;
                // 继续搬移原数组的下一个节点
                x = next;
            }
        }
        // 更新data的指向
        data = newData;
    }

(4)查找是否包含key值

//    查看是否包含key
    public boolean containsKey(int key){
        int index = hash(key);
        for (Node x = data[index]; x != null ; x = x.next) {
            if(x.key == key){
                return true;
            }
        }
        return false;
    }

(5)删除指定key值

// 在当前哈希表中删除指定的key值节点
    public boolean removeKey(int key){
        // 1.先求索引
        int index = hash(key);
//        判空
        if(data[index] == null){
            return false;
        }
        // 剩下就是链表的删除问题
        if (data[index].key == key) {
            data[index] = data[index].next;
            size --;
            return true;
        }
        Node prev = data[index];
        while (prev.next != null) {
            if (prev.next.key == key) {
                prev.next = prev.next.next;
                size --;
                return true;
            }
        }
        // 此时不存在指定的key值
        return false;
    }

到了这里,关于【数据结构】用Java实现哈希表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 「数据结构」哈希表2:实现哈希表

    🎇 个人主页 :Ice_Sugar_7 🎇 所属专栏 :Java数据结构 🎇 欢迎点赞收藏加关注哦! 在讲插入之前需要先了解扩容,因为 插入后载荷因子如果超过阈值,那我们就要扩容,即扩容是插入操作的一部分 扩容后,原先哈希表中的元素的哈希地址会改变。之前会发生哈希冲突的元素

    2024年02月21日
    浏览(40)
  • 【数据结构】 | java中 哈希表及其冲突解决

    🎗️ 博客新人,希望大家一起加油进步 🎗️ 乾坤未定,你我皆黑马 1、哈希表概念 顺序结构以及平衡树中 ,元素关键码与其存储位置之间没有对应的关系,因此在 查找一个元素时,必须要经过关键码的多次比较。顺序查找时间复杂度为O(N),平衡树中为树的高度,即O(Lo

    2024年01月19日
    浏览(46)
  • 【Java数据结构】顺序表、队列、栈、链表、哈希表

    是一个有类型参数(type parameter)的范型表(generic class) 能够自动调整容量,并且不需要写额外的代码 存放数据使用数组但是可以编写一些额外的操作来强化为线性表,底层依然采用顺序存储实现的线性表,称为顺序表 创建 常见操作 一旦确认数组列表大小恒定,不再发生

    2024年02月02日
    浏览(44)
  • 【数据结构篇C++实现】- 哈希表

    友情链接:C/C++系列系统学习目录 哈希表:也叫做散列表。是根据和值(Key-Value)直接进行访问的数据结构。也就是说,它通过 key 和一个映射函数 Hash(key) 计算出对应的一个存储位置,然后把键值对映射到哈希表上的对应位置来访问记录,以加快查找的速度。这

    2024年02月02日
    浏览(45)
  • java数据结构(哈希表—HashMap)含LeetCode例题讲解

      目录 1、HashMap的基本方法 1.1、基础方法(增删改查) 1.2、其他方法  2、HashMap的相关例题 2.1、题目介绍 2.2、解题 2.2.1、解题思路 2.2.2、解题图解 2.3、解题代码 HashMap 是一个散列表,它存储的内容是键值(key-value)映射。 HashMap 的 key 与 value 类型可以相同也可以不同,根据定

    2024年02月05日
    浏览(52)
  • 【数据结构】【王道】【数据结构实现】文章目录

    持续更新中。。。 数据结构 链接 顺序表实现及基本操作(可直接运行) 文章链接 无头结点单链表的实现及基本操作(可直接运行) 文章链接 带头结点单链表的实现及基本操作(可直接运行) 文章链接 双链表的实现及基本操作(可直接运行) 文章链接 循环链表的实现及

    2023年04月08日
    浏览(92)
  • 【Java程序员面试专栏 数据结构】四 高频面试算法题:哈希表

    一轮的算法训练完成后,对相关的题目有了一个初步理解了,接下来进行专题训练,以下这些题目就是汇总的高频题目,一个O(1)查找的利器哈希表,所以放到一篇Blog中集中练习 题目 解题思路 时间 空间 两数之和 辅助哈希 使用map存储出现过的值,key为值大小,v

    2024年02月22日
    浏览(59)
  • Java学数据结构(4)——散列表Hash table & 散列函数 & 哈希冲突

    1.散列表,key,散列函数; 2.哈希冲突的解决; 3.string中的hashCode; 查找树ADT,它允许对元素的集合进行各种操作。本章讨论散列表(hash table)ADT,不过它只支持二叉查找树所允许的一部分操作。散列表的实现常常叫作散列(hashing)。散列是一种用于以常数平均时间执行插入、删除和

    2024年02月10日
    浏览(55)
  • 【数据结构】树、二叉树的概念和二叉树的顺序结构及实现

    之前我们学习了顺序表、链表以及栈和队列这些数据结构,但这些数据结构都是线性的(一对一)。接下来要学习 非线性的数据结构——树(二叉树) ,相比前面的,树的结构更加复杂,话不多说,直接进入正题吧。 树是一种 非线性的数据结构 ,它是 一对多(也有可能是

    2024年02月07日
    浏览(42)
  • 【数据结构】哈希底层结构

    目录 一、哈希概念 二、哈希实现 1、闭散列 1.1、线性探测 1.2、二次探测 2、开散列 2.1、开散列的概念 2.2、开散列的结构 2.3、开散列的查找 2.4、开散列的插入 2.5、开散列的删除 3、性能分析  顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查

    2024年02月06日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包