HashMap的hash碰撞

HashMap的hash碰撞看了看HashMap的源码,有些心得先写下,以便以后查看,不然又要忘了,但不知道对不对,希望没误人子弟吧。主要是解释下HashMap底层实现与如何解决hash碰撞的。HashMap底层是table数组,Entry是HashMap的内部类。可以看到HashMap的key与value实际是保存在Entry中的,next是下一个Entry节点。staticfinalEntry<…

大家好,又见面了,我是你们的朋友全栈君。

看了看HashMap的源码,有些心得先写下,以便以后查看,不然又要忘了,但不知道对不对,希望没误人子弟吧。

主要是解释下HashMap底层实现与如何解决hash碰撞的。

HashMap底层是table数组,Entry是HashMap的内部类。

可以看到HashMap的key与value实际是保存在Entry中的,next是下一个Entry节点。

static final Entry<?,?>[] EMPTY_TABLE = {};
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

static class Entry<K,V> implements Map.Entry<K,V> {

        final K key;
        V value;
        Entry<K,V> next;
        int hash;

}

public V put(K key, V value) {

        if (table == EMPTY_TABLE) {

            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);

        //计算key的hash值
        int hash = hash(key);

        //计算通过key的hash值与table长度来计算位置
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {

            Object k;

             //判断key是否重复,如果重复则替换
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {

                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

void addEntry(int hash, K key, V value, int bucketIndex) {

        //判断是否容量超过极限
        if ((size >= threshold) && (null != table[bucketIndex])) {

            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }

这里实际才是将key与value保存了,先获取之前的位于bucketIndex位置的的Entry元素e(如果不存在则为null,如果存在则代表有重复的hash值,我自己理解为这就是HashMap的hash碰撞),在新建一个Entry元素,将之前的Entry元素e放入新建的Entry元素内部,新建的Entry保存在table中。

void createEntry(int hash, K key, V value, int bucketIndex) {

        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }

HashMap的hash碰撞

0,1,2,3位置都有Entry元素,但1,3有两个Entry元素,(21,21)与(13,13)实际保存在13与8元素next属性上。如果还有重复的hash(key)值那就继续保存,这就是HashMap对hash碰撞的处理方式,拉链法。

写的不好请见谅,如果哪里说的不对,请讲出来,小菜鸟一个。

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

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

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

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

(0)
blank

相关推荐

  • Conda 替换镜像源方法尽头,再也不用到处搜镜像源地址[通俗易懂]

    Conda 替换镜像源方法尽头,再也不用到处搜镜像源地址[通俗易懂]文章目录conda替换镜像源教程1镜像源添加方法2如何找到你要用的源conda替换镜像源教程由于国内访问conda官网很慢,离线安装又费时费力,因此,替换国内源是一个极佳的办法。但是,目前国内源的替换教程过于老旧,都是2018-2021年的方法,尽管替换镜像源的方法不变,但是网上的资料中,很多镜像源都失效了,没有一个教程能够告诉大家如何去找自己的镜像源并添加进去。本教程出于此目的,保证大家以后添加的镜像源实效性强。(时间2022.3.10)1镜像源添加方法首先是一些常用命令,帮你诊断目前你的co

  • Java取余和取模

    Java取余和取模抛开高级语言的实现,取余运算和取模运算本身并不完全一致,区别在于对负整数进行取商时操作不同。虽然这样说,但是取余运算和取模运算的公式都一样。对于x和y两个整数(int),通过以下两个操作获取余数或模数:step1、求商:intz=x/ystep2、求余数或模数:intresult=x-y*z它们的差别在于,如果z的值…

  • JAVA bean的作用域

    JAVA bean的作用域1、Bean的5种作用域(1)singleton:单例模式,SpringIoC容器中只会存在一个共享的Bean实例,无论有多少个Bean引用它,始终指向同一对象Singleton作用域是Spring中的缺省作用域,也可以显示的将Bean定义为singleton模式,配置为:<beanid=”userDao”class=”com.ioc.UserDaoImpl”scope=”singleton”/>(2)prototype:原型模式,每次通过Spring容器获取prototype定

    2022年10月29日
  • JSON中,java.lang.NoClassDefFoundError: net/sf/ezmorph/Morpher问题解决[通俗易懂]

    JSON中,java.lang.NoClassDefFoundError: net/sf/ezmorph/Morpher问题解决[通俗易懂]JSON中,java.lang.NoClassDefFoundError: net/sf/ezmorph/Morpher问题解决

  • DDoS攻击模拟与Metasploitable渗透

    DDoS攻击模拟与Metasploitable渗透DDoS攻击模拟与Metasploitable渗透Part.1DDoS介绍和发展史1.DDoS:DistributedDenialofService,分布式拒绝服务攻击。2.带宽消耗型攻击,所谓带宽消耗型攻击就是攻击者将提供网络服务的正常的带宽消耗殆尽,带宽消耗殆尽后就会造成网络堵塞,从而当正常的用户与服务器进行通信时无法提供正常服务。举vps的例子,vps服务器一般都有固定的带宽,…

    2022年10月21日
  • Spring3.0 AOP 具体解释

    Spring3.0 AOP 具体解释

发表回复

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

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