哈希表超详解

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

目录

哈希表

概念

冲突-概念

冲突-避免

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

冲突-避免-负载因子的调节

冲突-解决-闭散列

冲突-解决-开散列

哈希桶的实现

 性能分析

java和类集的关系


哈希表

概念

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

因此我们就会想,有没有一种理想的方法,可以不经过任何比较,一次从表中得到要搜索的元素那么就可以构造某种函数,使该元素的存储位置与关键码之间存在映射关系,(即key->通过某种方法->一次定位到key的位置),那么这种通过函数的方式就很容易找到元素

当向该结构中:

插入元素

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

搜索元素

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

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

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

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

存储情况如下:

哈希表超详解,散列表,数据结构,算法

用该方法进行搜索不必进行多次关键码的比较,因此搜索的速度比较快。而此时又衍生出来了一个问题,万一两个关键码通过函数计算的存放位置相同,该怎么办?这就涉及到了冲突。

冲突-概念

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

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

冲突-避免

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

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

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

1.哈希函数的定义域必须包括需要存储的全部关键码,而如果散列表允许有m个地址时,其值域必须在0到m-1之间。

2.哈希函数计算出来的地址能均匀分布在整个空间中

3.哈希函数应该比较简单

常见哈希函数(常用)

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

2.除留余数法:设散列表允许的地址数为m,取一个不大于m,但最接近或者等于m的质数p

作为除数,按照哈希函数: Hash(key) = key% p(p<=m), 将关键码转换成哈希地址
注意:哈希函数设计的越精妙,产生哈希冲突的可能性就越低,但是无法避免哈希冲突

冲突-避免-负载因子的调节

散列表的载荷因子定义为 : a = 填入表中元素个数 / 散列表的长度

注:由于散列表长度是定值,所以填入表中的元素个数越多,产生冲突的可能性就越大。

对于开放定址法,荷载因子是特别重要的因素,应该严格限制在0.7-0.8以下,超过0.8,查表时CPU缓存不命中按照指数直线上升。因此,一些采用开放定址法的hash库,如Java系统库限制了荷载因子为0.75,如果超过荷载因子的话将对散列表进行扩容。

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

哈希表超详解,散列表,数据结构,算法

所以当冲突率达到一个无法忍受的程度时,我们需要通过降低负载因子来降低冲突率。

已知哈希表中已有关键字个数是不可变的,那么我们只能调整哈希表中数组的大小。

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

冲突-解决-闭散列

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

1.线性探测

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

线性探测:从发生冲突的位置开始,依次向后探测,直到寻找到下一个空位置为止。
插入
通过哈希函数获取待插入元素在哈希表中的位置
如果该位置中没有元素则直接插入新元素,如果该位置中有元素发生哈希冲突,使用线性探测找到下一个空位置,插入新元素

哈希表超详解,散列表,数据结构,算法 

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

2.二次探测

线性探测的缺陷是产生的数据堆积在一块(导致不能均匀分布在空间中),这与其找下一个空位置有关系,因为找空位置的方式就是挨个往后逐个去找 ,因此二次探测为了避免该问题,找下一个空位置的方法为:Hi = (H0 + i ^ 2) % m.H0为应该放置的位置,m为冲突次数,m为表的大小。

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

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

冲突-解决-开散列

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

方法如图所示:

哈希表超详解,散列表,数据结构,算法

从上图可以看出,开散列中每个桶中放的都是发生哈希冲突的元素。

开散列,可以认为是把一个大集合中的搜索问题转化为在小集合中搜索了。

哈希桶的实现

 下面是基于key-value模型写的哈希桶部分方法的代码:

//key-value模型
public class HashBucket {
    private static class Node {
        private int key;
        private int value;
        Node next;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    //用数组表示哈希表
    private Node[] array;
    //当前哈希表元素个数
    private int size;
    //定义荷载因子
    private static final double LOAD_FACTOR = 0.75;

    public int put(int key, int value) {
        //根据哈希函数确定存放的下标
        int index = key % array.length;

        //在链表中查找key所在的结点
        //如果找到了,更新
        //所有节点都不是key,插入一个新的结点
        for (Node cur = array[index]; cur != null; cur = cur.next) {
            if(key == cur.key) {
                int oldValue = cur.value;
                cur.value = value;
                //返回更新前key对应的value
                return oldValue;
            }
        }
        //链表遍历完成,没有找到这个key
        Node node = new Node(key, value);
        node.next = array[index];
        array[index] = node;
        size++;

        if(loadFactor() >= LOAD_FACTOR) {
            resize();
        }
        return -1;
    }

    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) {
               //利用tmp记录cur的位置
               Node tmp = cur.next;
               //计算元素在新数组中的位置
               int newIndex = cur.key % newArray.length;
               //头插法
               cur.next = newArray[newIndex];
               newArray[newIndex] = cur;
               //回溯cur的位置
               cur = tmp;
           }
       }
        //将新数组赋值给原数组
        array = newArray;
    }

    //计算当前荷载因子的大小
    private double loadFactor() {
        return size * 1.0 / array.length;
    }

    public HashBucket() {
        array = new Node[8];
        size = 0;
    }

    //get方法
    public int get(int key) {
        int index = key % array.length;

        Node head = array[index];
        Node cur = head;
        while(cur != null) {
            if(key == cur.key) {
                return cur.value;
            }
            cur = cur.next;
        }

        //未找到,则返回-1
        return -1;
    }
}

 性能分析

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

java和类集的关系

1.HashMap和HashSet即java中利用哈希表实现的Map和Set

2.java中使用的是哈希桶的方式解决冲突的

3.java会在冲突链表长度大于一定阈值后,将链表转变为二叉搜索树(红黑树)

4.java中计算哈希值实际上是调用的类的hashCode方法,进行key的相等性比较是调用key的equals方法。所以如果要用自定义类作为HashMap的key或者HashSet的值,必须覆写hashCode和equals方法,而且要做到equals相等的对象,hashCode一定是一致的文章来源地址https://www.toymoban.com/news/detail-722589.html

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

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

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

相关文章

  • Java学数据结构(4)——散列表Hash table & 散列函数 & 哈希冲突

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

    2024年02月10日
    浏览(52)
  • 一篇就能学懂的散列表,让哈希表数据结构大放光彩

    目录 1.散列表的基本概念 2.散列表的查找 3.散列函数的构造方法 1.直接定址法 2.除留余数法 4.散列表解决冲突的方法 1.开放定址法 2.链地址法 基本思想 :记录的存储位置与之间存在的对应关系 对应关系——hash函数 Loc(i) = H(keyi) Hash:哈希——翻译为:散列、杂凑(感

    2024年02月09日
    浏览(52)
  • 【高阶数据结构】哈希表详解

    上一篇文章我们学习了STL中unordered系列容器的使用,并且提到,unordered系列容器的效率之所以比较高(尤其是查找),是因为它底层使用了哈希结构,即哈希表。 那这篇文章,我们就来学习一下哈希表 顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,

    2024年02月11日
    浏览(36)
  • 【数据结构与算法】前缀和+哈希表算法

    关于前缀和和哈希这两个概念大家都不陌生,在之前的文章中也有过介绍:前缀和与差分算法详解 而哈希表最经典的一题莫过于 两数之和 题目链接 题目描述: 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它

    2024年02月01日
    浏览(110)
  • 【数据结构】——单链表超详细介绍(小白必看!!!)

     c语言中的小小白-CSDN博客 c语言中的小小白关注算法,c++,c语言,贪心算法,链表,mysql,动态规划,后端,线性回归,数据结构,排序算法领域. https://blog.csdn.net/bhbcdxb123?spm=1001.2014.3001.5343 给大家分享一句我很喜欢我话: 知不足而奋进,望远山而前行!!! 铁铁们,成功的路上必然是孤

    2024年04月11日
    浏览(60)
  • 【数据结构】哈希表(算法比赛向)

    目录 一:介绍 一:什么是哈希表 二、哈希表的应用 二:存储结构 a.拉链法: b.开放寻址法: 三:扩展 a.字符串哈希: 例题:      一:什么是哈希表 1、哈希表也叫散列表,哈希表是一种数据结构,它提供了快速的插入操作和查找操作,无论哈希表总中有多少条数据,插

    2023年04月25日
    浏览(46)
  • 数据结构,查找算法(二分,分块,哈希)

    一、查找算法         1、二分查找:(前提条件: 必须有序的序列) 2、分块查找:(块间有序,块内无序)     索引表  +  源数据表     思路:     (1)先在索引表中确定在哪一块中     (2)再遍历这一块进行查找 //索引表 typedef  struct  {     int max; //块中最大值

    2024年02月11日
    浏览(56)
  • 【数据结构与算法】哈希—— 位图 | 布隆过滤器 | 哈希切割

    🐱作者:一只大喵咪1201 🐱专栏:《数据结构与算法》 🔥格言: 你只管努力,剩下的交给时间! 哈希是一种映射思想,这里再讲解两种应用哈希思想的数据结构。 问题: 给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数

    2024年02月02日
    浏览(54)
  • C++数据结构与算法——哈希表

    C++第二阶段——数据结构和算法,之前学过一点点数据结构,当时是基于Python来学习的,现在基于C++查漏补缺,尤其是树的部分。这一部分计划一个月,主要利用代码随想录来学习,刷题使用力扣网站,不定时更新,欢迎关注! 给定两个字符串 s 和 t ,编写一个函数来判断

    2024年02月19日
    浏览(56)
  • 【数据结构与算法——TypeScript】哈希表

    哈希表介绍和特性 哈希表是一种非常重要的数据结构,但是很多学习编程的人一直搞不懂哈希表到底是如何实现的。 在这一章节中,我门就一点点来实现一个自己的哈希表。 通过实现来理解哈希表背后的原理和它的优势。 几乎所有的编程语言都有直接或者间接的应用这种数

    2024年02月13日
    浏览(40)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包