第三章 5.集合-HashMap原理解析

1.问题引入

我们都接触过这道题,有如下字符串aabcccdd由任意英文字母组成,试统计每个字母的出现次数?

一种笨办法是:

public static void main(String[] args) {
    String str = "aabcccdd";
    for(int i = 0; i < str.length(); i++) {
        char ch = str.charAt(i);
        if(ch == 'a') {
            System.out.println("a的计数+1");
        } else if(ch == 'b') {
            System.out.println("b的计数+1");
        } else if(ch == 'c') {
            System.out.println("c的计数+1");
        } else if(ch == 'd') {
            System.out.println("d的计数+1");
        }
        // ...
    }
}

前几个字符还好说,如果有好多z字符,那么每次计数都有25次无效比较

F

高效的解法是:

  1. 设计一个长度为26的数组,分别用来存储每个字母的次数
  2. 怎么知道某个字母对应数组哪个下标呢?每个字母字符都对应一个整数,而且它们是连续的,因此a字符减去a字符得0,对应数组的下标0,b字符减去a字符得1,对应数组的下标1,以此类推
  3. 遍历整个字符串,让他们按第二步的规则,一个萝卜一个坑找到数组下标,计数加一即可
public static void main(String[] args) {
    String str = "aabcccdd";
    int[] counts = new int[26];
    for(int i = 0; i < str.length(); i++) {
        // 找到字符对应的数组下标
        int index = str.charAt(i) - 'a';
        counts[index]++;
    }
    // 打印结果
    for(int i = 0; i < counts.length; i++) {
        System.out.println(((char) (i + 'a')) + "的个数是:" + counts[i]);
    }
}

这里的一个关键点在于将字母映射到数组下标,我们比较的是下标而不是内容,帮助我们实现了快速定位

2.问题升级

有多个单词:abc,hello,world,abc ... 如何实现单词的计数统计?思考一下能否继续用数组来实现快速定位?

回忆一下,解决上一个问题的关键点是将字母映射到数组下标+比较的是下标,当时我们找到了字符与下标之间的规律,现在我们能不能找到单词与下标的规律呢?

3.hashCode

3.1最初的思路:

单词是字符,下标是数字,因此首先要把字符转换为数字
a对应的特征数字是97
b对应的特征数字是98
c对应的特征数字是99
综合他们的特征数字,97+98+99 作为abc对应的特征数字行不行呢?不行,因为这样的话acb的特征是 97+99+98 与之相同,就没法区分abcacb以及bac,bca,cab,cba

3.2改进的思路

数学家为我们提供了一个公式:
比如要计算abc的特征
$ a31^{3-1} + b31^{3-2}+c31^{3-3} 即 9731^{3-1} + 9831^{3-2}+9931^{3-3} = 96354 如果是`acb`呢 9731^{3-1} + 9931^{3-2}+9831^{3-3} = 96384 如果是四位的单词也没有问题,例如:`abcd` 9731^{4-1} + 9831^{4-2}+9931^{4-3}+100*31^{4-4} 通用的公式为: s[0]*31^{n-1} + s[1]*31^{n-2}+s[2]*31^{n-3} ... s[n-1]*31^{n-n} {,其中s为字符数组,n为长度}$

这个公式能够最大程度地让每个单词计算的结果特征数字不同,有没有可能冲突呢?答案是有。但据统计linux字典的48万个单词冲突数仅为15,冲突率仅为0.0031%。而且后面我们还有解决冲突的办法

冲突单词举例

[BM与C.], [BR与C3], [DM与E.], [FM与G.], [KP与L1], [KS与L4], [NF与O'], [QM与R.], [SP与T1], [TM与U.], [VM与W.], [mM与n.], [nF与o'], [gen.与i'll], [Ar.与BRM]

3.3把上述公式转换为java代码

// s 即为字符串中的字符数组 
public int hashCode() {
	int h = 0;
	int n = s.length;
	if (n > 0) {
		for (int i = 0; i < n; i++) {
			h = 31 * h + s[i];
		}
	}
	return h;
}

这段代码就是java.lang.String中hashCode代码的实现,我们之前说的特征数字就是hashCode,当然,java中的类型千千万万,其它类型的hashCode计算方式与字符串的有所不同,但本质思路是一致的,hashCode就代表了对象的特征码

为什么选择31这个质数呢
第一:经验证明,31、33、37、41这几个质数套入上述公式计算获得的hashCode碰撞都很小
第二:31 * i == (i << 5) - i 现代的JVM都可以对此进行识别并优化,把乘法运算转为移位和减法运算,提高效率

4.equals

刚才说了字符串单词的hashCode还是有可能冲突,那么冲突后怎么辨别呢,用字符串的equals方法,它会检查两个字符串中每个字符是否一样。

5.映射

5.1空间的抉择

继续我们的思路,将字符串的hashCode特征数字与数组下标对应,最简单的就是直接把hashCode与数组下标对应,例如:

a: 97
b: 98
c: 99
d: 100
e: 101
f: 102

那是不是要我们创建一个长度约为103的数组来存储这6个字符串呢,显然太浪费了,
有人说可以统统减去97(最早那个问题的映射方法)
但现在我们要统计的不仅仅是26个字母了,就拿abc来说它的hashCode是96354,难道要创建长度约为97000的巨大数组吗?

不用!我们可以创建一个固定长度的数组,然后用 hashCode % 数组长度来计算下标,因为求余数运算不可能超过除数(数组长度)

5.2 演示

例如:放入a,b,c,d四个字符串至长度为8数组:以后把每个数组下标对应的位置称之为一个桶(bucket)

注意桶下标的计算
例如 a的hashCode是97 那么 97 % 8 = 1

6.解决冲突-链表登场

现在数据存储空间变小了,单词字符串存入同一个桶的冲突几率就会增加,例如: i的hashCode是105 那么 105 % 8 = 1a的桶下标一样。当然也不排除之前我们提到的单词字符串自身也存在hash碰撞(虽然几率非常小),怎么解决这个问题呢?

不妨允许这些单词字符串存入同一桶下标

它们之间构成一个链表,下一次再访问a的时候先计算hashCode模长度找到下标,再顺着链表使用equals逐一比较,直到找到a

7.rehash(重新计算桶下标)

链表显然是在节省空间和查找效率之妥协的结果,冲突越多,链表越长,比较次数就越多,查找效率就越低。

我们应当在链表过长之前让数组变大,缩短链表,提升效率
例如:让数组长度翻倍为16,这样a的桶下标还是 97 % 16 = 1,但i的桶下标就变成了 105 % 16 = 9

显然,数组变大后,冲突减少了。

那么什么时机进行rehash呢?经验告诉我们当数组内元素的总数超过数组长度的3/4应该进行rehash,这里有个专业名词叫做负载因子 LOAD_FACTOR 这个值越大,桶内冲突的几率就越多;值越小,冲突就越小,但空间浪费也越多,0.75是它的默认值,我们最好不要轻易对它进行改动。

rehash因为要重新计算每个元素的桶下标,因此对性能有一定影响,如果已知元素的多少,可以在一开始就估算出数组的大小(元素个数*4/3)

可以试试abc的桶下标受扩容的影响

8. 这就是HashMap

HashMap的数据结构:数组+链表
HashMap的负载因子:0.75,会在元素个数/数组长度>0.75时进行扩容并rehash
HashMap(int) 的构造方法可以指定数组的初始大小
HashMap的key:必须实现hashCode和equals方法,它要参与之前提到的各项运算
HashMap的value:可以是任意的东西,例如单词的计数

最后用HashMap解一下我们之前提过的单词计数的问题:

public static void main(String[] args) {
    HashMap<String,Integer> map = new HashMap<>();
    String[] words = {"hello", "world", "hello", "abc", "abc"};
    for(String w: words) {
	    // 计算w的hashCode,并根据它定位桶下标,看看map中有没有这个w
        Integer count = map.get(w);
        if(count == null) {	    
        // map中还没有,将w放入map并存入初始计数1
            map.put(w,1);
        } else {
        // 计算w的hashCode,并根据它定位桶下标,找到这个key,更新值
            map.put(w,count+1);
        }
    }
    System.out.println(map);
}