3 ms·

I'm generally a big fan of DJB, but I see a few problems with this scheme. First, it seems like the prefix-free requirement means that the strings can't contai

by chubot 10y ago

I'm generally a big fan of DJB, but I see a few problems with this scheme. First, it seems like the prefix-free requirement means that the strings can't contain internal NUL bytes. In Python you can store 'a\0' as well as 'a\0b' in a hash table -- how do you handle this with crit-bit trees? Second, in Python, unlike JavaScript, arbitrary types can be hashable. Tuples are hashable. How do you store ('a', 0) and ('b', 1) as keys in a crit-bit tree?

eutectic 10y ago
Just store a bit (for a set) at each internal node, denoting whether a string ends there. For a map you also need a value pointer. Hashing keys is also easy: add a pointer to a linked list of key-value pairs to each leaf node. To save space you could even use a flag bit and then a pointer to a single key-value pair, or a linked list in case of collision. Note that you can store tuples directly as the concatenation of their fields; no need to use hashing.
- socmag 10y ago
  What are you talking about. How do tuples preclude the requirement of a way to hash? That's a very naive way to map using the delimeter of the tuple parts. You might have interior elements that are 10k long.
  - eutectic 10y ago
    And strings can also be long.
socmag 10y ago
I'm using Cedar to store arbitrary order preserving tuples. After a lot of perf testing, and that library along with others had the same issue with not allowing null bytes. Initially i thought it was a deal breaker, especially since I needed to preserve order. Ended up doing a possibly mutating prepass on any keys keys that might contain nulls (Which is generally very fast O(len(key)) before storing, to rewrite without them. It was still worth it.