-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathhashmap.java
More file actions
153 lines (127 loc) · 4.15 KB
/
Copy pathhashmap.java
File metadata and controls
153 lines (127 loc) · 4.15 KB
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
package com.bryantchang.hashsearch;
import java.util.;
Created by Bryant_Chang on 2016918.
class MapItemK, V{
MapItemK, V next;
K key;
V value;
int hash;
MapItem(K k, V v, int hash){
this.key = k;
this.value = v;
this.hash = hash;
}
}
class MyHashMapK, V {
private int size;当前容量
private static int DEFAULT_CAPACITY = 16;默认容量
private MapItemK, V[] itemTable;
private static float LOAD_FACTOR = 0.75f;
private int max;最大承载能力
public MyHashMap(int init_capacity, float load_factor) {
对于装载因子进行判断
if(init_capacity 0) {
throw new IllegalArgumentException(init_capacity illegal);
}
if(load_factor = 0 Float.isNaN(load_factor)) {
throw new IllegalArgumentException(load_factor illegal);
}
this.LOAD_FACTOR = load_factor;
max = (int)(init_capacity load_factor);
itemTable = new MapItem[init_capacity];
}
public MyHashMap() {
this(DEFAULT_CAPACITY, LOAD_FACTOR);
}
public boolean setMapItem(MapItemK, V tmp, MapItem[] table) {
int index = indexFor(tmp.hash, table.length);
MapItemK, V entry = table[index];
存在冲突
if(null != entry) {
while(null != entry) {
若有相同的值则不存
if(tmp.key == entry.key tmp.key.equals(entry.key) &&
tmp.value == entry.value tmp.value.equals(entry.value)&&
tmp.hash == entry.hash ){
return false;
}
else if(tmp.key != entry.key && tmp.value != entry.value) {
if(null == entry) {
break;
}
entry = entry.next;
}
}
addEntry2Last(entry, tmp);
}
setFirstEntry(tmp, index, table);
return true;
}
添加元素
public boolean put(K k, V v) {
计算k的hash值
int hash_key = k.hashCode();
MapItemK, V tmp = new MapItemK, V(k, v, hash_key);
if(setMapItem(tmp, itemTable)) {
size++;
return true;
}
return false;
}
public V get(K k) {
MapItemK, V item = null;
int index = indexFor(k.hashCode(), itemTable.length);
MapItemK, V entry = itemTable[index];
if (null == entry) {
return null;
}
while(null != entry) {
if(entry.key == k entry.key.equals(k)) {
return entry.value;
}
entry = entry.next;
}
return null;
}
扩容方法
private void reSize(int newSize) {
MapItemK, V[] newTable = new MapItem[newSize];
max = (int)(newSize DEFAULT_CAPACITY);
for(int j = 0; j itemTable.length; j++) {
MapItemK, V entry = itemTable[j];
entry是linklist
while(null != entry) {
setMapItem(entry, newTable);
entry = entry.next;
}
}
itemTable = newTable;
}
将元素挂在队尾
private void addEntry2Last(MapItemK, V entry, MapItemK, V tmp) {
if(size max) {
reSize(itemTable.length 2);
}
entry.next = tmp;
}
根据hash码，容器长度计算hash码在数组中的下标值
public int indexFor(int hashcode, int itemLength) {
return hashcode & (itemLength - 1);
}
不冲突时直接添加元素
private void setFirstEntry(MapItemK, V tmp, int index, MapItem[] table) {
if(size max) {
reSize(table.length 2);
}
table[index] = tmp;
tmp.next = null;
}
}
public class Main {
public static void main(String args[]) {
MyHashMapString, Integer map = new MyHashMapString, Integer();
map.put(BryantChang, 1);
map.put(WangYueHan, 2);
System.out.println(map.get(BryantChang));
}
}