On 03/20/2013 02:44 PM, Sönke Ludwig wrote:

Built-in AAs use a linked list to handle collisions and thus allocate for every element that is inserted. HashMap on the other hand uses a single closed array to store all elements and uses a special key value (e.g. null) to mark an empty slot. This makes it a lot more memory and cache friendly, although deletions and handling many big-objects can have a higher overhead.

We should collect more statistical data or benchmarks to optimize the
standard implementation. I do agree, that arrays make a saner default
choice, but only for a reasonable load factor.