Java Hashmap底层源码剖析

java , , 评论

Hash数据结构基础#

哈希表：#

  • 一个基于数组的K-V存储结构，K经过hash函数后散列到数组的某个位置，去拿到所需的K-V对。适用于可预测数据量且不需要遍历的场合。
  • 哈希表的效率：插入和删除需要O(1)的时间。(既能够具备数组的快速查询的优点又能融合链表方便快捷的增加删除元素的优势)

哈希表的缺点：#

  1. 基于数组，由于数组是定长的，长度塞满时效率很低（碰撞太多）。

    •  所以程序需要在合适的时候（如loadFactor大于2/3）把数据移动到更大的哈希表中，这个操作非常费时（因为地址是和数组长度有关的，移动时所有的元素将会逐一重新算hash地址）。

  2. 没有一种机制可以有序遍历(如从小到大)哈希表中的数据，如果需要则只能借助使用其他的数据结构。

Hash碰撞解决？—开放地址/链地址#

多个对象通过hash算法后的的地址相同，就产生了“哈希碰撞”。解决哈希碰撞的方法一般有两种：

  1. 开放地址法：即在数组中向后找一个合适的空位存储新的碰撞的对象。
    1. 线性探测：若碰撞，则从第一次hash的地址开始逐一向后找，找到空位则存储新的对象。（这种算法会在数组的某一段聚集大量的值，会增大碰撞的概率。聚集会降低hash表的效率）
    2. 二次探测：若碰撞，则从第一次hash的地址开始继续向后找，但每次找的步长为 1、4、9、16、25…以平方数递增。（比上一种略好，但因为碰撞元素探测的补偿相同，故会造成更细小的碰撞，在数组上聚集很多小段连续元素）
    3. 再hash方法：通过另一个hash算法算出第二次的步长。这个步长为一个与hash地址有关的值。如：stepSize = constant - （key % constant） key为第一次hash后碰撞的地址，这个常量要求是小于数组长度的质素。（数组长度也是质数）
  2. 链地址法：即在发生碰撞的位置存储一个链表。

好的哈希函数:#

  1. 可以快速的计算,有许多乘法/除法会比较慢不合适,除了取模之外可以考虑位运算,左移N位相当于除以2的N次方

  2. 结果要随机,哈希函数为了避免哈希碰撞,需要把key映射到数组的下标,越随机越好

  3. 使用质数取模,也就是数组长度要是质数,否则会有很大的聚集效应!

  4. 字符串hash的时候可以把每一位按照ascii码乘以27的N次方,再相加. 如china的c计算: (charAt(0)-97)*27^4 子母h:(charAt(1)-97)*27^3 …

  5. 如果最后数字太大可以使用[同余定理]拆分:

    (A×B + C×D + E×F +...)%P == ((A×B)%P + (C×D)%P +...)%P

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
package com.sam.phoenix.datastructure.e_HashTable;

import java.math.BigDecimal;

/**
*  本例子采用线性线性探测法
 * @author sam
 */
public class HashTableLine {
	//最大可以存放数据的总数
	private int maxDataSize = 0;
	//数组长度是arraySize除以loadFactor,除完的结果最好是一个质数,否则会有比较大的聚集效应
	private Node[]hashArray;
	//已经使用的长度
	private int length = 0;
	
	//删除标记
	static final Node DELETEED_NODE = new Node(Integer.MIN_VALUE,null);
	
	/**
	 * 构造方法，构造数组，初始化数组长度
	 * 
	 * 这里初始化一个比最大长度更长的数组,解决哈希碰撞开放地址后效率下降的问题,用空间换取时间
	 * @param size 最大存储的数量
	 * @param loadFactor
	 */
	public HashTableLine(int size, float loadFactor){
		if(loadFactor <= 0 || loadFactor>1){
			System.out.println("装载因子必须大于0,小于1,因为输入非法,默认取0.5!!!!");
			loadFactor = 0.5f;
		}
		int len = new BigDecimal(size).divide(new BigDecimal(loadFactor),0,BigDecimal.ROUND_HALF_EVEN).intValueExact();
		hashArray = new Node[len];
		maxDataSize = size;
	}
	
	/**
	 * 哈希算法，根据key的大小，算出在数组中的位置
	 * @param key
	 * @return
	 */
	private int hashFunction(int key){
		return key % hashArray.length;
	}
	
	/**
	 * 向hash表插入key-value数据,采用线性探测,如果插入的位置已经有值,自动往后面寻找一个空的位置存储
	 * @param key 
	 * @param value
	 */
	public void insert(int key, Object value){
		if(length == maxDataSize){
			System.out.println("已经满了,无法插入!!!!!!");
			//再插入就超过装载因子,碰撞太多,性能急剧下降
		}
		int index = hashFunction(key);
		//该位置恰好空余,可以插入.发生哈希碰撞,采用线性探测往后找,
		while(index < hashArray.length){
			if(hashArray[index] == null || hashArray[index] == DELETEED_NODE){
				//插
				hashArray[index] = new Node(key,value);
				//记录长度
				length++;
				return;
			}
			//此处使用线性探测: 每次+1,线性往后探测空余位置
			//[二次探测:不使用index++,而是使用每次往后1,4,9...平方探测,将连续的大区域碰撞转化为分散的碎片碰撞导致二次聚集(因为步长是确定的)]
			//[再hash: 将当前的index再次使用一个不同的hash算法计算后往后找,直到找到目标或者发现null,可以消除原始聚集和二次聚集(步长是不确定的)]
			index++;
			//找到了数组最后面,任然没有空余位置
			if(index == hashArray.length-1){
				//返回数组最前面继续找
				index = 0;
			}
		}
	}
	
	/**
	 * 查找对象
	 * @param key
	 * @return
	 */
	public Object find(int key){
		//是否为空
		if(length == 0){
			return null;
		}
		int index = hashFunction(key);
		//往后找
		while(index < hashArray.length){
			//找到一个空节点还没有,说明没有该条记录
			if(hashArray[index] == null){
				return null;
			}
			//该节点有数据,判断是不是目标节点,不是的话可能是碰撞过的,往后找
			if(hashArray[index].getKey() == key){
				return hashArray[index].getValue();
			}else{
				index++;
			}
			if(index == hashArray.length-1){
				//找到最后还没有,从队首开始找
				index = 0;
			}
		}
		//所有节点都非空,找了还没有
		return null;
	}
	
	/**
	 * 从hash表删除
	 * @param key
	 * @return
	 */
	public boolean delete(int key){
		//不能硬删除!!!!! 否则之前因为哈希碰撞线性探测存储的数据就找不到了!!!!!!!
		int index = hashFunction(key);
		if(hashArray[index]==null){
			return false;
		}
		//往后找,找到这个元素就软删除,下次查询到这里直接跳过往后找...
		while(index < hashArray.length){
			//找到一个空节点还没有,说明没有该条记录
			if(hashArray[index] == null){
				return false;
			}
			//该节点有数据,判断是不是目标节点,不是的话可能是碰撞过的,往后继续找
			if(hashArray[index].getKey() == key){
				//找到了，软删除之
				hashArray[index] = DELETEED_NODE;
				length--;
				return true;
			}else{
				index++;
			}
			if(index == hashArray.length-1){
				//找到最后还没有,从队首开始找
				index = 0;
			}
		}
		//没找到
		return false;
	}
	
	/**
	 * 打印hash表
	 */
	public void display(){
		for(int i = 0; i < hashArray.length; i ++){
			if(hashArray[i]==null){
				System.out.print("null,");
				continue;
			}
			System.out.print(hashArray[i].getKey()+""+hashArray[i].getValue()+",");
		}
		System.out.println();
	}

	/**
	 * 获取长度
	 */
	public int getSize() {
		return this.maxDataSize;
	}
}

QA#

  • 装载因子为啥是0.75？

    • 是一个时间和空间的这种，tradeoff
    • 这决定扩容的阈值，太低会浪费空间，很早就开始扩容。不过碰撞概率低，查询效率高。
    • 太高会碰撞加剧，插入和查询慢。但是节省空间。

  • 长度为什么是n^2?

    • 因为有一个取&的操作简化取模，保证冲突记录小。否则

    • # 数组长度是2^3=8
key=2：               00000010    
length-1=7：     00000111    
-------------------------------------------
取&                        00000010  = 2


key=3：               00000011    
length-1=7：     00000111    
-------------------------------------------
取&                        00000011  = 3

# 可以看到长度为8的时候，不同的key取的值是不同的



# 数组长度是=9  （非2的整数倍）
key=2：               00000010    
length-1=8：     00001000    
-------------------------------------------
取&                        00000000  = 0


key=3：               00000011    
length-1=8：     00001000    
-------------------------------------------
取&                        00000000  = 0

# 可以看到长度为8的时候，不同的key取的值是不同的

猫哥Risk Control Engineer

一个金融风控软件工程师。