   Question about double Hashing
  I am trying to write a HashTable and I encountered a problem thats confusing me.Hopefully someone can clarify. The problem is with the double hashing part. I hope an example will best explainthe problem :Say this is the initial call ://my own HashTable objectHashTable<String,Integer> hs = new HashTable<String,Integer>(11);hs.put("AAA",1); //maps to 8hs.put("BBB",2); //maps to 0hs.put("CCC",3); //maps to 3hs.put("DDD",4); //maps to 6hs.put("EEE",5); //maps to 9hs.put("FFF",6); //maps to 1hs.put("GGG",7); //maps to 4hs.put("HHH",8); //maps to 7hs.put("III",9); //maps to 10hs.put("JJJ",10); //maps to 2hs.put("random",11); //maps to 9 -- collision occurs see belowso in the last call there is a collision, the key mapped to 9, initially.But we use the double hashing technique now to get a different index. In mycode, this is the relevant part for the double hashing :else //collision, so rehash{ int j = 0; //look more open spots while(_array[index] != null && _array[index] != OPEN){   ++j;   index = (index + _rehash(j,entry.getKey().hashCode())) % _array.length; }}and my _rehash function is this :private int _rehash(int j, int k){ int q = getPrime(true); //get prime under array capacity return j*(q - (k % q));}so you are asking whats the problem , right ? The problem is that whena collision occurs the program enters the else loop shown above, and insidethe else loop we look for a different available index. This is where the problemoccurs. Realize that the hashtable object, hs, has only the slot 5 left open, since nothing mapped to it yet. But my while loop, where i look for open slots, never maps to 5 for the particular hashcode that the key "random" produced. The while loop repeats a pattern like 10,1,4,8,2,8,4,1,1,0,9,9. So it goes into an infinite loop. My hashtable size is 11, the "q" in q = getPrime(true) is equal to 7. By the way, the _rehash function I am using is a method from my book, it says use a second hash function of the form j*h`(k), where h`(k) = q-(k mod q), for some q < N, where N is the capacity of the array. I hope someone can help me please. I have spent too much time on this. I must be doing something wrong. But then again, before I implement the doublehashing, I was wondering what if the sequence produced by the second hashdoes not map to an open slot, even if there is one. At effectively, I haveran into this problem. I have taken the time to write this, with the hope that someone can help me. I have searched online as well, but was confusedstill. Thank you for reading at least.   
  It's possible to enter an infite loop in a hash ifa) the hash function is bad (too many entries map to the same spaces, doesn't map all spaces at all)b) the container is too small. With hash maps you won't always get the optimal result "I have 10 values to store so I only need a container of size 10".The hashing function is fundamental for this container type, you should read this article for more information. It's a math problem, not programming.http://en.wikipedia.org/wiki/Hash_function   ;  http://en.wikipedia.org/wiki/Linear_probingor Use a linked list or something at each hash elements so collisions are added to the list at each hash element.http://en.wikipedia.org/wiki/Hash_table#Separate_chaining   ;  Oh ok, so I'm not going crazy, it could happen. Yea, the load factor is wellover 0.5 which is recommended for open addressing, because there are 10 elementsin a 11 capacity so 10/11 = 0.91. I am not trying to use chaining, becausethis is a h.w and it needs to be implemented by open addressing/double hashingmethod. This class is called a HashTable, we have also been given a SmartHashTablewhere SmartHashTable extends HashTable but implements a grow() function togrow the array to keep the load factor small. So I don't think we aresupposed to grow the bucket array. Anyone have some idea on how to solve this?   