confusion about HashMap's method containsValue

I'm trying to find a simplified version of my method and I wanted to know if you have a better opinion.

Basically I have a HashMap that stores key-value as String-String[]

I开发者_运维知识库 would like to have a method that finds out if a new inserted String[]-value, contains a String that is already present in already stored String[]-value.

What I have written "and apparently works fine" is the following method:

static Map<String,String[]> myMap=new HashMap<String,String[]>();

    public static boolean kijkContains(String[] syn){

for(String s:myMap.keySet()){

    String[]temp=myMap.get(s);

    for(int i=0; i<temp.length; i++){

        for(int k=0; k<syn.length; k++){

            if(temp[i].equals(syn[k])){

                return true;
            }
        }
    }
  }
return false;
}

My doubts are about the number of loops, it is obviously a high memory-consuming method, and I was wondering if you can think of any better version.

I have tried with Map's containsValue() method but since that method sees as value the String[] instead of reading through the array, I cant really use it as comparator.

With the data structure you currently have, there is no better way than looping over all those values (at least you are breaking out early on the first hit).

If performance does become a concern, you may want to keep a second datastructure to index what is already there. If you only need to know if a given String is (deep) in the Map (but not where), maybe a HashSet<String> would work.

This is a memory tradeoff: The added index structure would take up extra space. (By the way, what you are doing now does not use any space in addition to what the map already takes up, you are just iterating over arrays by reference, there are no extra copies being made).

Your code doesn't use a particularly big amount of memory, since you're not creating copies of any String[] (you're only copying references to them, which is very cheap).

However, you need to loop through all values in the HashMap, which makes this O(n) (or simply speaking: slow).

If this is a relatively rare operation, then this is probably acceptable, and I wouldn't worry about it.

If inserting is a common operation, then you should definitely think about a better data structure for this (you'd need to tell us more about the actual use case for us to make good suggestions here).

Well I didn't know of a different way beside looping trough the values, but I would suggest a more easier code for that:

Map<String, String[]> map = new HashMap<String, String[]>();
for (String[] strings : map.values()) {
    ArrayUtils.contains(strings, "foo");
}

ArrayUtils is a helper class from apache commons but of course you can also loop trough the strings array and call equals each time. Be carefull that this is case sensitive.

Map<String, String[]> map = new HashMap<String, String[]>();
for (String[] strings : map.values()) {
    for (String string : strings) {
        if (string.equals("foo")) {
            return true;
        }
    }
}

You can reduce time complexity by copying the syn array into a HashSet. Then instead of iterating over syn over and over again you can use the HashSet#contains method which is O(1):

public static boolean kijkContains(String[] syn){
  if (syn == null || syn.length == 0) return false; // that was missing
  Set<String> input = new HashSet<String>();
  for (String s:syn)
    input.add(s);         // will remove duplicates, another perfo improvement

  for(String key:myMap.keySet()){
    for(String s:myMap.get(key)){  // we don't need the loop variable
      if (input.contains(s)) {
        return true;
      }
    }
  }
  return false;
}

the complexity was O(i*j*k) and I've reduced it to O(i*j+k) (with i being the size of the map, j the average size of the value arrays and k the size of the syn array)

So what you want is each string in the value of HashMap must be unique. I think if you use HashSet instead of String[] for the value of Map it will work.

import java.util.*;

public class TestHashMap { public static void main(String args[]) {

System.out.println("Hashmap Test");
HashMap<String, HashSet> myMap = new HashMap<String, HashSet>();

HashSet<String> s1 = new HashSet<String>();
s1.add("one");
s1.add("two");
s1.add("three");

myMap.put("1", s1);
System.out.println("Value for key 1" + myMap.get("1"));

} }

I hope this is the way you wanted it.

you can use containsValue() method to do this.you don't have to iterate throw entire HashMap.

http://msdn.microsoft.com/en-us/library/aa989118%28v=vs.80%29.aspx

http://www.javadocexamples.com/java/util/HashMap/containsValue%28Object%20value%29.html