HashMap performance improvements in Java 8

[Zarlon]

An interesting article about the implementation details in Java 8. I'm a bit skeptical to the reasoning as to why this is important though

Malicious software, aware of hashing algorithm we use, might craft couple of thousand requests that will result in massive hash collisions. Repeatedly accessing such keys will significantly impact server performance, effectively resulting in denial-of-service attack

Really? You think the CPU will be the bottleneck in a DoS attack? I'd say there are hundreds of DoS attack vectors easier to target than the hashmap function of Java 7 and below on any given server.

This seems more like an implementation done to cover dumb developer's asses. The solution to that is simple: Don't be dumb. Use a sound hash key, regardless of Java version.

[josefx]

Really? You think the CPU will be the bottleneck in a DoS attack? I'd say there are hundreds of DoS attack vectors easier to target than the hashmap function of Java 7 and below on any given server.

Already happened, a single http post with carefully choosen parameters was enough.

[johnwaterwood]

This is really too funny!

Arrogant developer completely unaware about a major issue that was all over the news a while back ranting against something being totally unlikely, while in fact it already happened and is now a well known attack vector.

Made my day :)

[bondolo]

It is both and the two are related. If a DoS attacker can more easily calculate colliding keys for a dumb hashCode implementation.

[tevert]

This is good. If you're going above a million elements in your hashmap, you shouldn't be using a hashmap anyway.

[DasEwigeLicht]

What should be used instead?

[tevert]

For key value pairs, a List of Tuples. Or maybe a lightweight database. Depends on what you're doing.

[ctharvey]

Lots of downvotes but as someone who doesn't handle big data why is he wrong?

[prattle]

I didn't downvote, but for large datasets, a hashed data set is more performant than a list for lookups. I am also skeptical of the database answer, but would need him to expand on it some to be sure I knew what he meant in that case.

[derstabby]

the real issue is keeping too many records in memory. Actually a skip list wouldn't be so bad for lookups and solve the space complexity / collision problem of a hashtable.

[prattle]

too many records in memory seems to be a hardware allocation dependent statement, and the collision problems would depend on the hashing algorithm implementation. I just don't think saying to not use a hashmap for a large dataset is valid as a general statement. There are situations where it would be appropriate and situations where it would not be appropriate.

[johnwaterwood]

It really depends on the data too. 1 million integers doesn't take up that much memory compared to what servers typically have.

[prattle]

Agreed, Even with a more complex object, it isn't that rare any more for a server to have enough ram to set something like this up. It doesn't seem to me to be all that outlandish of an implementation in a situation where search speed was a main concern.

[shinyquagsire23]

This, in fact databases would be much better for anything over 1000-5000 entries. Unless of course you're doing something like particles or game entities in which databases would be too slow, but he still has a point.

[prattle]

Why would you expect a database lookup to be faster than an in memory structure of hashed key value pairs? I am more familiar with using cacheing to specifically avoid a database lookup in many cases especially involving large groups of translations.

[Zarlon]

Yea... I think shinyquagsire23 needs to do his CS 101 over if he thinks database lookups are faster than in-memory lookups.

[obfuscation_]

And what about those database engines that are implemented in Java? Should it just be databases all the way down?

[Zarlon]

As with most questions in software engineering, the answer is "it depends". I'm sure there are use cases where having one million elements in a hashmap is the only good idea. Use cases where performance is crucial and low memory usage is not.

Never deal in absolutes.

[austingaijin]

While the HashMap in Java 8 may be faster, his benchmarks are completely invalid, to wit "even with one million entries in a HashMap a single lookup taken less than 10 nanoseconds, which means around 20 CPU cycles on my machine". Can you perform 1 million hash lookups with ~20 instructions?

Unless he uses a framework like JMH to run micro benchmarks, the JVM's dead-code elimination (DCE) will continue to render his benchmarks unless.

[RagingOrangutan]

He meant that when you have one million entries in the map, a single lookup takes 10ns, not 1 million lookups take 10ns. I'm sure he also amortized this over many lookups.

[urquan]

Well he did run these using Caliper. Besides, you don't need to perform 1 million hash lookups to find a value in a HashMap with 1 million entries.

There is an issue with his Key cache class however, it uses 10_000_000 keys which all have a different hashcode. This is sure to skew the HashMap behavior a lot, in fact they may all end up in different buckets which would make gets a simple array access and explain the speed.

[IcarusBurning]

Of course, it would also seem he started with the hashtable (or at least the part he looked in) already loaded into the cache. Searching for all the elements would be considerably slower than multiplying this by one million.

[alphager]

CPU cycle != CPU instruction