Search code examples
algorithmdata-structureshashtablechaining

Hash Table with Chaining (Table Doubling)


  1. How to fix the Hash Table with Chaining when all the Items hash into same slot (One giant LinkedList)?
  2. Does Hash Table with Chaining uses Table Doubling? If so when is the good time to Double the size of the Table.

Solution

  • Expanding on the answer from NikiC's comments:

    For your first question, this is unfortunately a real possibility when implementing a chained hash table. Assuming that you have a good hash function - or, better yet, by choosing a hash function that involves some element of randomness - this is extremely unlikely. Unfortunately, Bad People sometimes use this to take down web servers. Not too long ago, an attack called a "Hash DoS" was developed whereby someone would craft a bunch of specialized requests to a web server that would cause everything to get stored in the same slot in a chained hash table, which led to huge performance drops and eventually took some websites offline. The good news, though, is that many programming language implementations have been updated so that their hash tables aren't vulnerable to things like this.

    For your second question, the answer is "it depends." Most good implementations of chained hash tables do rehash and grow when the load factor gets too high (usually, load factors between 1 and 2 are common). Some implementations do not, though. For example, the ConcurrentHashMap implementation in Java, I believe, does not do any rehashing because doing so is not feasible when many reads and writes are executing concurrently.