Context
关于 HashMap, 有一件事儿一直很困惑,,在『Redis 核心历险』中是这样被提到的:
Redis 的字典相当于 Java 语言中的 HashMap,它是无序字典,内部存储了很多键值对。实现结构上与 Java 的 HashMap 也是一样的,都是”数组 + 链表”二维结构。第一维的 hash 的数组位置碰撞时,就会将碰撞的元素使用链表串接起来。
嗯,第一句没啥问题,,然而”数组 + 链表”什么鬼?还有 hash 碰撞。。作者并没有详细解释这儿,应该默认是每个 Java 开发者都知道的知识点了。然而我却在这儿卡壳了,心慌慌。。趁着周末赶紧补补课。事实证明,这波补课是很有效果的,在这本书后边的内容中,hash 还将会一直出现。
Hash
在 Wiki 中的定义为:
散列函数(英语:Hash function)又称散列算法、哈希函数,是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要,使得数据量变小,将数据的格式固定下来。该函数将数据打乱混合,重新创建一个叫做散列值(hash values,hash codes,hash sums,或hashes)的指纹。散列值通常用一个短的随机字母和数字组成的字符串来代表。好的散列函数在输入域中很少出现散列冲突。在散列表和数据处理中,不抑制冲突来区别数据,会使得数据库记录更难找到。
用我自己的话来说就是,,为数据创建指纹摘要,通过该摘要就可以找到原始数据。我觉得更多的场景是为相对大的数据创建摘要。假如有个 hash(),可以为任意数据生成一个32位的摘要。那么我们在互联网下载文件的时候,有的网站会在下来链接处给出该文件的 hash 值,等用户下载完成之后,通过 hash() 对该文件提取摘要,将两个 hash 值,进行对比。如果结果一样,说明文件在下载过程中没有被篡改。
那倘若我们对数字 1 进行 hash(),那应该也会得到一个长度为 32 位的摘要,但这时候还能叫『摘要』么?我感觉是不太合适的。
HashMap
-Basic JDK7
OK,back to the point..关于 Hash 我们需要知道👇
所有散列函数都有如下一个基本特性:如果两个散列值是不相同的(根据同一函数),那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有确定性的结果,具有这种性质的散列函数称为单向散列函数。但另一方面,散列函数的输入和输出不是唯一对应关系的,如果两个散列值相同,两个输入值很可能是相同的,但也可能不同,这种情况称为“散列碰撞(collision)”。
按我之前不成熟的想法,,HashMap 中为什么要放链表?直接放数据对象不就够了么。。原因就是当我们通过 get(key) 方法从 HashMap 中获取对象的时候,理论上这个 key 对应的 hash 值和某个 whateverKey 对应的 hash 值是一样的(即,散列碰撞),,因为『如果两个散列值相同,两个输入值很可能是相同的,但也可能不同(即,key 和 whateverKey)』。此时我们可以通过 key 和 whateverKey 都可以获取到对应的数据对象。如此,为了解决散列碰撞带来的问题,我们需要在 HashMap 中将两个‘key’都指向同一个数据对象,而在 HashMap 中的链表就是用来维护这些‘key’的。下面,我们试着读读 HashMap 源码。
HashMap 的 DOC 注释
1 |
|
put() 方法
1 | public V put(K key, V value) { |
get() 方法👇
1 | public V get(Object key) { |
remove() 方法
1 | public V remove(Object key) { |
entrySet() 方法
1 | /** |
到这里之后是有点儿懵的,,因为 entrySet0() 方法中第一行代码,entrySet
在 HashMap 中是这样声明的:👇1
private transient Set<Map.Entry<K,V>> entrySet = null;
之后在其他地方没有明确对其进行赋值的代码,然鹅我们在 Test
类进行 for(Map.Entry<String,String> m: map.entrySet())
循环时,entrySet
明明是有值的。那么 map.entrySet()
到底是在什么时候进行赋值的呢?!这个问题困扰了我很久,在 HashMap 显式继承的 AbstractMap 类和实现的 Map<K,V> 接口中,也没有找到答案。出门遛了一圈,突然想到了 Test
类被编译之后的 class 文件!!然后用 JD-JUI 反编译之后,终于有些发现了:👇1
2// class 文件反编译之后的 forEach 循环
for (Iterator i$ = map.entrySet().iterator(); i$.hasNext(); localEntry = (Map.Entry)i$.next())
👆我们可以看到,虽说用的是 forEach 循环,但在编译之后还是通过 Iterator 迭代器进行遍历的。首先初始条件 Iterator i$ = map.entrySet().iterator()
,我们可以看到 map.entrySet()
返回的是一个 Set<Map.Entry<K,V>>
,所以其 iterator()
是 Set
接口实现类的 iterator()
方法。我们继续看 entrySet0()
方法的第二行代码,在 entrySet
为空的情况下,会初始化一个新的 Set<Map.Entry<K,V>>
对象,即 new EntrySet()
,我们看看 EntrySet
类:👇
1 | private final class EntrySet extends AbstractSet<Map.Entry<K,V>> { |
<<<<<<<<<<<< 2019-04-02.update
上个月末的时候,花了一个晚上更新了下简历,但并没有到处去投,只是对外可见。陆陆续续开始有公司接触,其中还接到一个电话面试,,是某外包公司的。突如其来的电话面试,有点仓促,但好在前端时间也一直在看书恶补。其中有个很基础的问题,,『简单说下 Java 集合框架各容器类之间的关系』。多亏了学习 『Redis 核心历险』时,对 LinkedList 多看了一眼,也经受住了超越妹妹的考验。当中面试官特地提到 Map
和 Collection
有没有关系? 可以确定是肯定有关系,但有什么关系呢?没有答上来。。那时还没有整理 HashMap 这篇文章,只有 LinkedList。其实在整理这篇文章时也没找到两者之间的关系,因为 interface Map<K,V>
与 interface Collection<E>
并没有直接的继承关系。。这时候需要感谢的是『码出高效 Java 开发手册』了,平时把这本书放在了床头,睡前会翻一翻从此再无失眠,并没有从第一张开始读,而是直接挑了最薄弱的数据结构与集合这一章。
OK,下面来说说 Map
和 Collection
的关系!在书中是这样描述的: 👇
在数据元素的存储、查找、修改和遍历中,Java 中的 Map 类集合都与 Collection 类集合存在很大的不同。它是与 Collection 类平级的一个接口,在集合框架图上,它有一条微弱的依赖线月 Collection 类产生联系,那是因为部分方法返回 Collection 视图,比如 values() 方法返回的所有 values 的列表
我们先看 Map
接口的 values()
方法:👇1
2// Map 接口类
Collection<V> values();
非常明显,,说到values()
方法,肯定会想到 keySet()
和 entrySet()
,毕竟这三个方法在 HashMap
迭代的时候可是肩并肩的~👇1
2
3// Map 接口类
Set<K> keySet();
Set<Map.Entry<K, V>> entrySet();
我们再看看,这三个方法在 HashMap
中的实现~ 👇1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44// values 方法
public Collection<V> values() {
Collection<V> vs = values;
return (vs != null ? vs : (values = new Values()));
}
// Values 类,AbstractCollection 类实现类了 Collection 接口
private final class Values extends AbstractCollection<V> {
public Iterator<V> iterator() {
return newValueIterator();
}
public int size() {
return size;
}
public boolean contains(Object o) {
return containsValue(o);
}
public void clear() {
HashMap.this.clear();
}
}
// keySet 方法
public Set<K> keySet() {
Set<K> ks = keySet;
return (ks != null ? ks : (keySet = new KeySet()));
}
// KeySet 类,abstract class AbstractSet<E> 继承了 AbstractCollection<E> 实现了 Set<E>,而抽象类 AbstractCollection 和 Set 接口 都继承了 Collection 接口。
private final class KeySet extends AbstractSet<K> {
public Iterator<K> iterator() {
return newKeyIterator();
}
public int size() {
return size;
}
public boolean contains(Object o) {
return containsKey(o);
}
public boolean remove(Object o) {
return HashMap.this.removeEntryForKey(o) != null;
}
public void clear() {
HashMap.this.clear();
}
}
// 至于 entrySet() 方法,我们在分析 HashMap 的 forEach 循环时已经挖过源码了。EntrySet 类与 KeySet 类一样,都继承了 AbstractSet 抽象类。