Quel est le pire des cas, la durée de fonctionnement de Hachage avec Chaînage?

Supposons que le numéro de la table de hachage de fentes(disons n), est proportionnelle au nombre d'éléments dans le tableau(dire m). On a n = O(m),
le facteur de charge l = O(m)/m = O(1)
Ainsi, Sous l'hypothèse de Simple et Uniforme de Hachage, la Recherche prend de temps constant sur une moyenne. Ce qui signifie une moyenne de recherche prend du temps proportionnel à la longueur de la liste, qui est la même pour toutes les machines à sous et donc la constante de temps. Mais quel est le cas le pire temps d'exécution en vertu de l'hypothèse de Simple et Uniforme de Hachage. Est-il également être constante ou il va O(1 + l). Veuillez expliquer, je suis confus. [Référence CLR Page 260]

N'pire des cas le temps pour les nations Unies-la Recherche réussie dans l'hypothèse d'un Simple uniforme de hachage sera la même que la moyenne affaire de temps. Et le cas le pire moment pour le succès de la Recherche dans l'hypothèse d'un Simple uniforme de hachage sera différent de celui de la moyenne affaire de temps.

  • Uniforme de hachage n'est pas assez pour vous donner de bonnes pire des cas limites. Une table de hachage de la famille peut être uniforme, tandis que d'une fonction spécifique encore les hachages de chaque clé le même compartiment. Si vous pouvez vous procurer universelle d'une fonction de hachage, vous pouvez obtenir O(logn) limites, avec une haute probabilité: stackoverflow.com/questions/4553624/hashmap-get-put-complexity/...
InformationsquelleAutor Sonali | 2013-11-27
  1. 3

    Dans l'hypothèse d'un Simple Uniforme de Hachage (c'est à dire qu'une hypothétique fonction de hachage sera de répartir uniformément les éléments dans les fentes d'une table de hachage), je crois que le pire cas de performance pour une opération de recherche serait le même que le cas moyen (pour un échec de la recherche) - Θ(n/m + 1) (moyenne des cas comme par Wikipédia).

    Pourquoi? Eh bien, penser que, dans l'hypothèse ci-dessus, chaque fente de la table ont le même nombre d'éléments dans la chaîne. De ce fait, à la fois le moyen et le pire des cas impliquera à la recherche par le biais de tous les éléments dans l'une des chaînes.

    C'est, bien sûr, une jolie hypothèse optimiste - il la pratique, nous pouvons rarement /jamais prédéterminer une fonction de hachage qui sera de répartir uniformément inconnue ensemble de données (et de nous construire rarement les fonctions de hachage spécifiquement pour les ensembles de données), mais, dans le même temps, nous sommes peu de chances d'obtenir le vrai pire des cas.

    En général, le pire temps d'exécution d'une recherche ou de retirer de l'opération pour une table de hachage en utilisant le chaînage est Θ(n).

    Dans les deux cas, insérez peut encore être mis en œuvre comme Θ(1), puisque vous pouvez simplement insérer à l'avant de la chaîne. C'est, si l'on autoriser les doublons (comme Jim mentionné), parce que, sinon, nous devons d'abord vérifier si il est déjà là (c'est à dire faire une recherche).

    Le pire des cas se produit lorsque tous les éléments de hachage à la même valeur, donc vous auriez une très longue chaîne, essentiellement en transformant la structure de données dans une liste liée.

    |--------|
|element1| -> element2 -> element3 -> element4 -> element5
|--------|
|  null  |
|--------|
|  null  |
|--------|
|  null  |
|--------|
|  null  |
|--------|
    • Insertion peut être mis en œuvre que O(1)? Seulement si vous autorisez les doublons.
    • Oh, à droite. Merci. J'ai oublié à ce sujet. Ajout d'une note.
    • "en vertu de l'hypothèse ci-dessus, chaque fente de la table ont le même nombre d'éléments dans la chaîne" - tout à fait tort. ce n'est pas ce Simple Uniforme de Hachage moyens. Tout simplement parce que la fonction de hachage de répartir uniformément le tout ensemble d'éléments, cela ne signifie pas que cela ne sera que pour un sous-ensemble spécifique. Pire moment, comme vous l'avez dit, est O(n).
    InformationsquelleAutor Dukeling