When two keys hash into the same bucket, HashMap keeps them as a chain of Node objects joined by a next field, and adding to one bucket touches nothing else in the table. A singly linked chain is the right shape because the only access pattern is a forward walk from the bucket head, so the back pointers of a doubly linked list would be paid for on every entry and never read. Java 8 added a limit: a bucket that reaches eight entries is converted into a red-black tree, so long as the table itself already holds at least 64 buckets, and below that the map resizes instead. Either way a flood of colliding keys no longer degrades to a linear scan.