Hacker News new | past | comments | ask | show | jobs | submit login

Re: vs. hash tables

Both nedtries (as specified / implemented) and hash tables use fixed length keys. Either can be implemented with an arbitrary fixed length, but both are fixed.

The reason you can store arbitrary length keys in hash tables is only because you hash the key to a fixed length and then specify some form of collision resolution.

This hashing means, of course, that you lose order (disallowing what this author calls "nearest fit" searches). But, if you are considering using hash tables for your use case, you already don't care about that feature.

In the case of nedtries, you don't even need to do anything fancy (linear probing) or use a secondary data structure (chaining): as nedtries already allow you to store the same value twice (so he said... I didn't pay attention to how; worst case you can use chaining ;P) you can make the same tradeoff.

I guess you could argue this is an unrelated data structure, a "hash nedtrie", but if you are comparing the overall abilities of these data structure concepts it seems unfair to not point this out, especially given that it doesn't require changing his implementation (the user can do the disambiguation, as they may even be used to doing anyway with hash tables).




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: