关于hashcode 里面 使用31 系数的问题
hashcode其实就是散列码,使用hashcode使用高效率的哈希算法来定位查找对象!
我们在使用容器来存储数据的时候会计算一串散列码,然后将数据放入容器。
如:String s =“java”,那么计算机会先计算散列码,然后放入相应的数组中,数组的索引就是从散列吗计算来的,然后再装入数组里的容器里,如List.这就相当于把你要存的数据分成了几个大的部分,然后每个部分存了很多值, 你查询的时候先查大的部分,再在大的部分里面查小的,这样就比先行查询要快很多!
一个对象的HashCode就是一个简单的Hash算法的实现,虽然它和那些真正的复杂的!Hash算法相比还不能叫真正的算法,但如何实现它,不仅仅是程序员的编程水平问题, 而是关系到你的对象在存取时性能的非常重要的问题.有可能,不同HashCode可能 会使你的对象存取产生成百上千倍的性能差别!
java String在打印这个类型的实例对象的时候总是显示为下面的形式
test.Test$tt@c17164
上面test.Test是类名$tt是我自己写的内部类,而@后面这一段是什么呢?他其实就是tt这个实例类的hashcode是的16进制!
它使用了Object 里面的toString()方法
-
return getClass().getName() + “@” + Integer.toHexString(hashCode());
继续看看java里 String hashcode的源码:
public int hashCode() {
int h = hash; int len = count; if (h == 0 && len > 0) { int off = offset; char val[] = value; for (int i = 0; i < len; i++) { h = 31*h + val[off++]; } hash = h; } return h;}
其实上面的实现也就是数学里:
s[0]31^(n-1) + s[1]31^(n-2) + … + s[n-1]
的实现!我们会注意那个狗血的31这个系数为什么总是在里面乘来乘去?为什么不适用32或者其他数字?
大家都知道,计算机的乘法涉及到移位计算。当一个数乘以2时,就直接拿该数左移一位即可!选择31原因是因为31是一个素数!
所谓素数:
质数又称素数
。指在一个大于1的自然数中,除了1和此整数自身外,没法被其他自然数整除的数。
素数在使用的时候有一个作用就是如果我用一个数字来乘以这个素数,那么最终的出来的结果只能被素数本身和被乘数还有1来整除!如:我们选择素数3来做系数,那么3*n只能被3和n或者1来整除,我们可以很容易的通过3n来计算出这个n来。这应该也是一个原因!
在存储数据计算hash地址的时候,我们希望尽量减少有同样的hash地址,所谓“冲突”。如果使用相同hash地址的数据过多,那么这些数据所组成的
hash链就更长,从而降低了查询效率!所以在选择系数的时候要选择尽量长的系数并且让乘法尽量不要溢出的系数,因为如果计算出来的hash地址越大,所
谓的“冲突”就越少,查找起来效率也会提高。
31可以 由i*31== (i<<5)-1来表示,现在很多虚拟机里面都有做相关优化,使用31的原因可能是为了更好的分配hash地址,并且31只占用5bits!
在java乘法中如果数字相乘过大会导致溢出的问题,从而导致数据的丢失.
而31则是素数(质数)而且不是很长的数字,最终它被选择为相乘的系数的原因不过与此!
参考文档:http://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/
http://www.cogs.susx.ac.uk/courses/dats/notes/html/node114.html
本文来源于"阿里中间件团队播客",原文发表时间" 2012-03-19"
相关文章
- 在 Go 里用 CGO?这 7 个问题你要关注!
- 9款优秀的去中心化通讯软件 Matrix 的客户端
- 求职数据分析,项目经验该怎么写
- 在OKR中,我看到了数据驱动业务的未来
- 火山引擎云原生大数据在金融行业的实践
- OpenHarmony富设备移植指南(二)—从postmarketOS获取移植资源
- 《数据成熟度指数》报告:64%的企业领袖认为大多数员工“不懂数据”
- OpenHarmony 小型系统兼容性测试指南
- 肯睿中国(Cloudera):2023年企业数字战略三大趋势预测
- 适用于 Linux 的十大命令行游戏
- GNOME 截图工具的新旧截图方式
- System76 即将推出的 COSMIC 桌面正在酝酿大变化
- 2GB 内存 8GB 存储即可流畅运行,Windows 11 极致精简版系统 Tiny11 发布
- 迎接 ecode:一个即将推出的具有全新图形用户界面框架的现代、轻量级代码编辑器
- loongarch架构介绍(三)—地址翻译
- Go 语言怎么解决编译器错误“err is shadowed during return”?
- 敏捷:可能被开发人员遗忘的部分
- Denodo预测2023年数据管理和分析的未来
- 利用数据推动可持续发展
- 在 Vue3 中实现 React 原生 Hooks(useState、useEffect),深入理解 React Hooks 的