Skip to main content

New best story on Hacker News: Ask HN: What are some cool but obscure data structures you know about?

Ask HN: What are some cool but obscure data structures you know about?
783 by Uptrenda | 371 comments on Hacker News.
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.

Labels:

Comments

Post a Comment

Popular posts from this blog

New best story on Hacker News: Ask HN: I’m an FCC Commissioner proposing regulation of IoT security updates

Ask HN: I’m an FCC Commissioner proposing regulation of IoT security updates 449 by SimingtonFCC | 144 comments on Hacker News. Hi everyone, I’m FCC Commissioner Nathan Simington, and I’m here to discuss security updates for IoT devices and how you can make a difference by filing comments with the FCC. As you know, serious vulnerabilities are common in IoT, and it often takes too long for these to be patched on end-user devices—if the manufacturer even bothers to release an update, and if the device was even designed to receive them. Companies may cease supporting a device well before consumers have stopped using it. The support period is often not communicated at the time of sale. And sometimes the end of support is not even announced, leaving even informed users unsure whether their devices are still safe. I’ve advocated for the FCC to require device manufacturers to support their devices with security updates for a reasonable amount of time [1]. I can't bring such a proposal
Post a Comment
Read more