Re: maintenance of hash tables.



On Jun 29, 11:58 am, mohangupta13 <mohangupt...@xxxxxxxxx> wrote:
hello everyone,
This may sound pretty basic but still I have this doubt.
It is know that to maintain the constant time operations in a hash
table the number of elements in the table should be proportional to
the slots in the table.
But I have seen in a lot many places that to maintain this, whenever
the number of elements in a hash table reach half the table size ,the
size of the table is doubled.

Why this factor of 2 (only)  is chosen most of the time??

Look at this diagram:

-A
-BB
-
-CCCC
-
-
-
-DDDDDDDD
-
-
-
-
-
-
-

Now look what happens when I let the towers hang down:

-A
-B
-B
-C
-C
-C
-C
-D
-D
-D
-D
-D
-D
-D
-D

Enjoy,
Andrew.
.