0

I'm really new to HashTables and I'm having a hard time understanding, the process of collision handling, and increasing it's capacity if we run out of space and how does the loadFactor come into play when measuring the available space and capacity? If any code could be provided would really help and appreciated. Side Note: I'm not allowed to use the available class so I have to implement it on my own.

Here's my put method that I override from the interface.

@Override
public String put(String key, String value) {


    int i = key.hashCode();
    int hash = (i % capacity);

    while (table[hash] != null && table[hash].key() != key)
    {
        if(hash > loadFactor*capacity)
        {
            capacity = capacity*2; 
        }

        if(hash == TABLE_SIZE)
        {
            return null; 
        }

        hash = (hash + 1) % capacity;
    }

    System.out.println("Collision Detected");

    String oldKey = table[hash].key();
    String oldValue = table[hash].value(); 

    //replace old value with the new
    table[hash] = new Entry(key, value);


    //return "index " + i + " hash " + hash; 
    return "Old key: " + oldKey + ", Old Value: " + oldValue;
}
user2268636
  • 11
  • 1
  • 5
  • 3
    I think you should step away from code and read a good textbook, e.g., CLRS has a great chapter about hash tables. – Giovanni Botta Mar 18 '14 at 03:22
  • Also, if you want to see an actual code example, check out Java's [`HashMap` implementation](http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/HashMap.java?av=f), in particular, `put()`, `addEntry()`, and `resize()`. For a good online read, make a cup of coffee and check out http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_hashtable.aspx, which is well-written (despite its hideous gray-blue background) and goes into great detail about all aspects of hash table implementation. – Jason C Mar 18 '14 at 03:23
  • `Linked List Hashtable` handles collisions quite nicely if you want to look into that approach. – Tdorno Mar 18 '14 at 03:25
  • Related (collisions): http://stackoverflow.com/questions/4980757/how-do-hashtables-deal-with-collisions?rq=1 – Jason C Mar 18 '14 at 03:28

0 Answers0