CODEWITHSUNDEEP
javaarraysstringperformancearraylist
Joel
Joel

Reputation: 1833

String[] or ArrayList better as Key in HashMap?

So I need to choose between

  1. HashMap<String[], Object>
  2. HashMap<ArrayList<String>,Object>

My input Parameter is: ArrayList<String> in.

The whole ArrayList<String> in cannot be the key, since it does contain elements, which are not supposed to be like a Primary Key in a database. I do know, that the first n elements of the incoming ArrayList<String> in supposed to be the primary Keys.

Which one would be faster?

Scenario:

HashMap<ArrayList<String>, Object> hmAL = new HashMap<>();
HashMap<String[], Object> hmSA = new HashMap<>();
ArrayList<String> in = new ArrayList<>(); 
fillWithStuff(in);

//Which one would be faster?
getObject(in,hmAL,5);
getObject(in,hmSA,5);

With Option 1:

private Object getObject(ArrayList<String> in, HashMap<ArrayList<String>, Object> hm, int n){
  return hm.get(in.sublist(0,n));
}

With Option 2:

private Object getObject(ArrayList<String> in, HashMap<String[], Object> hm, int n){
String[] temp = new String[n];
for(int i=0; i<n; i++)
  temp[i]=in.get(i);

  return hm.get(temp);
}

Considering:

  1. Which is faster? Short the list, or copy to an array?
  2. I'm wondering, which hash (since it is a HashMap) would be faster. Hashing of a ArrayList, or an equal-sized array. Or doesn't it make any difference?

Upvotes: 1

Views: 526

Answers (3)

TheCodingFrog
TheCodingFrog

Reputation: 3504

Just to add on above two answers, I have tested in Java 7 and found on an average with list it's 50 times faster with 2000000 total elements and 1000000 elements which participate in calculating hashcode i.e. primary keys (hypothetical number). Below is the program.

public class TestHashing {

    public static void main(String[] args) {
        HashMap<ArrayList<String>, Object> hmAL = new HashMap();
        HashMap<String[], Object> hmSA = new HashMap<>();
        ArrayList<String> in = new ArrayList<>();
        fillWithStuff(in);

        // Which one would be faster?
        long start = System.nanoTime();
        getObject(in, hmAL, 1000000);
        long end = System.nanoTime();

        long firstTime = (end-start);
        System.out.println("firstTime :: "+ firstTime);

        start = System.nanoTime();
        getObject1(in, hmSA, 1000000);
        end = System.nanoTime();

        long secondTime = (end-start);

        System.out.println("secondTime :: "+ secondTime);

       System.out.println("First is faster by "+ secondTime/firstTime);
    }

    private static void fillWithStuff(ArrayList<String> in) {
        for(int i =0; i< 2000000; i++) {
            in.add(i+"");
        }
    }

    private static Object getObject(ArrayList<String> in,
            HashMap<ArrayList<String>, Object> hm, int n) {
        return hm.get(in.subList(0, n));
    }

    private static Object getObject1(ArrayList<String> in, HashMap<String[], Object> hm, int n){
        String[] temp = new String[n];
        for(int i=0; i<n; i++)
          temp[i]=in.get(i);

          return hm.get(temp);
        }
}

Output

firstTime :: 218000
secondTime :: 11627000
First is faster by 53

Upvotes: 0

logee
logee

Reputation: 5067

Using String[] is not a good idea because it does not implement hashCode(). This means if you have 2 string arrays which are different objects but with the exact same values, the map will not find it.

The implementation of 'hashCode` seems to use each of the string elements hashcode so the lookup in a map would succeed. So I'd go with this one.

That said, I would rather build a key myself based on the objects in the list.

Upvotes: 2

Strikeskids
Strikeskids

Reputation: 4052

Dealing with copying only

The subList method is implemented very efficiently in Java 7+, not requiring any copying at all. It simply returns a view directly onto the original array. Thus, in Java 7+, it will be faster than the copy element by element method. However, in Java 6, both ways are essentially equivalent.

Dealing with the method as a whole

If you look at the whole method, your choice is no longer a choice. If you want the method to function, you will have to use the first implementation. Array hashCode() does not look at the elements inside it---only the identity of the array. Because you are creating the array in your method, the Map.get() will necessary return null.

On the other hand, the List.hashCode() method runs a hash on all of the contained elements, meaning that it will successfully match if all of the contained elements are the same.

Your choice is clear.

Upvotes: 1

Related Questions