The art of hashing

Last week I wrote about Bloom filters, giving there an example of simple implementation of that data structure in Python, for which I have used three hash functions from Python hashlib library, that in fact are cryptographic hash functions, so using them is such a way is an overkill. In the meantime I have implemented … Continue reading The art of hashing

Bloom filters are O(k)

Imagine you are creating a user registration module for your website and you need a way of checking that the chosen user name is available. What are your options? Sequential search with its O(n) worst-case run-time complexity? Think about those hundreds of thousands or even millions of user you will have one day! What about … Continue reading Bloom filters are O(k)