Not an different algorithm, but around 15 years ago I looked at the JDK’s hashmap implementation and saw it was doing a loop to calculate the next highest power of two (after some multiplier) to determine the table capacity.

For fun, I swapped it for a bitwise calculation from Hacker’s Delight. It benchmarked surprisingly well, multiple percent improvement at various map sizes (even after JIT warmup). Swapping a 3 line loop for a one line bit twiddle wasn’t the most beautiful change, but I was surprised I could beat the original with such a trivial change. It also made me wonder why it hadn’t already been done.

I didn’t have any interest in trying to push it back upstream, but it was a fun to do.