Quelle est la complexité temporelle de HashMap.containsValue () dans java?

M'a donné un problème à résoudre en O(n) complexité temporelle :

"Donné une liste de nombres et x. Trouver si il y a tout les 2 numéros dans la liste qui s'ajoutent à x?"

Et c'est ma solution :

public class SumMatchResult {

  public static void main(String[] args){
    int[] numberList = {6,1,8,7,4,6};
    int requiredSum = 8;
    boolean isSumPresent = checkSumPresentHash(numberList,requiredSum);
    if(isSumPresent) {
      System.out.println("Numbers exist");
    }else {
      System.out.println("Numbers donot exist");
    }
  }

  private static boolean checkSumPresentHash(int[] numberList, int requiredSum) {
    Map<Integer, Integer> m = new HashMap<Integer,Integer>();
    int count = 0;
    for(int i=0;i<numberList.length;i++){
      m.put(i, numberList[i]);
    }
    for(int i=0;i<numberList.length;i++){
      if(m.containsValue(requiredSum - numberList[i])){
        count++;
      }
    }
    if(count>1){
        return true;
    }
    return false;
  }

}

Je suis en utilisant HashMap.containsValue() au lieu d'utiliser un HashSet.contains() qui a sûrement de la complexité de O(1) parce que, je compte pour le scénario où mon entrée peut contenir des valeurs identiques. Par exemple, dans le cas ci-dessus, je peux avoir un ensemble de valeurs d'entrée {3,6,4,4,7} être appariés pour l' sum 8qui doit retourner true.

Ma solution ci-dessus est l'heure de la complexité dépend de la complexité de HashMap.containsValue() méthode. S'il vous plaît faire la lumière sur la complexité du temps de containsValue() méthode et me suggère, si il y a une meilleure solution pour le problème ci-dessus en termes de temps de la complexité. Merci.

source d'informationauteur Vishnu Vedula

  1. 12

    Pour répondre à la question dans le titre - comme mentionné par d'autres, containsValue est O(n), parce que sans la clé, il ne sait pas où il est et l'algorithme a pour aller au-dessus de toutes les valeurs stockées dans la carte.

    Pour répondre à la question dans le corps de votre question sur la façon de la résoudre, il suffit de considérer si vous vraiment besoin d'une carte générale qui peut compter combien de cas avez-vous vu de chaque numéro. Je veux dire, le seulement fois que vous voulez si il n'y a plus d'une apparition d'un certain nombre, c'est quand c'est x/2, droit? Qui sent comme un cas de coin à moi. Il suffit d'ajouter un test qui vérifie que les cas de coin - quelque chose comme l'incorporation de if (numberList[i] == requiredSum/2) half++ pendant votre set de construction de la boucle, puis if (requiredSum % 2 == 0 && half == 2) return true après (voir un autre type de variation ci-dessous).

    Alors vous pouvez simplement effectuer une itération sur l'ensemble et pour chaque élément de vérifier si requiredSum-item apparaît également dans le jeu.

    Pour résumer (avec sortie au plus tôt si possible):

    Set<Integer> seen = new HashSet<Integer>();
boolean halfSeen = false;
for (int num : numberList) {
    if (num == requiredSum/2 && requiredSum % 2 == 0) {
        if (halfSeen) return true;
        halfSeen = true;
    } else {
        seen.add(num);
    }
}
for (int num : seen) {
    if (seen.contains(requiredSum - num)) return true;
}
return false;
  2. 12

    La table de hachage est essentiellement une valeur-clé magasin, ce qui peut accéder à ses touches avec une complexité de O(1). Vérifier une valeur, cependant, il n'y a rien de la table de hachage peut faire, mais de vérifier toutes les valeurs et de voir si elles sont équivalentes à celle que vous soyez à la recherche. Par conséquent, la complexité est O(n), n étant le nombre d'éléments dans la table de hachage.

    Sur une note différente: Vous êtes à la recherche de valeurs primitives (int) dans une collection de ses boxed de type (Entier). Cela signifie que chaque fois que vous appelez une méthode sur la table de hachage, Java doit boîte valeurs primitives: http://docs.oracle.com/javase/1.5.0/docs/guide/language/autoboxing.html

  3. 3

    HashMap.containsValue la complexité est O(n). Mais ce n est pas exactement la taille de la carte, mais plutôt la table de hachage de taille, car containsValue passe en revue tous les éléments de la table, même si la taille de la carte = 0.
    Supposons que nous avons créé une carte vide avec une capacité initiale = 1024. containsValue devra passer par 1024 éléments de la table de hachage tableau:

    public boolean containsValue(Object value) {
    if (value == null)
        return containsNullValue();

    Entry[] tab = table;
    for (int i = 0; i < tab.length ; i++)
        for (Entry e = tab[i] ; e != null ; e = e.next)
            if (value.equals(e.value))
                return true;
    return false;
}