CODEWITHSUNDEEP
javaarraysstringloopshashmap
JBoy
JBoy

Reputation: 5735

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.

Upvotes: 1

Views: 2105

Answers (6)

Sachin Karjatkar
Sachin Karjatkar

Reputation: 313

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.

Upvotes: 0

Andreas Dolk
Andreas Dolk

Reputation: 114757

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)

Upvotes: 0

Rupok
Rupok

Reputation: 2082

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

Upvotes: -1

rit
rit

Reputation: 2308

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;
        }
    }
}

Upvotes: 0

Thilo
Thilo

Reputation: 262474

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).

Upvotes: 3

Joachim Sauer
Joachim Sauer

Reputation: 308001

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).

Upvotes: 2

Related Questions