2

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.

Zubair
  • 93
  • 1
  • 8
  • 2
    For convenience's sake, you may just be better off with the `Set`; this way, you can guarantee behavior around what happens with `equals` and `hashCode`. – Makoto Oct 15 '15 at 23:21
  • See also [Can a java array be used as a HashMap key](http://stackoverflow.com/questions/16839182/can-a-java-array-be-used-as-a-hashmap-key). As suggested, you should use a `Set` instead, because you cannot override the behaviour of `equals`/`hashCode` for arrays. – Mick Mnemonic Oct 15 '15 at 23:24
  • okay, what about the second problem, any idea? – Zubair Oct 15 '15 at 23:47
  • For the second part, a _trie_ (or a `TreeMap`) could be useful: [Partial search in HashMap](http://stackoverflow.com/questions/6713239/partial-search-in-hashmap) – Mick Mnemonic Oct 16 '15 at 01:02

2 Answers2

2

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.

Stephen C
  • 698,415
  • 94
  • 811
  • 1,216
0

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
OsYYYY
  • 243
  • 3
  • 14
  • Did you read my quest? How your first solution helps in key mapping? you are just adding string array into a list and then printing it. – Zubair Oct 16 '15 at 04:06
  • If I have misunderstand your question, plz clarify me. I have already added my suggestion in key mapping. You could sort them first and then compare the element one by one in a quick way to determine if the key contained by two lists are equal. It addresses the purpose that (String[] a={"A","B"}, String[] b={"B","A"}) should be equal by your definition. For the code part, I just eliminate the duplication. For the comparsion part, I use words instead of code. – OsYYYY Oct 16 '15 at 04:14
  • I need to use them as Keys of HashMap, So the real problem is working around that issue – Zubair Oct 16 '15 at 04:49