The java.util.HashSet and java.util.HashMap use hash code indexed array as its backend data-structure. Hash Table keys are not sorted, the order is random.
Code:
import java.util.*;
public class test {
public static void main(String...args) {
Set<Integer> set = new HashSet<>();
Map<Integer, String> map = new HashMap<>();
set.add(100);
set.add(10);
set.add(5);
set.add(3);
set.add(30);
set.stream().forEach(System.out::println);
System.out.println("=========");
map.put(100, "one hundred");
map.put(10, "ten");
map.put(5, "five");
map.put(3, "tree");
map.put(30, "thirty");
map.values().stream().forEach(System.out::println);
}
}
Here is a simple example of Hash Table.
//Time: O(N/M), Space: 48N + 32M
public class SeperateChainST<Key, Value> {
private int M;
private SeqST<Key, Value>[] st;
public SeperateChainST(int M) {
this.M = M;
st = (SeqST<Key, Value>[])new SeqST[M];
for(int i = 0; i < M; i++) {
st[i] = new SeqST<>();
}
}
public Value get(Key key) {
return (Value)st[hashCode(key)].get(key);
}
public void put(Key key, Value val) {
st[hashCode(key)].put(key, val);
}
private int hashCode(Key key) {
return (key.hashCode() & 0x7fffffff) % M;
}
private class SeqST<Key, Value> {
private Node first;
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 = first; x != null; x = x.next) {
if(x.key == key) return x.val;
}
return null;
}
public void put(Key key, Value val) {
for(Node x = first; x != null; x = x.next) {
if(x.key.equals(key)) {
x.val = val; return;
}
}
first = new Node(key, val, first);
}
}
public static void main(String...args) {
SeperateChainST<Integer, String> map = new SeperateChainST<>(998);
map.put(100, "one hundred");
map.put(10, "ten");
map.put(5, "five");
map.put(3, "tree");
map.put(30, "thirty");
System.out.println(map.get(5));
System.out.println(map.get(100));
System.out.println(map.get(500));
}
}
