Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Ask HN: What are some cool but obscure data structures you know about?

news.ycombinator.com

Post reply on HN
Print view View original

121–130 of 772 posts

Re: Ask HN: What are some cool but obscure data structures you know about?

#121

Post by adgjlsfhk1 »

jefftk wrote: post #109
NSMutableSet wrote: post #75

Earlier quoted context omitted.

I'm not sure what the point of your post is. While bloom filters are heavily used in actual production code throughout the industry, it is very rare for anyone to need to code their own, or make changes to a prior legacy implementation. Not all educational programs will cover bloom filters, and for those that do, there's no guarantee that the students will retain the information, and be able to recall it. I don't kno…

I was with you until the last seven words ;) Trees were a huge part of CS practice and education historically, but have been replaced by hash-based methods in many cases. For example, in C++ std::map is generally a tree, while in a more recent language the standard Map data structure will be a hashmap. My impression is that the instruction time devoted to Bloom filters (and other hash-based methods) vs trees has shif…

a lot of this is that other than heaps, most tree based algorithms involve O(logn) random access pointer lookups which make them relatively slow for in memory data structures

Re: Ask HN: What are some cool but obscure data structures you know about?

#122

Post by bglazer »

loxias wrote: post #64

(Fantastic post idea OP. One of the best I've ever seen :D) Related to bloom filters, xor filters are faster and more memory efficient, but immutable. HyperLogLog is an efficient way to estimate cardinality. Coolest thing I've learned recently was Y-fast trie. If your dataset M is bounded integers (say, the set of all 128 bit numbers), you get membership, predecessor, or successor queries in log log time, not log, li…

I think what you’re describing in the last example is the MinHash algorithm

edit: actually I’m not sure, sounds related though

Re: Ask HN: What are some cool but obscure data structures you know about?

#123

Post by burntsushi »

nicwolff wrote: post #104

The Aho-Corasick automaton [0]. You have a bunch of strings, and you want to know if and where they appear in a longer string. You build a search trie from the strings, but add links back from each node to the node representing the longest suffix of the string it represents that is also in the trie, so you can skip backtracking as you scan, yielding linear time complexity in O(length of string being searched + number…

The aho-corasick Rust crate[1] also provides a way to build the automaton in a slightly different way to provide leftmost first or "preference first" match semantics. This matches how popular backtracking regex engines implement alternations of literals, for example. (It also provides leftmost longest semantics, which matches how POSIX regexes implement alternations.)

[1]: https://docs.rs/aho-corasick

Re: Ask HN: What are some cool but obscure data structures you know about?

#124

Post by gordaco »

Fenwick Trees (which, despite the name, are implemented using an array) allow counting prefix sums AND updating prefix sums in O(log n) time. Very useful when n is in the order of millions. I have used them a few times in Project Euler problems.

https://en.wikipedia.org/wiki/Fenwick_tree

Re: Ask HN: What are some cool but obscure data structures you know about?

#126

Post by andyferris »

ztorkelson wrote: post #57
H8crilA wrote: post #23

Earlier quoted context omitted.

You forgot the most important feature over normal hash maps: they offer a deterministic iteration order without incurring the cost of a tree-based ordered map. (If you don't know why this is important then maybe you haven't worked on large systems that undergo rigorous evaluation)

Is (non-)determinism really the right concern here? I’m aware that most hash tables do not have generally predictable iteration orders, but I nevertheless understood them to be deterministic.

Well, hard/impossible to predict perhaps. Iteration order can depend on the order things were inserted and deleted and may differ from computer to computer (for example in Julia the hash-based dictionary ordering differs between 32 and 64 bit systems, and might change between versions of Julia, etc - you’d see the same thing with C++ unordered maps, etc, etc).

Re: Ask HN: What are some cool but obscure data structures you know about?

#127

Post by andyferris »

H8crilA wrote: post #23
okennedy wrote: post #13

Linked Hash/Tree Maps, simple, but elegant. A Map with its nodes connected in a linked list so you can traverse them in insertion order (and O(n) time). Very useful for window queries over sequential data and other cases where you want FIFO access, but also quick access by a field of the data.

You forgot the most important feature over normal hash maps: they offer a deterministic iteration order without incurring the cost of a tree-based ordered map. (If you don't know why this is important then maybe you haven't worked on large systems that undergo rigorous evaluation)

You can do this without a linked list and it can be quite performant, like python’s newest dictionary implementation (appeared around Python 3.6 or 3.7 from memory).

Re: Ask HN: What are some cool but obscure data structures you know about?

#128

Post by blueblob »

pacaro wrote: post #98
zarzavat wrote: post #55

Spatial hashing. Say that you have data that is identified with points in 2D or 3D space. The standard way that CS students learn in school to represent this is via a quadtree or octree. However, these tree data structures tend to have a lot of "fluff" (needless allocations and pointer chasing) and need a lot of work to be made efficient. Spatial hashing is the stupidly simple solution of just rounding coordinates to…

TBH even quadkeys are a fun answer to OPs question, many people aren't aware of them. Simple explanation: If you have data with x y coordinates and you know the bounds. To compute the quad key for a point: 1. The key starts as the empty string. (I've also seen it start with "Z" to handle points outside the bounds) 2. Divide the space into 4 quadrants 3. determine which quadrant the point falls in, append a letter (A-…

From a basic binary search, this is very intuitive. Your explanation was well written.

Re: Ask HN: What are some cool but obscure data structures you know about?

#129

Post by pianoben »

swizzler wrote: post #125

I like consistent hashing ( https://en.m.wikipedia.org/wiki/Consistent_hashing ). When a hash table (or load balancing pool) needs to be resized, it usually reduces the number of keys (clients) that need to be remapped.

Even simpler is Weighted Rendezvous Hashing (https://www.snia.org/sites/default/files/SDC15_presentations...).

It's quite a bit easier to implement and verify than consistent hashing, and carries the same benefits (minimal reshuffling on ring resizes, etc)

Re: Ask HN: What are some cool but obscure data structures you know about?

#130

Post by pianoben »

jez wrote: post #61
tialaramex wrote: post #52

Hazard Pointers are an interesting concurrent data structure. Suppose we've got a lot of Doodads, let's say there's a Graph of ten million Doodads, and a whole bunch (dozens? hundreds?) of threads are poking around in this same graph, maybe looking at Doodads and sometimes (but not often) removing them from the Graph. What happens if my thread is looking at a Doodad, and meanwhile a different thread removes it from t…

Have you used this before? What was the domain?

These are not commonly used in application code, but are "commonly" used to implement reclamation in languages without memory management for concurrent mutable data structures.
Post reply on HN