Lisp - Re: is it true that hash-tables increase their capacity to the next prime number?

You are viewing an archived Text-only version of the thread. To view this thread in it's original format and/or if you want to reply to this thread please [click here]

Author

Re: is it true that hash-tables increase their capacity to the next prime number?

Harald Hanche-Olsen

2008-01-31, 7:29 pm

+ Kaz Kylheku <kkylheku@gmail.com>:

> There is also quadratic probing, where a quadratic function is used
> to scan through the entries. For instance hash(key) + i^2, for i =
> 0, 1, 2, ... A prime table size allows quadratic probing to also
> visit all of the nodes.

That doesn't sound right to me. You should get only half of the
nodes, since squaring modulo P is a two-to-one map. More precisely,
n^2 is congruent to (P-n)^2 modulo P.

--
* Harald Hanche-Olsen <URL:http://www.math.ntnu.no/~hanche/>
- It is undesirable to believe a proposition
when there is no ground whatsoever for supposing it is true.
-- Bertrand Russell

Sponsored Links