Re: [Devel] FTC_Manager - crashing on 'FTC_Manager_Done'

[Nathan Hurst]

On Tue, 5 Dec 2000, David Turner wrote:

> if you have comments on them:
> 
>   - dynamic hash tables are nice and flexible, but each re-sizing operation
>     needs a complete re-computation of the hash value for all of the table's
>     nodes. This _is_ a problem when you have a slow processor with lots of
>     cached nodes, because it will somewhat "stall" your application..
> 
>   - using a one-level hashing scheme, by embedding glyph set information
>     within the cache node themselves. Using a static or dynamic hash table
>     would also mean
> 
>   - using trees. This seems to be much more reasonable, because the cost
>     of re-ordering the structure is paid on each insertion/removal, instead
>     of a one big stop as in the case of dynamic hash tables, however, I'm
>     unsure they'll perform better than hash tables for fast lookups (my
>     past experience tells me that they're usually slightly slower than
>     hashes in numerous occasions, so testing is needed).

I think the 'right' way to do it would be to compute an efficient hash
which gives good mixing across bits (md5 is good, probably somethingfish
too) and making the hash table take n bits from the hash then use
something like a patricia from the base table.  The table can be grown by
simply splitting each node into two corresponding to the left and right
sub trees hanging from the previous node.  the cost of rehashing is then
both linear in the table size(not the number of elements) and very quick.
By using a large hash space(lots of bits), and having good mixing, you can
avoid changing the hash for each size, and avoid having to move each
element around by itself.

njh