当前位置: 首页 > article >正文

【java数据结构】哈希表

【java数据结构】哈希表

  • 一、概念
  • 二、哈希函数
  • 三、冲突
      • 3.1 概念
      • 3.2 冲突避免
        • 3.2.1 冲突避免-设计哈希函数
        • 3.2.1 冲突避免-负载因子调节
      • 3.2 解决冲突
        • 3.2.1 解决冲突-闭散列
        • 3.2.2 解决冲突-开散列/哈希桶
          • 哈希桶代码实现

博客最后附有整篇博客的全部代码!!!

一、概念

哈希表(Hash Table)是一种基于哈希函数实现的数据结构,用于存储键值对(Key-Value Pair)。它通过哈希函数将键(Key)映射到一个特定的存储位置,从而实现快速的数据查找、插入和删除操作。
HashMap的操作时间复杂度O(1),相比于TreeMap(操作时间复杂度O(logN))我们会更加偏向使用HashMap。

二、哈希函数

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

例如:这里有一组数据集合{1,7,6,4,5,9}
在这里插入图片描述

但是如果再向集合中存储元素44,那么此时应该怎么存储?

三、冲突

3.1 概念

对于两个数据元素的关键字 和 (i != j),有 != ,但有:Hash( ) == Hash( ),即:不同关键字通过相同哈希哈数计算出相同的哈希地址,该种现象称为哈希冲突或哈希碰撞。根据上述,我们发现再向集合中存储元素大小为44时,此时数组小标为4 的位置已经有元素,我们将这个就叫做冲突。

3.2 冲突避免

首先,我们明确,哈希存储的底层数组大小往往小于实际存储数据的大小,这就导致一个问题,冲突的发生是必然的,但我们能做的应该是尽量的避免冲突。

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

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

  • 哈希函数的定义域必须包括需要存储的全部关键码,而如果散列表允许有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种不同的符号在各位上出现的频率不一定相同,可能在某些位上分布比较均匀,每种符号出现的机会均等,在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小,选择其中各种符号分布均匀的若干位作为散列地址。
    注意:哈希函数设计的越精妙,产生哈希冲突的可能性就越低,但是无法避免哈希冲突
3.2.1 冲突避免-负载因子调节

概念:负载因子(Load Factor)是哈希表(如HashMap、Hashtable等)的一个重要参数,用于控制哈希表的扩容时机,从而在性能和内存使用之间取得平衡。

定义:负载因子是哈希表中元素数量与哈希表容量(桶的数量)之间的比例关系,计算公式为:
负载因子=当前元素个数 / 哈希表容量

负载因子和冲突率的关系粗略演示:
在这里插入图片描述
这里发现负载因子越大冲突率就越大,所以这里我们需要降低负载因子的大小,从而使冲突率降低。
负载因子是由当前元素个数和哈希表容量控制的,但我们不能控制当前元素个数,所以我们一般控制哈希表容量。在java系统库中,我们规定负载因子大小为0.75,当负载因子超过0.75,我们就会扩大哈希表容量。

3.2 解决冲突

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

3.2.1 解决冲突-闭散列

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

  1. 线性探测
    线性探测:从发生冲突的位置开始,依次向后探测,直到寻找到下一个空位置为止。
    在这里插入图片描述
    采用闭散列处理哈希冲突时,不能随便物理删除哈希表中已有的元素,若直接删除元素会影响其他元素的搜索。比如删除元素4,如果直接删除掉,44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。
    伪删除法
  1. 标记状态:
    • EMPTY:表示该位置为空,可以插入新元素。
    • EXIST:表示该位置有元素。
    • DELETE:表示该位置的元素已被逻辑删除。
  2. 插入操作:
    • 计算哈希值,找到初始位置。
    • 如果该位置为空(EMPTY)或已被删除(DELETE),则可以插入新元素。
    • 如果该位置已被占用(EXIST),则通过线性探测找到下一个空位置
  3. 查找操作:
    • 计算哈希值,从初始位置开始查找。
    • 如果遇到标记为EXIST的元素,比较键值是否匹配。
    • 如果遇到标记为DELETE的位置,继续向后查找,直到遇到EMPTY为止。
  4. 删除操作:
    • 计算哈希值,找到目标元素。
    • 将目标元素的状态标记为DELETE,而不是直接物理删除。
  1. 二次探测
    线性探测的缺陷是产生冲突的数据堆积在一块,这与其找下一个空位置有关系,因为找空位置的方式就是挨着往后逐个去找,因此二次探测为了避免该问题,找下一个空位置的方法为: H= (H0 +i^2 )% m, 或者:H= ( H0-i^2 )% m。其中:i = 1,2,3…, 是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置,m是表的大小。
    在这里插入图片描述
    闭散列最大的缺陷就是空间利用率比较低,这也是哈希的缺陷。
3.2.2 解决冲突-开散列/哈希桶

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

在这里插入图片描述

哈希桶代码实现
  1. 基本类型的哈希桶
    static class Node{
        int key;
        int value;
        Node next;

        public Node(int key, int value){
            this.key = key;
            this.value = value;
        }
    }
    public Node[] array=new Node[10];
    public int useSized;
    private static final double LOAD_FACTOR=0.75;
    public void put(int key, int value){
        //1.先获取插入元素的下标
        int index=key% array.length;
        Node cur=array[index];
        //2.判断集合中是否已经包含key
        while(cur!=null){
            if(cur.key==key){
                cur.value=value;
            }
            cur=cur.next;
        }
        //3.插入key
        Node newNode=new Node(key,value);
        newNode.next=array[index];
        array[index]=newNode;
        useSized++;
        //4.判断是否需要扩容
        if(Do_LOAD_FACTOR()>=LOAD_FACTOR){
            resize();
        }
    }

    private void resize() {
        //5.因为数组容量扩大,所以需要重新遍历一遍原来的数组
        Node[] newArray=new Node[array.length*2];
        for(int i=0;i<array.length;i++){
            Node cur=array[i];
            while(cur!=null){
                Node curN=cur.next;
                int index=cur.key% newArray.length;
                cur.next=newArray[index];
                newArray[index]=cur;
                cur=curN;
            }
        }
        array=newArray;
    }

    private double  Do_LOAD_FACTOR(){
        return useSized*1.0 /array.length;
    }

    public int getValue(int key){
        int index=key% array.length;
        Node cur=array[index];
        while(cur!=null){
            if(cur.key==key){
                return cur.value;
            }
            cur=cur.next;
        }
        return -1;
    }
  1. 引用类型的哈希桶
class Person{
    String name;
    public Person(String name){
        this.name = name;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person preson = (Person) o;
        return Objects.equals(name, preson.name);
    }

    @Override
    public int hashCode() {
        return Objects.hashCode(name);
    }
}
public class RTHashbucket<K,V> {
    static class Node<K,V>{
        K key;
        V value;
        Node<K,V> next;

        public Node(K key, V value){
            this.key = key;
            this.value = value;
        }
    }
    public Node<K,V>[] array=(Node<K, V>[])new Node[10];
    public int useSized;
    private static final double LOAD_FACTOR=0.75;

    public void put(K key, V value){
        int hash = key.hashCode();
        int index = hash % array.length;
        Node<K,V> cur=array[index];
        while(cur!=null){
            if(cur.key.equals(key)){
                cur.value=value;
            }
            cur=cur.next;
        }
        Node<K,V> newNode=new Node<>(key, value);
        newNode.next=array[index];
        array[index]=newNode;
        useSized++;
        if(Do_LOAD_FACTOR()>=LOAD_FACTOR){
            resize();
        }
    }

    private void resize() {
        Node<K,V>[] newArray=(Node<K, V>[]) new Node[2* array.length];
        for(int i=0;i<array.length;i++){
            Node<K,V> cur=array[i];
            while(cur!=null){
                Node<K,V> curN=cur.next;
                int hash = cur.key.hashCode();
                int index = hash % newArray.length;
                cur.next=newArray[index];
                newArray[index]=cur;
                cur=curN;
            }
        }
        array=newArray;
    }

    private double Do_LOAD_FACTOR() {
        return useSized*1.0/array.length;
    }
    public V getValue(K key){
        int hash = key.hashCode();
        int index = hash % array.length;
        Node<K,V> cur=array[index];
        while(cur!=null){
            if(cur.key==key){
                return cur.value;
            }
            cur=cur.next;
        }
        return null;
    }
}

在引用类型的哈希桶代码实现,有个非常重要的方法:hashCode()方法

作用:

  1. hashCode()方法是将对象的内存地址或其他特征转换为一个整数值,从而让我们得到数组下标。
  2. 对象的比较:如果两个对象的哈希码不同,那么它们一定不相等;如果哈希码相同,还需要进一步调用 equals() 方法来确认对象是否相等。

注意:如果要用自定义类作为 HashMap 的 key 或者 HashSet 的值,必须覆写 hashCode 和 equals 方法,而且要做到 equals 相等的对象,hashCode 一定是一致的。

此篇博客的全部代码!!!


http://www.kler.cn/a/521082.html

相关文章:

  • FileReader使用
  • vue中的el是指什么
  • 速通Docker === Docker Compose
  • Apache Flink 概述学习笔记
  • Java 注解与元数据
  • Linux初识——基本指令(2)
  • 2025年美赛数学建模F题 为农业再培养腾出空间
  • 葡萄果品分级以及葡萄簇识别-目标检测数据集
  • SOAFEE 技术研讨会:汽车软件定义与自动驾驶技术探讨
  • arduino学习
  • Kotlin单例类
  • LeetCode - Google 校招100题 第9天 Hard 题汇总 (12题)
  • 2025年数学建模美赛 A题分析(4)楼梯使用人数模型
  • Vuex 的核心概念:State, Mutations, Actions, Getters
  • 提供一种刷新X410内部EMMC存储器的方法
  • 【AI论文】Sigma:对查询、键和值进行差分缩放,以实现高效语言模型
  • AndroidStudio 下载链接
  • Blazor-@typeparam
  • C++资料
  • 序列标注:从传统到现代,NLP中的标签预测技术全解析
  • dev c++ ‘unordered_set‘ does not name a type
  • 工业数据分析:解锁工厂数字化的潜力
  • Pyecharts之饼图与多饼图的应用
  • .NET 8 项目 Docker 方式部署到 Linux 系统详细操作步骤
  • 蓝桥杯第十二届省赛真题
  • MongoDB中单对象大小超16M的存储方案