手写Hashmap

代码

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
public class CustomHashMap<K, V> {

private class Entry<K, V> {
int hash;
K key;
V value;
Entry<K, V> next;

Entry(int hash, K key, V value, Entry<K, V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}

private static final int DEFAULT_CAPACITY = 1 << 4;

private Entry<K, V>[] table;

private int capacity;

private int size;

public CustomHashMap() {
this(DEFAULT_CAPACITY);
}

public CustomHashMap(int capacity) {
if (capacity < 0) {
throw new IllegalArgumentException();
} else {
table = new Entry[capacity];
size = 0;
this.capacity = capacity;
}
}

public int size() {
return size;
}

public boolean isEmpty() {
return size == 0 ? true : false;
}

private int hash(K key) {
int i = key.hashCode() & (capacity - 1);
double tmp = key.hashCode() * (Math.pow(5, 0.5) - 1) / 2;
double digit = tmp - Math.floor(tmp);
return (int) Math.floor(digit * capacity);
}

public void put(K key, V value) {
if (key == null) {
throw new IllegalArgumentException();
}
int hash = hash(key);
Entry<K, V> nEntry = new Entry<K, V>(hash, key, value, null);
Entry<K, V> entry = table[hash];
while (entry != null) {
if (entry.key.equals(key)) {
entry.value = value;
return;
}
entry = entry.next;
}
nEntry.next = table[hash];
table[hash] = nEntry;
size++;
}

public V get(K key) {
if (key == null) {
throw new IllegalArgumentException();
}
int hash = hash(key);
Entry<K, V> entry = table[hash];
while (entry != null) {
if (entry.key.equals(key)) {
return entry.value;
}
entry = entry.next;
}
return null;
}

public static void main(String[] args) {
CustomHashMap<String, String> map = new CustomHashMap<String, String>();
map.put("1", "11");
map.put("1", "22");
map.put("3", "33");
System.out.println(map.get("1"));
}

}

最后

本文到此结束,感谢阅读。如果您觉得不错,请关注公众号【当我遇上你】,您的支持是我写作的最大动力。