Ask HN: What is your favourite data structure and why?

9 points·ghoshbishakh··3 comments

Apart from the well known ones, have you come across any very useful data structure which is not yet mainstream?

I've not had any particular reason to specifically use this but I found Robin Hood Hashing to be quite an interesting concept. It improves performance by essentially reducing the distance from the key to its matching key-value pair.

Advantages listed from [3]:

- The number and variance of look-ups are reduced

- Searches can be ended early, since 'hits' are found much quicker

- The flat array structure eliminates need for linked lists or pointers: reduces misses and overhead

- Even finding non-existent elements is fast

- This method approaches O(1), meaning the most efficient search

[1]Part 1: https://www.sebastiansylvan.com/post/robin-hood-hashing-shou...

[2]Part 2 (slight update based on suggestions in part 1's comment): https://www.sebastiansylvan.com/post/more-on-robin-hood-hash...

[3]https://study.com/academy/lesson/robin-hood-hashing-concepts...

If I could broaden the question - what have you found useful of the well-known data structures that a self-taught dev may not be fully aware of?

Yes! That also makes sense. But even people going through formal CS education might miss a lot of things.

I learnt something called "Probabilistic Timed Automata". That was actually perfect for one problem we were trying to solve!

I consider Dictionary (Hash Maps) as well known. But bloom filters not so.

Reply on news.ycombinator.com