精华内容
下载资源
问答
  • 数据结构——哈希
    千次阅读
    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%数据的查询速度。同时内存的实际原则很符合哈希表存储密度低的特点,因为在内存中为了提升速度,本来就已经将存储单元划分的比较大了,这可能正和哈希表中链式结构的意,非常的相得益彰。

    更多相关内容
  • Redis数据结构哈希

    2021-06-08 13:06:48
    本文来说下Redis数据结构哈希 文章目录概述 概述 大部分编程语言都提供了 哈希(hash)类型,它们的叫法可能是 哈希、字典、关联数组。在 Redis 中,哈希类型 是指键值本身又是一个 键值对结构。 哈希 形如 ...

    本文来说下Redis数据结构之哈希


    概述

    大部分编程语言都提供了 哈希(hash)类型,它们的叫法可能是 哈希、字典、关联数组。在 Redis 中,哈希类型 是指键值本身又是一个 键值对结构。

    在这里插入图片描述
    哈希 形如 value={ {field1,value1},…{fieldN,valueN} },Redis 键值对 和 哈希类型 二者的关系如图所示

    在这里插入图片描述

    哈希类型中的 映射关系 叫作 field-value,这里的 value 是指 field 对应的 值,不是 键 对应的值


    Redis hash结构命令

    官网 https://redis.io/commands#hash

    在这里插入图片描述


    相关命令

    基本命令

    设置值:hset key field value

    下面为 user:1 添加一对 field-value,如果设置成功会返回 1,反之会返回 0

    127.0.0.1:6379> hset user:1 name tom
    (integer) 1
    (1.89s)
    

    此外 Redis 提供了 hsetnx 命令,它们的关系就像 set 和 setnx 命令一样,只不过 作用域 由 键 变为 field。


    获取值:hget key field

    下面操作用于获取 user:1 的 name 域(属性) 对应的值

    127.0.0.1:6379> hget user:1 name
    "tom"
    

    如果 键 或 field 不存在,会返回 nil:

    127.0.0.1:6379> hget user:1 name
    "tom"
    127.0.0.1:6379> hget user:2 name
    (nil)
    127.0.0.1:6379> hget user:1 age
    (nil)
    127.0.0.1:6379>
    

    删除field:hdel key field [field …]

    hdel 会删除 一个或多个 field,返回结果为 成功删除 field 的个数,例如

    127.0.0.1:6379> hdel user:1 name
    (integer) 1
    127.0.0.1:6379> hdel user:1 age
    (integer) 0
    127.0.0.1:6379>
    

    计算field个数:hlen key

    例如键 user:1 有 3 个 field

    127.0.0.1:6379> hset user:1 name tom
    (integer) 1
    127.0.0.1:6379> hset user:1 age 24
    (integer) 1
    127.0.0.1:6379> hset user:1 city shanghai
    (integer) 1
    127.0.0.1:6379> hlen user:1
    (integer) 3
    127.0.0.1:6379>
    

    批量设置或获取field-value:hmget key field [field …] hmset key field value [field value …]

    hmset 和 hmget 分别是 批量设置 和 获取 field-value,hmset 需要的参数是 key 和 多对 field-value,hmget 需要的参数是 key 和 多个 field。例如:

    127.0.0.1:6379> hmset user:1 name tom age 12 city shanghai
    OK
    127.0.0.1:6379> hmget user:1 name city
    1) "tom"
    2) "shanghai"
    127.0.0.1:6379>
    

    判断field是否存在:hexists key field

    例如 user:1 包含 name 域,所以返回结果为 1,不包含时返回 0:

    127.0.0.1:6379> hexists user:1 name
    (integer) 1
    127.0.0.1:6379> hexists user:1 names
    (integer) 0
    127.0.0.1:6379>
    

    获取所有field:hkeys key

    hkeys 命令应该叫 hfields 更为恰当,它返回指定 哈希键 所有的 field,例如:

    127.0.0.1:6379> hkeys user:1
    1) "name"
    2) "age"
    3) "city"
    127.0.0.1:6379>
    

    获取所有value:hvals key

    下面操作获取 user:1 的全部 value:

    127.0.0.1:6379> hvals user:1
    1) "tom"
    2) "12"
    3) "shanghai"
    127.0.0.1:6379>
    

    获取所有的field-value:hgetall key

    下面操作获取 user:1 所有的 field-value:

    127.0.0.1:6379> hgetall user:1
    1) "name"
    2) "tom"
    3) "age"
    4) "12"
    5) "city"
    6) "shanghai"
    127.0.0.1:6379>
    

    在使用 hgetall 时,如果 哈希元素 个数比较多,会存在 阻塞 Redis 的可能。如果开发人员只需要获取 部分 field,可以使用 hmget,如果一定要获取 全部 field-value,可以使用 hscan 命令,该命令会 渐进式遍历 哈希类型。


    不常用命令

    键值自增:hincrby key field hincrbyfloat key field

    hincrby 和 hincrbyfloat,就像 incrby 和 incrbyfloat 命令一样,但是它们的 作用域 是 field。


    计算value的字符串长度:hstrlen key field

    例如 hget user:1 name 的 value 是 tom,那么 hstrlen 的返回结果是 3。

    127.0.0.1:6379> hstrlen user:1 name
    (integer) 3
    

    下面是 哈希类型命令 的 时间复杂度,开发人员可以参考此表选择适合的命令。

    在这里插入图片描述

    在这里插入图片描述


    内部编码

    哈希类型 的 内部编码 有两种

    ziplist(压缩列表)

    当 哈希类型 元素个数 小于 hash-max-ziplist-entries 配置(默认 512 个)、同时 所有值 都 小于 hash-max-ziplist-value 配置(默认 64 字节)时,Redis 会使用 ziplist 作为 哈希 的 内部实现,ziplist 使用更加 紧凑的结构 实现多个元素的 连续存储,所以在 节省内存 方面比 hashtable 更加优秀。


    hashtable(哈希表)

    当 哈希类型 无法满足 ziplist 的条件时,Redis 会使用 hashtable 作为 哈希 的 内部实现,因为此时 ziplist 的 读写效率 会下降,而 hashtable 的读写 时间复杂度 为 O(1)。

    下面的示例演示了 哈希类型 的 内部编码,以及相应的变化。

    当 field 个数 比较少,且没有大的 value 时,内部编码 为 ziplist

    127.0.0.1:6379> hmset hashkey f1 v1 f2 v2
    OK
    127.0.0.1:6379> object encoding hashkey
    "ziplist"
    

    当有 value 大于 64 字节时,内部编码 会由 ziplist 变为 hashtable

    127.0.0.1:6379> hset hashkey f3 "one string is bigger than 64 byte...忽略..."
    OK
    127.0.0.1:6379> object encoding hashkey
    "hashtable"
    
    

    当 field 个数 超过 512,内部编码 也会由 ziplist 变为 hashtable

    127.0.0.1:6379> hmset hashkey f1 v1 f2 v2 f3 v3 ... f513 v513
    OK
    127.0.0.1:6379> object encoding hashkey
    "hashtable"
    

    适用场景

    如图所示,为 关系型数据表 的两条 用户信息,用户的属性作为表的列,每条用户信息作为行。

    在这里插入图片描述
    使用 Redis 哈希结构 存储 用户信息 的示意图如下

    在这里插入图片描述
    相比于使用 字符串序列化 缓存 用户信息,哈希类型 变得更加 直观,并且在 更新操作 上会 更加便捷。可以将每个用户的 id 定义为 键后缀,多对 field-value 对应每个用户的 属性,类似如下伪代码:

    public UserInfo getUserInfo(long id) {
        // 用户id作为key后缀
        String userRedisKey = "user:info:" + id;
        // 使用hgetall获取所有用户信息映射关系
        Object userInfoMap = redis.hgetAll(userRedisKey);
        UserInfo userInfo;
        if (userInfoMap != null) {
            // 将映射关系转换为UserInfo
            userInfo = transferMapToUserInfo(userInfoMap);
        } else {
            // 从MySQL中获取用户信息
            userInfo = mysql.get(id);
            // 将userInfo变为映射关系使用hmset保存到Redis中
            redis.hmset(userRedisKey, transferUserInfoToMap(userInfo));
            // 添加过期时间
            redis.expire(userRedisKey, 3600);
        }
        return userInfo;
    }
    
    

    哈希结构与关系型表

    需要注意的是 哈希类型 和 关系型数据库 有两点不同之处

    哈希类型 是 稀疏的,而 关系型数据库 是 完全结构化的,例如 哈希类型 每个 键 可以有不同的 field,而 关系型数据库 一旦添加新的 列,所有行 都要为其 设置值(即使为 NULL),如图所示:

    在这里插入图片描述
    关系型数据库 可以做复杂的 关系查询,而使用 Redis 去模拟关系型复杂查询 开发困难,维护成本高。


    几种缓存方式

    到目前为止,我们已经能够用 三种方法 缓存 用户信息,下面给出三种方案的 实现方法 和 优缺点分析。

    原生字符串类型

    给用户信息的每一个属性分配 一个键

    set user:1:name tom
    set user:1:age 23
    set user:1:city beijing
    
    • 优点:简单直观,每个属性都支持 更新操作。
    • 缺点:占用 过多的键,内存占用量 较大,同时用户信息 内聚性比较差,所以此种方案一般不会在生产环境使用。

    序列化字符串类型

    将用户信息 序列化 后用 一个键 保存

    set user:1 serialize(userInfo)
    
    • 优点:简化编程,如果合理的使用 序列化 可以 提高内存利用率。
    • 缺点:序列化 和 反序列化 有一定的开销,同时每次 更新属性 都需要把 全部数据 取出进行 反序列化,更新后 再 序列化 到 Redis 中。

    哈希类型

    每个用户属性使用 一对 field-value,但是只用 一个键 保存

    hmset user:1 name tom age 23 city beijing

    • 优点:简单直观,如果使用合理可以 减少内存空间 的使用。
    • 缺点:要控制和减少 哈希 在 ziplist 和 hashtable 两种 内部编码 的 转换,hashtable 会消耗 更多内存。

    本文参考

    《Redis 开发与运维》


    本文小结

    本文介绍了 Redis 中的 哈希结构 的 一些 基本命令、内部编码 和 适用场景。最后对比了 关系型表 和 哈希结构 的区别,以及几种 存储方式 的优缺点。

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

    千次阅读 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
    展开全文
  • 底层结构2.1哈希概念2.2哈希函数2.3常见哈希函数2.4 哈希冲突3.闭散列(开放定址法)3.1线性探测3.2闭散列扩容-载荷因子3.3二次探测4.开散列4.1开散列增容 1.unordered_map/unordered_set unordered_map是存储<...

    1.unordered_map/unordered_set

    1. unordered_map是存储<key, value>键值对的关联式容器,其允许通过keys快速的索引到与其对应的value。
    2. 在unordered_map中,键值通常用于惟一地标识元素,而映射值是一个对象,其内容与此键关联。键和映射值的类型可能不同。
    3. 在内部,unordered_map没有对<kye, value>按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value,unordered_map将相同哈希值的键值对放在相同的桶中。
    4. unordered_map容器通过key访问单个元素要比map快,但它通常在遍历元素子集的范围迭代方面效率较低。

    unordered_map的元素访问:
    在这里插入图片描述

    2. 底层结构

    unordered系列的关联式容器之所以效率比较高,是因为其底层使用了哈希结构

    2.1哈希概念

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

    当向该结构中插入元素:根据待插入元素的关键码,以 函数(hashFunc) 计算出该元素的存储位置并按此位置进行存放。

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

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

    在这里插入图片描述

    2.3常见哈希函数

    1.直接定址法–(常用):

    • 取关键字的某个线性函数为散列地址:Hash(Key)= A*Key + B ;
      优点:简单、高效 ;
      缺点:需要事先知道关键字的分布情况 ;

    使用场景:适合查找比较小且连续的情况,比如:第一次出现的字符:构建一个数组hash[ch-‘a’] 来映射位置;
    不适用场景:数据分散,数据元素不连续,很容易造成空间浪费,比如 :一组数据最小的为1,最大的到了99999999;

    2.除留余数法(常用)

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

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

    2.4 哈希冲突

    • 不同关键字通过相同哈希哈数计算出相同的哈希地址,该种现象称为哈希冲突或哈希碰撞

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

    3.闭散列(开放定址法)

    当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以把key存放到冲突位置中的“下一个” 空位置中去。寻找下一个空位置的方法有线性探测法和二次探测法

    3.1线性探测

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

    • 插入:通过哈希函数获取待插入元素在哈希表中的位置
      在这里插入图片描述

    删除:

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

    线性探测的缺点:空间踩踏

    3.2闭散列扩容-载荷因子

    在这里插入图片描述

    3.3二次探测

    在这里插入图片描述
    在这里插入图片描述
    因此:闭散列最大的缺陷就是空间利用率比较低,这也是哈希的缺陷;

    4.开散列

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

    4.1开散列增容

    开散列最好的情况是:每个哈希桶中刚好挂一个节点,再继续插入元素时,每一次都会发生哈希冲突,因此,在元素个数刚好等于桶的个数时,可以给哈希表增容;

    • 载荷因子为1进行扩容;

    优点:
    - 不同位置冲突时,不再互相干扰,载荷因子一般控制在1

    缺点:
    - 迭代器遍历输出的时候,不是有序输出的;

    在这里插入图片描述

    如果所有的数据都冲突到一个桶下面了,怎么办?

    1.桶下面挂红黑树:极限也是logN的时间复杂度,但是也只是这一会而已,当增容的时候,这种现象就会缓解;
    2.多阶哈希

    展开全文
  • Java 哈希数据结构

    2021-04-03 18:11:34
    哈希表结合在一起,发挥他们的优点 哈希表底层源代码 public class HashMap{ HashMap底层实际是一个数组 Node<K,V>[] table 静态内部类HashMap.Node static calsss Node<K,V>{
  • 数据结构哈希

    2021-05-21 09:56:33
    我们在这篇文章将要学习最有用的数据结构之一—哈希表,哈希表的英文叫 Hash Table,也可以称为散列表或者 Hash 表。 哈希表用的是数组支持按照下标随机访问数据的特性,所以哈希表其实就是数组的一种扩展,由数组...
  • JAVA数据结构哈希

    千次阅读 2018-09-02 10:50:21
    但是在有该优点的情况下,需要考虑哈希冲突 本例结构中采用链地址法【在hash表的每一个表单元,都是链表结构,发生冲突的元素,自动加入链表】 在jdk8以前采用的是链表解决,在jdk8之后,在处理哈希冲突时,...
  • 1实验目的 1) 复习顺序查找二分查找分块查找的基本算法及适用场合 2) 掌握哈希查找的基本方法及适用场合并能在解决实际问题时灵活应用 3) 巩固在散列查找时解决冲突的方法及特点 2实验内容 1) 哈希表查找的实现用...
  • 数据结构 哈希查找

    2021-09-18 00:07:36
    哈希查找1. DS哈希查找--链地址法题目...给出一个数据序列,建立哈希表,采用求余法作为哈希函数,模数为11,哈希冲突用链地址法和表头插入 如果首次查找失败,就把数据插入到相应的位置中 实现哈希查找功能 输入 第
  • 哈希1. 哈希概念2. 哈希函数3. 哈希冲突3.1 闭散列3.1.1 闭散列模拟实现3.2 开散列3.2.1 开散列模拟实现4. 基于开散列实现unordered_set5. 基于开散列实现unordered_map6. 闭散列和开散列对比7. 哈希的应用7.1 位图 ...
  • ## 数据结构之链式哈希哈希表(Hash table,散列表),由多组键-值组成一张查询表,通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。 哈希表中元素是由哈希函数确定的。将数据元素的关键字K作为自...
  • 文章目录一、哈希表1.哈希表概念2.冲突的概念3.避免冲突与解决冲突3.1 避免冲突的方式1——哈希函数的设计3.2 避免冲突的方式2——负载因子的调节3.3 解决冲突的方式1——闭散列3.4 解决冲突的方式2——开散列、哈希...
  • =n)的连续内存单元,以每个元素的关键字k为自变量,通过哈希函数把k映射为内存单元的地址(下标),并把该元素存储在这个内存单元中,如此构造的存储结构称为哈希表 8.2哈希表的特点 基于数组实现,速度比树快,...
  • 【Java数据结构哈希表详解

    千次阅读 2021-12-30 09:27:43
    哈希表详解
  • 数据结构与算法(哈希表) 哈希函数:在记录的关键字与记录的存储地址之间建立的一 种对应关系叫哈希函数。 哈希函数是一种映象,是从关键字空间到存储地址空间的一 种映象。可写成:addressi=H(keyi) ,其中i是表中...
  • 顺序查找 二分查找 索引查找 哈希查找【数据结构与算法】
  • MySQL哈希索引的数据结构以及索引的优缺点

    千次阅读 多人点赞 2021-08-03 11:27:39
    MySQL哈希索引结构的实现,以及索引的优缺点。
  • 数据结构与算法(七)-哈希表(HashTable)

    千次阅读 2022-01-11 17:04:47
    1. 哈希表的优点 哈希表可以提供非常快速的插入-删除-查找操作; 无论多少数据,插入和删除值都只需要非常短的时间,即O(1)的时间级。实际上,只需要几个机器指令即可完成; 哈希表的速度比树还要快,基本可以瞬
  • JS实现常见数据结构哈希

    千次阅读 2019-10-19 17:17:08
    哈希特点:存储键值对的数据结构哈希表内部是使用一个hash函数把传入的键转换成一串数字,而这串数字将作为键值对实际的key,通过这个key查询对应的value非常快。 哈希表方法: 1. add:添加一组键值对。 2. ...
  • 将任意长度的二进制值串映射成固定长度的二进制值串,这个映射的规则就是哈希算法,而通过原始数据映射之后得到的二进制值串就是哈希值。 2.如何设计一个优秀的哈希算法? ①单向哈希: 从哈希值不能反向推导出哈希...
  • 哈希表的特点 哈希表通常是基于数组进行实现的 优点 提供非常快速的插入-删除-查找操作 无论数据多少,插入和删除的效率都非常高(即 O(1)的时间级) 哈希表的速度比树快,几乎瞬间可找到 代码相对树简单 缺点 ...
  • 哈希表的介绍
  • C++哈希结构

    2021-07-19 15:32:48
    C++哈希结构分类 数组 set map set和map的特点如下所示 哈希结构 底层实现方式 set 红黑树 multiset 红黑树 map 红黑树 multimap 红黑树 unordered_set 哈希表 unordered_map 哈希表 底层以...
  • 参考书籍:大话数据结构 一、Hash表定义 在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使得每个关键字key对应一个存储位置。查找的时候,根据这个确定的对应关系找到给定值key的映射f(key)。 类似于...
  • JS 数据结构哈希

    2020-08-17 15:38:09
    哈希结构就是数组,但是不同的地方是,对下标值的一种变换,这种变换被称为哈希函数,通过哈希函数可以获取到 HashCode 。 哈希表和数组相比有什么优点哈希表通常是基于数组进行实现的,但是相对于数组,它...
  • 数据结构复习-哈希

    2022-02-20 16:47:41
    一:什么是哈希表 二:构造哈希函数的方法 三:处理冲突的方法

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 121,802
精华内容 48,720
关键字:

哈希数据结构的优点

数据结构 订阅