Java中HashMap的自定义实现

122 阅读 0 评论 81 点赞

我是靠谱客的博主潇洒发夹，这篇文章主要介绍Java中HashMap的自定义实现，现在分享给大家，希望可以做个参考。

HashMap是我们在Java程序中常用的数据结构，但是他的具体实现你是否了解，接下来，我们将自己来写一个HashMap类，从中可以看到HashMap的底层实现是什么。
当然我们实现的HashMap与Java自己的相比并不一致，只是一个简单的实现以此来熟悉一下HashMap的实现原理。
在Java中HashMap的实现原理是数组+链表(当链表中的元素超过8个时候将会变成红黑树)

1.什么是hash
HashMap离不开hash，什么是hash？他是一种算法可以将任意长度的输入转化为固定长度的输出，在HashMap里面hash算法将任意的key转化为数组对应的下标以此来存储key-value形式的对象。理想的hash算法可以使得输入均匀分散的遍布整个数组。当然也有几率出现，两个不同的key生成的hashCode一致的情况，这样的情况被称为碰撞。
如何解决碰撞？Java的处理方式是将数组里面的元素变成链表，当发生碰撞的时候将元素插入链表的头部。当查询的时候，若是该数组元素中不止一个，便依次遍历链表直到找到相同的key进行覆盖存储，若是没有则进行链表的新增（当然Java还会在大于8个元素的时候进行红黑树的转换，依次来减小时间的开销）
2.什么是HashMap
HashMap可以这样来形容，他类似于一个有许多抽屉的柜子(容器)，每个抽屉上面都有一个标签来标识这个抽屉里面装的类别(key)，打开对应标签的抽屉以后你可以就可以找到对应的东西(value)，因此可以看到当查找HashMap的时候他理想的时间复杂度为O(1)
3.简单Hash算法的实现、

复制代码

1
2
3
4
5
6
7
public int hash(String key){
if(key == null){
return 0;
}else{
return key.length();
}
}

通过以上的程序，我们可以得到一个简单的hash算法，当然这边明显可以看到不足，当key传入cat与dog两个字符串的时候，他返回的hash值是一样的，但是其实他不一样，所以我们需要进行改进。

复制代码

1
2
3
4
5
6
7
8
9
10
11
public int hash(String key){
if(key == null){
return 0;
}else{
int code = 0;
for(int i =0 ; i < key.length();i++){
code += key.codePointAt(i);
}
return code;
}
}

以上方法便可以解决传入cat与dog的问题了，但是问题还是要有的 cat 与 act的问题又出现了。
所以继续改进：

复制代码

1
2
3
4
5
6
7
8
9
10
11
public int hash(String key){
if(key == null){
return 0;
}else{
int code = 0;
for(int i =0 ; i < key.length();i++){
code += key.codePointAt(i)<< (i * 8);
}
return code;
}
}

我们按照位置的不同将每次得到的int值进行位运算这样就可以得到不同的hash值了，现在即使是cat 与 act也不一样了。有了hash值我们接下来需要的就是进行下一步的转化，将hash值变成可以用的index数组下标。
4.数组下标
首先既然要用到数组那么我们就要先建立数组才可以。那么此时我们就忽然想到，在Java中建立数组是需要指定数组类型的，那么此时我们需要指定什么呢？字符串？数字？都不是，是链表。在HashMap源代码的内部，Java建立了内部静态类Node<K,V>来进行链表的储存，在这里我们就以Node来进行表示，并不会进行Node<K,V>的详解。

复制代码

1
Node[] nodeArray = new Node[2];

我们先把数组元素定位2，看以后会发生什么情况。
有了数组，我们就该存储了，怎么将不固定的hash值变成不会越界的index数组下标呢？有一个十分简单的方式——取模(%)，就是余数。

复制代码

1
2
3
public int getIndex(int hashCode){
return hashCode%2;
}

这样的话，我们就可以获取不同的hash值对应的index了，然后根据链表的存取就可以实现一个简单的HashMap了。但是从以上的方法执行后，我们可以看到，一个index中会有大量的元素存在，链表很长，这样就不是我们想要的了。因此此时，我们需要的是扩大数组，数组变大了，取余的数也变多了，一个index中的链表自然会减少了，这就是HashMap的resize操作。
（在HashMap中若不指定数组容量，程序会默认2^4（16）为初始建立的数组大小）
在resize方法中，需要将原本的数组进行重新分配，存入新的数组里面。这样便可以减少碰撞。
这里贴个源码：

复制代码

final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else {
// zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}

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
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else {
// zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}

以上便是HashMap的简单实现，里面的方法并没有完成写出来，可以自行书写。
附带一下node的源码：

复制代码

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
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey()
{ return key; }
public final V getValue()
{ return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}