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.
.

Relevant Pages

  • maintenance of hash tables.
    ... This may sound pretty basic but still I have this doubt. ... It is know that to maintain the constant time operations in a hash ... Mohan Gupta ...
    (comp.programming)
  • Re: maintenance of hash tables.
    ... It is know that to maintain the constant time operations in a hash ... it has to do a lot with the expected growth rate... ... is a very simple expansion, and with a power-of-2 sized table, can keep ...
    (comp.programming)
  • Re: maintenance of hash tables.
    ... It is know that to maintain the constant time operations in a hash ... Imagine you have a vector, and you keep inserting elements, from slot ... When you reach the end of the vector, you allocate a new vector ...
    (comp.programming)
  • Re: [Fwd: Re: No sound problems on Intel board]
    ... |> Hash: SHA1 ... |>> update or other has muted the sound, and you now need to unmute it. ... To UNSUBSCRIBE, email to debian-user-REQUEST@xxxxxxxxxxxxxxxx with a subject of "unsubscribe". ...
    (Debian-User)
  • Re: The "Pound Sign" vs. the "Number Sign"
    ... Does it sound any less wrong if I stick in a comma before the 'nor'? ... I can not recall having heard 'hash include', ...
    (alt.usage.english)