Binary Semaphore, software for AI and distributed systems

Collections in anger

Which one to reach for, what it costs, and what happens when you mutate while iterating.

The collections framework is the part of Java you will use every single day, and the part most people learn by copying whatever was already in the file.

Most of what goes wrong comes from three questions nobody asked: what does this cost, what does it guarantee about order, and can I change it.

ArrayList against LinkedList

The textbook answer is that ArrayList is slow to insert in the middle and LinkedList is fast. The textbook answer is nearly always wrong in practice.

ArrayList is a contiguous array. Reading by index is one memory access, and walking it is close to the fastest thing a computer does, because the whole region is already in cache.

LinkedList is a chain of separately allocated nodes. Getting to element 500 means following 500 pointers to 500 places that are probably not near each other. It has a better complexity class for middle insertion and it still usually loses, because you spend all your time waiting on memory rather than doing work.

Use ArrayList. The exceptions are narrow enough that if you are in one, you will know.

HashMap, and the resize you did not think about

A HashMap puts entries in buckets chosen by hash. When it gets too full it allocates a bigger table and rehashes everything into it.

That means two things. Building a large map without sizing it does that work repeatedly, so pass an initial capacity when you know roughly how many entries are coming. And iteration order is not insertion order, is not sorted, and is not stable across versions. If you rely on it, you have written a bug that will surface during a demo.

When you want insertion order, that is LinkedHashMap. When you want sorted order, that is TreeMap, and it costs you log n per operation to get it.

Modifying while iterating

More on this is coming, and asking moves it up the list.

Want this written up?

Or sit with someone on it instead of waiting for us to write it.

Collections in anger

Which one to reach for, what it costs, and what happens when you mutate while iterating.

The collections framework is the part of Java you will use every single day, and the part most people learn by copying whatever was already in the file.

Most of what goes wrong comes from three questions nobody asked: what does this cost, what does it guarantee about order, and can I change it.

ArrayList against LinkedList

The textbook answer is that ArrayList is slow to insert in the middle and LinkedList is fast. The textbook answer is nearly always wrong in practice.

ArrayList is a contiguous array. Reading by index is one memory access, and walking it is close to the fastest thing a computer does, because the whole region is already in cache.

Use ArrayList. The exceptions are narrow enough that if you are in one, you will know.

HashMap, and the resize you did not think about

A HashMap puts entries in buckets chosen by hash. When it gets too full it allocates a bigger table and rehashes everything into it.

When you want insertion order, that is LinkedHashMap. When you want sorted order, that is TreeMap, and it costs you log n per operation to get it.

Modifying while iterating

More on this is coming, and asking moves it up the list.

Want this written up?

Or sit with someone on it instead of waiting for us to write it.

Collections in anger

ArrayList against LinkedList

HashMap, and the resize you did not think about

Modifying while iterating

Collections in anger

ArrayList against LinkedList

HashMap, and the resize you did not think about

Modifying while iterating

Three ways to get a list, three different objects

Choosing, in one pass

The thing that catches people

Under questioning