New articles in the 'Java collections' section

Readers are invited to explore some new material that has been added to the Java collections section of the web site. By rights, this material would probably belong in a "Java algorithms" section, as they don't use the collections framework as such, but rather look at structures closely related to those used in the standard collections classes.

In the section on Advanced use of hash codes, some new material firstly looks at how we can implement a strong, 64-bit hash code in Java, and how we can use this to create a Java hash map implementation that saves memory by storing only the keys.

A further section on Bloom filters builds on this strong hash function further, allowing a set of objects to be represented very compactly in memory in return for a certain "false positive rate". This tradeoff is useful in certain situations where we want to "weed out" certain items that require further, resource-intensive processing from those that don't (for example, when wanting to reduce database hits), but where it doesn't matter too much if a small percentage of items "slip through the net". We look more closely at how the initialisation parameters of the Bloom filter can be configured to tune the false positive rate in return for more or less memory space being required.

Advanced use of hash codes

For many purposes, the plain old HashMap and related collections serve their purpose well and you don't need to worry too much about their gory details.

But in some cases, some more advanced hashing-related techniques can help us save memory. In a new section on advanced hashing techniques, we discuss using a BitSet to perform duplicate elimination with a certain degree of error but a significant memory saving. Knowing a little about the statistics of hash codes helps us work out the degree of error involved. For example, with a BitSet taking up around 120K, we can perform duplicate elimination on tens of thousands of strings with a 'false positive' rate of around 2%. This is a technique that I use, for example, in gathering web site statistics, and in similar cases where I want the functionality of a hash map or hash set but can accept a certain degree of error. The technique allows what would otherwise be quite a large amount of data to be 'held in memory', thus significantly reducing database hits, for example.

Have you been using hash codes in an interesting way that I haven't mentioned? If so, I'd be interested to hear.