>> I've implemented (A) (a counter that tells me when every position
>> had been checked).
> I am affraid that this is not good solution.
As I said. That is only to ensure termination of the search.
> Namely, before you get every position taken by an entry or deleted
> marker you will have period of time when effective load factor for
> insertiong new entries is close to one.
Not necessarily. (Well, it depends, what you mean by "effective load
factor".) I could do something like.
t:=table()
for i in 1..n repeat t.randomkey := ...
for k in keys repeat remove!(k,t)
for i in 1..somebigbound repeat
k := randomkey
t.k := entry
remove!(k,t)
That might mark every position as DELETED. Now the table is empty, but
elt(t,k) would return "failed" only after it has tested every bucket.
> Crude estimate of runtime indicates that average time to insert an
> entry will be of order of logarithm of table size.
Yep, that should be the case, but with double hashing one can get
surprising results. I think it was on a test with 1000 entries (1..1000)
where there was one entry with probing length 22, but none with probing
length 21 or 20 or 19. (no deletion)
> IMHO we should rehash if effective load factor for insertions (that
> is ratio of number of occupied and deleted entires to the table
> size) exceeds some fixed treshold (say 0.8 or 0.9). If load factor
> is small enough (say < 0.6) then keep size, otherwise grow the
> table.
OK, I'll try to implement that. To make it clear, do you want me to set
my current load factor from 0.7 to 0.6. In fact, I thought about
lowering it. The suggestion of 0.75 at
http://docs.oracle.com/javase/1.4.2/docs/api/java/util/Hashtable.html
might be good when all entries with the same hash go into a common
bucket list, but with double hashing the probing might hit entries that
actually come from a totally different bucket position (i.e. probing
sequences mix somehow).
So it's probably better to keep the load factor closer to 1/2.
Ralf
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/fricas-devel?hl=en.
