Testing for element membership in a Bloom filter requires hashing of a test element (e.g. a string) and multiple lookups in memory. A design of a new two-tier Bloom filter with on-chip hash functions and cache is described. For elements with a heavy-tailed distribution for popularity, membership testing time can be significantly reduced.