Hacker News Icon Hacker News

A thread of cool but obscure data structures  ↦

User Uptrenda asked HN about their favorite data structures, sharing their own to get it started:

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.)

The responses are numerous with a lot of signal, which is increasingly rare on the orange website these days. Worth a read!


Discussion

Sign in or Join to comment or subscribe

Player art
  0:00 / 0:00