Hash碰撞

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

Hash碰撞

什么是Hash碰撞

Hash碰撞是指两个不同的输入值,经过哈希函数的处理后,得到相同的输出值,这种情况被称之为哈希碰撞。

  • 例如:两个不同的对象(object1和object2的值)经过Hash函数计算后的,得到的hash值相同,object2应放到object1的位置,但是存储桶中的位置已经被object1占用了,导致冲突

为什么会发生Hash碰撞

哈希表是一种数据结构,它使用哈希函数将键映射到存储桶中。哈希函数将键转换为索引,这个索引指向哈希表中的一个桶。哈希表的目的是提供一种快速的查找方法,它可以在较快的时间内查找一个键。

当然,这需要一个好的哈希函数,它可以将键均匀地分布在哈希表中。如果哈希函数不好,就会出现哈希碰撞,这会导致性能下降。

Hash碰撞

解决Hash碰撞

在这种情况下,我们可以使用链式哈希表来解决哈希碰撞的问题。链式哈希表是一种将哈希值相同的元素存储在同一个链表中的哈希表。当发生哈希碰撞时,我们只需要将新元素添加到对应的链表中即可。这样可以保证哈希表的性能和正确性。

package com.sin.demo;

import java.util.LinkedList;

/**
 * @CreateName SIN
 * @CreateDate 2023/05/11 11:04
 * @description 链式哈希表,用来解决hash碰撞的问题。
 *              具体实现:将hash值相同的元素存储在同一个链表中,当发生hash碰撞时,
 *                      只需要将新的元素添加到对应的链表中即可,这样可以保证hash表的新能和正确性
 */
public class ChainedHashTable<K, V> {

    //声明一个链表数组
    private LinkedList<Entry<K, V>>[] table;
    //记录长度
    private int size;

    /**
     * 构造方法
     * @param capacity 传入hash表容量
     */
    public ChainedHashTable(int capacity) {
        //初始化链表数组长度
        table = new LinkedList[capacity];
        //初始长度为0
        size = 0;
    }

    /**
     * 添加元素
     * @param key 键
     * @param value 值
     */
    public void put(K key, V value) {
        //计算哈希值
        int index = hash(key);
        //如果当前索引位置为null
        if (table[index] == null) {
            //创建一个新的链表在当前索引
            table[index] = new LinkedList<>();
        }
        // 遍历当前索引的链表
        for (Entry<K, V> entry : table[index]) {
            //判断链表中是否有这个key键,
            if (entry.getKey().equals(key)) {
                //如果有则更新对应的value值
                entry.setValue(value);
                //直接返回
                return;
            }
        }
        //如果不存在将新的元素(键值对)添加到链表中
        table[index].add(new Entry<>(key, value));
        //增加长度
        size++;
    }

    /**
     * 获取元素
     * @param key 键
     * @return 返回对应的值
     */
    public V get(K key) {
        //计算hash值
        int index = hash(key);
        //如果当前值为null
        if (table[index] == null) {
            //返回null
            return null;
        }
        //遍历该位置的链表
        for (Entry<K, V> entry : table[index]) {
            //判断链表中是否有这个key键,
            if (entry.getKey().equals(key)) {
                //存在则返回元素的值
                return entry.getValue();
            }
        }
        //否则返回null
        return null;
    }

    /**
     * 删除元素
     * @param key 所需要删除的key
     * @return false:删除失败,true:删除成功
     */
    public boolean remove(K key) {
        //计算hash值
        int index = hash(key);
        //如果当前位置为null
        if (table[index] == null) {
            //返回false
            return false;
        }
        //遍历该位置的链表
        for (Entry<K, V> entry : table[index]) {
            //判断链表中是否有这个key键,
            if (entry.getKey().equals(key)) {
                //从链表中删除该元素
                table[index].remove(entry);
                //减小长度
                size--;
                //返回true
                return true;
            }
        }
        //返回false
        return false;
    }

    /**
     * 获取长度
     * @return 返回长度
     */
    public int size() {
        return size;
    }

    /**
     * 计算hash值
     * @param key 键
     * @return 返回自定义的hash值(可按照自己的规则编写)
     */
    private int hash(K key) {
        //绝对值并取模
        return Math.abs(key.hashCode()) % table.length;
    }

    /**
     * 静态内部类
     * @param <K>
     * @param <V>
     */
    private static class Entry<K, V> {
        //key,键
        private K key;
        //value,值
        private V value;

        /**
         * 构造方法
         * @param key 传入的key
         * @param value 传入的值
         */
        public Entry(K key, V value) {
            //初始化键和值
            this.key = key;
            this.value = value;
        }

        // 获取键
        public K getKey() {
            // 返回键
            return key;
        }
        // 获取值
        public V getValue() {
            // 返回值
            return value;
        }
        // 设置值
        public void setValue(V value) {
            // 更新值
            this.value = value;
        }
    }
}

Hash碰撞

解析:

方法 返回值 说明
ChainedHashTable 构造方法,创建对象时需要传入具体的长度
put void 添加元素,先计算key的hash值,判断是否有这个key,没有新建一个l链表并添加到数组元素的末尾。有则更新对应的value
get V 获取元素,先计算key的hash值,判断是否有这个key,没有则返回null,然后遍历链表,有则返回对应的value,没有返回null
remove boolean 删除元素,先计算key的hash值,判断是否有这个key,没有则返回false,然后遍历链表,有则删除对应的value,没有返回false
size int 获取长度
hash int 计算hash值

代码持续开发中:不合理之处,可指导指导!!!

Hash碰撞文章来源地址https://www.toymoban.com/news/detail-439243.html

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

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

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

相关文章

  • 云计算中的出口数据是指什么?

    谷歌云(Google Cloud)近日宣布了一项重大政策变动,决定免除那些选择终止使用其服务并将数据迁移到其他云服务商或本地环境的客户的出口数据费用(数据导出费用) 。 这一举措由谷歌云平台负责人阿米特·扎维里(Amit Zavery)在其博客中公布,他表示:“如果有谷歌云客

    2024年01月25日
    浏览(91)
  • 【Python 基础】输入两个数,求它们的求最大公约数(伪码描述 + Python实现)| 区块链 面试题:区块链技术中的“闪电网络”是什么?有什么作用?

      “这样的年代没有谁是值得信任的,你只能靠自己。”     🎯作者主页: 追光者♂🔥          🌸个人简介:   💖[1] 计算机专业硕士研究生💖   🌿[2] 2023年城市之星领跑者TOP1(哈尔滨)🌿   🌟[3] 2022年度博客之星人工智能领域TOP4🌟   🏅[4] 阿里云社区特邀专家博

    2024年02月01日
    浏览(71)
  • 大数据平台安全主要是指什么安全?如何保障?

    大数据时代已经来临,各种数据充斥着我们的生活与工作。随着数据的多样性以及复杂性以及大量性,大数据平台诞生了。但对于大数据平台大家都不是很了解,有人问大数据平台安全主要是指什么安全?如何保障? 大数据平台安全主要是指什么安全? 大数据平台安全主要

    2024年02月11日
    浏览(44)
  • Redis设置hash,为不同的field设置不同的过期时间

    最近做了一个小需求,由于系统对接,导致我们的系统在高峰的时候CPU飙升,所以需要在高峰的时候保护系统进程不受影响。 而且还需要我们知道当前对接的数据总量,并且可以实时释放,如果释放失败了,还需要定时释放,减少系统卡顿的同时,不能对第三方产生影响。

    2024年02月08日
    浏览(42)
  • 43.241.18.X微端服务器一般是指的什么意思

    “微端”是微型客户端的简写,微端游戏客户端只有一些基本的功能,客户端会根据玩家所到地图,自动将地图文件,以及一些其它文件下载到玩家本地的客户端文件夹中,这样就形成了玩家一边玩游戏一边下载相关的文件到本地。这一特性就需要放游戏服务端的服务器的上

    2024年02月13日
    浏览(44)
  • OSPF : 区域 / 为什么非骨干互访需要经过骨干

    OSPF系列第二篇 , 今天来围绕着区域这个概念展开写一篇博客 先来讨论一下技术背景 , 也就是为什么要分区 ? 所有设备都在一个区域不行吗 会有什么问题呢 . 首先明确一个知识点 : 正常状态下一个区域内的所有设备的LSDB都是一样的 .区域内的路由器必须为所属的区域保存拓扑

    2024年01月25日
    浏览(61)
  • OpenCV每日函数 了解不同的图像哈希函数、以及OpenCV的img_hash哈希模块

            图像哈希是 使用算法为图像分配唯一哈希值的过程 。图像的副本都具有完全相同的哈希值。因此,它有时被称为“数字指纹”。         在深度学习普及之前,一些搜索引擎使用散列技术来索引图像。这就需要一个哈希函数,对于文件的微小更改,该函数会

    2024年02月11日
    浏览(51)
  • 编写函数,判断一个字符串是否是回文。在主函数中输入一个字符串,调用自定义函数,输出结果。 所谓回文是指顺读和倒读都一样的字符串。如“AMNMA“是回文。

    编写函数,判断一个字符串是否是回文。在主函数中输入一个字符串,调用自定义函数,输出结果。 所谓回文是指顺读和倒读都一样的字符串。如\\\"AMNMA\\\"是回文。 测试输入:abcba 测试输出:是回文! 这道题要求编写一个函数来判断一个字符串是否是回文,并在主函数中调用该

    2024年02月03日
    浏览(68)
  • 使用git合并两个不同项目代码

    前言, 这里解决的是两个不同的项目, 因为不同项目那必然是两个不同的git仓库 都是不同的git仓库了那就更不可能是相同的分支了(即使分支名相同) 至于为什么会有这种业务情况出现, 我也不知道, 反正先学干就完了 这里图形化界面演示用的是idea自带的git插件, 因为不是git命令

    2024年02月02日
    浏览(41)
  • git如何比较两个分支的不同

    工作使用git代码仓库,当分支多任务细分,两个分支之间的比较变得重要,由于之前的某种操作,两个分支的合并情况已经不再清晰,迫切需要我们比较两个分支的不同。下面讲解使用两个方式去比较分支文件、比较分支下的单个文件不同 git 命令行比较 (通用) vscode 插件

    2024年02月07日
    浏览(46)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包