logo头像

黑客的本质就是白嫖

Java HashMap原理

前言

Apache Commons Collections反序列化漏洞的复现文章里,有一条攻击链涉及到了Java HashMap的操作,而笔者在这之前都没有接触过这部分知识,故此先将Apache Commons Collections反序列化漏洞复现放一放,先把HashMap的东西学习一下

正文

拿到新的东西先别说别的,拿一段代码跑一跑就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package com.dldxz.study;

import java.util.HashMap;
import java.util.Map;

public class test {
public static void main(String[] args) {
HashMap<String,Integer> map = new HashMap<String, Integer>();
map.put("test1",1);
map.put("test2",2);
map.put("test3",3);
map.put("test4",4);
map.put("test5",5);
map.put("test6",6);
map.put("test7",7);

for(Map.Entry<String,Integer> entry : map.entrySet()) {
System.out.println(entry.getKey()+": "+entry.getValue());
}
}
}

以上代码的输出如下

1
2
3
4
5
6
7
test1: 1
test6: 6
test7: 7
test4: 4
test5: 5
test2: 2
test3: 3

这里可以看到一个比较奇怪的地方,明明代码是在一个for循环里面的,但是没有按照顺序输出,这就涉及到了HashMap的一些特性了

定义

HashMap实现了Map接口,继承了AbstractMap,其中Map接口定义了键映射到值的规则,而AbstractMap已经实现了Map接口

1
2
3
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable

构造函数

HashMap里面有四个构造函数

1
2
3
4
5
6
7
8
9
10
11
// 默认构造函数,构造一个具有默认初始容量(16)和默认加载因子(0.75)的空HashMap
HashMap()

// 构造一个带指定初始容量和默认加载因子(0.75)的空HashMap
HashMap(int initialCapacity)

// 构造一个带指定初始容量和指定加载因子的空HashMap
HashMap(int initialCapacity, float loadFactor)

// 构造一个与指定Map相同映射的HashMap,加载因子默认,初始容量需要足以保存指定Map中的映射
HashMap(Map<? extends K, ? extends V> m)

这里提到的初始容量和加载因子是两个影响HashMap性能的重要参数,其中容量表示哈希表中桶的数量(?),而加载因子是哈希表在其容量自动增加前可以达到多满的一种尺度,当哈希表中的条目数超出了加载因子与当前容量的乘积时,则要对该哈希表进行rehash操作(重建内部数据结构),从而哈希表将具有大概两倍的桶数

数据结构

Java里面最基础的两种数据结构就是数组和指针(引用)了,HashMap就是通过这两种数据结构组合实现,它是一种“链表散列”的数据结构,如下图

hm_1

HashMap的底层结构就是一个数组,数组的每一项又是一个链表,当我们新建一个HashMap的时候,就会初始化一个数组,而上面说到的initialCapacity参数就是该数组的长度

下面看一下其中一个构造函数的源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//jdk1.6
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);

// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;

this.loadFactor = loadFactor;
threshold = (int)(capacity * loadFactor);
table = new Entry[capacity];
init();
}

从上面可以看出,每次新建一个HashMap时都会初始化一个节点为Entry类型的数组,而EntryHashMap的内部类,其部分代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;

/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
...

它包含了键key,值value,下一节点next以及hash值,而HashMap是怎么实现快速存取的呢?

存储实现:put(key,value)

直接看源码

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
   public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
//计算key的hash值
int hash = hash(key.hashCode());
//计算key的hash值在table中的位置
int i = indexFor(hash, table.length);
//从i处开始迭代e,找到key保存的位置
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//判断该链上是否有hash值相同、key相同的节点
//若存在,则直接覆盖value,返回旧value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}

modCount++;
addEntry(hash, key, value, i);
return null;
}
...
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
}

以上代码大致流程如下

  1. 首先计算keyhashCode()hash值,再计算该元素在数组中的位置
  2. 在数组的下标i处,即第i条链表的链表头处开始迭代查找是否有节点的hash值与key值都与传入的相同
  3. 若有,则将传入的value赋值到该节点上,并返回该节点的旧value
  4. 若无,则调用addEntry方法插入一个新节点,此时有两种情况,其一即新建一条链表,并将该keyvalue所在的节点作为链头;其二为上面判断条件中只满足了一个,hash值相等但key不等,这时候就是在那个链表上插入一个新节点作为链头

读取实现:get(key)

源码:

1
2
3
4
5
6
7
8
9
10
11
12
13
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}

相对于putget方法就要简单一些了,传入的keyhash,在对应下标的链表处挨个找key值相等的value,若找到了即返回,没找到就返回null

结论

HashMap是一个由链表组成的数组,或者说由链表的表头对象组成的数组,数据在数组的哪个位置取决于他的keyhash值,而在链表的哪个位置就需要细看了,而由于它在数组的位置取决于其hash值,不与插入的先后时间相关,所以按顺序插入的数据在里面很有可能会乱掉

References

Java HashMap原理

Java HashMap工作原理及实现

java提高篇(二三)—–HashMap

评论系统未开启,无法评论!