Skip to content

Instantly share code, notes, and snippets.

Created August 1, 2012 19:24
Show Gist options
  • Save anonymous/3229931 to your computer and use it in GitHub Desktop.
Save anonymous/3229931 to your computer and use it in GitHub Desktop.
HashTable as array of Linked Lists
class Node {
public int data;
public Node pointer;
}
class LinkedList {
Node first;
int count = 0;
public void add(int data){
if(first == null){
Node node = new Node();
node.data = data;
node.pointer = null;
first = node;
count = 1;
return;
}
Node next = first;
while(next.pointer != null){
next = (Node)next.pointer;
}
Node newNode = new Node();
newNode.data = data;
newNode.pointer = null;
next.pointer = newNode;
count++;
}
public Node getFirst(){
return first;
}
public Node getLast(){
Node next = first;
while(next.pointer != null)
next = next.pointer;
return next;
}
public int[] get(){
if(count != 0){
int arr[] = new int [count] ;
Node next = first;
int i = 0;
arr[0]= next.data;
while(next.pointer != null){
next = next.pointer;
i++;
arr[i] = next.data;
}
i++;
return arr ;
}
return null ;
}
public int count(){
return count;
}
}
class LongIntParallelHashMultimap {
LinkedList[] l ;
public LongIntParallelHashMultimap() {
int i = 0;
try{
l = new LinkedList[214748364];
for (i=0; i<214748364; ++i){
l[i] = new LinkedList(); // initialize linked lists
if(i % 10000000 == 0)
System.out.println("OK"); // just to check how often linked lists are created
}
}catch (Exception e) {
System.err.println(i);
}
}
public void load(){
}
public void put(int key, int value) {
l[key].add(value);
}
public int[] get(int key) {
int k[] = l[key].get();
return k ;
}
public void save() {
}
}
public class Test{
public static void main(String args[]) {
try {
long startTime = System.nanoTime();
LongIntParallelHashMultimap lph = new LongIntParallelHashMultimap();
long endTime = System.nanoTime() - startTime;
System.out.println(endTime);
startTime = System.nanoTime();
for (int i= 0 ; i < 2500000 ; i++)
lph.put(i, i+100);
endTime = System.nanoTime() - startTime;
System.out.println(endTime);
startTime = System.nanoTime();
startTime = System.nanoTime();
for (int i= 0 ; i < 100 ; i++){
int k[] = lph.get(i);
System.out.print(k[0] + " ");
}
endTime = System.nanoTime() - startTime;
System.out.println(endTime);
} catch (Exception e) {
System.err.println("Error: " + e.getMessage());
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment