8000 增加了对 hash方法的理解 · axepudding/Java-Guide@63d436e · GitHub
[go: up one dir, main page]
Skip to content

Commit 63d436e

Browse files
SnailclimbSnailclimb
authored
增加了对 hash方法的理解
1 parent 2a14332 commit 63d436e

File tree

1 file changed

+61
-28
lines changed

1 file changed

+61
-28
lines changed

‎Java相关/HashMap.md

Lines changed: 61 additions & 28 deletions
Original file line numberDiff line numberDiff line change
@@ -1,31 +1,62 @@
11
<!-- MarkdownTOC -->
22

3-
- [简介](#简介)
4-
- [内部结构分析](#内部结构分析)
5-
- [JDK1.8之前](#jdk18之前)
6-
- [JDK1.8之后](#jdk18之后)
3+
- [HashMap 简介](#hashmap-简介)
4+
- [底层数据结构分析](#底层数据结构分析)
5+
- [JDK1.8之前](#jdk18之前)
6+
- [JDK1.8之后](#jdk18之后)
77
- [HashMap源码分析](#hashmap源码分析)
8-
- [构造方法](#构造方法)
9-
- [put方法](#put方法)
10-
- [get方法](#get方法)
11-
- [resize方法](#resize方法)
8+
- [构造方法](#构造方法)
9+
- [put方法](#put方法)
10+
- [get方法](#get方法)
11+
- [resize方法](#resize方法)
1212
- [HashMap常用方法测试](#hashmap常用方法测试)
1313

1414
<!-- /MarkdownTOC -->
1515

16+
## HashMap 简介
17+
HashMap 主要用来存放键值对，它基于哈希表的Map接口实现</font>，是常用的Java集合之一。
1618

17-
## <font face="楷体" id="1">简介</font>
18-
<font color="red">HashMap</font>主要用来存放<font color="red">键值对</font>，它<font color="red">基于哈希表的Map接口实现</font>，是常用的Java集合之一。与HashTable主要区别为<font color="red">不支持同步和允许null作为key和value</font>，所以如果你想要保证线程安全，可以使用<font color="red">ConcurrentHashMap</font>代替而不是线程安全的HashTable，因为HashTable基本已经被淘汰。
19-
## <font face="楷体" id="2">内部结构分析
20-
### <font face="楷体" id="2.1">JDK1.8之前</font>
21-
JDK1.8之前HashMap底层是<font color="red">数组和链表</font>结合在一起使用也就是<font color="red">链表散列</font>。HashMap通过key的hashCode来计算hash值，当hashCode相同时，通过<font color="red">“拉链法”</font>解决冲突。
19+
JDK1.8 之前 HashMap 由 数组+链表 组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）.JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树，以减少搜索时间。
2220

23-
所谓<font color="red">“拉链法”</font>就是：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。
21+
## 底层数据结构分析
22+
### JDK1.8之前
23+
JDK1.8 之前 HashMap 底层是 **数组和链表** 结合在一起使用也就是 **链表散列**。**HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，当 hash 值相同时，通过拉链法解决冲突。**
2424

25-
![jdk1.8之前的内部结构](https://user-gold-cdn.xitu.io/2018/3/20/16240dbcc303d872?w=348&h=427&f=png&s=10991)
25+
**所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法 换句话说使用扰动函数之后可以减少碰撞。**
26+
27+
**JDK 1.8 HashMap 的 hash 方法源码:**
28+
29+
JDK 1.8 的 hash方法 相比于 JDK 1.7 hash 方法更加简化，但是原理不变。
30+
31+
```java
32+
static final int hash(Object key) {
33+
int h;
34+
// key.hashCode()：返回散列值也就是hashcode
35+
// ^ ：按位异或
36+
// >>>:无符号右移，忽略符号位，空位都以0补齐
37+
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
38+
}
39+
```
40+
对比一下 JDK1.7的 HashMap 的 hash 方法源码.
41+
42+
```java
43+
static int hash(int h) {
44+
// This function ensures that hashCodes that differ only by
45+
// constant multiples at each bit position have a bounded
46+
// number of collisions (approximately 8 at default load factor).
2647

27-
简单来说，JDK1.8之前HashMap由<font color="red">数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）,那么对于查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度依然为O(1)，因为最新的Entry会插入链表头部，急需要简单改变引用链即可，而对于查找操作来讲，此时就需要遍历链表，然后通过key对象的equals方法逐一比对查找.</font>
28-
### <font face="楷体" id="2.2">JDK1.8之后</font>
48+
h ^= (h >>> 20) ^ (h >>> 12);
49+
return h ^ (h >>> 7) ^ (h >>> 4);
50+
}
51+
```
52+
53+
相比于 JDK1.8 的 hash 方法 ，JDK 1.7 的 hash 方法的性能会稍差一点点，因为毕竟扰动了 4 次。
54+
55+
所谓 **“拉链法”** 就是：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。
56+
57+
![jdk1.8之前的内部结构](https://user-gold-cdn.xitu.io/2018/3/20/16240dbcc303d872?w=348&h=427&f=png&s=10991)
58+
如果定位到的数组位置不含链表（当前entry的next指向null）,那么对于查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度依然为O(1)，因为最新的Entry会插入链表头部，急需要简单改变引用链即可，而对于查找操作来讲，此时就需要遍历链表，然后通过key对象的equals方法逐一比对查找.
59+
### JDK1.8之后
2960
相比于之前的版本，jdk1.8在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。
3061
![JDK1.8之后的内部结构](https://user-gold-cdn.xitu.io/2018/3/20/16240e0e30123cfc?w=552&h=519&f=png&s=15827)
3162
**类的属性：**
@@ -59,15 +90,15 @@ public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneabl
5990
final float loadFactor;
6091
}
6192
```
62-
<font color="red">(1)loadFactor加载因子</font>
93+
- **(1)loadFactor加载因子**
6394

64-
loadFactor加载因子是控制数组存放数据的疏密程度，loadFactor越趋近于1，那么 数组中存放的数据(entry)也就越多，也就越密，也就是会让链表的长度增加，load Factor越小，也就是趋近于0，
95+
loadFactor加载因子是控制数组存放数据的疏密程度，loadFactor越趋近于1，那么 数组中存放的数据(entry)也就越多，也就越密，也就是会让链表的长度增加，load Factor越小，也就是趋近于0，
6596

66-
**loadFactor太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。loadFactor的默认值为0.75f是官方给出的一个比较好的临界值**。 　
97+
**loadFactor太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。loadFactor的默认值为0.75f是官方给出的一个比较好的临界值**。 　
6798

68-
<font color="red">(2)threshold</font>
99+
- **(2)threshold**
69100

70-
**threshold = capacity * loadFactor**，**当Size>=threshold**的时候，那么就要考虑对数组的扩增了，也就是说，这个的意思就是 **衡量数组是否需要扩增的一个标准**。
101+
**threshold = capacity * loadFactor**，**当Size>=threshold**的时候，那么就要考虑对数组的扩增了，也就是说，这个的意思就是 **衡量数组是否需要扩增的一个标准**。
71102

72103
**Node节点类源码:**
73104
```java
@@ -130,8 +161,8 @@ static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
130161
r = p;
131162
}
132163
```
133-
## <font face="楷体" id="3">HashMap源码分析</font>
134-
### <font face="楷体" id="3.1">构造方法</font>
164+
## HashMap源码分析
165+
### 构造方法
135166
![四个构造方法](https://user-gold-cdn.xitu.io/2018/3/20/162410d912a2e0e1?w=336&h=90&f=jpeg&s=26744)
136167
```java
137168
// 默认构造函数。
@@ -162,7 +193,9 @@ static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
162193
this.threshold = tableSizeFor(initialCapacity);
163194
}
164195
```
165-
putMapEntries方法：
196+
197+
**putMapEntries方法：**
198+
166199
```java
167200
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
168201
int s = m.size();
@@ -189,7 +222,7 @@ final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
189222
}
190223
}
191224
```
192-
### <font face="楷体" id="3.2">put方法</font>
225+
### put方法
193226
HashMap只提供了put用于添加元素，putVal方法只是给put方法调用的一个方法，并没有提供给用户使用。
194227
```java
195228
public V put(K key, V value) {
@@ -295,7 +328,7 @@ final Node<K,V> getNode(int hash, Object key) {
295328
return null;
296329
}
297330
```
298-
### <font face="楷体" id="3.4">resize方法</font>
331+
### resize方法
299332
进行扩容，会伴随着一次重新hash分配，并且会遍历hash表中所有的元素，是非常耗时的。在编写程序中，要尽量避免resize。
300333
```java
301334
final Node<K,V>[] resize() {
@@ -379,7 +412,7 @@ final Node<K,V>[] resize() {
379412
return newTab;
380413
}
381414
```
382-
## <font face="楷体" id="4">HashMap常用方法测试</font>
415+
## HashMap常用方法测试
383416
```java
384417
package map;
385418

0 commit comments

Comments
 (0)
0