CODEWITHSUNDEEP
java
Zubair
Zubair

Reputation: 93

String Array as Key of HashMap

I need to solve two problems for our project, where (1) I have to find a way in which I can keep an array (String[] or int[]) as a key of the Map. The requirement is that, if the contents of two arrays are equal (String[] a={"A","B"}, String[] b={"B","A"}) then they should be considered as equal/same keys, i.e., if I use a, or b as key of Map then a.equal(b)=true

I found that Java Sets adds the hashcodes of all the objects stored in them. The addition of hashcode allows to compare two hashsets, to see if they are equal or not, this means that such mechanism allows to compare two java Sets based on their contents.

So for the above problem I can use Sets as a Key of the Map, but the thing is I want to use Arrays as Key. So any idea for this?

(2) the next thing is, we are interested in an efficient partial key matching mechanism. For instance, to see if any key in the Map contains a portion of the Array, such as to find some thing like Key.contains(new String[]{"A"}).

Please share your ideas, any alternate way of doing this, I am concern with space and time optimal implementations. As this will be used in Data Stream processing projects. So space and time is really an issue.

Upvotes: 2

Views: 2083

Answers (2)

Stephen C
Stephen C

Reputation: 719416

Q1 - You can't use bare arrays as HashMap keys if you want key equality based on the array elements. Arrays inherit equals(Object) and hashCode() implementations from java.lang.Object, and they are based on object identity, not array contents.

The best alternative I can think of is to wrap the arrays as (immutable) lists.

Q2 - I don't think there is a simple efficient way to do this. The best I can think of are:

  • Extract all possible subarrays of each array and make each one an alternative key in the hash table. The problem is that the keys will take O(N M^2) space where M is the average (?) number of strings in the primary key String[]'s . Lookup will still be O(1).

  • Build an inverted index that gives the location of each string in all of the keys, then do a "phrase search" for a sequence of strings in the key space. That should scale better in terms of space usage, but lookup is a lot more expensive. And it is complicated.

Upvotes: 2

OsYYYY
OsYYYY

Reputation: 253

I try to use lambda expression in Java8 to solve your problem

For Problem 1:

    String[] arr1 = {"A","B","A","C","D"};
    List<String> list1 = new ArrayList<String>(new LinkedHashSet<>(Arrays.asList(arr1)));
    list1.stream().forEach(x -> System.out.println(x));

If you would like to compare them if they are equal. I suggest you could sort them first and then compare. Of course, It's much better to use Set and Hashcode to do comparsion

For Problem 2(Some variable in the above would be re-used):

    String[] arr2 = {"A"};
    List<String> list2 = new ArrayList<String>(Arrays.asList(arr2)); //Assume List2 element is also unique
    int NumOfKeyContain = list1.stream().filter(a -> (list2.stream().filter(b -> !b.equals(a)).count())<list2.size())
            .collect(Collectors.toList())
            .size();
    System.out.println(NumOfKeyContain); //NumOfKeyContain is the number that of key in list2 contained by list1

Upvotes: 0

Related Questions