1 Satz- und Speicherreihenfolge
Das zu Set hinzugefügte Element muss sein definierteequals() Methode, um die Einzigartigkeit des Objekts sicherzustellen.
hashCode() ist nur erforderlich, wenn diese Klasse in HashSet oder LinkedHashSet platziert ist. Aus Gründen eines guten Programmierstils sollten Sie jedoch immer die Methode hashCode() überschreiben, wenn Sie die Methode equal() überschreiben.
Wenn ein Objekt in einem beliebigen sortierten Container verwendet wird, z. B. SortedSet (TreeSet ist die einzige Implementierung von it) , dann muss es die Schnittstelle Comparable implementieren.
Beachten Sie, dass SortedSet „Elemente nach der Vergleichsfunktion des Objekts sortieren“ bedeutet, obwohl dies der Fall ist beziehen sich nicht auf „die Reihenfolge, in der Elemente eingefügt werden“. Einfügungsauftrag wird mit LinkedHashSet gespeichert.
2 Queue
stellt gleichzeitige Anwendungen in die Warteschlange. Die einzigen zwei Implementierungen von Queue in Java SE5 sind LinkiedList und PriorityQueue, sie unterscheiden sich nur im Sortierverhalten und es gibt keinen Unterschied in der Leistung.
Die Reihenfolge der Prioritätswarteschlange PriorityQueue wird auch durch die Implementierung von Comparable gesteuert.
3 Karte
Kartentabelle (auch bekannt als Assoziatives ArrayAssoziativ Array).
3.1 Leistung
HashMap verwendet einen speziellen Wert, der als Hash-Code (Hash-Code) bezeichnet wird, um den Schlüssel „Suche langsam“ zu ersetzen. Ein Hash-Code ist ein „relativ eindeutiger“ Wert, der zur Darstellung eines Objekts verwendet wird. Er wird durch die Umwandlung int bestimmter Informationen über das Objekt erreicht und generiert. hashCode() ist eine Methode in der Stammklasse Object, sodass alle Objekte Hash-Codes generieren können.
Die Anforderungen für Schlüssel, die in einer Karte verwendet werden, sind die gleichen wie für Elemente in einem Set:
, um zu bestimmen, ob der aktuelle Schlüssel mit dem Schlüssel übereinstimmt, der in der Datei vorhanden ist Tisch.
Die Standardeinstellung Object.equals() vergleicht nur die Adresse des Objekts equals(). Wenn Sie Ihre eigene Klasse als Schlüssel von HashMap
verwenden möchten, müssen Sie sowohl als auch gleichzeitig überschreiben. hashCode() Die richtige equals()Methode muss die folgenden fünf Bedingungen erfüllen:
equals()Reflexivität.
Sie möchten ein Objekt verwenden, um ein anderes Objekt zu finden
.
Die Kartenimplementierungsklasse verwendet Hashing, um
die Abfragegeschwindigkeit zu erhöhen
. Der Wert von Hashing liegt in der Geschwindigkeit
:
Hashing macht Abfragen schnell. Da der Engpass bei Abfragegeschwindigkeit liegt, besteht eine der Lösungen darin, die Schlüssel sortiert zu halten und dann für die Abfrage zu verwenden. Collections.binarySearch() Hashing geht noch einen Schritt weiter und speichert den Schlüssel irgendwo, damit
schnell gefunden werden kann. Die schnellste Datenstruktur zum Speichern einer Reihe von Elementen ist ein Array. Verwenden Sie es daher zur Darstellung der Schlüsselinformationen (beachten Sie sorgfältig, dass ich die Schlüsselinformationen meine, nicht den Schlüssel selbst). Da das Array seine Kapazität jedoch nicht anpassen kann, gibt es ein Problem: Wir möchten eine unbestimmte Anzahl von Werten in der Map speichern, aber was ist, wenn die Anzahl der Schlüssel durch die Kapazität des Arrays begrenzt ist? Die Antwort lautet: Arrays speichern nicht die Schlüssel selbst. Stattdessen wird aus dem Schlüsselobjekt eine Zahl als -Index des Arrays generiert. Diese Zahl ist der Hash-Code, dargestellt durch die Methode hashCode(), die in Object definiert und möglicherweise von Ihrer Klasse überschrieben wird (in der Informatiksprache genannt). Hash-Funktion ) wird generiert.
Um das Problem der festen Array-Kapazität zu lösen, können verschiedene Schlüssel denselben Index erzeugen. Das heißt, es kann zu Kollisionen kommen, d. h. Hashcodes müssen nicht eindeutig sein. Daher spielt es keine Rolle, wie groß das Array ist, jeder Schlüssel findet immer seinen Platz im Array.
4.2 Hashing verstehen
Zusammenfassend besteht Hash darin, eine Zahl aus einem Objekt zu generieren und diese (als unteren Teil) zu speichern des Arrays) (Standard) und finden Sie dann einfach direkt die Nummer, wenn Sie nach diesem Objekt suchen. Der Zweck des Hashings besteht also darin, die Suchgeschwindigkeit zu verbessern, und das Mittel darin Kombinieren Sie die von einem Objekt generierte Zahl mit der zugehörigen und gespeicherten Zahl (über ein Array, das als Hash-Tabelle bezeichnet wird). Die generierte Zahl ist der Hash-Code . Die Methode zur Generierung dieses Hash-Codes heißt Hash-Funktion (hashCode()).
4.3 HashMap-Abfrageprozess (schneller Grund)
Daher ist der Prozess der Abfrage eines HashMap in key:
Zuerst berechnen der Hash-Wert Spaltencode
Dann verwenden Sie den Hash-Code, um das Array abzufragen (der Hash-Code wird als variabler Array-Index verwendet)
Wenn kein Konflikt vorliegt, wird dieser generiert. Es gibt nur ein Hash-Code-Objekt, dann ist die Position des Array-Index, der dem Hash-Code entspricht, das zu findende Element
Wenn ja Bei einem Konflikt befindet sich der Array-Index, der dem Hash-Code entspricht. Das Element speichert ein list und führt dann mit der list-Methode eine lineare Abfrage für den Wert in equals() durch.
Anstatt also das gesamte list abzufragen, springt schnell zu einer bestimmten Position im Array und vergleicht nur sehr wenige Elemente . Deshalb HashMapwarum es so schnell ist.
4.4 Implementierung einer einfachen Hash-Map
Der Slot (Slot) in der Hash-Tabelle wird normalerweise als Bucket-Position(Bucket)
- Um den Hash gleichmäßig zu machen, verwendet die Anzahl der Buckets normalerweise eine
Primzahl (Es ist eine Primzahl in JDK5 und In JDK7 Powered ist es bereits eine Ganzzahl von 2 ).
Es stellt sich heraus, dass Primzahlen eigentlich nicht die ideale Kapazität für einen Hash-Bucket sind. In letzter Zeit verwenden Javas Hash-Funktionen (durch umfangreiche Tests) 2 hoch . Division und Rest sind die langsamsten Operationen auf modernen Prozessoren. Bei Verwendung einer Hash-Tabelle mit einer ganzzahligen Potenz von 2 der Länge kann die -Maske anstelle der Division verwendet werden. Da get() die am häufigsten verwendete Operation ist, ist die %-Operation zum Ermitteln des Restes der teuerste Teil, und die Verwendung der ganzzahligen Potenz von 2 kann diesen Overhead eliminieren (dies kann auch Auswirkungen auf hashCode() haben).
- Die get()-Methode berechnet den Index im Buckets-Array auf die gleiche Weise wie die put()-Methode. Dies ist wichtig, da dadurch sichergestellt wird, dass beide Methoden
Gleiches berechnen können Standort .
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'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());
}
}Nach dem Login kopieren
4.5 Überschreiben von hashCode()
Beim Entwerfen von „hashCode()“ zu berücksichtigende Faktoren:
- Die wichtigsten Faktoren:
Der Aufruf von hashCode() für dasselbe Phasenobjekt sollte denselben Wert erzeugen, wann immer .
- Darüber hinaus sollte hashCode() nicht auf eindeutige Objektinformationen angewiesen sein, insbesondere nicht auf deren Wert, da dies nur zu einem sehr schlechten hashCode() führen kann. Denn dadurch kann kein neuer Schlüssel generiert werden, der mit dem Schlüssel im ursprünglichen Schlüssel-Wert-Paar in put() übereinstimmt. Das heißt, es sollten die
aussagekräftigen Identifikationsinformationen innerhalb des Objekts verwendet werden. Das heißt, es muss einen Hash-Code basierend auf dem Inhalt des Objekts generieren.
- Equals() muss jedoch in der Lage sein, die Identität des Objekts durch hashCode() vollständig zu bestimmen.
- Da hashCode() vor der Generierung des Subskripts des Buckets eine weitere Verarbeitung erfordert, spielt der Generierungsbereich des Hash-Codes keine Rolle, solange es sich um einen int handelt.
- Ein guter hashCode() sollte gleichmäßig verteilte Hash-Codes erzeugen.
„Effective Java™ Programming Language Guide (Addison-Wesley, 2001)“ gibt eine grundlegende Anleitung zum Schreiben eines anständigen hashCode():
- Weisen Sie der
-Variable int eine Konstante mit einem Wert ungleich Null zu, z. B. result17
为对象内每个有意义的域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>());
}
}Nach dem Login kopieren
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);
}
}
}Nach dem Login kopieren
相关文章：
Java编程思想学习课时（三）第15章-泛型
Java编程思想学习课时（五）第18章-Java IO系统
Das obige ist der detaillierte Inhalt vonJava-Programmiergedanken-Lernklasse (4) Kapitel 17 – Ausführliche Diskussion von Containern. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
