• Jerry银银
    2018-11-04
    int hash(Object key) {
        int h = key.hashCode();
        return (h ^ (h >>> 16)) & (capitity -1); //capicity 表示散列表的大小
    }

    先补充下老师使用的这段代码的一些问题:在JDK HashMap源码中,是分两步走的:
    1. hash值的计算,源码如下:
    static final int hash(Object key) {
            int hash;
            return key == null ? 0 : (hash = key.hashCode()) ^ hash >>> 16;
     }

    2. 在插入或查找的时候,计算Key被映射到桶的位置:
    int index = hash(key) & (capacity - 1)

    ----------------------------
    JDK HashMap中hash函数的设计,确实很巧妙:

    首先hashcode本身是个32位整型值,在系统中,这个值对于不同的对象必须保证唯一(JAVA规范),这也是大家常说的,重写equals必须重写hashcode的重要原因。

    获取对象的hashcode以后,先进行移位运算,然后再和自己做异或运算,即:hashcode ^ (hashcode >>> 16),这一步甚是巧妙,是将高16位移到低16位,这样计算出来的整型值将“具有”高位和低位的性质

    最后,用hash表当前的容量减去一,再和刚刚计算出来的整型值做位与运算。进行位与运算,很好理解,是为了计算出数组中的位置。但这里有个问题:
    为什么要用容量减去一?
    因为 A % B = A & (B - 1),所以,(h ^ (h >>> 16)) & (capitity -1) = (h ^ (h >>> 16)) % capitity,可以看出这里本质上是使用了「除留余数法」

    综上,可以看出,hashcode的随机性,加上移位异或算法,得到一个非常随机的hash值,再通过「除留余数法」,得到index,整体的设计过程与老师所说的“散列函数”设计原则非常吻合!

    ---------
    有分析不准确的地方,请指正!
    展开

    作者回复: 👍

     13
     371
  • Flash
    2019-01-07
    经过一番资料查阅理解之后,说说我的理解:
    JDK hashMap源码,hash表中数组位置的计算分两步:
    1.计算hash值:
     hash(Object key) {
            int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    这一步有一种说法,叫它扰动函数,为什么要右移16位再与本身异或呢?
    1.1 首先hashCode()返回值int最高是32位,如果直接拿hashCode()返回值作为下标,大概40亿的映射空间,只要哈希函数映射得比较均匀松散,一般是很难出现碰撞的。
    问题是一个40亿长度的数组,内存是放不下的。
    1.2 所以,用自己的高半区和低半区做异或,混合原始哈希码的高位和低位,关键是以此来加大低位的随机性。为后续计算index截取低位,保证低位的随机性。
    1.3 这样设计保证了对象的hashCode的32位值只要有一位发生改变,整个hash()返回值就会改变,高位的变化会反应到低位里,保证了hash值的随机性。

    2.在插入或查找的时候,计算Key被映射到桶的位置:
    int index = hash(key) & (capacity - 1)
    hash()扰动函数计算的值和hash表当前的容量减一,做按位与运算。
    这一步,为什么要减一,又为什么要按位与运算?
    因为A % B = A & (B - 1),当B是2的指数时,等式成立。
    本质上是使用了「除留余数法」,保证了index的位置分布均匀。

    为什么HashMap的数组长度必须是2的整次幂?
    数组长度是2的整次幂时,(数组长度-1)正好相当于一个**“低位掩码”**,“与”操作的结果就是散列值的高位全部归零,只保留低位值,用来做数组下标访问。

    以初始长度16为例,16-1=15。2进制表示是00000000 00000000 00001111。“与”操作的结果就是截取了最低的四位值。也就相当于取模操作。
    展开
     4
     121
  • SCu
    2018-11-16
    可能会有同学对那个mod (capacity-1)有疑问 这个很正常,因为缺少前置描述条件 即当且仅当 capacity是2的整数倍的时候该公式才成立 当capacity为2的整数倍时(无符号)仅有一位是1其余位为0 减1后 后续为为1当前位为0 做与运算等于取后面的所有位的值 比如capacity=8 即00001000 减1为00000111 如has code=5 即00000101 此时5%8=00000101&00000111=00000101=5 其他大家举一反三即可
     2
     70
  • 拉欧
    2018-11-02
    比如Redis中的hash,set,hset,都是散列表实现,他们的动态扩容策略是同时维护两个散列表,然后一点点搬移数据
     2
     54
  • 天王
    2018-11-02
    能否每节讲完都有个代码的demo?

    作者回复: 是个好建议 我考虑下

    
     53
  • 姜威
    2018-11-03
    总结:散列表(中)
    面试题目:如何设计一个工业级的散列函数?
    思路:
    何为一个工业级的散列表?工业级的散列表应该具有哪些特性?结合学过的知识,我觉的应该有这样的要求:
    1.支持快速的查询、插入、删除操作;
    2.内存占用合理,不能浪费过多空间;
    3.性能稳定,在极端情况下,散列表的性能也不会退化到无法接受的情况。
    方案:
    如何设计这样一个散列表呢?根据前面讲到的知识,我会从3个方面来考虑设计思路:
    1.设计一个合适的散列函数;
    2.定义装载因子阈值,并且设计动态扩容策略;
    3.选择合适的散列冲突解决方法。
    知识总结:
    一、如何设计散列函数?
    1.要尽可能让散列后的值随机且均匀分布,这样会尽可能减少散列冲突,即便冲突之后,分配到每个槽内的数据也比较均匀。
    2.除此之外,散列函数的设计也不能太复杂,太复杂就会太耗时间,也会影响到散列表的性能。
    3.常见的散列函数设计方法:直接寻址法、平方取中法、折叠法、随机数法等。
    二、如何根据装载因子动态扩容?
    1.如何设置装载因子阈值?
    ①可以通过设置装载因子的阈值来控制是扩容还是缩容,支持动态扩容的散列表,插入数据的时间复杂度使用摊还分析法。
    ②装载因子的阈值设置需要权衡时间复杂度和空间复杂度。如何权衡?如果内存空间不紧张,对执行效率要求很高,可以降低装载因子的阈值;相反,如果内存空间紧张,对执行效率要求又不高,可以增加装载因子的阈值。
    2.如何避免低效扩容?分批扩容
    ①分批扩容的插入操作:当有新数据要插入时,我们将数据插入新的散列表,并且从老的散列表中拿出一个数据放入新散列表。每次插入都重复上面的过程。这样插入操作就变得很快了。
    ②分批扩容的查询操作:先查新散列表,再查老散列表。
    ③通过分批扩容的方式,任何情况下,插入一个数据的时间复杂度都是O(1)。
    三、如何选择散列冲突解决方法?
    ①常见的2中方法:开放寻址法和链表法。
    ②大部分情况下,链表法更加普适。而且,我们还可以通过将链表法中的链表改造成其他动态查找数据结构,比如红黑树、跳表,来避免散列表时间复杂度退化成O(n),抵御散列冲突攻击。
    ③但是,对于小规模数据、装载因子不高的散列表,比较适合用开放寻址法。
    展开
    
     28
  • 
    2018-11-02
    老师能不能就具体的题,讲讲数据结构呀。这种高大上的,对我来说有点难😔

    作者回复: 我后面还打算把所有的课后题集中写一写答案 那个时候会具体分析题目对应的就解决思路

    
     21
  • w1sl1y
    2018-11-05
    看了下,的确是TREEFY_THRESHOLD等于8
    UNTREEFY_THRESHOLD等于6
     1
     20
  • kakasi
    2018-11-16
    对于回答点赞第一的 @Jerry银银 有疑问:首先hashcode本身是个32位整型值,在系统中,这个值对于不同的对象必须保证唯一(JAVA规范),这也是大家常说的,重写equals必须重写hashcode的重要原因。
    hashcode不一定是唯一的,重写equals必须重写hashcode的原因是:java中有很多集合类是基于散列工作的,如果不重写hashcode, 两只值相等的对象就无法相等,因为object的hashcode是32位内存地址。
    
     16
  • w1sl1y
    2018-11-03
    我怎么hashmap记得红黑树树化的阈值是8,退化的阈值是6,回头看看源码确认下

    作者回复: 确认好留言给我啊

     1
     12
  • Infinite_gao
    2018-11-02
    老师可以分享一下,你对hashmap的默认负载因子是0.75的理解吗?是与泊松分布有关吗?

    作者回复: 大牛 能否详细说说

    
     12
  • angel😇txy🤓
    2019-08-29
    我来谈谈为何hashmap每次扩容试都要扩两倍,resize()时为何每次要扩两倍?
    计算桶位置,i = (n - 1) & hash,n 为2的幂时,(n-1) & hash = hash % n, 相当于对length求模,位运算效率更高。
    rehash时需要重新计算桶位置,如果不是2的幂,n -1转为二进制后,最低位始终是0,导致最低位为0的桶被浪费,造成更多的hash碰撞。
    如果length不为2的幂,比如15。那么length-1的2进制就会变成1110。在h为随机数的情况下,和1110做&操作。尾数永远为0。那么0001、1001、1101等尾数为1的位置就永远不可能被entry占用。这样会造成浪费,不随机等问题。 length-1 二进制中为1的位数越多,那么分布就平均。
    所以HashMap的初始容量是2的n次幂,扩容也是2倍的形式,元素均匀分布在HashMap中的数组上,减少hash碰撞,避免形成链表的结构,使得查询效率降低!
    展开
    
     11
  • 喜欢你的笑
    2018-11-02
    能分析一下HashMap的散列函数吗?

    作者回复: 不建议搞得这么详细 :)你就看一眼 有个印象就好了

    
     9
  • 强哥
    2019-03-07
    X % 2^n = X & (2^n - 1)
    2^n表示2的n次方,也就是说,一个数对2^n取模 == 一个数和(2^n - 1)做按位与运算 。
    所以说评论第一个说A%B=A&(B-1),并不成立。
    
     8
  • Yishem
    2018-12-14
    关于HashMap的loadFactor为什么是0.75?已经有网友整理好了(https://www.jianshu.com/p/64f6de3ffcc1),可以看看,很详细
    
     8
  • 猫头鹰爱拿铁
    2018-11-02
    集合类的带hash的,例如hashmap、hashset、hashtable等。hashmap中散列函数是key的hashcode与key的hashcode右移16位异或,这是为了把key的高位考虑进去,如果key是0,hash值为0。在put的时候,如果表没有初始化,需要初始化下,在计算key的位置的时候很巧妙,使用表的length-1和key的hash值与计算的,实际上就是对key的hash值对表长取模,基于hashmap是2的幂次方特性,这种位运算速度更快。如果put后hashmap的数据容量超过了表的容量*负载因子,就会自动扩容,默认是两倍,自动扩容方法是将key的hash与表长直接与判断是否有高位,有高位就把这个node放到新表里旧表对应位置加旧表长的地方。没有高位就直接是新表旧位置。这是hashmap1.8的处理方法。hashmap1.7还是对key的hash取模。如果是个非常大的数,赋值为integer.max。hashmap采用的是链地址法结合红黑树解决hash冲突,当桶中链表长度大于8就会将桶中数据结构转化为红黑树。hashtable默认的初使容量11,负载因子也是0.75,如果要指定初始化hashtable容量最好是给一个素数。这是因为放入table的时候需要对表长取模,尽量分散地映射。hashtable通过链地址法解决hash冲突,当数据容量大于数据容量*负载因子自动扩容,扩容原表长两倍+1。
    展开
    
     7
  • Ruhm
    2018-12-29
    NOTE 这节课给我的启发太大了,以前去阅读go的源码,总是感觉异常吃力,看完这节课之后去读了go关于map这个内置类型的源码,发现思路一下就清晰起来了,阅读效率高了很多,做到了有的放矢。那么以后阅读代码之前,先了解相关知识的方法论是很有必要的,这样比拿到源码就开始读,实际从长远看是节省了时间的。
    
     6
  • 辰陌
    2018-11-05
    python的字典就是封装好的散列吧

    作者回复: 嗯嗯

    
     6
  • 左胜利
    2018-12-21
    JAVA中使用散列表的数据类型:
    HashTable:
    1、默认初始大小:11
    2、装载因子:0.75
    3、散列函数:int hash = key.hashCode();
                          int index = (hash & 0x7FFFFFFF) % tab.length;
    4、当装载因子大于0.75时,启动扩容机制
    4、冲突解决方法:使用单链表解决hash冲突
    HashMap:
    1、默认初始大小:16
    2、装载因子:0.75
    3、散列函数:
            hash(Object key) {
                int h;
                return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
            }
    4、当装载因子大于0.75时,启动扩容机制
    5、使用单链表解决hash冲突,当链表长度大于8,将单链表转换成红黑树
    ThreadLocalMap
    1、初始容量:16
    2、装载因子:2/3
    3、散列函数:
        hash(Object key) {
            int HASH_INCREMENT = 0x61c88647;
            AtomicInteger nextHashCode = new AtomicInteger();
            nextHashCode.getAndAdd(HASH_INCREMENT)
            int threadLocalHashCode = nextHashCode()
            int i = threadLocalHashCode & (table.length - 1);
        }
    4、当装载因子大于2/3时,启动扩容机制
    5、使用线性探测的开放地址法解决hash冲突
    展开
    
     5
  • Allen Zou
    2018-11-03
    老师,开放寻址法如果冲突了,占用其它hash code对应的位置,那该位置真正的数据来的时候怎么办,接着往后放么?删除的时候是否要搬回来?

    作者回复: 不存在真正的数据的说法 都是先来先占坑

     2
     5
我们在线,来聊聊吧