How to improve performance of iteration through a HashMap in Java?

Question

Does anybody have any idea about how I could improve the performance of this method? Note that this.allActions is a hashmap with around half a million keys.

Maybe there is a faster way of iterating through a HashMap that I don't know.

public String get_random_legal_action(String stateJSON) {

        Collections.shuffle(this.allActionsKeys);

        boolean legal;

        HashMap<String, Integer> state = new Gson().fromJson(stateJSON, this.stateType);

        for (String action : this.allActionsKeys) {

            legal = true;

            for (Map.Entry<String, Integer> precondition : this.allActions.get(action).precondition.entrySet()) {
                try {
                    if (!state.get(precondition.getKey()).equals(precondition.getValue())) {
                        legal = false;
                        break;
                    }
                } catch (NullPointerException e) {
                    if (!this.immutableProps.contains(precondition.getKey())) {
                        legal = false;
                        break;
                    }
                }
            }

            if (legal)
                return action;
        }

        return null;
    }

Does this answer your question? [How do I efficiently iterate over each entry in a Java Map?](https://stackoverflow.com/questions/46898/how-do-i-efficiently-iterate-over-each-entry-in-a-java-map) — daniu, May 11 '20 at 19:01
The best way to improve the performance is not to iterate over it at all. `HashMap` is a keyed collection, not a linked list. Either find a way to look it up directly via your search criteria, or use a more appropriate data structure. For a million entries a database comes to mind. — user207421, May 12 '20 at 01:36

0xh3xa · Answer 1 · 2020-05-12T12:27:01.003

2

Convert the HashMap to LinkedHashMap to improve the performance,

the complexity of Get O(1), Contains O(1) and Next O(1)

, You can create custom Key class and update hashCode() function

Use it in like LinkedHashMap<Key, Integer>

static class Key {

    private static final int R = 256;
    private static final long Q = longRandomPrime();

    private String k;

    public Key(String k) {
      this.k = k;
    }

    public String key() {
      return k;
    }

    @Override
    public int hashCode() {
      return Long.hashCode(hash());
    }

    @Override
    public boolean equals(Object o) {
      if (this == o)
        return true;
      if (o == null)
        return false;
      if (getClass() != o.getClass())
        return false;
      Key other = (Key) o;
      return k.equals(other.k);
    }

    @Override
    public String toString() {
      return k;
    }

    private long hash() {
      long h = 0;
      for (int j = 0; j < k.length(); j++) {
        h = (R * h + k.charAt(j)) % Q;
      }
      return h;
    }

    private static long longRandomPrime() {
      BigInteger prime = BigInteger.probablePrime(31, new Random());
      return prime.longValue();
    }
  }

edited May 12 '20 at 12:27

answered May 11 '20 at 18:55

0xh3xa

4,801
2
14
28

Only amortized though. – Zabuzard May 11 '20 at 19:01
+1 for your first paragraph, but your second paragraph is misleading at best. I don't think asymptotic complexity is really relevant here. Unless the map has had a large proportion of keys removed from it, a full iteration pass through a HashMap *or* a LinkedHashMap will take O(N) time. LinkedHashMap will be faster, but only by a constant factor. – ruakh May 11 '20 at 19:59
Thanks for your answer @sc0der . I've substituted every HashMap involved in this method (allActions, state, and the attributes in class Action) by a LinkedHashMap but I don't really see a difference. Is this normal? Did you mean only one in particular? – CSR95 May 11 '20 at 22:22
What is the of Key in the `allActions` and also how do you define the `hashCode()`? – 0xh3xa May 11 '20 at 23:36
The key in `allActions` is a String. Before calling this method I pass the content of a JSON file to the `HashMap allActions`, where the `Action` class contains other 3 `HashMap` attributes like the `precondition` one in the code snippet. Thank you again for your time @sc0der . – CSR95 May 12 '20 at 00:29

How to improve performance of iteration through a HashMap in Java?

1 Answers1