3 ms·
Ask HN: What is your favourite data structure and why?
Apart from the well known ones, have you come across any very useful data structure which is not yet mainstream?
- techstrategist 7y agoIf 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?
- ghoshbishakh 7y agoYes! 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.
- keyP 7y agoI'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-should-be-your-default-hash-table-implementation/ 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-hashing-2/ https://www.sebastiansylvan.com/post/more-on-robin-hood-hash... [3]https://study.com/academy/lesson/robin-hood-hashing-concepts-algorithms.html https://study.com/academy/lesson/robin-hood-hashing-concepts...