Quel est exactement le seau dans la table de hachage?

Récemment, dans une interview, on m'a demandé, qu'est-ce exactement un seau dans la table de hachage? Si c'est un tableau ou une liste de tableaux ou quoi?

Je suis confus. Je sais hashmaps sont soutenus par des tableaux. Je peux donc dire que le seau est un tableau avec une capacité de 16 dans le de commencer à stocker hashcodes et à qui reliait les listes le début de leurs pointeur ?

Je sais comment faire une table de hachage interne fonctionne, je voulais juste savoir ce qu'est exactement un seau en termes de structures de données.

vous devez lire ce (stackoverflow.com/questions/6493605/...)
Je voulait savoir plus précisément ce qu'est un seau? Dans la question mentionnée, c'est plus de travail sur les hashcodes et hashmap mise en œuvre. Donc, je ne considère pas ma question être un doublon. Les questions peuvent être similaires, mais la réponse qu'ils cherchent sont différents.

OriginalL'auteur dgupta3091 | 2016-06-22

  1. 22

    Non, un seau de chaque élément dans le tableau, vous faites allusion. Dans les précédentes versions de Java, chaque seau contenait une liste d'entrées de Mappage. Dans les nouvelles versions de Java, chaque seau contient une arborescence d'inscriptions ou d'une liste d'entrées.

    De la mise en œuvre de notes dans Java 8:

    /*
 * Implementation notes.
 *
 * This map usually acts as a binned (bucketed) hash table, but
 * when bins get too large, they are transformed into bins of
 * TreeNodes, each structured similarly to those in
 * java.util.TreeMap. Most methods try to use normal bins, but
 * relay to TreeNode methods when applicable (simply by checking
 * instanceof a node).  Bins of TreeNodes may be traversed and
 * used like any others, but additionally support faster lookup
 * when overpopulated. However, since the vast majority of bins in
 * normal use are not overpopulated, checking for existence of
 * tree bins may be delayed in the course of table methods.
 ...
    Donc, quand nous disons hashmap a une capacité de 16 dans le début, donc, à l'époque, il crée un tableau de 16 espace et a ses chaque élément appelé comme un seau.?
    oui, bien que dans Java 8 mise en œuvre le tableau est créé paresseusement (c'est à dire que lorsque la première entrée est mis dans la table de hachage).
    Je viens de vérifier la mise en œuvre en Java 8, et aucun des constructeurs initialiser le tableau. Il n'est initialisé par resize() (qui sera appelé par put si la matrice est nulle) et readObject(java.io.ObjectInputStream s) (désérialisation).
    Ce qui est logique, j'ai oublié la raison principale pour définir une capacité initiale est de minimiser le nombre de ressasser des opérations. Je pense juste que c'est bizarre pour créer le tableau paresseusement, par exemple, vous créez une table de hachage avec une assez grande capacité initiale dans une méthode de chargement, pensant qu'il va prendre un certain temps. Puis plus tard, sur la route, vous découvrez le premier appel à mettre prend plus de temps que la fonction de chargement. Peut-être que ma logique est, je suis assez fatigué. Merci pour votre réponse à mon commentaire.

    OriginalL'auteur

  2. 17

    Quel est exactement le seau dans la table de hachage?

    J'espère que cela peut vous aider à comprendre la mise en œuvre de hachage de la carte.

    OriginalL'auteur

  3. 4

    Seaux exactement est un tableau de Nœuds. Donc seul seau est une instance de la classe java.util.HashMap.Nœud. Chaque Nœud est une structure de données similaire à LinkedList, ou peut-être comme un TreeMap (depuis Java 8), HashMap décide lui-même ce qui est mieux pour la performance--keep seaux comme LinkedList ou TreeMap. TreeMap seront choisies uniquement en cas de mal conçus hashCode() de la fonction, lorsque beaucoup d'entrées sera placé dans le seul compartiment.
    Voir comment seaux ressembler dans la table de hachage:

    /**
     * The table, initialized on first use, and resized as
     * necessary. When allocated, length is always a power of two.
     * (We also tolerate length zero in some operations to allow
     * bootstrapping mechanics that are currently not needed.)
     */
    transient Node<K,V>[] table;

    OriginalL'auteur

  4. 0

    Seaux sont essentiellement une structure de données qui est utilisé dans la Pagination de l'algorithme du Système d'Exploitation . Pour être dans un très Dilettantes de la langue.

    Les objets représentant un hashcode est stockée dans ce seau.(fondamentalement, vous pouvez envisager l'en-tête de la liste liée structure de données pour être le hashcode de la valeur qui est représentée dans les conditions de seau)

    Les références de l'objet est stocké dans la liste des liens , dont la tête représente la valeur de la Hashcode.

    La JVM crée entre eux et la taille dépend de la mémoire allouée par la JVM.

    OriginalL'auteur