V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
amiwrong123
V2EX  ›  Java

Java 里 hashset 放置元素的过程,这么理解对吗?

  •  
  •   amiwrong123 · 2019-12-01 15:51:10 +08:00 · 2850 次点击
    这是一个创建于 1579 天前的主题,其中的信息可能已经有所发展或是发生改变。

    正在写一篇博客,但是由于还没有去看过 hashset 或 hashmap 的源码,只是自己想当然的这么理解哈希容器放置元素的过程,怕自己误人子弟啊😂

    1. 放置元素时,先调用元素的 hashcode 方法,为元素找到哈希桶的位置,之后元素就会放到这个哈希桶里。
    2. 此时哈希桶里可能已经有了多个元素。根据上图,两个对象 hashcode 相同,并不能得出两个对象是否为 equal 的。而哈希容器是不允许有两个 equal 的元素同时放在容器里的。所以哈希桶里的每个元素会分别和传入的元素执行 equals 比较。
    3. 如果哈希桶的每个元素执行 equals 比较后,返回的都是 false,那么放入传入的元素。如果哈希桶里某个元素和传入的元素执行 equals 比较后,返回了 true,那么需要执行相应的策略( 1.用传入元素替换掉哈希桶里既存元素 2.忽略传入元素,哈希桶里既存元素不变)。
    4. 这也是为什么源码注释说,unequal 的两个对象最好是产生不同的 hashcode,因为一个哈希桶里的元素越多,需要执行的 equals 的次数就越多。
    6 条回复    2019-12-01 19:33:45 +08:00
    renmu
        1
    renmu  
       2019-12-01 16:07:38 +08:00 via Android
    就是很标准的哈希表的实现,可以去看一下哈希表的 wiki
    cxtrinityy
        2
    cxtrinityy  
       2019-12-01 16:15:48 +08:00 via Android   ❤️ 3
    对倒是没啥不对,就是还要稍微深入点,第一点,数组下标是由 hashcode 和 size 通过除留余数法得出的,第二点,jdk 的实现一般在桶位上使用链表,链表内超过 8 个会转换为红黑树,以此加速相同 hash code 的查找比较,第三点,每个 key 得到不同 hashcode 这种完美散列实际情况常常难以满足,因为 jdk 的实现,数组 size 不是素数,而是 2 的幂次,方便用位操作加速下标的计算,开发编写的 hash 方法也是其中影响的一环,同时注意 load factor
    amiwrong123
        3
    amiwrong123  
    OP
       2019-12-01 16:20:53 +08:00
    @renmu
    看到这句话 A real world example of a hash table that uses a self-balancing binary search tree for buckets is the HashMap class in Java version 8.

    self-balancing binary search tree 这难道就是传说中的红黑树😂
    amiwrong123
        4
    amiwrong123  
    OP
       2019-12-01 16:24:50 +08:00
    @cxtrinityy
    好吧,确实是不够深入。你说的这几点我记下,回头再继续看。你说的第三点感觉挺有意思,虽然我现在有点理解不了,哎,得看源码了。
    qwerthhusn
        5
    qwerthhusn  
       2019-12-01 19:29:40 +08:00
    你没有提到一个哈希桶里面具体是什么,
    其实是一个双向链表,如果链表里面的值过多(好像是 6 还是 8 忘记了),会转化成红黑树。
    lhx2008
        6
    lhx2008  
       2019-12-01 19:33:45 +08:00 via Android
    差不多
    @cxtrinityy 其实并不是 hashcode 直接算的,还要高低一半的位做一些运算,确保 hashcode 足够混乱
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1198 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 18:13 · PVG 02:13 · LAX 11:13 · JFK 14:13
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.