2013.01.04 06:53:33 (287074267584139264) from Daniel J. Bernstein, replying to "zooko❤ⓩ🛡🦓🦓🦓 (@zooko)" (287056839965827073):
@zooko No. The worst case for a properly implemented crit-bit tree is a few dozen cycles per input byte.
2012.12.31 18:08:42 (285794623971028992) from "zooko❤ⓩ🛡🦓🦓🦓 (@zooko)":
The CCC talk on hash-flooding DoS makes me want to explore balanced trees more: https://www.youtube.com/watch?v=wGYj8fhhUVA
2013.01.01 15:26:54 (286116291499151362) from Daniel J. Bernstein, replying to "zooko❤ⓩ🛡🦓🦓🦓 (@zooko)" (285794623971028992):
If you're not tied to hash tables then I recommend crit-bit trees. See also http://cr.yp.to/talks.html#2012.10.22 ("Data-structure lock-in"). @zooko
2013.01.04 05:44:18 (287056839965827073) from "zooko❤ⓩ🛡🦓🦓🦓 (@zooko)":
@hashbreaker If I understand critbit trees correctly, maliciously chosen values can lead to O(n) complexity to e.g. insert.