Re: is it true that hash-tables increase their capacity to the next prime number?
- From: Harald Hanche-Olsen <hanche@xxxxxxxxxxxx>
- Date: Thu, 31 Jan 2008 20:13:31 +0100
+ Kaz Kylheku <kkylheku@xxxxxxxxx>:
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
.
- References:
- adjustable array vs hash-table
- From: Slobodan Blazeski
- Re: adjustable array vs hash-table
- From: Xah Lee
- Re: adjustable array vs hash-table
- From: Slobodan Blazeski
- is it true that hash-tables increase their capacity to the next prime number?
- From: Slobodan Blazeski
- Re: is it true that hash-tables increase their capacity to the next prime number?
- From: Kaz Kylheku
- adjustable array vs hash-table
- Prev by Date: Re: Paul Graham's Arc is released today... what is the long term impact?
- Next by Date: Re: Order of macroexpansion
- Previous by thread: Re: is it true that hash-tables increase their capacity to the next prime number?
- Next by thread: Re: adjustable array vs hash-table
- Index(es):
Relevant Pages
|
