Skip to content

Instantly share code, notes, and snippets.

@lowasser
Forked from anonymous/Test.java
Created August 1, 2012 19:26
Show Gist options
  • Save lowasser/3229940 to your computer and use it in GitHub Desktop.
Save lowasser/3229940 to your computer and use it in GitHub Desktop.
HashTable as array of Linked Lists
class Node {
public int data;
public Node next;
public Node(int data, Node next) {
this.data = data; this.next = next;
}
}
class LongIntParallelHashMultimap {
Node[] l ;
public LongIntParallelHashMultimap() {
l = new Node[Integer.MAX_VALUE];
}
public void load(){
}
public void put(int key, int value) {
// Assume ordering is significant, for now.
Node prev = l[key];
if (prev == null) {
l[key] = new Node(value, null);
} else {
while (prev.next != null) {
prev = prev.next;
}
prev.next = new Node(value, null);
}
}
public int[] get(int key) {
// Re-counting the values every time is...probably actually better than storing the counts.
// Based on the listed RAM constraints, we almost certainly cannot afford the overhead of
// the LinkedList objects.
// Anyway, with an average count around 3, this shouldn't be a significant hit.
int count = 0;
for (Node n = l[key]; n != null; n = n.next) {
count++;
}
int[] result = new int[count];
int i = 0;
for (Node n = l[key]; n != null; n = n.next) {
result[i++] = n.data;
}
return result;
}
public void save() {
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment