Java - String类中的hashCode()方法

in TCEHJava with 0 comment

前言

在研究HashMap时,发现其用key进行哈希运算,其值映射到表中一个位置来访问记录,供后续查找节点使用。更多细节《HashMap源码分析
以key为String类型为例,研究了下哈希值得如何产生的。

简介

哈希值一般指哈希函数。一般的线性表,树中,记录在结构中的相对位置是随机的,即和记录的关键字之间不存在确定的关系,因此,在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较“的基础上,查找的效率依赖于查找过程中所进行的比较次数。 理想的情况是能直接找到需要的记录,因此必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使每个关键字和结构中一个唯一的存储位置相对应。哈希值即是f的值。

哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表M为哈希(Hash)表,函数f(key)为哈希(Hash) 函数。

更详细的描述可查阅百科以上内容来自百度百科

Hash,一般翻译做散列、杂凑,或音译为哈希,是把任意长度的输入(又叫做预映射pre-image)通过散列算法变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。对不同的关键字可能得到同一散列地址,即key1≠key2,而f(key1)=f(key2),这种现象称碰撞或哈希碰撞。更详细的描述可查阅百科以上内容来自百度百科

源码

//String 类中的hashCode方法

/** 使用字符数组存储字符串 */
private final char value[];

/** 缓存字符串的哈希码 */
private int hash; // 默认值为0
public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

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

分析

以字符串"abcde"为例

其char value[] = {'a','b','c','d','e'};

第一次循环后(char 运算会依据ASCII转化成int)
h = 97 = a
第二次循环后
h = 3105 = 31a + b
第三次循环后
h = 96354 = 31(31
a + b)+c
第四次循环后
h = 2987074 = (31(31a + b)+c)+d
第五次循环后
h = 92599395 = ((31(31
a + b)+c)+d)+e

即h = 31倍乘以上一次运算的值,加上这次的ascii值

最终字符串"abcde"的哈希值为 92599395。

Comments are closed.