写点什么

那个业务大拿死在了这个地方

发布于: 2020 年 05 月 22 日
那个业务大拿死在了这个地方

业务代码中的技术是每个程序员的基础,但只是掌握了这些技巧,并不能成为技术大牛,还要不断打怪升级。Do more,Do better,Do exercise ,送给身边所有程序员 !!!







一个工业级哈希表的要求:

  • 支持快速的查询、插入、删除操作

  • 内存占用合理,不能浪费过多的内存空间

  • 性能稳定,极端情况下,散列表的性能也不会退化到无法接受的情况







Java 8 中哈希表底层采用数组存储,利用 hash 算法计算出下标值来存储元素,再配合上动态扩容,才能成为大拿写业务代码的利器。在哈希表中,最最重要的是哈希函数,其次是如何解决哈希冲突。我们分别来看:

哈希算法



在 Java 8 的源码中,hash函数的实现极其简单:

static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}



往数组中存储时,利用哈希值与数组长度做按位与运算,得到数组下标:

if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);



参数key的 hashcode 是个整型值,内存中占了32个字节,右移16位的结果是前16位都变成了0。再与hashcode值做异或操作,得到新的hash值。新的hash值,在与数组长度做按位与运算,得到数组下标。



举个例子,计算 "helloworld" 作为 key 存储时,数据下标的计算过程:

int h = "hello".hashCode();
System.out.println("原始的hashcode值 :" + getReplace(h));
int t = h >>> 16;
System.out.println("左移位16之后的值 :" + getReplace(t));
int r = h ^ t;
System.out.println("异或结果 :" + getReplace(r));
int n = 15;
System.out.println("数长度-1的哈希值 :" + getReplace(n));
int i = r & n;
System.out.println("最终结果 :" + getReplace(i));
System.out.println("最终结果10进制 = " + i);
System.out.println("00000101111010010001100011010010");
}
private static String getReplace(int r) {
return String.format("%32s", Integer.toBinaryString(r)).replace(' ', '0');
}

把计算过程的二进制运算,绘制在下图中:



最终结果 1011 转换为 10 进制为11,也就是以 “hello” 为 key 的元素,保存在数据下标 11 的位置。

数组大小



在 hash(Object key) 函数中把 hash 值右移16位,刚是 32位字节的一半。再与自身异或,相当于用原始 hash 值的前半部分和后半部分混合,增加了 hash 的随机性。



与数组长度减一做按位与运算,相当于只保留了哈希值的低位值(后半部分)用来做数组下标。因此,要保证数组长度加一的 hash 值,高位为 0 低位都为 1。所以 HashMap 数组长度必须是 2 的整次幂,才能保证这一点。



构造函数中的确有指定参数的方法,具体跟踪代码在真正执行赋值时,会执行如下函数:

static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

先右移去掉低位数,再做按位或操作,相当于把结果固定在这样的范围:

2^{0},2^{1},2^{2},2^{3},2^{4},2^{5}……2^{n}

因此即使是你传入了初始数组大小,也会调整最接近的长度范围,所以一定是2的整次幂

哈希冲突

再好的哈希算法也解决不了哈希冲突的问题,只能尽量的减少发生概率。那么如何处理真实发生的哈希冲突呢?



Java 8 中除了用单链表解决哈希冲突外,还引入了红黑树。我们看一下源码 (java.util.HashMap#putVal):

for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}



当链表上的长度大于 TREEIFY_THRESHOLD - 1 时,调用 treeifyBin() 方法。TREEIFY_THRESHOLD 为 8,意味着,当链表上的数据大于等于7个时,链表升级为红黑树。具体红黑树的实现,请自己赏悦代码。



当数据大小需要从新计算时,在java.util.HashMap#resize 中调用 java.util.HashMap.TreeNode#split

if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}



如果小于等于 UNTREEIFY_THRESHOLD (默认是6)执行 java.util.HashMap.TreeNode#untreeify,红黑树退化为链表。至于红黑树相关的代码,你还是自己查阅代码吧。



写业务代码的程序员



每个技术人员都有个成为技术大牛的梦。工作后都会发现,梦想是成为大牛,但做的事情看起来跟大牛都不沾边。也总能听到有人说,“天天写业务代码还加班,如何才能成为技术大牛”。



业务代码都写不好的程序员肯定无法成为技术大牛,只把业务代码写好的程序员也还不能成为技术大牛。



写业务代码,一样可以有各种技巧,可以使得业务代码更具可扩展性,可以和产品经理多交流以便更好的理解和实现业务,可以做好日志记录提升故障定位效率……



大拿是一个业务写的快的程序员,可能不是业务写的好的程序员。大拿也是一个想成为大牛的程序员,可能大拿只是想想什么也没做



业务代码中的技术是每个程序员的基础,但只是掌握了这些技巧,并不能成为技术大牛,还要不断打怪升级。送给所有奋斗在业务泥潭中的程序员三个锦囊:

Do more

  • 熟悉更多的业务

  • 了解系统的全貌

  • 自学用到的框架

Do better

  • 改进不合理、可改进的地方

  • 没发现有可以改进的地方,那说明功力不够,那就继续去发现

Do exercise

  • 功利学习

  • 刻意练习

  • 教会别人



关注我



如果您在微信阅读,请您点击链接 关注我 ,如果您在 PC 上阅读请扫码关注我,欢迎与我交流随时指出错误



发布于: 2020 年 05 月 22 日阅读数: 1058
用户头像

欢迎关注公众号“小眼睛聊技术” 2018.11.12 加入

互联网老兵,关注产品、技术、管理

评论 (6 条评论)

发布
用户头像
“再与hashcode值做异或操作,新的hash值的前16位也都变成了0。”新的hash值前16位不全是0,因为是异或操作不是与操作
2020 年 05 月 25 日 17:45
回复
是的,感谢订正,确实不全是0。下一part也提了,异或相当于前半部分和后半部分混合,增加了 hash 的随机性。再次感谢!
2020 年 05 月 25 日 23:44
回复
用户头像
哇,小眼睛同学太有才了!文末的“ DDD ”也超真诚,手动点赞!
2020 年 05 月 22 日 17:38
回复
感谢
2020 年 05 月 23 日 01:05
回复
用户头像
漫画是作者画的?特别加分,内容比较轻松,我晚点儿推荐到首页,下班时候可以刷着看。
2020 年 05 月 22 日 15:17
回复
是我画的。感谢
2020 年 05 月 23 日 01:05
回复
没有更多了
那个业务大拿死在了这个地方