我的编程空间,编程开发者的网络收藏夹
学习永远不晚

Java中哈希表的示例分析

短信预约 -IT技能 免费直播动态提醒
省份

北京

  • 北京
  • 上海
  • 天津
  • 重庆
  • 河北
  • 山东
  • 辽宁
  • 黑龙江
  • 吉林
  • 甘肃
  • 青海
  • 河南
  • 江苏
  • 湖北
  • 湖南
  • 江西
  • 浙江
  • 广东
  • 云南
  • 福建
  • 海南
  • 山西
  • 四川
  • 陕西
  • 贵州
  • 安徽
  • 广西
  • 内蒙
  • 西藏
  • 新疆
  • 宁夏
  • 兵团
手机号立即预约

请填写图片验证码后获取短信验证码

看不清楚,换张图片

免费获取短信验证码

Java中哈希表的示例分析

这篇文章将为大家详细讲解有关Java中哈希表的示例分析,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。

    1,概念

    顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过关键 码的多次比较。顺序查找时间复杂度为O(N),平衡树中为树的高度,即O( ),搜索的效率取决于搜索过程中 元素的比较次数。

    理想的搜索方法:可以不经过任何比较,一次直接从表中得到要搜索的元素。 如果构造一种存储结构,通过某种函 数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系,那么在查找时通过该函数可以很快找到该元素。

    当向该结构中:

    插入元素

    根据待插入元素的关键码,以此函数计算出该元素的存储位置并按此位置进行存放

    搜索元素

    对元素的关键码进行同样的计算,把求得的函数值当做元素的存储位置,在结构中按此位置取元素比较,若关键码相等,则搜索成功

    例如:数据集合{1,7,6,4,5,9};

    哈希函数设置为:hash(key) = key % capacity; capacity为存储元素底层空间总的大小。

    Java中哈希表的示例分析

    2,冲突-避免

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

    3,冲突-避免-哈希函数设计

    常见哈希函数

    直接定制法--(常用)

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

    除留余数法--(常用)

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

    平方取中法--(了解)

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

    4,冲突-避免-负载因子调节

    Java中哈希表的示例分析

     负载因子和冲突率的关系粗略演示

    Java中哈希表的示例分析

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

    5,冲突-解决-闭散列

    闭散列:也叫开放定址法,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以 把key存放到冲突位置中的“下一个” 空位置中去。

    ①线性探测

    比如上面的场景,现在需要插入元素44,先通过哈希函数计算哈希地址,下标为4,因此44理论上应该插在该 位置,但是该位置已经放了值为4的元素,即发生哈希冲突。 线性探测:从发生冲突的位置开始,依次向后探测,直到寻找到下一个空位置为止。

    插入

    通过哈希函数获取待插入元素在哈希表中的位置 如果该位置中没有元素则直接插入新元素,如果该位置中有元素发生哈希冲突,使用线性探测找到 下一个空位置,插入新元素

    Java中哈希表的示例分析

    采用闭散列处理哈希冲突时,不能随便物理删除哈希表中已有的元素,若直接删除元素会影响其他 元素的搜索。比如删除元素4,如果直接删除掉,44查找起来可能会受影响。因此线性探测采用标 记的伪删除法来删除一个元素。

    ②二次探测

    线性探测的缺陷是产生冲突的数据堆积在一块,这与其找下一个空位置有关系,因为找空位置的方式就是挨 着往后逐个去找,因此二次探测为了避免该问题,找下一个空位置的方法为: = ( + )% m, 或者: = ( - )% m。其中:i = 1,2,3…, 是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置, m是表的大小。 对于2.1中如果要插入44,产生冲突,使用解决后的情况为:

    Java中哈希表的示例分析

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

    6,冲突-解决-开散列/哈希桶

    开散列法又叫链地址法(开链法),首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子 集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中。

    Java中哈希表的示例分析

    Java中哈希表的示例分析

          static class Node {         public int key;         public int val;         public Node next;          public Node(int key, int val) {             this.key = key;             this.val = val;         }     }      private Node[] array;     public int usedSize;      public HashBucket() {         this.array = new Node[10];         this.usedSize = 0;     }

    Java中哈希表的示例分析

    Java中哈希表的示例分析

     public void put(int key,int val){        int index = key % this.array.length;        Node cur = array[index];        while (cur != null){            if(cur.val == key){                cur.val = val;                return;            }            cur = cur.next;        }        //头插法         Node node = new Node(key,val);        node.next = array[index];        array[index] = node;        this.usedSize++;        if(loadFactor() >= 0.75){            resize();        }    }
    public int get(int key) {         //以什么方式存储的  那就以什么方式取         int index = key % this.array.length;         Node cur = array[index];         while (cur != null) {             if(cur.key == key) {                 return cur.val;             }             cur = cur.next;         }         return -1;//     }

    Java中哈希表的示例分析

    Java中哈希表的示例分析

    Java中哈希表的示例分析

    public void resize(){         Node[] newArray = new Node[2*this.array.length];        for (int i = 0; i < this.array.length; i++){            Node cur = array[i];            Node curNext = null;            while (cur != null){                 curNext = cur.next;                int index = cur.key % newArray.length;                cur.next = newArray[i];                newArray[i] = cur;                cur = curNext.next;                cur = curNext;             }        }        this.array = newArray;    }

    7,完整代码

     class HashBucket {      static class Node {         public int key;         public int val;         public Node next;          public Node(int key, int val) {             this.key = key;             this.val = val;         }     }      private Node[] array;     public int usedSize;      public HashBucket() {         this.array = new Node[10];         this.usedSize = 0;     }      public void put(int key,int val) {         //1、确定下标         int index = key % this.array.length;         //2、遍历这个下标的链表         Node cur = array[index];         while (cur != null) {             //更新val             if(cur.key == key) {                 cur.val = val;                 return;             }             cur = cur.next;         }         //3、cur == null   当前数组下标的 链表  没要key         Node node = new Node(key,val);         node.next = array[index];         array[index] = node;         this.usedSize++;         //4、判断  当前 有没有超过负载因子         if(loadFactor() >= 0.75) {             //扩容             resize();         }     }      public int get(int key) {         //以什么方式存储的  那就以什么方式取         int index = key % this.array.length;         Node cur = array[index];         while (cur != null) {             if(cur.key == key) {                 return cur.val;             }             cur = cur.next;         }         return -1;//     }       public double loadFactor() {         return this.usedSize*1.0 / this.array.length;     }       public void resize(){         Node[] newArray = new Node[2*this.array.length];        for (int i = 0; i < this.array.length; i++){            Node cur = array[i];            Node curNext = null;            while (cur != null){                 curNext = cur.next;                int index = cur.key % newArray.length;                cur.next = newArray[i];                newArray[i] = cur;                cur = curNext.next;                cur = curNext;             }        }        this.array = newArray;    }  }

    关于“Java中哈希表的示例分析”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,使各位可以学到更多知识,如果觉得文章不错,请把它分享出去让更多的人看到。

    免责声明:

    ① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

    ② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

    Java中哈希表的示例分析

    下载Word文档到电脑,方便收藏和打印~

    下载Word文档

    猜你喜欢

    Java中哈希表的示例分析

    这篇文章将为大家详细讲解有关Java中哈希表的示例分析,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。1,概念顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过
    2023-06-29

    Laravel中加密解密与哈希实例的分析

    这篇文章给大家分享的是有关Laravel中加密解密与哈希实例的分析的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。一、加密解密当你的应用程序中需要用到加密和解密的地方时可以使用Laravel自带的加密解密工具。La
    2023-06-14

    如何有效处理 Java 哈希表中的空值?(如何处理Java哈希表中的空值)

    在Java编程中,哈希表(HashTable)是一种常用的数据结构,它通过哈希函数将键(Key)映射到存储位置,以实现快速的数据存储和检索。然而,在处理哈希表时,我们经常会遇到空值(NullValue)的情况,这可能会导致一些问题,如哈希冲突、性能下降等。本文将介绍如何处理Java
    如何有效处理 Java 哈希表中的空值?(如何处理Java哈希表中的空值)
    Java2024-12-22

    Java中链表的示例分析

    这篇文章将为大家详细讲解有关Java中链表的示例分析,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。题目一 解法/** * Definition for singly-linked list. * publ
    2023-06-29

    Java数据结构中实现哈希表的分离链接法

    这篇文章主要介绍“Java数据结构中实现哈希表的分离链接法”,在日常操作中,相信很多人在Java数据结构中实现哈希表的分离链接法问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”Java数据结构中实现哈希表的分离
    2023-06-20

    Java顺序表的示例分析

    这篇文章主要介绍Java顺序表的示例分析,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完!一 、前言顺序表常用的一种,学习并了解显得十分重要,顺序表为以后的学习打下了基石。二、顺序的定义顺序表示在计算机内存中以数组的形式
    2023-06-25

    Java中正则表达式的示例分析

    这篇文章主要介绍了Java中正则表达式的示例分析,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。前几天线上一个项目监控信息突然报告异常,上到机器上后查看相关资源的使用情况,发现
    2023-06-15

    Java复杂链表的示例分析

    这篇文章将为大家详细讲解有关Java复杂链表的示例分析,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。1.题目请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个
    2023-06-28

    Java中BeanUtils.copyProperties的示例分析

    这篇文章将为大家详细讲解有关Java中BeanUtils.copyProperties的示例分析,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。场景开发中经常遇到,把父类的属性拷贝到子类中。通常有2种方法:
    2023-06-20

    Java中hashcode的示例分析

    小编给大家分享一下Java中hashcode的示例分析,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!java基本数据类型有哪些Java的基本数据类型分为:1、整数
    2023-06-14

    Java中NIO的示例分析

    这篇文章主要介绍了Java中NIO的示例分析,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。一、Java思维导图二、I/O模型I/O模型的本质是用什么样的通道进行数据的发送和接
    2023-06-29

    java中JDBC的示例分析

    这篇文章将为大家详细讲解有关java中JDBC的示例分析,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。常用的java框架有哪些1.SpringMVC,Spring Web MVC是一种基于Java的实现了
    2023-06-14

    php中链表的示例分析

    这篇文章将为大家详细讲解有关php中链表的示例分析,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。链表的操作相对顺序表来说就复杂了许多。因为PHP确实已经为我们解决了很多数组操作上的问题,所以我们可以很方便
    2023-06-20

    Java中锁的示例分析

    小编给大家分享一下Java中锁的示例分析,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!Java中的锁Java中的加锁操作有两种: 1.synchronized锁(
    2023-06-20

    编程热搜

    • Python 学习之路 - Python
      一、安装Python34Windows在Python官网(https://www.python.org/downloads/)下载安装包并安装。Python的默认安装路径是:C:\Python34配置环境变量:【右键计算机】--》【属性】-
      Python 学习之路 - Python
    • chatgpt的中文全称是什么
      chatgpt的中文全称是生成型预训练变换模型。ChatGPT是什么ChatGPT是美国人工智能研究实验室OpenAI开发的一种全新聊天机器人模型,它能够通过学习和理解人类的语言来进行对话,还能根据聊天的上下文进行互动,并协助人类完成一系列
      chatgpt的中文全称是什么
    • C/C++中extern函数使用详解
    • C/C++可变参数的使用
      可变参数的使用方法远远不止以下几种,不过在C,C++中使用可变参数时要小心,在使用printf()等函数时传入的参数个数一定不能比前面的格式化字符串中的’%’符号个数少,否则会产生访问越界,运气不好的话还会导致程序崩溃
      C/C++可变参数的使用
    • css样式文件该放在哪里
    • php中数组下标必须是连续的吗
    • Python 3 教程
      Python 3 教程 Python 的 3.0 版本,常被称为 Python 3000,或简称 Py3k。相对于 Python 的早期版本,这是一个较大的升级。为了不带入过多的累赘,Python 3.0 在设计的时候没有考虑向下兼容。 Python
      Python 3 教程
    • Python pip包管理
      一、前言    在Python中, 安装第三方模块是通过 setuptools 这个工具完成的。 Python有两个封装了 setuptools的包管理工具: easy_install  和  pip , 目前官方推荐使用 pip。    
      Python pip包管理
    • ubuntu如何重新编译内核
    • 改善Java代码之慎用java动态编译

    目录