Over a million developers have joined DZone.

Key Collections: Boost Productivity with Keys and Constraints

DZone 's Guide to

Key Collections: Boost Productivity with Keys and Constraints

· Java Zone ·
Free Resource

The classes of the Java Collections Framework are probably the most used in the whole JDK. Nevertheless the interfaces and provided implementations have some omissions and drawbacks which are addressed by various third party libraries.

Brownies Collections already provides GapList (see java.dzone.com/articles/gaplist-lightning-fast-list), a lightning fast List implementation. GapList is a drop-in replacement for ArrayList and LinkedList and it has been designed to alleviate some of the known performance problems.

Whereas GapList improves application performance, the here introduced key collections will increase developer productivity. To achieve this, the concepts of keys and constraints are integrated into the collections and can be used in an orthogonal and declarative way.

Sounds interesting, but too theoretical? Let's start with an example.

A First Example

Let's say we need to represent the list of columns in a table with the following requirements:

  • columns are ordered

  • column names must be unique

  • efficient access to the columns by both index and name

So what collection should we choose? A list gives us efficient access by index. If you are confident that the number of elements remains small, we could implement access by name (which is also needed to check for the uniqueness of the column names) by just iterating through the list, but it clearly needs coding for a solution which would not scale. For a scalable solution, we would need to synchronize a list and a map. This is not an impossible task, but plenty of work for a quite common requirement.

Enter our key collections. They allow the creation of the needed collection with one single statement:

Key1List<Column,String> columns = new Key1List.Builder<Column,String>.



The code is easy to understand: Create a list to store column objects and allow access to them by a string key defined by the specified mapper. This key must not be null and duplicates are not allowed.

To get the complete picture, see the following definition of class and mapper:

class Column {

static Mapper<Column,String> Mapper = new Mapper<Column,String>() {

String getKey(Column col) { return col.getName(); }


private String name;

public String getName() { return name; }


You might first think that the creation of the collection look clumsy, but think at the amount of code you would have to write otherwise. What's more, the upcoming lambda functionality in Java 8 will make the explicit definition of mappers unnecessary as method references can be used.


After this first example we will now look in more detail at the definition and functionality of keys: A key is a value which is extracted from an element stored in a collection. It can be used for access and for defining constraints. We call all extracted key values of a collection a key map. There can be one or more key maps for a collection and also the element itself can be used as key - we call this the element set.

For each key map, the following behavior can be defined:

  • Null values: can be allowed (default) or prohibited (withKeyNull())

  • Duplicate values: can be allowed (default) or prohibited (withKeyDuplicates()). There is also a mode where duplicate values are prohibited, but null values can occur without limitation

  • Sort order: the order of keys can be random (default) or sorted. For sorting either the natural order or any order defined by a comparator can be used (withKeySort())

If you define a sort order on a key map, you have also the possibility to specify that the whole collection should use this order (withKeyOrderBy()).

If you have a database background, these concepts will sound familiar to you. In our example, we defined the column name to be the primary key of the collection. To make this more obvious and also shorter, we could also use the method withPrimarKey(). There is also a second method withUniqueKey() which defines a key which can be null but must be unique if not null.

Note that the values used for keys should be immutable. This is necessary as the key maps are populated upon adding elements and later changes will not be detected. This is however not a problem specific to our key collections, also key values used in sets or maps must not change if the element is contained in a collection. If you really have to change a key value, you can use the method invalidateKey() to update the internal state of the key collection.


The possibility to restrict null and duplicate values already showed some of the power of constraints. Unfortunately the concepts of constraint collections is missing from the JDK classes. While some classes like Set have intrinsic constraints, there is no general way to apply a constraint to collections. What's more, the classes have also not been designed for extensibility, so implementing a constraint involves overwriting a lot of methods.

Maybe you're wondering why we need constraint collection anyhow, but this feature is an essential feature for providing good APIs. Let's consider the case that our class should maintain a list of tasks which may not be null. Client code should be able to read and write these tasks using the provided API but it must be guaranteed that only non-null tasks can be added to the list. Clearly

class Task {

List<Task> tasks;

List<Task> getTasks() { return tasks; }


is dangerous: The client has unrestricted write access to the list, so she can easily insert null values. We can use a slightly modified version to get a good read-only interface:

List<Task> getTasks() { return Collections.unmodifiableList(tasks); }

But we still have to fix the write part of the API. There are different options:

The lazy developer will offer only a minimalistic API:

void addTask(int index, Task task) {
checkTask(task); tasks.add(index, task); }

void setTask(int index, Task task) {
checkTask(task); tasks.set(index, task); }

The hardworking developer could implement all mutator methods (twice add(), twice addAll(), set()). Or she offers only a single method:

void setTasks(List<Task> tasks) { checkTasks(tasks); this.tasks = tasks; }

With this approach, we have to validate all tasks after every change. This may not be a problem if the number of elements is low and the check is as easy as checking for null, but obviously this approach will not scale.

With constrained collections however, our API becomes again as simple as

List<Task> getTasks() { return constraintTasks; }

because the list itself is able to check the elements for validity.

Therefore the key collections offer a general concept to apply constraints to the elements stored in the collections. Per default, key collections allow null and duplicate values like Collection and List do. It is however easily to possible to prohibit null (withElemNull()) and duplicate values (withElemDuplicates()).

You can also define a predicate constraint which must evaluate to true for an element to be added to the collection (withConstraint()). If the predicate evaluation fails, operation is cancelled by throwing an exception.

There is also the possibility to define trigger like handlers (withBeforeInsert(), withBeforeDelete()) where you can prohibit the action to be executed by throwing an exception.

There is also a last kind of constraint ready to use: you can restrict the number of entries allowed in the collection by defining a maximum size (withMaxSize()): an attempt to add more elements will then be rejected with an exception. If your collection is of type list, you can also define a window size (withWindowSize()): this also means that the list will store at maximum the defined number of elements, but if another element is added, the first one is automatically removed.


The functionality of keys and constraints is provided by the following classes:




Maintains a collection of elements. It will provide fast access to the elements.


A key collection with one additional key. It provides fast access to the key and optionally to the element itself.


A key collection with two additional keys. It provides fast access to the key and optionally to the element itself.


Maintains a list of elements. It optionally provides fast access to the element itself.


A key list with one additional key. It provides fast access to the key and optionally to the element itself.


A key list with two additional keys. It provides fast access to the key and optionally to the element itself.

The key collections use the JDK collections as building blocks for their implementation: The element set is realized using HashSet/TreeSet, for the key maps HashMap/TreeMap are used.

The following illustration shows how the key collections use different components to store some elements with two keys:

The classes KeyCollection, Key1Collection, and Key2Collection implement the Collection interface. The order of elements is per default determined by the set component, it can however also be changed to use on of the key maps.

The classes KeyList, Key1List, and Key2List implement the List interface, so the order of elements is always determined by the List. The list order can however be specified to reflect the order of the set or of a key map resulting in a sorted list.

To access the values in the key maps, specific methods have are available: containsKey(), getByKey(), getAllByKey(), getCountByKey(), getDistinctKeys(), removeByKey(), removeAllByKey(), and indexOfKey() (for lists only). For the elements set, the following methods are provided: getAll(), getCount(), removeAll(), getDistinct().

You can also use asSet() and asMap() to access the values by JDK interfaces.

Key Lists

All key lists (except if sorted) have the problem that removal of an element by key is slow as the element must be found by iterating through the list. You should therefore only use a key list if the number of elements remains small or you remove element by index only.

Sorted Key Lists

There are numerous discussions of why Java does not have sorted lists. There are basically two arguments against: The first, puristic one is that a sorted list would violate the contract designed by List.add() because the element is not added at the end. The second, more practical one is that is not possible to implement a sorted list which performs well in adding elements in random order.

While both arguments are true, a sorted key list can nevertheless be created because it can be handy. You must however be aware that adding elements in random order to a sorted list will always be an order of magnitude slower that using a sorted map because the elements must be moved in memory during addition.

More Examples

Let's conclude our article with a few more examples which show the power of key collections:

A collection of tickets with a mandatory internal and an optional external id:

Key2Collection<Ticket,String,String> coll =
new Key2Collection.Builder<Ticket,String,String>.

A column list sorted by name:

Key1List<Column,String> list = new Key1List<Column,String>.

A sorted list of primitive int values:

Note that sorted lists provide special support to use primitive values:

KeyList<Integer> list = new KeyList<Integer>.

This list uses internally an IntObjGapList for storage. So storing 1,000,000 elements will only use 4 MBytes, where the standard approach with

Set<Integer> set = new HashSet<Integer>()

will need more than 44 MBytes. But please make sure you have your values sorted before adding them to get a reasonable performance.

A constraint list:

KeyList<String> = new KeyList<String>.

A constraint set:

KeyCollection<String> = new KeyCollection<String>.

A constraint map:

Key1Collection<Column,String> = new Key1Collection<Column,String>.

And now enjoy your productivity boost by downloading the newest release of Brownies Collections from www.magicwerk.org/collections.


Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}