//Time: O(N/M), Space: 48N + 32M
public class SeperateChainST<Key, Value> {
int M = 0;
private SequentialSearchST<Key, Value>[] st;
private int hash(Key key) {
return (key.hashCode() & 0x7fffffff) % M;
}
public SeperateChainST(int M) {
this.M = M;
st = (SequentialSearchST<Key, Value>[])new SequentialSearchST[M];
for(int i = 0; i < M; i++) {
st[i] = new SequentialSearchST<>();
}
}
public Value get(Key key) {
return (Value)st[hash(key)].get(key);
}
public void put(Key key, Value val) {
st[hash(key)].put(key, val);
}
public int size() {
int cnt = 0;
for(int i = 0; i < M; i++) {
cnt += st[i].size();
}
return cnt;
}
private class SequentialSearchST<Key, Value> {
private Node root;
private class Node {
private Key key;
private Value val;
private Node next;
public Node(Key key, Value val, Node next) {
this.key = key;
this.val = val;
this.next = next;
}
}
public Value get(Key key) {
for(Node x = root; x != null; x = x.next) {
if(key.equals(x.key)) return x.val;
}
return null;
}
public void put(Key key, Value val) {
for(Node x = root; x != null; x = x.next) {
if(key.equals(x.key)) {
x.val = val;
return;
}
}
root = new Node(key, val, root);
}
public int size() {
int cnt = 0;
for(Node x = root; x != null; x = x.next) {
cnt ++;
}
return cnt;
}
}
public static void main(String... args) {
SeperateChainST<Integer, String> st = new SeperateChainST<>(997);
st.put(1, "one");
st.put(4, "four");
st.put(9, "nine");
st.put(4, "IV");
st.put(5, "five");
System.out.println(st.get(5));
System.out.println(st.get(10));
System.out.println(st.get(4));
System.out.println(st.size());
}
}
