Why and How CPython use Bloom Filters inside some of its String APIs, such as splitlines and strip? Let's take a tour of CPython internals to understand the use of bloom filters within CPython's string APIs and to see how it implements the bloom filter. Use of Bloom FIlters in splitlines(): The splitlines() API is used to split a string by lines. Naturally, it needs to scan the string character by character and check if it is a line break character. This would have been straightforward if there was only one way to represent line breaks, e.g. '\n'. However, as it turns out there are 8 different code points in Unicode to represent a new line. Now, doing 8 comparisons for each character when most of them are going to result in a negative answer is expensive. We can't afford this in applications processing large amounts of data. Using a set would be an obvious option but they require hash functions, which can be costly when performed so frequently. Instead, CPython employs a bloom filter to do this. Yes, a bloom filter also requires hash function(s). However, CPython devs have implemented it in a clever manner which circumvents any hash computation whatsoever. Sounds curious, isn't it? If you are interested in learning how they do it, keep reading! Now, using a bloom filter for checking line break characters is fast because for majority of characters the answer is negative. And, if the answer turns out to be positive, CPython does a full comparison against all 8 possible line break chars. The following illustration shows the code. Use of Bloom Filters in strip() API: Similarly, CPython uses bloom filters in the strip API. The strip method removes specified characters from the start, end, or both ends of a string. It takes the list of characters to be removed as a parameter and there is no limit on how many characters you can specify. As the size of the set of characters to be stripped is potentially unbounded, comparing against every member of this set is impractical. Therefore, CPython uses a bloom filter as a first point of check which can quickly return negative. In case it does give a positive result, then CPython needs to do a full comparison. The following listing shows the code for the strip API implementation from CPython code. Bloom Filter Implementation in CPython: Now, coming to how CPython implements bloom filter such that it avoids expensive hash functions? The following listing shows the full C code, which is < 50 lines. I have annotated it to explain what's happening. But the key points are: - It uses an unsigned long value as the bit vector. It gives 64 bits on 64-bit hardware which is sufficient for storing characters of a string - Instead of using expensive hash functions, it uses lower n-bits of the character and sets the corresponding bits on in the bit vector to add the character - On 64 bit hardware, it uses lower 6 bits of each character, whereas on 32 bit hardware it uses lower 5 bits. This was a curtailed version of my latest article. In the article I break down the CPython code explain the bloom filter implementation piece by piece. Check it out (link in the replies).