精华内容
下载资源
问答
  • 哈希表结构
    千次阅读
    2019-03-29 11:43:28

    1、哈希值

    (1)、概念: 是一个十进制的整数,由系统随机给出;
           就是对象的地址值,但这是一个逻辑地址,是模拟出来的;不是数据实际存储的物理地址
    (2)、获取哈希值: 可通过Object类hasCode() 方法获取哈希值
    hasCode()源码如下:

    public native int hasCode() {
    	...
    }
    // native:表示该方法调用的是本地操作系统的方法
    

    (3)、String类重写了hasCode(),所以new出来对象的值如果一样,哈希值就一样;否则不一样
      特例:

    "重地".hasCode()  :哈希值是1179395
    "通话".hasCode()  :哈希值是1179395
    

    2、哈希表结构

    (1)、哈希表的初始长度是16(0~15)
    (2)、哈希表组成:
      java7 及之前:哈希表 = 数组 + 链表
      java8 及之后:哈希表 = 数组 + 链表
             或者:哈希表 = 数组 + 红黑树 (只是为了提高查询的速度)
         先使用数组 + 链表,当同个hasCode的下挂元素超过8个时,就改用数组 + 红黑树
    (3)、哈希表的查询、增删速度非常快,但创建速度非常慢
    (4)、哈希表图解
    在这里插入图片描述

    3、哈希表不允许存储重复元素的原理

    注意: 集合中存储的只能是类对象或者是自定义对象,不能是基本类型。所以这边说的 元素其实是对象元素
        哈希表结构的集合在调用添加元素的方法时,会先调用元素的hasCode()和equals()两个方法;以判断元素是否重复
    (1)、调用hasCode(),查看哈希值,不一样则存储到对应哈希值下;一样则调用equals()
    (2)、调用equals(),返回false则存储到对应哈希值下;否则不存储

    更多相关内容
  • 哈希表课程设计数据结构实验报告——哈希表设计 针对某个集体中的人名设计一个哈希表,使得平均查找长度不超过R,完成相应的建立和查表程序. 1.2 人名为汉语拼音形式,最长不超过18个字符(如:庄双双 ...
  • 哈希表设计程序设计+数据结构实验报告 1.1 针对某个集体中的人名设计一个哈希表,使得平均查找长度不超过R,完成相应的建立和查表程序. 1.2 人名为汉语拼音形式,最长不超过18个字符(如:庄双双 zhuangshuangshuang)...
  • 按照学生数据student.txt 实现对学生信息的...3.按照姓名字段构建哈希表结构,实现姓名的模糊查询。姓名取中文姓氏作为哈希地址 4.排序 实现多关键字排序 5.分别使用堆排和快排显示成绩前10名学生 并展示2种不同时间
  • 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个,取平均查找长度的上限为2。哈希函数用除留余数法构造,用线性探测再散列法或链地址法处理冲突。 [测试数据] 取读者周围较熟悉的30个人名
  • 哈希表底层实现

    2021-01-20 13:46:03
    哈希表使用数组作为主干,实现查找,插入,删除元素的时间复杂度为O(1)。 哈希表(key,value) 就是把Key通过一个固定的算法函数既哈希函数转换成一个整型数字,然后将该数字对数组长度进行取余,取余结果就当作数组...
  • 数据结构哈希表

    千次阅读 2022-01-24 17:03:11
    数据结构哈希表(解决冲突常用方法)1.什么哈希表2.构造哈希函数3.解决哈希冲突3.1.开放定址法(开地址法)3.2.链地址法(拉链法) 1.什么哈希表 散列表(Hash table,也叫哈希表),是根据关键 码值(Key ...

    1.什么是哈希表

    • 散列表(Hash table,也叫哈希表),是根据关键 码值(Key value)而直接进行访问的数据结构。也
      就是说,它通过把关键码值映射到表中一个位置来 访问记录,以加快查找的速度。这个映射函数叫做 散列函数,存放记录的数组叫做散列表。

    • 给定表M,存在函数f(key),对任意给定的关键字 值key,代入函数后若能得到包含该关键字的记录
      在表中的地址,则称表M为哈希(Hash)表,函数 f(key)为哈希(Hash) 函数。

    2.构造哈希函数

    除留余数法(常用)
       此方法为最常用的构造哈希函数方法。对于哈希表长为m的哈希函数公式为:
       f(key) = key mod p (p <= m)

    本方法的关键在于选择合适的p,一般来说,若散列表的表长为m,通常p为小于或等于表长(最好接近m)的最小质数或不包含小于20质因子的合数。这样可以减少地址的重复(冲突)
    其他还有
    1.直接定址法
    2.平方取中法
    3.折叠法
    4.随机数法
    都可以用于构造哈希函数。
    选好要用的哈希函数,完成关键字和存储位置的对应,即可构建哈希表。

    3.解决哈希冲突

    下面介绍两种解决哈希冲突的方法

    3.1.开放定址法(开地址法)

    基本思想:有冲突时就去寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到,并将数据元素存入。(其中散列表的表长用m表示)
    在这里插入图片描述
    线性探测法

    在这里插入图片描述
    实例:

    关键码集为{47,7,29,11,16,92,22,8,3},散列的表长为m=11;散列函数为Hash(key)=key mod 11;拟用线性探测法解决哈希冲突。
    建散列表如下:
    在这里插入图片描述

    3.2.链地址法(拉链法)

    基本思想:相同散列地址的记录链成一单链表
    在这里插入图片描述

    本文的图片来自哔哩哔哩王卓老师的网课截图。

    展开全文
  • 散列表的设计实验报告 1题目 散列表的设计:针对某个集体中人名设计一个散列表使得平均查找长度不超过R,并完成相应的建表和查表程序 2基本要求 假设人名为中国人姓名的汉语拼音形式待填入哈希表的人名共30个取平均...
  • /******************* 数据结构哈希表算法实现 ********************/
  • 哈希表的数据结构

    2018-06-29 13:57:45
    哈希表的数据结构哈希表的数据结构哈希表的数据结构哈希表的数据结构
  • 数据结构 C语言作业/练习 代码完美运行
  • 任务要求:针对姓名信息进行初始化哈希表,可以进行显示哈希表,查找元素。 设计思想:哈希函数用除留余数法构造,用线性探测再散列处理冲突。 设人名为中国人姓名的汉语拼音的形式,有30个待入的人名,取平均查找...
  • 洛阳理工学院实验报告 系部 计算机与信息工程系 班级 学号 姓名 课程名称 数据结构 实验日期 2014.4.23 实验名称 实验5图的遍历的实现 成绩 实验目的 掌握图的邻接矩阵和邻接两种存储结构掌握图的深度优先和广度...
  • 数据结构——哈希表

    千次阅读 2022-03-24 00:16:09
    摘要:本篇笔记主要讲解了重要数据结构——哈希表,以及键值对的含义,为什么要用键值对,哈希表的应用场景,以及内存中运行的数据库的基础知识

    数据结构——哈希表

    摘要:本篇笔记主要讲解了重要数据结构——哈希表,以及键值对的含义,为什么要用键值对,哈希表的应用场景,以及内存中运行的数据库的基础知识

    1.何为哈希表?

    1.1.用于存储的数据结构

    ​ 在计算机中,数组和链表都可以用于数据的存储,既然有数据存储,那么必然要有数据的查询,因此我们在将数据存储进数组和链表中之后,必然要对它们进行查询操作。一个链表的查询时间复杂度为O(n),而一个无序数组的查询时间复杂度也是O(n),对于数组的查询时间,我们尚有讨论的余地,但是链表的查询时间肯定是更长的,因为链表是不连续的空间,它只能一个接一个的遍历查询,不管链表是否有序。但是数组的查询时间,是可以进行改进的,当数组中数据是有序的,我们就可以使用二分查找的方式查找数组中的数据,进而能大量节省查询时间,对于二分查找,并不是一个困难的问题,因为二分法每次都能甩掉一般的数据,因此其时间复杂度肯定比O(n)低很多,它的时间复杂度是O(logn),随着查询次数的增长,其时间复杂度会明显比O(n)低很多。

    ​ 因此对于数组而言,我们的研究方向便不再是如何找更优的查找方案,而是如何将其更快的排序,因此引出了排序算法,目前主流的排序算法有八种,实际上大家比较认可的排序方法还有更多,值得学习的排序方法至少有十种。现实告诉我们,矛盾很难消除,它只会转移,有了二分查找的数组,查询时间长的矛盾并不能直接消除,因为排序算法也是耗费时间的,查询的时间跑到了排序的时间里去了。对于排序的时间复杂度,最低的为O(nlogn),看上去也不是特别的少,这也就直接导致了两个算法加起来的时间复杂度,比直接无序状态查还耗费时间。

    ​ 基于这个问题,有人创造性的提出了一种新的思想,那就是:在存储数据的时候,不再来数就存,而是使用一种巧妙的分类方法,将数据们进行分类,进而达到像二分查找一样的大规模缩减查询范围的效果,这就是哈希存储。

    1.2.哈希表

    ​ 哈希表的物理结构多种多样,在基数排序中用到的桶结构,实际上就是一种哈希表,哈希表通常是基于某种分类规则,为存储的数据进行分类,然后将他们存储在不同的索引下,这样我们在查询一个数据的时候,先拿到索引,然后找到哈希表中索引吻合的数据存储表,然后直接在这个表中查询即可,而不用再遍历所有数据,这就是哈希表的好处。为了助记哈希表,我将使用一个例子来生动的阐述哈希表:在一个图书馆中,存放着很多各种类别的书,有小说,字典,杂志,专业书籍等若干本。在早期,图书管理员并不怎么好好打理这些书籍,它将这些书籍完全无序的堆放在一起,来了借阅的人,就要直接挨个翻找,直到找到自己想要看的书籍为止。在之后的某一天,来了一个新的图书管理员,这个图书管理员为这些书籍进行了分类,他按照这四种类别将这些书放到了不同的区域中,之后,来了借阅的人,首先会报出书名,然后图书管理员按照书名判断这本书的类别,如来了一个人想借阅《人民文学》,图书管理员就会告诉这名读者:该书籍属于杂志,请去杂志区寻找,这名读者就会直接步行至杂志区,这样就他就不用再对整堆书进行翻找,很大程度上的节省了时间。哈希表的工作原理,实际上就是这样的一种过程。其使用到的主要思想,就是索引存储,它按照某一种规则,为数据分类,然后将这些数据放入不同的类别下,这些类别会有相应的索引值,在我们进行查询的时候,首先会查询索引值,查询到索引值之后,便直接将这个数据与索引值对应的存储结构中进行查询,这样就直接缩减了查询范围,缩小了查询规模。

    1.3.什么是哈希表

    ​ 哈希表是一种计算机中常用的存储结构,其存储方式为索引存储。在进行数据存储的时候,首先会根据某种规则,对数据进行分类,然后将数据放入至相应类别的存储结构中去,在哈希表中,每一个类别都会有一个自己的存储空间,专门存放类别符合索引的数据们,在查询的时候,同样是按照规则先得到类别,然后直接查相应类别对应的存储结构中的数据,进而缩小查询范围,达到节省时间的目的。

    2.哈希表的一般构造

    ​ 哈希表通常是什么样的呢?我们举一个非常简单的例子,我们以某个数字对5取余数的结果对数字进行分类,进而绘制一个哈希表。既然是对5取余运算,我们知道,其结果只能是有0,1,2,3,4五个数,因此分类有五种,索引也就是五种:

    image-20220323182245427

    ​ 而当传入数据:23,12,43,15,24,33,79的时候,他们首先会被分类规则运算并分类,然后存放在自己相应的类别下,如23取余操作之后,结果为3,因此将其存放在索引为3的分类下;12求余之后为2,因此将其存放在索引为2的分类下;43求余结果为3,因此将其存放在索引为3的分类下;15求余结果为0,将其存放在索引为0的分类下;24求余结果为4,将其存放在索引为4的分类下;33求余结果为3,将其存放在索引为3的分类下;79求余结果为4,将其存放在索引为4的分类下。因此整个数据在存入之后,我们便得到了一个这样的结构:

    image-20220323190139693

    ​ 当我们要查询一个数据33的时候,首先就会根据规则对33进行运算,获取到其分类索引值:3,然后我们在分类索引表中搜索到索引为3的分类,然后再在它对应的表中进行查找,这样一来,我们就缩小了查找范围,进而节省了时间。

    3.自己书写一套哈希表

    ​ 显而易见的是,在计算机编程中,哈希表往往不是简单的一个数据结构,而是一个搭配数据结构并具备一套完整的操作的方法的套组,乃至是一个库,在Java中,就存在一个叫hashMap的类,用于进行哈希表结构的操作,因此,我们要书写一个简单的哈希表,其实也是书写了一个套组,接下来,我将分享我自己书写的一个简单的哈希表套组,进而加深对于哈希表的理解与知识点印象。

    /*员工类:哈希表中的存储节点,是我写的哈希表中最基础的存在,直接存储数据的单元*/
    package y2022.m3.d19.hash;
    
    public class Employee {
        public int id;//id号,本质上就是我的哈希表中进行分类的依托,对于表中数据的唯一识别码
        public String name;//姓名,表中想要存储的具备价值的信息
        public Employee next;//next指针,因为该哈希表是链式结构,所以有这个指针
    
        public Employee(int id, String name){//构造方法
            this.id = id;
            this.name = name;
        }
    }
    /*值得思考之处:
    	1.在一个哈希表节点中,我们为何要设定一个id字段,这个字段是干什么用的?
    	2.我们为什么要用链式结构存储一个哈希表?用数组不香吗?
    */
    

    ​ 对于上述两个值得思考的点,我们依次说明:首先,在哈希表中,我们为什么要单独设定一个id值?在初学阶段,我们都会写数组或链表,面对的问题也大多是一些基础的排序算法,总之就是象牙塔里搞的学术问题,也就是说很少面向实际,因此在做题的时候,面向的东西大多都是单纯的数字,没有额外的操作字段,实际上他们如果用于存储一些实际生活中的信息,也是应该有除了数字之外的字段的,还有就是在数组中,每一个节点中都有一个隐含的索引,也就是它的位置,即使是在链表当中,每个链表节点也是拥有属于自己的索引的,并且由于这两位的查找方式,多是穷举遍历然后对比的思想,即使是巧妙的二分查找,实际上也是直接通过数组位置进行计算,然后进行对比,因此他们使用线性结构中的隐藏索引:下标,就可以解决查找问题,但是哈希表中不一样,在哈希表中,我们首先就需要一个分类的依据,没有这个分类的依据,我们自然无法完成分类,也就无法完成哈希表的构建,其次,在真正的哈希表中,我们很少使用到线性结构,而是使用到一种充满灵性的结构:红黑树,并且我们不会使用基于顺序结构的树,而是使用链式结构的树,在这种树中下标概念会显得非常鸡肋,因此我们通常定义一个唯一识别码,这个唯一识别码最主要的作用就是用于分类,以及查找时的索引,这个唯一识别码可以是有意义的字段,比如姓名,我们完全可以自行设计一个可以对姓名进行分类的规则,然后按照姓名存储,但是由于哈希表的存储结构,当两个姓名重复,但两个人不是同一个人的时候,两个人就无法区分,在自己设计着玩的时候,可能伤害不大,然而一旦面临实际问题,面向用户的查找,我们必须保证结果准确无误,所以我们应该尽量保证分类依据是独一无二的数字。

    ​ 然后,我们为什么要使用链式结构呢?这是因为哈希表本身的结构,并不是一个规则的网格表,根据前文中的图片,大家就可以看出来,哈希表的每个分类下的数据表都又长又短,使用数组可能会导致浪费与不可预估的数据溢出,因此我们选择了链式存储结构,与此同时的,在更好的哈希表中,每项数据一旦过长,就不会再使用链表,而是使用红黑树进行存储,红黑树是一种非常好的数据存储结构,其查找速度非常快。使用链式结构,也意味着我们需要自定义一个索引字段,我们通常是根据这个索引字段进行查找。

    实际上,产生第一个疑问的原因,大多是因为很少接触实际问题,实际上,在数组和链表中,我们的数组或链表中的那一个数字,实际上就是我们的索引字段,只不过是为了简化问题,在学习排序或链表操作的时候,我们很少加入其他字段

    /*员工链表类:这个数据结构就是每一个分类索引下的那个表的实体,也就是存储数据的那个表,这个类里边就是表的一些操作*/
    package y2022.m3.d19.hash;
    
    import javax.swing.text.Style;
    
    public class EmpLinkedList {
        public Employee head;//上边定义的员工类的头结点
    
        public void add(Employee newEmployee){
            if(this.head==null){
                head = newEmployee;
                return;
            }//通过这里的添加方法可以看出这是一个无头节点的链表
            Employee tempEmp = head;
            while(true){
                if(tempEmp.next == null){
                    break;
                }
                tempEmp = tempEmp.next;
            }
            tempEmp.next = newEmployee;
        }
    
        public void list(){//链表展示方法,不是关键代码
            if(head == null){
                System.out.println("链表为空");
                return;
            }
    
            Employee tempEmp = head;
            int count = 0;
            while(true){
                System.out.print(" | ID = "+tempEmp.id +" | 姓名:"+tempEmp.name+" | ");
                count++;
                if(tempEmp.next == null){
                    System.out.println("共"+count+"个");
                    return;
                }
                tempEmp = tempEmp.next;
            }
    
        }
    }
    
    

    ​ 接下来是哈希表类的定义:

    package y2022.m3.d19.hash;
    
    public class HashTab {
        //定义数组
        private EmpLinkedList[] empLinkedLists;//这是一个链表类型的数组,需要注意的是,这个链表类型的数组中的元素并不是节点类型的,而是上面定义的链表类型的,这个数组中会有多个EmpLinkedList类型的对象,这些对象中的head字段才是节点类型的变量
        //定义数组的大小
        private int size;
    
        public HashTab(int size){
            this.size = size;
            empLinkedLists = new EmpLinkedList[size];//声明好数组之后,默认值是null
    		//这里的一个小细节需要注意,引用类型的变量在声明后如果不初始化那默认值就是null,数组也不例外,因此在这里声明好数组之后,还要初始化
            for(int i = 0;i<size;i++){//这个循环体就是在初始化
                empLinkedLists[i] = new EmpLinkedList();//在这里必须要逐一为每一个元素再进行实例化,否则它就没有,就是空,不能进行存储
            }
        }
    
        public  int hash(int id){
            return id % size;
        }//哈希存储规则,这个就是分类规则,因为我们在上边定义了一个数组,因此我们的数组下标就可以与求余结果相对应,返回的值,即使数字类型
    
        public void add(Employee employee){//添加方法,这个方法是调用链表数组中的一个链表元素的添加方法,它首先是调用了hash方法取得分类,然后根据这个分类结果进行数组元素定位,然后添加的,分类添加的原则就体现在了这里
            int num = hash(employee.id);
            empLinkedLists[num].add(employee);
        }
    
        public  void list(){//展示方法,这里调用了链表的展示方法,算是一种方法加强吧,并不重要
            for(int i = 0;i<size;i++){
                System.out.print("第"+i+"个链表状况:");
                empLinkedLists[i].list();
            }
        }
    }
    
    

    ​ 接下来我们来测试一下这套简单的哈希表效果如何,我们使用代码:

    package y2022.m3.d19.hash;
    
    public class Test {
        public static void main(String[] args) {
            HashTab hashtab = new HashTab(8);
            Employee employee1 = new Employee(10,"社会虎");
            Employee employee2 = new Employee(18,"废物刀");
            Employee employee3 = new Employee(26,"黑牛");
            Employee employee4 = new Employee(3,"白牛");
            Employee employee5 = new Employee(193,"小亮");
            Employee employee6 = new Employee(231,"唐老鸭");
            Employee employee7 = new Employee(12,"百特曼");
            Employee employee8 = new Employee(1,"独爱小尹");
            Employee employee9 = new Employee(123,"丽丽");
            Employee employee10 = new Employee(126,"带篮子");
            Employee employee11 = new Employee(29,"刘墉");
            Employee employee12 = new Employee(86,"丁真");
            Employee employee13 = new Employee(800,"王冰冰");//定义数据
    
            hashtab.add(employee1);
            hashtab.add(employee2);
            hashtab.add(employee3);
            hashtab.add(employee4);
            hashtab.add(employee5);
            hashtab.add(employee6);
            hashtab.add(employee7);
            hashtab.add(employee8);
            hashtab.add(employee9);
            hashtab.add(employee10);
            hashtab.add(employee11);
            hashtab.add(employee12);
            hashtab.add(employee13);//插入数据
    
            hashtab.list();//显示数据
        }
    }
    
    

    ​ 输出结果如下:

    image-20220323233609310

    ​ 在这个哈希表的实现过程中,我们定义了两个字段,id和name,在哈希表插入数据的过程中,是通过id进行分类,并进行放置,并进行查找的,因此我们可以发现id这个字段,是哈希表中的一个很重要的存在,因此在之后,人们称哈希表中这种决定存储和查询的关键字段为,而键对应的一些有意义的信息我们称之为:,两者在一起就是键值对,好,我们已经引出了哈希表中至关重要的一个概念:键值对

    4.HashMap与键值对

    ​ 在Java中,存在一种现成的哈希表类:HashMap,我们直接声明并使用它,使用这个类,我们就可以在其对象内部的哈希表中插入一个键值对,然后通过键来进行值的查找,同时在这个类中,键名不可重复,如果重复插入同样键名而值不同的键值对,会对已有的键值对进行更新,而不会添加新的键值对,也就是说:键是唯一的标识。接下来我们举个例子来看看Java中的HashMap类:

    package y2022.m3.d19.hash;
    
    import java.util.HashMap;
    
    public class HashMapStudy {
        public static void main(String[] args) {
            HashMap<String, Integer> map = new HashMap<String, Integer>();
            HashMap<String, Integer> map1 = new HashMap<String, Integer>();
            map.put("杀马特团长",100);
            map.put("社会虎",0);
            //System.out.println(map.get("Tom"));
            map.put("废物刀",10);
            map.put("唐老鸭",101);
            map.remove("杀马特团长");
            System.out.println(map.containsValue(10));
            map1.putAll(map);
            System.out.println(map1.get("社会虎"));
            map1.replace("社会虎",200);
            System.out.println(map1.get("社会虎"));
        }
    }
    

    ​ 运行结果为:

    image-20220323234250970

    ​ 可见它的键可以为字符串类型,这说明其内部肯定有一个针对字符串进行分类并存储的机制,关于这个机制在源码中可以找到,由于我现在还没有怎么看源码,这里先略过,但是我们可以知道的是,这个类的实现,必然包含了一个根据字符串进行分类的机制,同时我们需要知道的是其内部的键值对节点信息的存储,其存储结构是一种叫红黑树的存储结构,关于红黑树的具体知识,我会在以后进行分享。

    5.哈希表与键值对的应用场景

    ​ 好了,我们现在已经知道哈希表是怎么用了,也知道了哈希表中的键值对思想了,那么这些东西,我们苦哈哈的学会了,到底有什么用呢?答案是用于做数据库,你可能会说:啊?哈希表还能做数据库?是的,哈希表的思想被广泛应用于各种非关系型数据库中,根据上面的学习,我们可以感受到哈希表是为了存储数据而生的,其次是我们发现,哈希表的查询速度一定是比关系型数据库快的,为什么?因为关系型数据中是一张一张的表,而表中的信息实际上就是一个连续的数组:

    image-20220323235223492

    ​ 如图所示的表,实际上就是一块连续空间,其本质上就是一个数组。因此在数据库中,总会按照一个主键值进行排序,然后在select的时候使用二分搜索进行查找,这个过程上面也论述了,并不快,而且二分搜索属于一种查询时间比较恒定的算法,而使用哈希表,如果结合红黑树或者跳表进行实现,时间复杂度其实和二分搜索是不分上下的,其次是当某一个分类中的数据更少的时候,哈希表还会花费更少的时间,因此使用哈希表进行数据存储肯定是比数据库快,那这么好,这么快的数据库结构,为啥没有吧mysql和oracle那些传统数据库顶替了呢?道理很简单:存储密度低,那问题又来了:既然他们代替不了oracle,他们能干啥呢?答案是:用哈希表思想实现的数据库,通常在内存中进行数据存储,一些非关系型数据库如MangoDB,Redis等,通常会在内存中而非在磁盘中进行数据存储,为什么要让它们在内存中进行数据存储呢?这个问题值得我们好好讨论一下。所以我打算花费下边的一个小节讲一讲。

    6.为什么要有在内存中存储数据的数据库

    ​ 根据调查研究表明,一个系统中数据库里的数据,被经常查询到的数据,也就占20%作用,此所谓二八原则。既然这些数据经常被查询到,那肯定存在非常高的并发查询次数,如果这些数据被存在硬盘里,那速度肯定是极慢的,事实上,它就是极慢的,从磁盘中检索数据的时间比从内存中检索数据的速度慢了大概好几倍,甚至上十倍,在检索高峰期,很可能长时间查不出来,用户如果感觉查询速度很慢,比如我现在想搜一下滇红茶,如果它被存放在磁盘中,其查询速度可能是10秒,而如果放在内存中,其查询速度可能不到1秒,因为这9秒的时间差,我很可能就会改变心意,甚至骂这个网商公司,说搜个东西还这么慢,必须倒闭奥。因此为了提升用户体验,很多提供查询服务的大型企业,会专门配置一个内存存储阵列,在这个阵列中,可能有上百T的内存空间,而这个内存空间里边,存放的就是那20%的常用信息,用户在查询这些信息的时候非常快速,而管理这些数据的数据库,就是这些基于hash表的数据库,hash加内存,那速度肯定是杠杠的。这些数据库同时也具备持久化的能力,比如将非关系型数据转化成关系数据并放入传统数据库中,这些都是有可能的,关键是这里体现出的思想,实际上就是缓冲区思想,这这个用户与数据的系统中,我们把用户看成了计算机中的CPU,用户从数据库中请求信息,直接从磁盘中请求,每次的速度恒定,但是可能很慢,如果加上了一个内存阵列,作为信息缓冲区,当用户查询一些常用信息的时候就会非常快,查询20%以外的时候,速度就和磁盘中的恒定时间一样,但总体上,用户体验提升了。总之,内存中的数据库就是为了提升20%数据的查询速度。同时内存的实际原则很符合哈希表存储密度低的特点,因为在内存中为了提升速度,本来就已经将存储单元划分的比较大了,这可能正和哈希表中链式结构的意,非常的相得益彰。

    展开全文
  • 【数据结构哈希表 详解

    千次阅读 2022-02-23 17:53:45
    哈希表 详解

    1. 概念 引入

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

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

    当向该结构中

    • 插入元素 :根据待插入元素的关键码,以此函数计算出该元素的存储位置并按此位置进行存放
    • 搜索元素:对元素的关键码进行同样的计算,把求得的函数值当做元素的存储位置,在结构中按此位置取元素比较,若关键码相等,则搜索成功

    该方式即为哈希(散列)方法,哈希方法中使用的转换函数称为哈希(散列)函数,构造出来的结构称为哈希表(HashTable)(或者称散列表)

    例如:数据集合{1,7,6,4,5,9};
    哈希函数设置为:hash(key) = key % capacity; capacity为存储元素底层空间总的大小。
    在这里插入图片描述
    用该方法进行搜索不必进行多次关键码的比较,因此搜索的速度比较快

    2. 冲突

    2.1 概念

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

    2.2 避免

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

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

    引起哈希冲突的一个原因可能是:哈希函数设计不够合理。 哈希函数设计原则:

    • 哈希函数的定义域必须包括需要存储的全部关键码,而如果散列表允许有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种不同的符号在各位上出现的频率不一定相同,可能在某些位上分布比较均匀,每种符号出现的机会均等,在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小,选择其中各种符号分布均匀的若干位作为散列地址。

    数字分析法通常适合处理关键字位数比较大的情况,如果事先知道关键字的分布且关键字的若干位分布较均匀的情况

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

    2.4 冲突-避免-负载因子调节(重点)

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

    2.5 冲突-解决

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

    2.5.1 闭散列

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

    寻找下一个空位置的方法 :

    1. 线性探测
      比如上面的场景,现在需要插入元素44,先通过哈希函数计算哈希地址,下标为4,因此44理论上应该插在该位置,但是该位置已经放了值为4的元素,即发生哈希冲突。

    线性探测:从发生冲突的位置开始,依次向后探测,直到寻找到下一个空位置为止。

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

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

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

    2.6 冲突-解决-开散列/哈希桶 (数组+链表)

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

    2.7 冲突严重时的解决办法

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

    1. 每个桶的背后是另一个哈希表
    2. 每个桶的背后是一棵搜索树

    3. key-val值假设都为int型的代码实现

    public class HashBuck {
        static class Node{
            public int key;
            public int val;
            public Node next;
    
            public Node(int key,int val){
                this.key=key;
                this.val=val;
            }
        }
    
        public Node[] array;
        public int usedSize;
    
        public static final double DEFAULT_LOAD_FACTOR=0.75;
    
        public HashBuck(){
            this.array=new Node[10];
        }
    
        /**
         * put函数
         * @param key
         * @param val
         */
        public void put(int key,int val){
            //1.找到key所在的位置
            int index=key%this.array.length;
            //2.遍历这个下标的链表,看是不是有相同的key 有 更新val值
            Node cur=array[index];
            while (cur!=null){
                if (cur.key==key){
                    cur.val=val;//更新val的值
                    return;
                }
                cur=cur.next;
            }
            //3.没有这个key的话,采用头插法插入
            Node node=new Node(key,val);
            node.next=array[index];
            array[index]=node;
            this.usedSize++;
            //4.插入元素成功后,检查当前散列表的负载因子
            if (loadFactor()>=DEFAULT_LOAD_FACTOR){
    
            }
    
        }
    
        private void resize(){
            Node[] newArray=new Node[array.length*2];
            //扩容之后所有的元素需要重新哈希
            for (int i = 0; i < array.length; i++) {
                Node cur=array[i];
                while (cur!=null){
                    int index=cur.key%newArray.length;//获取新的下标
                    //重新哈希:就是把cur这个节点,以头插/尾插的形式 插入到新的数组对应下标的链表当中
                    Node curNext=cur.next;
                    cur.next=newArray[index];//先绑定后面
                    newArray[index]=cur;//再绑定前面
                    cur=curNext;
                }
            }
            array=newArray;
        }
    
        private double loadFactor(){
            return 1.0*usedSize/array.length;
        }
    
        /**
         * get函数
         * 根据key获取val的值
         * @param key
         * @return
         */
        public int get(int key){
            //1.找到key所在的位置
            int index=key%this.array.length;
            //2.获取val
            Node cur=array[index];
            while (cur!=null){
                if (cur.key==key){
                    return cur.val;
                }
                cur=cur.next;
            }
            return -1;
        }
    }
    
    

    扩容前:
    在这里插入图片描述
    扩容后:(重新哈希后再放置元素 )
    在这里插入图片描述

    4. 性能分析

    虽然哈希表一直在和冲突做斗争,但在实际使用过程中,我们认为哈希表的冲突率是不高的,冲突个数是可控的,也就是每个桶中的链表的长度是一个常数,所以,通常意义下,我们认为哈希表的插入/删除/查找时间复杂度是
    O(1) 。

    5.与Java类集的关系(代码举列)

    1. HashMap 和 HashSet 即 java 中利用哈希表实现的 Map 和 Set
    2. java 中使用的是哈希桶方式解决冲突的
    3. java 会在冲突链表长度大于一定阈值后,将链表转变为搜索树(红黑树)
    4. java 中计算哈希值实际上是调用的类的 hashCode 方法,进行 key 的相等性比较是调用 key 的 equals 方法。所以如果要用自定义类作为 HashMap 的 key 或者 HashSet 的值,必须重写 hashCode 和 equals 方 法,而且要做到 equals 相等的对象,hashCode 一定是一致的;
    5. hashcode一样,equals不一定一样!
    6. equals一样,hashcode一定一样!

    代码举列如下:

    import java.util.HashMap;
    import java.util.Objects;
    
    /**
     * Created with IntelliJ IDEA.
     * User: 12629
     * Date: 2022/2/22
     * Time: 21:32
     * Description:
     */
    class Person { //自定义person类
        public String ID;
    
        public Person(String ID) {
            this.ID = ID;
        }
    
    
        @Override // 重写equals方法
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Person person = (Person) o;
            return Objects.equals(ID, person.ID);
        }
    
        @Override //重写hashcode方法
        public int hashCode() {
            return Objects.hash(ID);
        }
    
        @Override
        public String toString() {
            return "Person{" +
                    "ID='" + ID + '\'' +
                    '}';
        }
    }
    public class HashBuck2<K,V> {
    
        static class Node<K,V> {
            public K key;
            public V val;
            public Node<K,V> next;
    
            public Node(K key,V val) {
                this.val = val;
                this.key = key;
            }
        }
    
        public Node<K,V>[] array = (Node<K,V>[])new Node[10];
        public int usedSize;
    
        public void put(K key,V val) {
            int hash = key.hashCode();//转换为一个整数 
            int index = hash % array.length;
            Node<K,V> cur = array[index];
            while (cur != null) {
                if(cur.key.equals(key)) {
                    cur.val = val;//更新val值
                    return;
                }
                cur = cur.next;
            }
            Node<K,V> node = new Node<>(key, val);
            node.next = array[index];
            array[index] = node;
            this.usedSize++;
        }
    
        public V get(K key) {
            int hash = key.hashCode();//转换为一个整数 
            int index = hash % array.length;
            Node<K,V> cur = array[index];
            while (cur != null) {
                if(cur.key.equals(key)) {
                    //更新val值
                    return cur.val;
                }
                cur = cur.next;
            }
            return null;
        }
    
        public static void main(String[] args) {
            
            //我们认为 身份证ID一样的两个人是同一个人 
            //通过对hashcode和equals方法的重写 可以实现这一逻辑
            //重写hashcode之后,字符串类型的ID相同的话生成的整数就是相同的
            //实现了ID一样的两个人是同一人这一逻辑
            
            Person person1 = new Person("123");
            Person person2 = new Person("123");
    
            HashBuck2<Person,String> hashBuck2 = new HashBuck2<>();
            hashBuck2.put(person1,"love");
    
            System.out.println(hashBuck2.get(person2));
        }
    
        
    }
    

    因为person1和person2是同一个人
    所以get person2的val其实就是放入person1的love

    在这里插入图片描述

    • over
    展开全文
  • 数据结构学习笔记(5)——使用draw.io绘制的映射、哈希表和跳跃表图,详细绘制了映射、哈希表和跳跃表图,使用draw.io——免费开源的画图工具。
  • 本文为大家分享了C语言基于哈希表实现通讯录的具体代码,供大家参考,具体内容如下 1.需求分析 本演示程序用C语言编写,完成哈希表的生成,电话号码的插入、以及查找等功能。  (1)按提示输入相应的联系人的相关...
  • 这是我们数据结构哈希表的实验报告,是严格按照实验报告格式来的,自己做的,希望能帮到你
  • 数据结构 哈希表.ppt

    2020-08-03 05:01:37
    上章回顾 e常见的排序算法有哪些 e其中那种算法的效率最高 对大量的数据进行排序的化最好使用那种排 序算法 第七章 哈希泰 本章结构 什么哈希表 哈希表 哈希函数的构造方法 处理冲突的方法 课程目标 e了解什么是...
  • 在本篇文章里小编给大家分享了关于java数据结构和算法中哈希表的相关知识点内容,需要的朋友们学习下。
  • 数据结构哈希表实验

    2014-03-02 12:54:06
    哈希表的代码,可以用于数据结构试验交作业或者用于写实验报告
  • 哈希表实现通讯录

    2018-01-23 12:11:22
    (1)每个人的信息至少包括姓名,...(2)假设人名为汉语拼音全拼形式,待插入哈希表的长度为你所在班级的人数。哈希函数用除留余数法构造,采用链地址法或二次探测再散列法解决冲突。 (3)完成菜单设计。操作有必要的提示。
  • 代码如下:/* 数据结构C语言版 哈希表 */#include <stdio>#include <malloc>#define NULLKEY 0 // 0为无记录标志 #define N 10 // 数据元素个数 typedef int KeyType;// 设关键字域为整型 typedef struct{ Key...
  • 哈希表数据结构实现代码,符合ADT要求,头文件放ADT函数接口定义和存储结构定义,cpp文件放实现,在控制台查看输出,C语言实现,功能多,注释多,轻松易懂,可用来初学或者作业完成
  • 资源包括:源代码,可执行文件。 1.问题描述 设计散列表实现电话...6)输出相应的哈希表,计算平均查找长度; 7)设计一个菜单,上述操作要求都作为菜单中的主要菜单项。 3.测试数据 取所在班级的 n(n>=20)个同学记录。
  • 福 建 工 程 学 院 课 程 设 计 课程 题目 专业 班级 座号 姓名 算法与数据结构 哈希表 网络工程 xxxxxx 班 xxxxxxxxxxxx xxxxxxx 2011 年 12 月 31 日 实验题目哈希表 一 要解决的问题 针对同班同学信息设计一个...
  • 文件clear - 清除哈希表display - 显示一个哈希表对象元素 - 获取所有哈希表元素get - 从哈希表中获取数据hashtable - HashTable 类的构造函数isempty - 检查哈希值是否为空iskey - 检查散列当前是否正在使用密钥键 ...
  • 密钥存储在内存中的哈希表(Python字典)中。 每个键都映射到一个条目,该条目指示在一次搜索中可以在磁盘上找到该值的位置。 免责声明:不适用于生产。 在设计数据密集型应用程序的第3章中了解到该项目后,我出于...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 251,981
精华内容 100,792
关键字:

哈希表属于什么结构