yes I have read the thread thank you very much
has anyone thought about using crit-bit / patricia trees?
they seem to give the same functionality of hash-tables, with
guaranteed performance (no worst case), and the capability to
support in-order scan of the tree; see:
https://cr.yp.to/critbit.html
about the performance: worst case is proportional to the
length of the key, not the number of elements in the tree; the
key is checked bit-by-bit (or byte-by-byte); no expensive key
comparisn (I am thinking about strcmp); there is no hash
involved, so no risk of flooding.
In fact I discovered this when thinking about the security
of the hash function used in Lua - it seems many other
languages already adopted SipHash which gives the strong
guarantee that no one can predict the hash of new data even if
they have seen the hash of previous data; look at
the wikipedia entry and here
https://131002.net/siphash/ on
the latter site there is a link to the presentation
https://cr.yp.to/talks/2012.12.12/slides.pdf where
crit-bit trees are mentioned as the preferred solution (rather
than using hash-table with secure hash functions)
so did anyone try with crit-bit/patricia trees?
Andrea
As I replied in another message, it is
absolutely NOT necessary to have ANY chaining pointer per
node: collision lists can just add (resp. substrict) a
constant prime to the current node index (and take the
result module the hash table size), to find the next
(resp.) previous node in the chain, until you find the
node with the correct hash or a null node.
--
