Pourquoi utiliser un tableau pour implémenter une "liste" au lieu d'une table de hachage?

Question

Considérons un tableau par rapport à une table de hachage où les clés ne sont que les index d'une liste. Leurs limites Big-O d'insertion, de recherche et de suppression en casse moyenne sont O(1). Je comprends que vous pouvez obtenir des gains de bas niveau dans la localité du cache avec un tableau, et il y a une surcharge marginale (principalement constante) pour les opérations de hachage, mais les hashtables vous procurent de l'éparpillement, ce qui dans certaines applications est une grande victoire .

Quels autres contrastes importants (ou petits) manque-t-il?

Contexte: J'entrevois parfois une discussion à ce sujet lorsque j'interviewe des candidats. Habituellement, le contexte est "comment implémenteriez-vous le type de tableau Javascript à l'intérieur de la VM JS?" Pour des données densément compactées, je me range du côté d'un tableau natif, mais je veux avoir un meilleur raisonnement que l'intuition selon laquelle «ça semble moins comme une surcharge».

Answer 1

Un tableau est jsut un cas particulier d'une table de hachage où la fonction de hachage est très simple

f(x) := x; 

et le modulo utilisé est le même que la taille de mot de données (et donc la taille du tableau).

Si vous n'autorisez pas les valeurs non uniques, vous n'avez pas besoin des pointeurs "next" et voila, nous avons un tableau. En raison de l'absence d'une fonction de hachage complexe et d'un calcul modulo, ceci est très rapide, mais seulement applicable lorsque le tableau peut être petit (les très grands tableaux avec beaucoup de places vides gaspillent des ressources mémoire et peuvent déclencher des choses méchantes comme échange/trashing sur le disque).

Answer 2

Parce qu'une liste est généralement ordonnée alors qu'une hashtable ne l'est pas. Dans le contexte où vous ajoutez des éléments dans une liste et attendez que la commande reste cohérente, une table de hachage ne fournit aucune garantie quant à l'ordre dans lequel vous reviendrez alors qu'un tableau conserve la commande.

Answer 3

Parce que les fonctions de hachage ne sont pas libres. Les facteurs linéaires sont importants. Les pires moments sont importants. Comptez les instructions.

Pour le cas particulier que vous citez, qui est l'implémentation sous-jacente de Javascript, il y a peut-être tellement d'autres frais généraux pour effacer ces problèmes. Pourtant, si quelqu'un essaie de faire quelque chose de mathématique qui frappe vraiment un tableau avec de simples touches numériques, un tableau doit être meilleur.

Answer 4

Lorsque vous le regardez sous l'angle de quelqu'un qui veut implémenter le pseudo-comportement de Javascript, vous avez raison de dire qu'une hashtable est la meilleure façon de le faire, en particulier. puisque les tableaux Javascript n'ont pas de longueur fixe et doivent pouvoir contenir des entrées à n'importe quel index. Les tableaux en Javascript ressemblent à des tableaux mais se comportent plutôt comme des hashtables. Mais dans un langage un peu plus proche de la machine, les avantages en termes de performances et d'espace d'utiliser un tableau réel pour des données pouvant être stockées efficacement dans un tableau sont tout à fait remarquables, d'autant plus que les avantages de l'utilisation de hashtables sont assez limité à des tableaux clairsemés ce qui n'est pas ce que vous devriez ou devriez utiliser un tableau pour. C'est en fait mieux fait avec hashtables qui ont des clés entières.

L'insertion, la recherche et la suppression sont également O (1) pour les tableaux dans tous les cas, mais ont une constante O beaucoup plus faible que les hashtables (pas seulement à cause de la localisation du cache). Et les tableaux ont besoin de moins d'espace par entrée.Si vous souhaitez supprimer et insérer des entrées de telle sorte que les entrées suivantes changent leur index en conséquence, ce serait O (n) avec n étant le nombre d'entrées qui doivent être déplacées, mais ce serait aussi O (n) pour les tables de hachage à faire cela et encore avec un frais généraux constant beaucoup plus élevé. C'est le genre d'opération pour lequel vous feriez mieux d'utiliser une liste chaînée. De plus, la croissance d'un tableau est moins coûteuse que la croissance d'une table de hachage qui pourrait nécessiter de réécrire toutes ses entrées.

Tous les différents types de collections ont leurs avantages et leurs inconvénients spécifiques. C'est pourquoi il y en a tellement en usage.