Java Hashmap Performance Optimization/Alternative

Java HashMap performance optimization / alternative

As many people pointed out the hashCode() method was to blame. It was only generating around 20,000 codes for 26 million distinct objects. That is an average of 1,300 objects per hash bucket = very very bad. However if I turn the two arrays into a number in base 52 I am guaranteed to get a unique hash code for every object:

public int hashCode() {       
    // assume that both a and b are sorted       
    return a[0] + powerOf52(a[1], 1) + powerOf52(b[0], 2) + powerOf52(b[1], 3) + powerOf52(b[2], 4);
}

public static int powerOf52(byte b, int power) {
    int result = b;
    for (int i = 0; i < power; i++) {
        result *= 52;
    }
    return result;
}

The arrays are sorted to ensure this methods fulfills the hashCode() contract that equal objects have the same hash code. Using the old method the average number of puts per second over blocks of 100,000 puts, 100,000 to 2,000,000 was:

Using the new method gives:

Much much better. The old method tailed off very quickly while the new one keeps up a good throughput.

The more I use a Java HashMap, the more the performance drops - even with stable size

I recommend using Java VisualVM to do some profiling. This comes with Java - go to the command line and type jvisualvm to run it. This makes it easy to see if memory churn is your problem, or if particular types of objects are being created hundreds of thousands of times.

If you break up your code into several methods, you'll also be able to tell which methods take too long to run.

I did notice that you are unnecessarily creating lots of objects in inner loops. This certainly won't help performance, although it may not be the main culprit.

For example:

float avg = new Float(sumItems) / new Float (freqMap.size());

should just be

float avg = (float)sumItems / freqMap.size();

Another piece of your code which also could be troublesome is:

System.out.println(numItems + " items counted");

Depending on your operating system or IDE, writing 100,000s of lines to the console requires significant time. Instead, just write an update of progress for each 1000 items.

What is a fast alternative to HashMap for mapping to primitive types?

Trove has optimized hashmaps for the case where key or value are of primitive type.

However, much will still depend on smart choice of structure and hash code for your keys.

This part of your question is unclear: The task starts off really quickly, about 10 sentences a second but scales off quickly. At 30 000 sentences( which is assuming 10 words in each sentence and about 3-4 dependences for each word which im storing) is about 300 000 entries in my hashmap.. But you don't say what the performance is for the larger data. Your map grows, which is kind of obvious. Hashmaps are O(1) only in theory, in practice you will see some performance changes with size, due to less cache locality, and due to occasional jumps caused by rehashing. So, put() and get() times will not be constant, but still they should be close to that. Perhaps you are using the hashmap in a way which doesn't guarantee fast access, e.g. by iterating over it? In that case your time will grow linearly with size and you can't change that unless you change your algorithm.

The performance of the HashMap in JAVA8

Your test scenario is non-optimal for Java 8 HashMap. HashMap in Java 8 optimizes collisions by using binary trees for any hash chains longer than a given threshold. However, this only works if the key type is comparable. If it isn't then the overhead of testing to see if the optimization is possible actually makes Java 8 HashMap slower. (The slow-down is more than I expected ... but that's another topic.)

Change your Test class to implement Comparable<Test> ... and you should see that Java 8 performs better than the others when the proportion of hash collisions is large enough.

Note that the tree optimization should be considered as a defensive measure for the case where the hash function doesn't perform. The optimization turns O(N) worst-case performance to O(logN) worst-case.

If you want your HashMap instances to have O(1) lookup, you should make sure that you use a good hash function for the key type. If the probability of collision is minimized, the optimization is moot.

Source code is so complicated, how much efficiency?

It is explained in the comments in the source code. And probably other places that Google can find for you :-)

Java: HashMap performance with millions of items vs if-else searching for numerical range

The best approach depends on your implementation under the hood. I see that the address space of the PSX is 32 bit, but as with many console, zones are mirrored. Now without seeing your actual implementation it's just guessing but here's some considerations.

I'll start considering this table

 KUSEG     KSEG0     KSEG1
  00000000h 80000000h A0000000h  2048K  Main RAM (first 64K reserved for BIOS)
  1F000000h 9F000000h BF000000h  8192K  Expansion Region 1 (ROM/RAM)
  1F800000h 9F800000h    --      1K     Scratchpad (D-Cache used as Fast RAM)
  1F801000h 9F801000h BF801000h  8K     I/O Ports
  1F802000h 9F802000h BF802000h  8K     Expansion Region 2 (I/O Ports)
  1FA00000h 9FA00000h BFA00000h  2048K  Expansion Region 3 (whatever purpose)
  1FC00000h 9FC00000h BFC00000h  512K   BIOS ROM (Kernel) (4096K max)
        FFFE0000h (KSEG2)        0.5K   I/O Ports (Cache Control)

So for I/O ports there not much you can do since they're separated and must be handled specifically we can try to study how to improve addressing of everything else.

We can see that mirrored regions differ from the 4 most relevant bits. Which means that we can do address &= 0x0FFFFFFF so that we ignore the region and consider only the significative part of the address.

So now we have 3 kinds of addresses:

the one starting at 0x0000000, mapped to main RAM
the group starting at 0xF000000 and ending at 0xFC00000 (+ bios rom)
the I/O ports at 0xFFFF0000

This could lead to an hybrid approach in which you use both if/else and a cache, eg:

byte readMemory(int address) 
{
  if ((address & 0xFF000000) == 0xFF000000)
    return ioPorts.read(address);

  // remove most significative nibble, we don't need it
  address &= 0x0FFFFFFF;

  // 0xF000000 zone
  // according to bios rom size you could need a different kind of comparison since it may wrap over 0xFFFFFFF
  if ((address & 0xF000000) == 0xF000000)
  {
    // now your address space is just from 0xF000000 to 0xFC00000 + size of BIOS ROM (4mb max?)
  }
  else
  {
    // we don't know if you map bios together with ram or separately
    return mainRam.readMemory(address);
  }
}

Now we have that address space between 0xF000000 and 0xFC000000 that must be split into multiple parts. As you can see from the memory map we have this:

F000000h
F800000h
F801000h
F802000h
FA00000h
FC00000h

If you notice you can see that first 4 bits are always 0xF while last 12 bits are always 0, so we don't need them to understand where to dispatch the call. This means that the interesting part of the address has the following mask 0x0FFF000, so we could translate the address:

address = (address >>> 12) & 0xFFF;

Now these are only 4096 possible values which could fit in a tight LUT table.

What is an efficient alternative for an extremely large HashMap?

I'm storing the mapping from a 4-byte cyphertext to a 4-byte key.

Conveniently, 4 bytes is an int. As you observed, array sizes are limited by Integer.MAX_VALUE. That suggests you can use an array – but there's a minor hangup. Integers are signed, but arrays only permit values >=0.

So you create two arrays: one for the positive cyphertexts, and one for the negative cyphertexts. Then you just need to make sure that you've given the JVM enough heap.

How much heap is that?

4 bytes * Integer.MAX_VALUE * 2 arrays

= 17179869176 bytes

= ~16.0 gigabytes.

Performance aspect of java.util.Property vs hashmap

java.util.Properties extends java.util.Hashtable, so it is a kind of Hashtable.

Below, there are couple differences relevant for your case:

java.util.Hashtable is synchronized, but java.util.HashMap is not. If you have one-threaded application, HashMap will perform better than Hashtable.

java.util.Hashtable does not allow null keys nor values, while java.util.HashMap allows one null key and many null values.

Consider these differences for your project and take a decision.

Java Hashmap Performance Optimization/Alternative