Le temps de la Complexité de la HashMap méthodes

Depuis que je suis en train de travailler autour de l'heure de la complexité, j'ai été à la recherche par le biais de l'oracle Java bibliothèque de classe pour le moment, la complexité de certaines méthodes standard utilisées sur des Listes, des Cartes et des Classes. (plus précisément, ArrayList, HashSet et HashMap)

Maintenant, quand on regarde le HashMap javadoc page, ils ne font que parler de la get() et put() méthodes.

Les méthodes que j'ai encore besoin de savoir sont:

remove(Object o)
size()
values()

Je pense que remove() sera la même complexité que get(), O(1), en supposant que nous n'avons pas un géant de la table de hachage avec une égale hashCodes, etc etc...

Pour size() je voudrais aussi assumer O(1), depuis un HashSet, qui n'a pas de commande, a un size() méthode de la complexité O(1).

Celui que je n'ai aucune idée de qui est values() - je ne suis pas sûr de savoir si cette méthode sera juste en quelque sorte une "copie" de la table de hachage, donnant une fois de la complexité de O(1), ou si elle devra effectuer une itération sur la table de hachage, faisant de la complexité égale à la somme des éléments stockés dans la table de hachage.

Grâce.

  • Btw, comment pourrait - values() donner O(1) si elle même si elle vient en quelque sorte de "copier" la table de hachage ?
  • par ailleurs, votre lien est rompu
  • Pourriez-vous s'il vous plaît mentionner le exactes de la complexité (moyenne ou pire) que vous cherchez dans votre question ? La complexité de supprimer() sera différente en conséquence, comme l'a justement signalé par @JavaGuy
InformationsquelleAutor Koeneuze | 2011-01-02
  1. 21

    La source est souvent utile: http://kickjava.com/src/java/util/HashMap.java.htm

    • remove: O(1)
    • size: O(1)
    • values: O(n) (sur traversée par itérateur)
    • supprimer a amorti complexité O(1+a), où a dépend de la façon dont de nombreux éléments sont dans la fente de la clé de hachage de l'objet supprimé
    • qu'est ce qu'un?
    • a - est un facteur de charge. Un facteur de charge est le rapport entre un certain nombre d'éléments et le nombre de slots de la carte de hachage est. Veuillez vous référer à l'Introduction aux Algorithmes 11.2 les Tables de Hachage pour des explications plus détaillées.
    InformationsquelleAutor b_erb
  2. 5

    Le code pour supprimer(comme dans rt.jar pour HashMap) est:

    /**
 * Removes and returns the entry associated with the specified key
 * in the HashMap.  Returns null if the HashMap contains no mapping
 * for this key.
 */
final Entry<K,V> removeEntryForKey(Object key) {
    int hash = (key == null) ? 0 : hash(key.hashCode());
    int i = indexFor(hash, table.length);
    Entry<K,V> prev = table[i];
    Entry<K,V> e = prev;

    while (e != null) {
        Entry<K,V> next = e.next;
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k)))) {
            modCount++;
            size--;
            if (prev == e)
                table[i] = next;
            else
                prev.next = next;
            e.recordRemoval(this);
            return e;
        }
        prev = e;
        e = next;
    }

    return e;
}

    Clairement, le pire des cas est O(n).

    • Bien que techniquement vrai, cette réponse pourrait être trompeur pour certains. Ce code est seulement O(n) si toutes les clés dans la table de hachage ont le même hashCode, ce qui est peu probable et/ou un bug. Je pense que Tim un commentaire est le mieux la vérité.
    • D'accord avec @HawkeyeParker, mais le point est toujours valide: le temps d'exécution = pire des cas = linéaire. Encore une fois, c'est rare et purement théorique, mais dans la façon dont nous définissons l'efficacité des algorithmes, la réponse doit être linéaire, car il existe une possibilité où O(n) est vrai.
    InformationsquelleAutor JavaGuy
  3. 1

    Vous pouvez toujours jeter un oeil sur le code source et de le vérifier par vous-même.

    De toute façon... une fois, j'ai vérifié le code source et ce dont je me souviens c'est qu'il y est une variable nommée size qui tiennent toujours le nombre d'éléments dans la HashMap donc size() est O(1).

    • Je suis nouveau sur Java donc je n'ai aucune idée sur le code source, mais je vais essayer. Merci!
    • où puis-je trouver le code source?
    InformationsquelleAutor Itay Karo
  4. 1

    De recherche: O(1+k/n)

    Insert: O(1)

    Supprimer: O(1+k/n)
    où k est le pas. de collision éléments ajoutés à la même LinkedList (k éléments avaient même hashCode)

    De l'Insertion est O(1) car vous ajoutez l'élément à droite à la tête de la LinkedList.

    Amorti Temps complexités sont à proximité de O(1) donne un bon hashFunction. Si vous êtes trop préoccupé par recherche de temps, puis essayer de résoudre les collisions à l'aide d'un BinarySearchTree au lieu de l'implémentation par Défaut de java j'.e LinkedList

    • "L'Insertion est O(1) car vous ajoutez l'élément à droite à la tête de la LinkedList." Il a encore à parcourir la liste pour vérifier si l'élément existe déjà, en comparant la clé de hachage (Ref - code source).
    • mieux utiliser la recherche, de mettre et de l'enlever 🙂
    InformationsquelleAutor Srujan Kumar Gulla