Cours d'apprentissage sur les réflexions sur la programmation Java (4) Chapitre 17 - Discussion approfondie sur les conteneurs-javaDidacticiel-php.cn

1 Ensemble et ordre de stockage

L'élément Set ajouté à doit être méthode définieequals() pour garantir l'unicité de l'objet.
hashCode() n'est requis que si cette classe est placée à l'intérieur de HashSet ou LinkedHashSet. Mais pour des raisons de bon style de programmation, vous devez toujours remplacer la méthode hashCode() lorsque vous remplacez la méthode equals().
Si un objet est utilisé dans n'importe quel type de conteneur trié , tel que SortedSet (TreeSet est la seule implémentation de it) , alors il doit implémenter l'interface Comparable.
Notez que SortedSet signifie "trier les éléments par la fonction de comparaison de l'objet ", alors qu'il le fait ne fait pas référence à "l'ordre dans lequel les éléments sont insérés". Ordre d'insertion est enregistré avec LinkedHashSet.

2 Queue

met en file d'attente les applications simultanées Les deux seules implémentations de Queue dans Java SE5 sont LinkiedList et. PriorityQueue, ils n'ont que la différence de comportement de tri, et il n'y a aucune différence de performance.
L'ordre de la file d'attente prioritaire PriorityQueue est également contrôlé par la mise en œuvre de Comparable.

3 cartes

Tableau de cartes (également connu sous le nom de Tableau associatifAssociatif Tableau).

3.1 Performances

HashMap utilise une valeur spéciale, appelée code de hachage (code de hachage), pour remplacer la clé Rechercher lentement. Un code de hachage est une valeur "relativement unique" qui représente un objet. Il est obtenu en convertissant int certaines informations sur l'objet et généré. hashCode() est une méthode de la classe racine Object, donc tous les objets peuvent générer des codes de hachage.

Les exigences pour les clés utilisées dans une carte sont les mêmes que pour les éléments d'un ensemble :

Toute clé doit avoir un
equals() Méthodes ;
Si la clé est utilisée pour hacher la carte, elle doit également avoir la méthode
hashCode() appropriée ; >Si une clé est utilisée pour
, alors elle doit implémenter
TreeMap. Comparable4 Hash et code de hachage

pour déterminer si la clé actuelle est la même que la clé qui existe dans le tableau.

L'Object.equals() par défaut compare simplement l'adresse de l'objet equals(). Si vous souhaitez utiliser votre propre classe comme clé de HashMap
, vous devez remplacer à la fois et en même temps. hashCode() La bonne equals() méthode doit remplir les cinq conditions suivantes :
equals()Réflexivité.

Symétrie.
Transitivité.
Cohérence.
Pour tout
qui n'est pas nul,
.
xx.equals(null)false4.1 Concept de hachage

Vous souhaitez utiliser un objet pour trouver un autre objet

.

La classe d'implémentation de carte utilise le hachage pour

augmenter la vitesse des requêtes
. La valeur du hachage est la vitesse

Le hachage rend les requêtes rapides
. Étant donné que le goulot d'étranglement est à la vitesse de requête , l'une des solutions consiste à garder les clés triées, puis à utiliser pour l'interrogation. Collections.binarySearch() Le hachage va encore plus loin et enregistre la clé quelque part afin que

puisse être trouvé rapidement. La structure de données la plus rapide pour stocker un ensemble d'éléments est un tableau, utilisez-le donc pour représenter les informations clés (notez attentivement que je parle des informations clés, pas de la clé elle-même). Mais comme le tableau ne peut pas ajuster sa capacité, il y a un problème : on veut sauvegarder un nombre incertain de valeurs dans la Map, mais que se passe-t-il si le nombre de clés est limité par la capacité du tableau ?
La réponse est : Les tableaux ne stockent pas les clés eux-mêmes. Au lieu de cela, un nombre est généré à partir de l'objet clé en tant qu' indice du tableau. Ce numéro est le code de hachage, représenté par la méthode hashCode() définie dans Object et éventuellement remplacée par votre classe (en termes informatiques appelée fonction de hachage ) est générée.

Pour résoudre le problème de la capacité fixe du tableau, différentes clés peuvent produire le même indice. Autrement dit, il peut y avoir des collisions, c'est-à-dire que les codes de hachage ne doivent pas nécessairement être uniques. Par conséquent, quelle que soit la taille du tableau, n'importe quelle clé trouvera toujours sa place dans le tableau.

4.2 Comprendre le hachage

En résumé, le Le hachage consiste à générer un nombre à partir d'un objet et à le sauvegarder (comme la partie inférieure du tableau) (standard), puis trouvez simplement le numéro directement lors de la recherche de cet objet, donc le but du hachage est d'améliorer la vitesse de recherche, et le moyen est de combiner le numéro généré par un objet avec son associé et enregistré (via un tableau, appelé table de hachage). Le numéro généré est le code de hachage . La méthode de génération de ce code de hachage est appelée fonction de hachage (hashCode()).

4.3 Processus de requête HashMap (raison rapide)

Par conséquent, le processus d'interrogation d'un HashMap dans key est :

Premier calcul la valeur de hachage Code de colonne
Utilisez ensuite le code de hachage pour interroger le tableau (le code de hachage est utilisé comme indice de tableau variable)
S'il n'y a pas de conflit, celui-ci est généré. Il n'y a qu'un seul objet hash code, alors la position de l'indice du tableau correspondant au hash code est l'élément à trouver
S'il y a en cas de conflit, l'indice du tableau correspondant au code de hachage est localisé. L'élément enregistre un list, puis utilise la méthode list pour effectuer une requête linéaire sur la valeur dans equals().

Ainsi, au lieu d'interroger l'intégralité de list, saute rapidement à une certaine position dans le tableau et ne compare très peu d'éléments . C'est HashMappourquoi c'est si rapide.

4.4 Implémentation d'une carte de hachage simple

Le slot (slot) dans la table de hachage est généralement appelé la position du compartiment(bucket)
Pour rendre le hachage pair, le nombre de buckets utilise généralement un nombre premier (C'est un nombre premier dans JDK5, et c'est déjà un entier de 2 dans JDK7 Powered ).

Il s'avère que les nombres premiers ne constituent pas réellement la capacité idéale pour un seau de hachage. Dernièrement, les fonctions de hachage de Java (grâce à des tests approfondis) utilisent 2 élevé à la puissance de . La division et le reste sont les opérations les plus lentes sur les processeurs modernes. En utilisant une table de hachage d'une puissance entière de 2 de longueur, le masque peut être utilisé à la place de la division. Étant donné que get() est l'opération la plus couramment utilisée, l'opération % consistant à trouver le reste est la partie la plus coûteuse, et l'utilisation de la puissance entière de 2 peut éliminer cette surcharge (cela peut également avoir un certain impact sur hashCode()).
La méthode get() calcule l'index dans le tableau buckets de la même manière que la méthode put() Ceci est important car cela garantit que les deux méthodes peuvent calculer Idem. emplacement .

package net.mrliuli.containers;

import java.util.*;public class SimpleHashMap<K, V> extends AbstractMap<K, V> {    // Choose a prime number for the hash table size, to achieve a uniform distribution:
    static final int SIZE = 997;    // You can&#39;t have a physical array of generics, but you can upcast to one:
    @SuppressWarnings("unchecked")
    LinkedList<MapEntry<K,V>>[] buckets = new LinkedList[SIZE];

    @Override    public V put(K key, V value){        int index = Math.abs(key.hashCode()) % SIZE;        if(buckets[index] == null){
            buckets[index] = new LinkedList<MapEntry<K,V>>();
        }

        LinkedList<MapEntry<K,V>> bucket = buckets[index];
        MapEntry<K,V> pair = new MapEntry<K,V>(key, value);

        boolean found = false;
        V oldValue = null;
        ListIterator<MapEntry<K,V>> it = bucket.listIterator();        while(it.hasNext()){
            MapEntry<K,V> iPair = it.next();            if(iPair.equals(key)){
                oldValue = iPair.getValue();
                it.set(pair); // Replace old with new
                found = true;                break;
            }
        }        if(!found){
            buckets[index].add(pair);
        }        return oldValue;
    }

    @Override    public V get(Object key){        int index = Math.abs(key.hashCode()) % SIZE;        if(buckets[index] == null) return null;        for(MapEntry<K,V> iPair : buckets[index]){            if(iPair.getKey().equals(key)){                return iPair.getValue();
            }
        }        return null;
    }

    @Override    public Set<Map.Entry<K,V>> entrySet(){
        Set<Map.Entry<K,V>> set = new HashSet<Map.Entry<K, V>>();        for(LinkedList<MapEntry<K,V>> bucket : buckets){            if(bucket == null) continue;            for(MapEntry<K,V> mpair : bucket){                set.add(mpair);
            }
        }        return set;
    }    public static void main(String[] args){
        SimpleHashMap<String, String> m = new SimpleHashMap<String, String>();        for(String s : "to be or not to be is a question".split(" ")){
            m.put(s, s);
            System.out.println(m);
        }
        System.out.println(m);
        System.out.println(m.get("be"));
        System.out.println(m.entrySet());
    }
}

Copier après la connexion

4.5 Remplacement de hashCode()

Facteurs à prendre en compte lors de la conception de `hashCode()` :

Le facteur le plus important : L'appel de hashCode() sur le même objet de phase devrait produire la même valeur à chaque fois .
De plus, hashCode() ne doit pas s'appuyer sur des informations d'objet uniques, en particulier en utilisant la valeur de this, qui ne peut produire qu'un très mauvais hashCode(). Parce que cela ne peut pas générer une nouvelle clé identique à la clé de la paire clé-valeur d'origine dans put(). Autrement dit, les informations d'identification significatives contenues dans l'objet doivent être utilisées. Autrement dit, il doit générer un code de hachage basé sur le contenu de l'objet.
Cependant, equals() doit être capable de déterminer complètement l'identité de l'objet via hashCode().
Étant donné que hashCode() nécessite un traitement supplémentaire avant de générer l'indice du bucket, la plage de génération du code de hachage n'a pas d'importance, tant qu'il s'agit d'un entier.
Un bon hashCode() devrait produire des codes de hachage uniformément répartis.

"Effective Java™ Programming Language Guide (Addison-Wesley, 2001)" donne un guide de base sur la façon d'écrire un hashCode() décent :

Attribuez une constante de valeur non nulle à la int variable result, telle que 17
为对象内每个有意义的域f（即每个可以做equals()操作的域）计算出一个int散列码c：

域类型	计算
boolean	c=(f?0:1)
byte、char、short或int	c=(int)f
long	c=(int)(f^(f>>>32))
float	c=Float.floatToIntBits(f);
double	long l = Double.doubleToLongBits(f);
Object,其equals()调用这个域的equals()	c=f.hashCode()
数组	对每个元素应用上述规则

3. 合并计算散列码：result = 37 * result + c;
4. 返回result。
5. 检查hashCode()最后生成的结果，确保相同的对象有相同的散列码。

5 选择不同接口的实现

5.1 微基准测试的危险（Microbenchmarking dangers）

已证明0.0是包含在Math.random()的输出中的，按照数学术语，即其范围是[0,1)。

5.2 HashMap的性能因子

HashMap中的一些术语：

容量（Capacity）：表中的桶位数（The number of buckets in the table）。
初始容量（Initial capacity）：表在创建时所拥有的桶位数。HashMap和HashSet都具有允许你指定初始容量的构造器。
尺寸（Size）：表中当前存储的项数。
负载因子（Loadfactor）：尺寸/容量。空表的负载因子是0，而半满表的负载因子是0.5，依此类推。负载轻的表产生冲突的可能性小，因此对于插入和查找都是最理想的（但是会减慢使用迭代器进行遍历的过程）。HashMap和HashSet都具有允许你指定负载因子的构造器，表示当负载情况达到该负载的水平时，容器将自动增加其容量（桶位数），实现方式是使容量大致加倍，并重新将现有对象分布到新的桶位集中（这被称为再散列）。

HashMap使用的默认负载因子是0.75（只有当表达到四分之三满时，才进行再散列），这个因子在时间和空间代价之间达到了平衡。更高的负载因子可以降低表所需的空间，但会增加查找代价，这很重要，因为查找是我们在大多数时间里所做的操作（包括get()和put()）。

6 Collection或Map的同步控制

Collections类有办法能够自动同步整个容器。其语法与“不可修改的”方法相似：

package net.mrliuli.containers;

import java.util.*;public class Synchronization {    public static void main(String[] args){
        Collection<String> c = Collections.synchronizedCollection(new ArrayList<String>());
        List<String> list = Collections.synchronizedList(new ArrayList<String>());        Set<String> s = Collections.synchronizedSet(new HashSet<String>());        Set<String> ss = Collections.synchronizedSortedSet(new TreeSet<String>());
        Map<String, String> m = Collections.synchronizedMap(new HashMap<String, String>());
        Map<String, String> sm = Collections.synchronizedSortedMap(new TreeMap<String, String>());
    }
}

Copier après la connexion

6.1 快速报错（fail-fast）

Java容器有一种保护机制能够防止多个进行同时修改同一个容器的内容。Java容器类类库采用快速报错（fail-fast）机制。它会探查容器上的任何除了你的进程所进行的操作以外的所有变化，一旦它发现其他进程修改了容器，就会立刻抛出ConcurrentModificationException异常。这就是“快速报错”的意思——即，不是使用复杂的算法在事后来检查问题。

package net.mrliuli.containers;
import java.util.*;public class FailFast {    public static void main(String[] args){
        Collection<String> c = new ArrayList<>();
        Iterator<String> it = c.iterator();
        c.add("An Object");        try{
            String s = it.next();
        }catch(ConcurrentModificationException e){
            System.out.println(e);
        }
    }
}

Copier après la connexion

Java编程思想学习课时（三）第15章-泛型

Java编程思想学习课时（五）第18章-Java IO系统

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!