CODEWITHSUNDEEP
javadata-structurescomplexity-theorydouble-hashing
user1897602
user1897602

Reputation:

Hash by Chaining VS Double Probing

I'm trying to compare between Chaining and Double probing. I need to insert 40 integers to table size 100, when I measure the time with nanotime (in java) I get that the Double is faster. thats because in the Insert methood of Chaining, I create every time LinkedListEntry, and it's add time. how can it be that Chaining is more faster than Double probing ? (that's what i read in wikipedia)

Thanks!!

this is the code of chaining:

public class LastChain
{
    int tableSize;
     Node[] st;
    LastChain(int size) {
        tableSize = size;
        st = new Node[tableSize];
        for (int i = 0; i < tableSize; i++)
            st[i] = null;
    }

    private class Node
    {
        int key;
        Node next;
        Node(int key, Node next)
        {
            this.key   = key;
            this.next  = next;
        }
    }

    public void put(Integer key) 
    {
       int i = hash(key);
       Node first=st[i];
       for (Node x = st[i]; x != null; x = x.next)
          if (key.equals(x.key))
             { 
             return; 
              }

       st[i] = new Node(key, first);

    }


    private int hash(int key)
    {  return key%tableSize;
    }

      }
}

and this is the relevant code from double probing:

public class HashDouble1 {
  private Integer[] hashArray; 

  private int arraySize;

  private Integer bufItem; // for deleted items

  HashDouble1(int size) {
    arraySize = size;
    hashArray = new Integer[arraySize];
    bufItem = new Integer(-1);
  }



  public int hashFunc1(int key) {
    return key % arraySize;
  }

  public int hashFunc2(int key) {
    return 7 - key % 7;
  }

  public void insert(Integer key) {
        int hashVal = hashFunc1(key); // hash the key
        int stepSize = hashFunc2(key); // get step size
        // until empty cell or -1
        while (hashArray[hashVal] != null && hashArray[hashVal] != -1) {
          hashVal += stepSize; // add the step
          hashVal %= arraySize; // for wraparound
        }
        hashArray[hashVal]  = key; // insert item
      }





}

in this way the insert in Double is more faster than Chaining. how can i fix it?

Upvotes: 1

Views: 841

Answers (2)

tjltjl
tjltjl

Reputation: 1479

Java has the special "feature" Objects take up a lot of memory.

Thus, for large datasets (where this will have any relevance) double probing will be good.

But as a very first thing, please change your Integer[] into int[] -> the memory usage will be one fourth or so and the performance will jump nicely.

But always with performance questions: measure, measure, measure, as your case will always be special.

Upvotes: 0

Peter Lawrey
Peter Lawrey

Reputation: 533500

Chaining works best with high load factors. Trying using 90 strings (not a well places selection of integers) in a table of 100.

Also chaining is much easier to implement removal/delete for.

Note: In HashMap, an Entry object is created whether it is chained or not, not there is no saving there.

Upvotes: 1

Related Questions