参考“705. 设计哈希集合”。
指针(引用)
拉链法
class MyHashMap {
final int N = (int)1e4 + 3;
LinkedList<Node>[] h = new LinkedList[N];
class Node {
int key, value;
public Node() {}
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
public MyHashMap() {
for (int i = 0; i < N; ++i) {
h[i] = new LinkedList<>();
}
}
public void put(int key, int value) {
int k = hash(key), t = find(k, key);
if (t == -1) {
h[k].add(new Node(key, value));
} else {
h[k].get(t).value = value;
}
}
public int get(int key) {
int k = hash(key), t = find(k, key);
return t == -1 ? t : h[k].get(t).value;
}
public void remove(int key) {
int k = hash(key), t = find(k, key);
if (t > -1) {
h[k].remove(t);
}
}
int find(int k, int x) {
for (int i = 0; i < h[k].size(); ++i) {
if (h[k].get(i).key == x) {
return i;
}
}
return -1;
}
int hash(int x) {
return (x % N + N) % N;
}
}
/**
* 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 MyHashMap {
final int N = (int)1e4 + 3;
int idx;
int[] h = new int[N], ne = new int[N];
Node[] e = new Node[N];
class Node {
int key, value;
public Node() {}
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
public MyHashMap() {
for (int i = 0; i < N; ++i) {
h[i] = -1;
}
}
public void put(int key, int value) {
int k = hash(key), t = find(k, key);
if (t == -1) {
e[idx] = new Node(key, value);
ne[idx] = h[k];
h[k] = idx++;
} else {
e[t].value = value;
}
}
public int get(int key) {
int k = hash(key), t = find(k, key);
return t == -1 ? t : e[t].value;
}
public void remove(int key) {
int k = hash(key), t = find(k, key);
if (t > -1) {
e[t].key = -1;
}
}
int find(int k, int x) {
for (int i = h[k]; i > -1; i = ne[i]) {
if (e[i].key == x) {
return i;
}
}
return -1;
}
int hash(int x) {
return (x % N + N) % N;
}
}
/**
* 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 MyHashMap {
final int N = (int)2e4 + 3;
Node[] h = new Node[N];
class Node {
int key, value;
public Node() {}
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
public MyHashMap() {
for (int i = 0; i < N; ++i) {
h[i] = new Node(-1, -1);
}
}
public void put(int key, int value) {
int k = find(key);
if (h[k].key == -1) {
h[k].key = key;
}
h[k].value = value;
}
public int get(int key) {
int k = find(key);
return h[k].key == -1 ? h[k].key : h[k].value;
}
public void remove(int key) {
int k = find(key);
h[k].key = -1;
}
int find(int x) {
int k = hash(x);
while (h[k].key > -1 && h[k].key != x) {
if (++k == N) {
k = 0;
}
}
return k;
}
int hash(int x) {
return (x % N + N) % N;
}
}
/**
* 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);
*/