解决hash冲突的几种方法_hashmap hash冲突

解决hash冲突的几种方法_hashmap hash冲突哈希表定义散列表(Hashtable,也叫哈希表),是根据键(Key)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称做散列函数,存放记录的数组称做散列表。实现关键点hash函数hash冲突解决首先来说hash函数,java中对象都已一个hashCode()方法,那为什么还

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

哈希表定义


  • 散列表(Hash table,也叫哈希表),是根据键(Key)而直接访问在内存存储位置的数据结构。 也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。 这个映射函数称做散列函数,存放记录的数组称做散列表。

实现关键点


  • hash函数
  • hash冲突解决

hash函数
首先来说hash函数,java中对象都已一个hashCode()
方法,那为什么还需要hash函数呢?hashCode是在jdk中是有符号int类型,这个一个很大的范围,如果散列表的数组能覆盖所有int值的话,就不需要hash函数了,当然内存不允许我们维护这么大的散列表。这时我们需要hash函数将原始hashCode映射到一个很小的数组上去。
常见的做法是取模法,也是jdk中的实现方式。

  • HashMap实现

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
 static int indexFor(int h, int length) {
         return h & (length-1);
     }

第一个hash函数有人称之为“扰动函数”,第二个indexFor函数在jdk8中去掉了,函数内的代码合并到了putVal中,个人认为这两个函数合并起来是一个完整的hash函数。
h & (length-1) 这段代码的作用其实就是取模,假设数组初始化长度为16,那么length-1的结果为15,对应二进制为00001111,如果我们有一个大小为20的key,对应二进制为00010100,与运算后结果为00000100,对应十进制为4.
这里数组的长度必须为2的次幂。

由于对key进行了取模运算,所以我们知道当length=16的时候,我们会舍弃调掉key高位的值,只保留了低4位。本来int是32位,只是用低4位冲突是不是太容易发生了?
所以第一个“扰动函数”的作用出现了,这个函数将key本身高16和低16位做了异或运算。
解决hash冲突的几种方法_hashmap hash冲突

从网上找了这张图,可以解释下(h = key.hashCode()) ^ (h >>> 16) 的作用。

通过高位和低位异或之后,本来被丢弃的高位值在做取模运算的时候也能体现得到。


  • ThreadLocal.ThreadLocalMap实现

 private void set(ThreadLocal<?> key, Object value) {

            // We don't use a fast path as with get() because it is at
            // least as common to use set() to create new entries as
            // it is to replace existing ones, in which case, a fast
            // path would fail more often than not.

            Entry[] tab = table;
            int len = tab.length;
            int i = key.threadLocalHashCode & (len-1);

            for (Entry e = tab[i];
                 e != null;
                 e = tab[i = nextIndex(i, len)]) {
                ThreadLocal<?> k = e.get();

                if (k == key) {
                    e.value = value;
                    return;
                }

                if (k == null) {
                    replaceStaleEntry(key, value, i);
                    return;
                }
            }

            tab[i] = new Entry(key, value);
            int sz = ++size;
            if (!cleanSomeSlots(i, sz) && sz >= threshold)
                rehash();
        }

其中int i = key.threadLocalHashCode & (len-1); 就是直接取模。


hash冲突避免

  • HashMap
    • 拉链法
  • ThreadLocal.ThreadLocalMap
    • 线性探测再散列
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/179087.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • QTabWidget的详细使用「建议收藏」

    QTabWidget的详细使用「建议收藏」QTabWidget介绍QTabWidget主要是用来分页显示的,每一页一个界面,众多界面公用一块区域,节省了界面大小,很方便的为用户显示更多的信息1,创建四个QWidgetself.tab1=QWidget()self.tab2=QWidget()self.tab3=QWidget()self.ta…

  • mysql smalldatetime_datetime与smalldatetime之间的区别

    mysql smalldatetime_datetime与smalldatetime之间的区别1、一直以为smalldatetime和datetime的差别只是在于时间范围:smalldatetime的有效时间范围1900/1/1~2079/6/6datetime的有效时间范围1753/1/1~9999/12/31所以我判断如果该值不用到太远的日期范围,就会使用smalldatetime。2、但我忽略了更关键的差别,那就是smalldatetime只精准到分,而datetime则可精准到3…

  • acwing1185. 单词游戏(欧拉图)「建议收藏」

    acwing1185. 单词游戏(欧拉图)「建议收藏」有 N 个盘子,每个盘子上写着一个仅由小写字母组成的英文单词。你需要给这些盘子安排一个合适的顺序,使得相邻两个盘子中,前一个盘子上单词的末字母等于后一个盘子上单词的首字母。请你编写一个程序,判断是否能达到这一要求。输入格式第一行包含整数 T,表示共有 T 组测试数据。每组数据第一行包含整数 N,表示盘子数量。接下来 N 行,每行包含一个小写字母字符串,表示一个盘子上的单词。一个单词可能出现多次。输出格式如果存在合法解,则输出”Ordering is possible.”,否则输出”The

  • futex_wait_cancelable_wait()方法

    futex_wait_cancelable_wait()方法国内几乎没啥说的,公司很多网站很多还不让上,用手机谷歌还可能会被领导批评,寻思回家查,还强制加班下班还很晚,这是又要马儿跑又要马儿不吃草啊。源码中这块是这么写的+#defineFUTEX_PRIVATE_FLAG 128+#defineFUTEX_CMD_MASK ~FUTEX_PRIVATE_FLAG++#defineFUTEX_WAIT_PRIVATE (FUTEX_WAIT…

  • python 删除文件、目录_python如何删除文件、目录[通俗易懂]

    python 删除文件、目录_python如何删除文件、目录[通俗易懂]本文讲述了python实现删除文件与目录的方法。分享给大家供大家参考。具体实现方法如下:os.remove(path)删除文件path.如果path是一个目录,抛出OSError错误。如果要删除目录,请使用rmdir().remove()同unlink()的功能是一样的在Windows系统中,删除一个正在使用的文件,将抛出异常。在Unix中,目录表中的记录被删除,但文件的存储还在。#…

  • 安卓7.0以上安装fiddler证书(模拟器)

    安卓7.0以上安装fiddler证书(模拟器)1.fiddler,最好fiddler4以上fiddler官网下载即可DownloadFiddlerWebDebuggingToolforFreebyTelerikhttps://www.telerik.com/download/fiddler2.夜神模拟器(百度下载)3.安装jdk(jdk8能够更好的支持自动化工具)JavaDownloads|Oraclehttps://www.oracle.com/java/technologies/downloads/#j

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号