Sure there is. Use a counting bloom filter. In order to increase the count for a given key, you expand the key into your probe sequence, find the minimum coun

Sure there is. Use a counting bloom filter. In order to increase the count for a given key, you expand the key into your probe sequence, find the minimum counter across all of the probed locations, and then increment all of the values equal to that minimum value. One generally uses saturating addition to avoid overflow. If you want to support removing items, you actually increment the values at all of the probe locations, at a cost of increasing the expected deviation from correct counts. To read the count for a given key, you generate your probe sequence and return the minimum of the values stored at the probed locations. Note that a regular Bloom filter is just a counting Bloom filter using 1-bit counters. In this case, I presume one would generate a counting bloom filter and then either store logarithm or quantile of the count, since there isn't a common use case for distinguishing between 4,096 and 4,095 occurrences of a given password.