Java performance of using class as key of map

Question

So basically I was trying to create a map to sort elements using their own type, and then being able to retrieve them using that type, while being able to hold only one item of each type at once. To do so I chose to use a Map<Class<? extends ParentClass>, ParentClass>.

I think it is called a heterogeneous container in Java (see this) but then I started thinking about performance issues (because I'm just curious, I don't think I will ever see a difference but who knows). So instead of storing my objects using ChildClass.class, I was about to declare some identifier variable in each class declaration all my ChildClasses, but I would have no way to enforce its declaration because it would need to be a static.

Should I keep on using .class as keys of the map?

Thank you.

Answer 1

It's quite common to use classes as map keys.

See for example JTree.createDefaultRenderers():

protected void createDefaultRenderers() {
  defaultRenderersByColumnClass = new UIDefaults(8, 0.75f);

  // Objects
  defaultRenderersByColumnClass.put(Object.class, (UIDefaults.LazyValue) t -> new DefaultTableCellRenderer.UIResource());

  // Numbers
  defaultRenderersByColumnClass.put(Number.class, (UIDefaults.LazyValue) t -> new NumberRenderer());

  // Doubles and Floats
  defaultRenderersByColumnClass.put(Float.class, (UIDefaults.LazyValue) t -> new DoubleRenderer());
  defaultRenderersByColumnClass.put(Double.class, (UIDefaults.LazyValue) t -> new DoubleRenderer());

  // Dates
  defaultRenderersByColumnClass.put(Date.class, (UIDefaults.LazyValue) t -> new DateRenderer());

  // Icons and ImageIcons
  defaultRenderersByColumnClass.put(Icon.class, (UIDefaults.LazyValue) t -> new IconRenderer());
  defaultRenderersByColumnClass.put(ImageIcon.class, (UIDefaults.LazyValue) t -> new IconRenderer());

  // Booleans
  defaultRenderersByColumnClass.put(Boolean.class, (UIDefaults.LazyValue) t -> new BooleanRenderer());
}

Answer 2

I started thinking about performance issues (because I'm just curious, I don't think I will ever see a difference but who knows)

Generally a mistake; performance is incredibly complicated, and hard to truly witness. CPUs do all sorts of crazy tricks (this is the cause of a bunch of these somewhat recent lasting vectors for hackery such as spectre, and your average computer is busy spending its time on many, many different things. It means 'just measure it' is not particularly feasible: A seemingly 'stable' algorithm (e.g. something that loops 100,000 times) has varying performance over its lifetime, so you can't just measure a loop and make assumptions, and code that runs here can have significant performance effects on different code; so you could write an algorithm that seems fast, if you measure it, it is fast, and nevertheless the net effect on the entire system is quite negative because it makes other code run slow (code that creates a ton of longer-lived garbage would do this).

In other words, the chances that either reasoning about performance, or even doing some basic measurements to back up your reasoning, actually leads to correct conclusions? Extremely low. Instead it is likely to lead you to misleading or outright incorrect conclusions.

More generally, performance is simply too hard to reason about, and this isn't just my opinion, it's the opinion of the team that works on the core JDK itself: They don't think they could just look at code and make meaningful statements about how it performs.

There are 2 major exceptions to this rule:

1. Algorithmic Complexity. This is the concept that involves 'big-O' notation, and tries to measure how the performance (in terms of CPU load and/or memory requirements) 'charts' when charting against a known variable. For example, your average efficient sort algorithm (such as quicksort) has the characteristic that if you chart 'time taken to sort a list' against 'size of the input list', that the chart will, eventually if 'size of input' list is large enough, look just like y = x*log(x). The thing is, y = x^2 means that your algorithm is just going to be slow, regardless of how many micro-optimizations you care to make, for large inputs, and anything even 'bigger' than y=x^2 (such as y=x^3 or y=e^x) means it's hopeless - large inputs will take literally forever (billions of years), the algorithm simply cannot be used on large inputs. Regardless of how many data centers you employ or tweaks you make.

Algorithmic complexity can be analysed. If you have a job, you know the job will eventually involve large enough inputs for complexity to matter, and you know of an algorithm that has less algorithmic complexity, then you can just rewrite that code to the better algorithm and rest safe and secure knowing that this will improve performance by many orders of magnitude, no need to measure anything or try to figure out what the system is doing under the hood; basic math makes this inevitable.

2. Use profilers, and JMH.

Profilers check where your code is spending the most time. If you have a project of, say, 100,000 lines of code and it isn't running as fast as you wanted to, then almost always about 100 lines (0.1 to 1% of the whole) are responsible for 99%+ of the time taken to run it. It therefore makes absolutely no sense to just 'start optimizing code here and there' - 99900 lines of code are completely irrelevant, you need to work on those 100 lines and any time spent elsewhere is a bit like trying to raise the ocean levels in New York by pissing in the sea in Amsterdam. Technically? Yeah, sure. Pragmatically? That is quixote-levels of idiotic.

It is not easy whatsoever to predict which code ACTUALLY is the cause of performance issues, so, just looking at code or doing some basic measurements will mislead you. Write the app. Run the profiler. Then act on the results. It is the only sensible thing to do, outside of writing 'better' algorithms, in the 'less algorithmic complexity' sense.

Profilers just measure where the system spends most of its time, it doesn't measure how long something takes. That is fraught with danger (fast algorithms that slow everything else down, for example), but if you must, the JVM is a complex machine that rewrites code all the time, so 'measure how long something takes' is far more convoluted than you think it is. Therefore, if you want to do that, you can't just start a timer, run some code, and then check how much time was taken. Instead, use the Java Microbenchmark Harness.

Now lets get to your actual question

HashMaps use the following algorithm:

1. To look up a key, first take the key and obtain its hashCode by invoking its hashCode() method.
2. The hashmap consists of buckets; which bucket an object is supposed to be in depends on its hashcode. So, now that we have it, find the appropriate bucket.
3. Look up the right 'position' in the bucket and the key is there, or not. There is absolutely no need to look anyplace else.
4. In case 2 different objects nevertheless end up with the same hashcode (a so called hash code collision), then just store a linked list there with all the elements.

The conclusion is thus simple: As long as there are virtually zero collisions, and the hashCode method used by the key object is fast, then all hashmap operations that operate on single elements are O(1) in nature - in other words, they are fast, and remain fast even if your map has millions of items in them. That's because the above algorithm takes the same amount of steps regardless of how many items are in the map, and each step runs in constant time, therefore the whole operation runs in constant time. Except for the 'walk through the linked list of all different objects with the same hashcode as what we are looking for' part, which is why excessive colissions ARE bad for performance.

Fortunately:

• java.lang.Class has no particular risks of excessive collisions.
• java.lang.Class's hashCode() implementation is very fast.

In other words, using a class object as a key in a map is performancewise excellent: Algorithm-Complexity-wise, it has O(1) behaviour, you can't get any better, and for the minor tweakage stuff, you're going to have to use a profiler, you can't just 'wonder' or 'ask' - it depends on far too many factors to just be able to tell you outright.

Whether your container is heterogenous or not has zero bearing on the performance characteristics of it all. Generics aren't even available at runtime, they don't affect it at all.

The key takeaway for performant code

The general way to have a fast code base is to have a clean codebase. You can't profile until your app is done, and only then do you know where to focus your performance efforts. It means that you want a clean and flexible codebase: One where it is easy to completely rewrite a small part of it.

This is best done by doing the opposite of what moronic performance 'guides' tell you to do. In other words, 'use an array instead of a list, it will be faster!' seems logical but is opposite advice! Arrays are far less flexible than lists are; it means rewriting some code is harder because the irrelevant (for performance purposes) parts of the codebase that flow data into and out of the part that you need to rewrite are harder to fix up because you chose less flexible data types 'for performance reasons'.

Whatever style of code strikes you as easy to read, easy to test, easy to verify (where when reading it you realize it does what you wanted it to do and doesn't easily do anything else - using proper types instead of all-ints-and-strings is a good way to improve verifiability) - THAT is the most performant code, because it means adapting the performance-crucial 1% is going to be much simpler and more reliable. You're trying to avoid codebases where it feels like changing one thing could bring the whole house of cards down.

That, and learn about algorithmic complexity. That one is a university-level course, though.