-
Notifications
You must be signed in to change notification settings - Fork 11
Expand file tree
/
Copy pathDesignHashmap.java
More file actions
153 lines (132 loc) · 3.94 KB
/
DesignHashmap.java
File metadata and controls
153 lines (132 loc) · 3.94 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
/**
* LeetCode 706 https://leetcode.com/problems/design-hashmap/
*/
class MyHashMap {
private class Pair {
private int key;
private int value;
public Pair(int key, int value) {
this.key = key;
this.value = value;
}
public int getKey() {
return key;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
}
private static final int BASE = 769;
private LinkedList[] data;
// initialize the data structure in constructor
public MyHashMap() {
data = new LinkedList[BASE];
for (int i = 0; i < BASE; i++) {
data[i] = new LinkedList<Pair>();
}
}
// inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.
public void put(int key, int value) {
int k = hash(key);
Iterator<Pair> iterator = data[k].iterator();
while (iterator.hasNext()) {
Pair pair = iterator.next();
if(pair.getKey() == key) {
pair.setValue(value);
return;
}
}
data[k].offerLast(new Pair(key, value));
}
// returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
public int get(int key) {
int k = hash(key);
Iterator<Pair> iterator = data[k].iterator();
while (iterator.hasNext()) {
Pair pair = iterator.next();
if (pair.getKey() == key) {
return pair.value;
}
}
return -1;
}
// removes the key and its corresponding value if the map contains the mapping for the key.
public void remove(int key) {
int k = hash(key);
Iterator<Pair> iterator = data[k].iterator();
while(iterator.hasNext()) {
Pair pair = iterator.next();
if (pair.getKey() == key) {
data[k].remove(pair);
return;
}
}
}
private static int hash(int key) {
return key % BASE;
}
}
/**
* Your MyHashMap object will be instantiated and called as such:
* MyHashMap obj = new MyHashMap();
* obj.put(key,value);
* int param_2 = obj.get(key);
* obj.remove(key);
*/
class MyHashSet {
private static int BASE = 769;
private LinkedList[] data;
// initialize the data structure in constructor
public MyHashSet() {
data = new LinkedList[BASE];
for (int i = 0; i < BASE; i++) {
data[i] = new LinkedList<Integer>();
}
}
public void add(int key) {
int k = hash(key);
Iterator<Integer> iterator = data[k].iterator();
while (iterator.hasNext()) {
int element = iterator.next();
if (element == key) {
return;
}
}
data[k].offerLast(key);
}
public void remove(int key) {
int k = hash(key);
Iterator<Integer> iterator = data[k].iterator();
while (iterator.hasNext()) {
Integer element = iterator.next();
if (element == key) {
data[k].remove(element);
return;
}
}
}
public boolean contains(int key) {
int k = hash(key);
Iterator<Integer> iterator = data[k].iterator();
while (iterator.hasNext()) {
Integer element = iterator.next();
if (element == key) {
return true;
}
}
return false;
}
private static int hash(int key) {
return key % BASE;
}
}
/**
* Your MyHashSet object will be instantiated and called as such:
* MyHashSet obj = new MyHashSet();
* obj.add(key);
* obj.remove(key);
* boolean param_3 = obj.contains(key);
*/