Saturday, January 15, 2011

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.