Ask HN: What are some cool but obscure data structures you know about?
750 by Uptrenda | 359 comments on
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.
No comments:
Post a Comment