Est un hashmap Java vraiment o (1) ?

Question

J'ai vu certains intéressant de réclamations sur DONC re Java hashmaps et leur O(1) temps de recherche. Quelqu'un peut m'expliquer pourquoi il en est ainsi? À moins que ces hashmaps sont très différentes de l'une quelconque des algorithmes de hachage je l'ai acheté, il doit toujours exister un ensemble de données qui contient les collisions.

Dans ce cas, la recherche serait O(n) plutôt que d' O(1).

Quelqu'un peut-il expliquer qu'ils sont en O(1) et, le cas échéant, la façon dont ils atteindre cela?

---

En fait, sur la base des réponses, il apparaît en O(1) est en fait mal, même pour la moyenne des cas. L'article de wikipédia indique également que la complexité pour la moyenne des cas est - O(1 + n/k) , ce qui équivaut O(n) , après le retrait de la baisse de l'ordre des facteurs.

L' exécution peut être plus efficace en raison de la sélection d'un bon algorithme de hachage et de facteur de charge, mais la complexité est encore très largement basé sur le nombre d'éléments dans le tableau.

Answer 1

Une caractéristique particulière d'une table de hachage, c'est que contrairement à, disons, équilibré arbres, son comportement est de nature probabiliste. Dans ces cas, il est généralement plus utile de parler de la complexité en termes de probabilité du pire cas d'événement survenant serait. Pour un hachage de la carte, qui est évidemment le cas d'une collision avec le respect de manière pleine et entière de la carte se trouve être. Une collision est assez facile à estimer.

p_collision = n / capacité

Donc un hachage de la carte, même avec un petit nombre d'éléments est assez susceptible de faire l'expérience au moins une collision. Big O notation allons-nous faire quelque chose de plus convaincant. Observons que pour tout arbitraire, fixe la constante k.

O(n) = O(k * n)

Nous pouvons utiliser cette fonctionnalité pour améliorer la performance de la valeur de hachage de la carte. On pourrait plutôt penser à la probabilité d'au plus 2 collisions.

p_{collision x 2} = (n / capacité)²

Ce est beaucoup plus faible. Puisque le coût de gestion d'une collision n'est pas pertinent à Grand O de la performance, nous avons trouvé un moyen d'améliorer les performances sans changer l'algorithme de! Nous pouvons generalzie de ce

p_{collision x k} = (n / capacité)^k

Et maintenant, nous pouvons ignorer certains nombre arbitraire de collisions et extrêmement infime probabilité de plus de collisions que nous sommes comptables. Vous pourriez obtenir la probabilité d'être arbitrairement une minuscule niveau en choisissant le bon k, le tout sans modifier la mise en œuvre effective de l'algorithme.

Nous parler de ce sujet en disant que le hachage de la carte a O(1) accès avec une forte probabilité

Answer 2

Vous semblez mélanger pire comportement avec cas moyenne DUREE (attendu). Le premier est en effet o (n) pour les tables de hachage en général (c'est-à-dire sans utiliser un malaxage parfait) mais cela est rarement utiles dans la pratique.

Toute implémentation de table de hachage fiable, couplée avec un demi hachage décent, a un rendement de récupération d’o (1) avec un facteur très petit (2, en fait) dans le cas prévu, avec une marge très étroite de la variance.

Answer 3

En Java, HashMap fonctionne à l’aide de code de hachage pour localiser un seau. Chaque compartiment est une liste des éléments résidant dans ce seau. Les éléments sont analysés, moyen d’equals pour comparer. Lors de l’ajout d’éléments, la table de hachage est redimensionnée après avoir atteint un certain pourcentage de la charge.

Donc, parfois, il faudra comparer à quelques articles, mais en général il est beaucoup plus proche d’o (1) à o (n). Pour des raisons pratiques, c’est tout que vous avez besoin de savoir.

Answer 4

Les différents taux de croissance des symboles (O, theta, omega, etc.) tous se réfèrent au taux de croissance dans le respect soit de meilleur et du pire, ou le cas moyen. Dans le meilleur des cas est fondamentalement sans valeur, car il est rarement, sinon jamais,--rencontrés. Le pire cas est ce qui est généralement appelé, mais il y a quelques algorithmes (quicksort et de nombreux algorithmes de hachage, par exemple) qui sont beaucoup plus probablement à l'approche moyenne-cas de temps qu'ils sont les pires cas de temps, de sorte que ce qui est utilisé.

Le seul type de données qui a un des PIRES CAS de recherche de temps de l' O(1) est une longueur fixe de tableau de longueur fixe structures (permettant d'adresse de mémoire de calcul au lieu de la liste de la traversée).

Ce que les gens sont susceptibles de référence est un MOYEN de CAS sur la recherche de temps, ce qui est certes difficile à vaincre. L'efficacité d'un algorithme de hachage dépend des données de la fed, mais il existe de nombreux algorithmes de l'approche fondée O(1) moyenne de cas sur l'efficacité.

Évidemment, vous avez raison en ce que tous les algorithmes ont le potentiel de collisions (vous êtes représentant les données de longueur inconnue en tant que données de longueur fixe, donc il y a toujours un moyen de nourrir les différentes entrées qui donnent le même résultat), mais pour des raisons pratiques, c'est une rareté.

Answer 5

Rappelez-vous que o(1) ne signifie pas que chaque recherche examine seulement un seul élément - cela signifie que le nombre moyen des éléments vérifiés reste constante w.r.t. le nombre d'éléments dans le conteneur. Donc si il faut en moyenne 4 comparaisons de trouver un élément dans un conteneur avec 100 éléments, il convient également de tenir une moyenne de 4 comparaisons de trouver un élément dans un récipient avec de 10000 articles, et pour tout autre nombre d'éléments (il y a toujours un peu de la variance, en particulier autour des points de la table de hachage rehashes, et quand il y a un très petit nombre d'articles).

Donc, les collisions ne pas empêcher le conteneur d'avoir o(1) opérations, tant que le nombre moyen de touches par seau reste à l'intérieur d'un fixe lié.