2026-11-22
问答
0

I’m very interested in what types of interesting data structures are out there HN. Totally your preference.

I’ll start: bloom filters. Lets you test if a value is definitely NOT in a list of pre-stored values (or POSSIBLY in a list - with adjustable probability that influences storage of the values.)

Good use-case: routing. Say you have a list of 1 million IPs that are black listed. A trivial algorithm would be to compare every element of the set with a given IP. The time complexity grows with the number of elements. Not so with a bloom filter! A bloom filter is one of the few data structures whose time complexity does not grow with the number of elements due to the ‘keys’ not needing to be stored (‘search’ and ‘insert’ is based on the number of hash functions.)

Bonus section: Golomb Coded Sets are similar to bloom filters but the storage space is much smaller. Worse performance though.---

HN 热门评论

@sgtnoodle: Monotonic stacks are neat.

I made up a data structure once, consisting of a pyramid of deques. It lets you efficiently compute any associative function over a streaming window of data.

@petethepig: Tries (or prefix trees).

We use them a lot at Pyroscope for compressing strings that have common prefixes. They are also used in databases (e.g indexes in Mongo) or file formats (e.g debug symbols in macOS/iOS Mach-O format are compressed using tries).

We have an article with some animations that illustrate the concept in case anyone’s interested [0].

[0] https://github.com/pyroscope-io/pyroscope/blob/main/docs/sto…

@llimos: The Israeli queue.

Like a regular queue, but if something new that comes in sees its friend in the queue already, it can jump the queue and go and stand next to her.

Useful for when something has a big overhead on top of its own processing, but the overhead can be shared between several similar entries. If you’re doing it anyway for the one already in the queue, you get to make the most of it for its friends too.

I chose it because I live here and it’s totally true :)


原文: https://news.ycombinator.com/item?id=32186203

本文作者:demo user

本文链接:

版权声明:本博客所有文章除特别声明外,均采用 许可协议。转载请注明出处!