CODEWITHSUNDEEP
data-structureshashhashtable
Alex.Kh
Alex.Kh

Reputation: 612

Inserting an element to a full hash table with a constant number of buckets

I am studying hash table at the moment, and got a question about its implementation with a fixed size of buckets.

Suppose we have a hash table with 23 elements(for example). Let's use the simplest hash function (hash_value = key%table_size) and the keys being integers only. If we say that one bucket can have at most only 1 element(no separate chaining), does it mean that when all buckets are full we will no longer be able to insert any element in the table at all? Or will we have to actually replace element that has the same hash value with a new element?

I do understand that I am putting a lot of constrains , and the real implementation might never look like that,but I want to be sure I understand that particular case.

Upvotes: 0

Views: 1179

Answers (2)

Gene
Gene

Reputation: 46990

Yes. An "open" hash table - which you are describing - has a fixed size, so it can fill up.

However implementations will usually respond by copying all contents into a new, bigger table. In fact, normally they won't wait to fill entirely, but use some criterion - for example a fraction of all space used (sometimes called the "load factor") - to decide when it's time to expand.

Some implementations will also "shrink" themselves to a smaller table if the load factor becomes too small due to deletions.

You'd probably find reading Google's hash table implementation, which includes some documentation of its internals, to be a good learning experience.

Upvotes: 1

LeoVen
LeoVen

Reputation: 672

A real implementation usually allows for a hash table to be able to resize, but this usually takes a long time and is undesired. Considering a fixed-size hash table, it would probably return an error code or throw an exception for the user to treat that error or not.

Or will we have to actually replace element that has the same hash value with a new element?

In Java's HashMap if you add a key that equals to another already present in the hash table only the value associated with that key will be replaced by the new one, but never if two keys hash to the same hash.

Upvotes: 2

Related Questions