Skip to content

Commit da78013

Browse files
crossoverJiecrossoverJie
committed
HashMap
1 parent abf3512 commit da78013

1 file changed

Lines changed: 12 additions & 1 deletion

File tree

‎MD/HashMap.md‎

Lines changed: 12 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,7 @@
11
# HashMap 底层分析
22

3+
> 基于 JDK1.7 分析。
4+
35
![](https://ws2.sinaimg.cn/large/006tNc79gy1fn84b0ftj4j30eb0560sv.jpg)
46

57
如图所示，HashMap 底层是基于数据和链表实现的。其中有两个重要的参数：
@@ -9,4 +11,13 @@
911

1012
容量的默认大小是 16，负载因子是 0.75，当 `HashMap` 的 `size > 16*0.75` 时就会发生扩容(容量和负载因子都可以自由调整)。
1113

12-
## put 方法
14+
## put 方法
15+
首先会将传入的 Key 做 hash 运算计算出 hashcode,然后根据数组长度取模计算出在数组中的 index 下标。
16+
17+
由于在计算中位运算比取模运算效率高的多，所以 HashMap 规定数组的长度为 `2^n` 。这样用 `2^n - 1` 做位运算与取模效果一致，并且效率还要高出许多。
18+
19+
由于数组的长度有限，所以难免会出现不同的 Key 通过运算得到的 index 相同，这种情况可以利用链表来解决，HashMap 会在 table[index] 处形成环形链表，采用头插法将数据插入到链表中。
20+
21+
## get 方法
22+
23+
get 和 put 类似，也是将传入的 Key 计算出 index ，如果该位置上是一个链表就需要遍历整个链表

0 commit comments

Comments
 (0)