A simpler way to do text matching since suffix array is the preorder traversal of a suffix trie constructed using the same string. Not heavily used in practice, but I do know bioinfo people used it a lot.
Not a data structure, but still very underrated. Robinhood hash basically means you keep the first insertion order and the actual insertion order and compare their distance. Once the difference is bigger than expected, you put it in front to "steal from the rich" to have better expected access distribution, hence Robinhood. Getting more prominent today thanks to Rust popularizing it again, since the default hash table implementation of Rust uses hashbrown which uses Robinhood hashing scheme.
A suffix array is useful as a part of binary diff, finding a longest matching substring to copy from an old file. Bsdiff makes heavy use of this, it's used in Courgette for patching after preprocessing.
Fibonacci heap is theoretically better than Binary heap but the cache behavior is terrible
https://en.wikipedia.org/wiki/Van_Emde_Boas_tree?wprov=sfla1
Well, I saw this in CLRS tho. Very clever way of abusing bit patterns for quick range query in O(log log M) where M is the integer size.
https://en.wikipedia.org/wiki/Suffix_array?wprov=sfla1
A simpler way to do text matching since suffix array is the preorder traversal of a suffix trie constructed using the same string. Not heavily used in practice, but I do know bioinfo people used it a lot.
https://study.com/academy/lesson/robin-hood-hashing-concepts...
Not a data structure, but still very underrated. Robinhood hash basically means you keep the first insertion order and the actual insertion order and compare their distance. Once the difference is bigger than expected, you put it in front to "steal from the rich" to have better expected access distribution, hence Robinhood. Getting more prominent today thanks to Rust popularizing it again, since the default hash table implementation of Rust uses hashbrown which uses Robinhood hashing scheme.
https://en.wikipedia.org/wiki/Skip_list?wprov=sfla1
The ordered linked list with a fast lane every log(n) level. Not used very much, but one of the place I know uses it is Redis
https://en.wikipedia.org/wiki/Double-ended_priority_queue?wp...
Basically one priority queue that does two things. Can ironically be implemented with two priority queues (dual)