开发者社区> hengyunabc> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

Java中String的hash函数分析

简介:
+关注继续查看
JDK6的源码:

    /**
     * Returns a hash code for this string. The hash code for a
     * <code>String</code> object is computed as
     * <blockquote><pre>
     * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
     * </pre></blockquote>
     * using <code>int</code> arithmetic, where <code>s[i]</code> is the
     * <i>i</i>th character of the string, <code>n</code> is the length of
     * the string, and <code>^</code> indicates exponentiation.
     * (The hash value of the empty string is zero.)
     *
     * @return  a hash code value for this object.
     */
    public int hashCode() {
	int h = hash;
	if (h == 0) {
	    int off = offset;
	    char val[] = value;
	    int len = count;

            for (int i = 0; i < len; i++) {
                h = 31*h + val[off++];
            }
            hash = h;
        }
        return h;
    }


以字符串"123"为例:

字符'1'的ascii码是49

hashCode = (49*31 + 50)*31 + 51

或者这样看:

hashCode=('1' * 31 + '2' ) * 31 + '3'

可见实际可以看作是一种权重的算法,在前面的字符的权重大。

这样有个明显的好处,就是前缀相同的字符串的hash值都落在邻近的区间。

好处有两点:

1.可以节省内存,因为hash值在相邻,这样hash的数组可以比较小。比如当用HashMap,以String为key时。

2.hash值相邻,如果存放在容器,比好HashSet,HashMap中时,实际存放的内存的位置也相邻,则存取的效率也高。(程序局部性原理)


以31为倍数,原因了31的二进制全是1,则可以有效地离散数据。

最后看下,两个字符串,由Eclipse生成的代码是如何计算hash值的:

public class Name{
	String firstName;
	String lastName;
	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result
				+ ((firstName == null) ? 0 : firstName.hashCode());
		result = prime * result
				+ ((lastName == null) ? 0 : lastName.hashCode());
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Name other = (Name) obj;
		if (firstName == null) {
			if (other.firstName != null)
				return false;
		} else if (!firstName.equals(other.firstName))
			return false;
		if (lastName == null) {
			if (other.lastName != null)
				return false;
		} else if (!lastName.equals(other.lastName))
			return false;
		return true;
	}	
}

可见,还是以31为倍数, hashCode = firstName.hashCode() * 31 + lastName.hashCode() 。

BTW:Java的字符串的hash做了缓存,第一次才会真正算,以后都是取缓存值。

eclipse生成的equals函数质量也很高,各种情况都考虑到了。


总结:字符串hash函数,不仅要减少冲突,而且要注意相同前缀的字符串生成的hash值要相邻。







版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
开发指南—函数—拆分函数—HASH
本文将介绍HASH函数使用方式。
28 0
Java String 源码分析
Java String 源码分析
15 0
牛逼!全网最全代表Java未来的ZGC深度剖析
JAVA程序最爽的地方是它的GC机制,开发人员不需要关注内存申请和回收问题。同时,JAVA程序最头疼的地方也是它的GC机制,因为掌握JVM和GC调优是一件非常困难的事情。在ParallelOldGC、CMS、G1之后,JDK11带来的全新的「ZGC」为我们解决了什么问题?Oracle官方介绍它是一个Scalable、Low Latency的垃圾回收器。所以它的目的是「降第停顿时间」,由此会导致吞吐量会有所降低。吞吐量降低问题不大,横向扩展几台服务器就能解决问题了啦。在全面介绍ZGC介绍,先统计一下大家线上环境在用什么垃圾回收器:
55 0
Java技术周刊第4期:闲鱼多业务隔离框架SWAK
Java的开发者们:云栖社区已有5000位Java开发者,发布了30000+Java文章(文章列表),沉淀了7000+的Java精品问答(问答列表)。 Java技术周刊将会为大家介绍最新的Java技术与动态、预告活动、最热问答、直播教程等,欢迎大家订阅Java技术周刊。
3138 0
Java-- String源码分析
  本篇博文基于java8,主要探讨java中的String源码。   首先,将一个类分为几个部分,分别是类定义(继承,实现接口等),全局变量,方法,内部类等等,再分别对这几个部分进行说明,这样到最后类的全貌也就比较直观了。
751 0
Java反射 - 获取Getters and Setters
使用Java反射,您可以检查类的方法并在运行时调用它们。 这可以用来检测给定的类有哪些getter和setter。 你不能明确地要求getter和setter,所以你将不得不扫描一个类的所有方法,并检查每个方法是否是getter或setter。
869 0
Java Set&amp;HashSet
Set接口及其实现类——HashSet Set是元素无序并且不可以重复的集合,被称为集; HashSet——哈希集,是Set的一个重要实现类。 1、Set没有像List中set()方法一样就修改,因为List是有序的,可以指定位置,而Set是无序的。
562 0
Java-类库-Guava-Ordering比较器
 Ordering是Guava类库提供的一个犀利强大的比较器工具,Guava的Ordering和JDK Comparator相比功能更强。它非常容易扩展,可以轻松构造复杂的comparator,然后用在容器的比较、排序等操作中。
961 0
java.utils.HashMap数据结构分析(转)
上图为Hashmap的数据结构图,具体实线是采用数组结合链表实现,链表是为了解决在hash过程中因hash值一样导致的碰撞问题。 所以在使用自定义对象做key的时候,一定要去实现hashcode方法,不然hashmap就成了纯粹的链表,查找性能非常的慢,添加节点元素也非常的慢。
597 0
+关注
hengyunabc
负责5K+应用,60K+机器的Spring Boot微服务技术落地,关注开发体验,微服务,APM,应用诊断,dubbo开源。Github: https://github.com/hengyunabc
106
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载