_______________________________________________I found this https://github.com/andreasvc/critbit/commit/dbe428849bf27f5e2717ef66362c5e8b0a22d3f0 saying that it is not competitive with hash tables.
On 12/5/20 17:35, Andrea wrote:
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
On Tue, May 12, 2020 at 2:58 AM Philippe Verdy <verdyp@gmail.com> wrote:
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.--
Andrea Vitali
_______________________________________________ lua-l mailing list -- lua-l@lists.lua.org To unsubscribe send an email to lua-l-leave@lists.lua.org
lua-l mailing list -- lua-l@lists.lua.org
To unsubscribe send an email to lua-l-leave@lists.lua.org
_______________________________________________ lua-l mailing list -- lua-l@lists.lua.org To unsubscribe send an email to lua-l-leave@lists.lua.org