Which one is faster? List.contains() or Map.containsKey()

user_485337 0
Viewed 41842

I'm writing an algorithm where I look for pairs of values which when added together results in another value I'm looking for.

I figured out that using a Map will speed up my algorithm from O(n²). I later realized that I don't really use the values contained in my Map so a List will suffice.

I did a power search on Google but I did not find any information on the asymptotic running time of those methods in the title of my question.

Can you point out where should I look for such information?

list map collections java
4 Answers

HashSet seems to be faster:

  • HashMap: 267
  • ArrayList: 2183
  • HashSet: 57

Also note that .contains() normally does not need to be called on HashMap and HashSet, but I kept it on the code to more accurately answer your question:

    long t = System.currentTimeMillis();
    HashMap<String, Boolean> map = new HashMap<>();
    for (int i = 0; i < 10000; i++) {
        String s = (Math.random() * 100) + "";
        if (!map.containsKey(s)) {
            map.put(s, true);
        }
    }
    System.out.println("HashMap: " + (System.currentTimeMillis() - t));

    t = System.currentTimeMillis();
    ArrayList<String> list = new ArrayList<>();
    for (int i = 0; i < 10000; i++) {
        String s = (Math.random() * 100) + "";
        if (!list.contains(s)) {
            list.add(s);
        }
    }
    System.out.println("ArrayList: " + (System.currentTimeMillis() - t));

    t = System.currentTimeMillis();
    HashSet<String> set = new HashSet<>();
    for (int i = 0; i < 10000; i++) {
        String s = (Math.random() * 100) + "";
        if (!set.contains(s)) {
            set.add(s);
        }
    }
    System.out.println("HashSet: " + (System.currentTimeMillis() - t));
user_8604500
Related