Most likely you get a deadlock in case same keys are updated in parallel putAll operations, but the order of these keys in the provided map is different. I would recommend to try using TreeMap instead of HashMap for 'keysValues'. It guarantees consistent ordering and should fix your issue.
No, you don't have to do that. The only requirement is that keys in putAll map are always ordered in the same way. In other words, intersecting keys in two concurrent putAlls should not be ordered differently.
For example, these two operations can lead to deadlock if executed concurrently:
// Only keys are listed for simplicity.
putAll(1, 2, 3);
putAll(4, 3, 2);
Here keys 2 and 3 are reordered and it's possible that they will wait for each other forever.
To avoid this you should use ordered map (e.g., TreeMap) instead of HashMap. It will guarantee that the order of the keys is always the same.