Skip to content

Instantly share code, notes, and snippets.

@tzafrir

tzafrir/Main.java

Created September 18, 2012 18:33
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save tzafrir/3744906 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save tzafrir/3744906 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. tzafrir created this gist Sep 18, 2012.
    95 changes: 95 additions & 0 deletions Main.java
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,95 @@
    import java.util.LinkedList;
    import java.util.ListIterator;
    import java.util.Random;

    public class Main {
    public static void main(String args[]) {
    HashTable t = new HashTable();
    t.insert(70000, "Lonely");
    Random r = new Random();
    for (int i = 0; i < 40000 * 97; ++i) {
    t.insert(r.nextInt(60000), "" + i);
    }
    t.allSizes();
    System.out.println("- -");
    System.out.println(t.get(70000));
    System.out.println(t.size());
    t.remove(70000);
    System.out.println(t.get(70000));
    System.out.println(t.size());
    }
    }

    class HashTable {
    private static final int PRIME = 97;

    static int hash(int num) {
    return (int)Math.abs(Math.floor(num * 33)) % PRIME;
    }

    class Node {
    int key;
    String value;
    Node(int key, String value) {
    this.key = key;
    this.value = value;
    }

    public int key() {return key;};
    public String value() {return value;};
    }

    LinkedList<Node>[] table;
    int size;

    HashTable() {
    table = new LinkedList[PRIME];
    size = 0;
    }

    public void insert(int key, String value) {
    final int hash = hash(key);
    if (table[hash] == null) {
    table[hash] = new LinkedList<Node>();
    }
    table[hash].add(0, new Node(key, value));
    ++size;
    }

    public String get(int key) {
    final int hash = hash(key);
    if (table[hash] == null) {
    return null;
    }
    for (Node n : table[hash]) {
    if (n.key() == key) {
    return n.value();
    }
    }
    return null;
    }

    public void remove(int key) {
    final int hash = hash(key);
    final LinkedList<Node> l = table[hash];
    if (l != null) {
    ListIterator<Node> li = l.listIterator();
    while (li.hasNext()) {
    if (li.next().key() == key) {
    li.remove();
    --size;
    }
    }
    }
    }

    public int size() {
    return size;
    }

    public void allSizes() {
    for (int i = 0; i < table.length; ++i) {
    System.out.println(i + ": " + (table[i] == null ? 0 : table[i].size()));
    }
    }
    }