-
-
Notifications
You must be signed in to change notification settings - Fork 299
/
706.java
146 lines (126 loc) · 3.25 KB
/
706.java
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
__________________________________________________________________________________________________
sample 52 ms submission
class MyHashMap
{
ListNode[] nodes = new ListNode[10000];
public int get(int key)
{
int index = getIndex(key);
ListNode prev = findElement(index, key);
return prev.next == null ? -1 : prev.next.val;
}
public void put(int key, int value)
{
int index = getIndex(key);
ListNode prev = findElement(index, key);
if (prev.next == null)
prev.next = new ListNode(key, value);
else
prev.next.val = value;
}
public void remove(int key)
{
int index = getIndex(key);
ListNode prev = findElement(index, key);
if(prev.next != null)
prev.next = prev.next.next;
}
private int getIndex(int key)
{
return Integer.hashCode(key) % nodes.length;
}
private ListNode findElement(int index, int key)
{
if(nodes[index] == null)
return nodes[index] = new ListNode(-1, -1);
ListNode prev = nodes[index];
while(prev.next != null && prev.next.key != key)
{
prev = prev.next;
}
return prev;
}
private static class ListNode
{
int key, val;
ListNode next;
ListNode(int key, int val)
{
this.key = key;
this.val = val;
}
}
}
__________________________________________________________________________________________________
sample 42908 kb submission
class MyHashMap {
Node[] tab;
int size;
/** Initialize your data structure here. */
public MyHashMap() {
// int i = 1;
// while(i <= 10000) {
// i = i << 1;
// }
size = 16384;
tab = new Node[size];
}
/** value will always be non-negative. */
public void put(int key, int value) {
Node n = find(key);
if (n != null) {
n.val = value;
} else {
int index = idx(key);
Node newN = new Node(key, value);
newN.next = tab[index];
tab[index] = newN;
}
}
/** 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) {
Node n = find(key);
if (n != null) {
return n.val;
} else {
return -1;
}
}
/** Removes the mapping of the specified value key if this map contains a mapping for the key */
public void remove(int key) {
Node n = find(key);
if (n != null) {
n.val = -1;
}
}
private int idx(int key) {
return (size-1) & (key ^ (key >>> 10));
}
private Node find(int key) {
Node cur = tab[idx(key)];
while(cur != null) {
if (cur.key == key) {
return cur;
}
cur = cur.next;
}
return null;
}
class Node {
int val;
int key;
Node next;
Node(int key, int val) {
this.val = val;
this.key = key;
}
}
}
/**
* 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);
*/
__________________________________________________________________________________________________