![Level 26. Antworten auf Interviewfragen zum Levelthema. Teil 1. Fragen 1-5, 10. - 1]()
Da sich die Zusammenfassung als ziemlich umständlich herausstellte, habe ich sie in zwei Teile geteilt. Der zweite Teil enthält Antworten auf Fragen zu Kankarency und Multithreading. Der erste Teil enthält den Rest. Das Schreiben war ziemlich schwierig. Ich verstehe immer noch nicht viel, daher sind Kommentare, Anmerkungen und Ergänzungen wie immer willkommen.)
1. Wie verwende ich die Comparable-Schnittstelle?
Die Schnittstelle
Comparabledeklariert nur eine Methode
compareTo(Object obj), die dazu dient, die Reihenfolge von Klassenobjekten zu implementieren. Es eignet sich zum Sortieren geordneter Listen oder Arrays von Objekten. Diese Methode vergleicht das aufgerufene Objekt mit
obj. Im Gegensatz zur Methode , die
true oder
false
equals zurückgibt , wird Folgendes zurückgegeben:
compareTo
- 0, wenn die Werte gleich sind;
- Ein negativer Wert, wenn der Aufgerufene kleiner als der Parameter ist;
- Positiv, wenn der Aufgerufene größer als der Parameter ist.
Es eignet sich vor allem zum Sortieren geordneter Listen (
java.util.List) und Arrays von Objekten. Wenn die Liste/das Array Elemente enthält, die diese Schnittstelle implementieren, können sie automatisch nach sortiert werden
java.util.Collections.sort(List)/Arrays.sort(Object[]). Das Konzept der natürlichen Ordnung ist mit einer Schnittstelle verbunden
Comparable, da es eine natürliche Ordnung für Instanzen jeder Klasse festlegt, die diese Schnittstelle implementiert. Mit anderen Worten: Die Reihenfolge (x, y) entspricht der Erfüllung der Bedingung
x.compareTo(y) <= 0. Die Regeln der Implementierung
Comparablebzw. ihrer Methode
compareTo(Object)lauten wie folgt (x und y sind Instanzen der Klasse, die implementiert
Comparable):
x.compareTo(y)gibt -1 oder 1 zurück, wenn x vor bzw. nach y liegen soll. Wenn die Methode 0 zurückgibt, sind die Ordnungen (x, y) und (y, x) äquivalent.- Wenn
sign(a)es sich um eine Funktion handelt, die für a jeweils -1,0,1 kleiner als 0, gleich 0 und größer als 0 zurückgibt, muss die Gleichheit erfüllt sein sign(x.compareTo(y))==-sign(y.compareTo(x)). Was logisch ist: Wenn x vor y kommt, muss y nach x kommen und umgekehrt.
- Wenn
x.compareTo(y) > 0und y.compareTo(z) > 0dann x.compareTo(z) > 0– das Verhältnis der Transitivität von Ungleichungen.
- Wenn
x.compareTo(y) == 0dann sign(x.compare(z)) == sign(y.compareTo(z))für jedes z.
- Der Aufruf
x.compareTo(null)muss eine Ausnahme auslösen NullPointerException. Dies ist eine Diskrepanz mit der Implementierungslogik equals(ich möchte Sie daran erinnern, dass sie falsex.equals(null) zurückgibt ).
- Wenn der Typ von y nicht mit x verglichen werden kann, muss der Aufruf
x.compareTo(y)eine Ausnahme auslösen ClassCastException.
(x.compareTo(y) == 0) == x.equals(y), d.h. Der Aufruf x.compareTo(y)muss genau dann 0 zurückgeben, wenn er truex.equals(y) zurückgibt . Dies ist eine Regel der Konsistenz und es ist sehr wichtig, sie zu berücksichtigen.
Quellen:
2. Wie verwende ich die Comparator-Schnittstelle?
Die Schnittstelle
Comparatordeklariert zwei Methoden
compare(Object obj1, Object obj2)und
equals(Object obj). Bei Verwendung der Schnittstelle
Comparatorist die Logik zum Vergleichen eines Objektpaars nicht innerhalb der Klasse/des Objekts verborgen, sondern in einer separaten Klasse implementiert. Die Methode
compare(x,y)ist genau die gleiche wie der Aufruf
x.compareTo(y). Alle Regeln müssen genauso befolgt werden wie die Regeln für die Implementierung einer
compareTo(Object)Schnittstellenmethode
Comparable.
Comparatorkann überall dort eingesetzt werden, wo eine Sortierung erforderlich ist. In diesem Fall zeigt sich zunächst die nötige Flexibilität – die Möglichkeit, mehrere Sortierregeln umzusetzen. Und zweitens implementieren die zu sortierenden Objekte möglicherweise nicht die
Comparable. Wenn sie es umsetzen,
Comparatorhat es Vorrang. Die Schnittstelle
Comparatordefiniert auch eine Methode
equals(Object), so paradox es auch erscheinen mag. Diese Methode vergleicht die Schnittstelleninstanzen selbst
Comparatorund sollte nur dann
„true“ zurückgeben , wenn die verglichenen Objekte dieselbe Sortierreihenfolge aufweisen. Es ist jedoch immer sicher, die ursprüngliche Implementierung
Object.equals(Object)intakt zu lassen
. Quelle:
3. Über welche Methoden verfügt die Collections-Klasse?
public static <T> boolean addAll(Collection<? super T> c, T... elements) Die Methode fügt
elementsder Sammlung Array-Elemente hinzu
Collection<? super T> c. Elemente können einzeln oder als Array angegeben werden. Wenn Elemente einzeln angegeben werden, bietet diese Methode die Möglichkeit, alle Elemente bequem zu einer vorhandenen Sammlung hinzuzufügen:
Collections.addAll(flavors, "Peaches 'n Plutonium", "Rocky Racoon");
public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key)
public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c) Beide Methoden durchsuchen die im Parameter übergebene Liste nach dem im Parameter übergebenen Objekt mithilfe eines binären Suchalgorithmus. Gibt den Index des Elements zurück, wenn ein solches Element in der Liste vorhanden ist, andernfalls wird der Index des ersten Elements der Liste größer als zurückgegeben
key. Wenn alle Elemente kleiner als sind
key, wird zurückgegeben
list.size(). Vor der Verwendung dieser Methoden müssen die Listen sortiert werden. Im ersten Fall erfolgt die Sortierung aufsteigend in der „natürlichen“ Reihenfolge der Listenelemente (wie bei der Verwendung
Collections.sort(list)). Im zweiten Fall muss die Liste aufsteigend in der vom übergebenen Komparator vorgegebenen Reihenfolge sortiert werden (dieselbe Reihenfolge wie bei Verwendung von
Collections.sort(list, c)[hier ist „mit“ ein Komparator aus den Parametern der beschriebenen Methode]).
public static <E> Collection<E> checkedCollection(Collection<E> c, Class<E> type)
Präambel: der Generics-Mechanismus in der Sprache bietet eine Typprüfung zur Kompilierungszeit. Normalerweise reicht das aus, aber es gibt Zeiten, in denen das nicht der Fall ist. Zum Beispiel übertragen wir unsere Sammlung an einen uns unbekannten Ort in den Bibliothekscode und möchten wirklich, dass der Code dieser „Drittanbieter-Bibliothek“ kein Element des falschen Typs in unsere Sammlung einfügt. Dies ist mögliches Problem Nummer 1. Mögliches Problem Nummer 2 ist das Folgende. Nehmen wir an, unser Programm gibt uns eine Nachricht
ClassCastException
, die uns darüber informiert, dass ein Element des falschen Typs in die Sammlung eingefügt wurde. Leider kann diese Ausnahme jederzeit ausgelöst werden, nachdem ein falsches Element eingefügt wurde, und gibt uns normalerweise nur wenige oder gar keine Informationen über die Ursache des Problems. Mit der Methode Methode
checkedCollectionkönnen wir uns die Probleme eins und zwei ersparen, denn Diese Methode erstellt eine Sammlung, die zur Laufzeit überprüfbar ist. Lösung von Problem Nummer zwei mit dieser Methode: Wir haben zum Beispiel dieses und es fällt heraus
ClassCastException.
Collection<String> c = new HashSet<String>();
Der obige Code kann vorübergehend ersetzt werden durch:
Collection<String> c = Collections.checkedCollection(
new HashSet<String>(), String.class);
Wenn wir das Programm erneut ausführen, lokalisieren wir die Codezeile, die ein Element des falschen Typs in unsere Sammlung einfügt. Verwandte Methoden meiner Meinung nach:
public static <E> List<E> checkedList(List<E> list,Class<E> type)
public static <K,V> Map<K,V> checkedMap(Map<K,V> m, Class<K> keyType,Class<V> valueType)
public static <E> Set<E> checkedSet(Set<E> s,Class<E> type)
public static <K,V> SortedMap<K,V> checkedSortedMap(SortedMap<K,V> m,Class<K> keyType,Class<V> valueType)
public static <E> SortedSet<E> checkedSortedSet(SortedSet<E> s,Class<E> type)
public static <T> void copy(List<? super T> dest,List<? extends T> src) Die Methode kopiert src-Elemente nach dest. Die Indizes der kopierten Elemente bleiben gleich.
public static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll)
public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll)
public static <T> T min(Collection<? extends T> coll,Comparator<? super T> comp)
public static <T> T max(Collection<? extends T> coll,Comparator<? super T> comp) Methoden geben das minimale/maximale Element in der Sammlung in Bezug auf die „natürliche Reihenfolge“ (Comparable-Schnittstelle) oder die Reihenfolge des übergebenen Komparators zurück.
Gibt „true“
public static boolean disjoint(Collection<?> c1,Collection<?> c2) zurück , wenn die Sammlungen keine identischen Elemente haben. – eine leere Liste, Karte bzw. Menge zurückgeben; – füllt die Liste mit dem angegebenen Element; – gibt die Anzahl der Vorkommen eines bestimmten Elements in der Sammlung zurück; – gibt eine Liste von
n angegebenen Elementen zurück; – ersetzt alle angegebenen Elemente durch neue; – „kehrt“ die Liste um; – verschiebt die Liste zyklisch um eine angegebene Anzahl von Elementen; – mischt Listenelemente; – eine Set-, Listen- und Anzeigekarte erstellen, die aus einem Element besteht; – Sortieren der Liste in natürlicher Reihenfolge und entsprechende Verwendung; – tauscht Listenelemente an angegebenen Positionen aus.
Quellen:
<T> List <T> emptyList(), <K,V> Map <K,V> emptyMap(),
<T> Set <T> emptySet()
<T> void fill(List<? super T> list, T obj)
int frequency(Collection<?> c, Object o)
<T> List <T> nCopies(int n, T o)
<T> boolean replaceAll(List<T> list, T oldVal, T newVal)
void reverse(List<?> list)
void rotate(List<?> list, int distance)
void shuffle(List<?> list)
<T> Set <T> singleton(T o), singletonList(T o), singletonMap(K key, V value)
<T extends Comparable<? super T>> void sort(List<T> list),
<T> void sort(List<T> list, Comparator<? super T> c)
Comparator
void swap(List<?> list, int i, int j)
4. Welche Methoden hat die Arrays-Klasse?
Eine vollständige Liste der Methoden der Arrays-Klasse finden Sie in
der Dokumentation . In dieser Zusammenfassung werde ich nur einige davon zitieren. [Methoden aus der Dokumentation übersetzt und leider den größten Teil meiner Übersetzung verloren. Schade, und ich möchte keine Zeit mit der gleichen Sache verschwenden, also füge ich ein, was ich gegoogelt habe]
public static <T> List<T> asList(T... a) generiert eine Liste basierend auf einem Array. Das Array wird für die interne Darstellung der Liste verwendet. Dadurch bleibt die Verbindung zwischen der Liste und dem ursprünglichen Array erhalten: Änderungen im Array werden in der Liste widergespiegelt:
String[] a = { "foo", "bar", "baz"};
List<String> list = Arrays.asList(a);
System.out.println(list);
a[0] = "aaa";
System.out.println(list);
Änderungen in der Liste werden im Array widergespiegelt:
String[] a = { "foo", "bar", "baz"};
List<String> list = Arrays.asList(a);
System.out.println(list);
list.set(0, "bbb");
System.out.println(Arrays.toString(a));
Wenn das Array Objekte enthält, verweisen sowohl das Array als auch die Liste offensichtlich auf dieselben Instanzen:
Object[] a = { new Object(), new Object(), new Object()};
List<Object> list = Arrays.asList(a);
System.out.println(a[0] == list.get(0));
int binarySearch(параметры)– eine überladene Methode zum Organisieren einer binären Suche nach einem Wert in Arrays von Grund- und Objekttypen. Gibt die Position des ersten Treffers zurück;
void fill(параметры)– eine überladene Methode zum Füllen von Arrays mit Werten verschiedener Typen und Grundelementen;
void sort(parameters) – eine überladene Methode zum Sortieren eines Arrays oder eines Teils davon mit und ohne die Comparator-Schnittstelle;
static <T> T[] copyOf(T[] original, int newLength)– füllt ein Array einer bestimmten Länge, verwirft Elemente oder füllt bei Bedarf mit Null auf;
static <T> T[] copyOfRange(T[] original, int from, int to)– kopiert den angegebenen Bereich des Arrays in ein neues Array;
<T> List<T> asList(T… a)– eine Methode, die Array-Elemente in ein Objekt vom Typ List<T> kopiert.
Quelle:
5. Wie heißt die Sortierung, die beim Aufruf von Collections.sort() verwendet wird?
Aus der Dokumentation : Die Implementierung ist eine Adaption der Python-Listensortierung (TimSort) von Tim Peters. Diese Implementierung speichert die Liste in einem Array, sortiert das Array, durchläuft dann die Liste und lädt jedes Listenelement aus dem entsprechenden Array-Element neu. Dadurch wird die n*n log(n)-Komplexität vermieden, die durch den Versuch entstehen würde, eine verknüpfte Liste direkt zu sortieren.
Aus dem Wiki : Timsort ist ein hybrider Sortieralgorithmus, der Einfügungssortierung und Zusammenführungssortierung kombiniert und 2002 von Tim Peters veröffentlicht wurde. Timsort ist derzeit der Standard-Sortieralgorithmus in Python, OpenJDK 7 und in Android JDK 1.5 implementiert. Die Hauptidee des Algorithmus besteht darin, dass sortierbare Datenarrays in der realen Welt häufig geordnete Unterarrays enthalten. Bei solchen Daten ist Timsort deutlich schneller als viele Sortieralgorithmen.
10. Was ist ein Iterator?
Die in der JDK-Version 1.2 der Java-Sprache eingeführte Schnittstelle
java.util.Iteratorermöglicht die Iteration von Containerklassen. Jeder Iterator implementiert Methoden
next()und
hasNext()kann optional eine unterstützen
remove(). Iteratoren werden von den entsprechenden Containerklassen erstellt, normalerweise von der
iterator(). Die Methode
next()setzt den Iterator auf den nächsten Wert und gibt den angegebenen Wert an den Iterator zurück. Bei der ersten Erstellung zeigt der Iterator auf einen speziellen Wert vor dem ersten Element, sodass das erste Element erst nach dem ersten Aufruf von abgerufen werden kann
next(). Um den Zeitpunkt zu bestimmen, an dem alle Elemente im Container iteriert wurden, wird die Testmethode verwendet
hasNext(). Das folgende Beispiel demonstriert die einfache Verwendung von Iteratoren:
Iterator iter = list.iterator();
while (iter.hasNext())
System.out.println(iter.next());
Bei einer Typsammlung, die dies unterstützt,
remove()entfernt die Iteratormethode das zuletzt „besuchte“ Element aus dem Container. Fast alle anderen Arten der Containeränderung während der Iteration sind unsicher. Darüber hinaus
java.util.Listverfügt for
java.util.ListIteratorüber eine ähnliche API, ermöglicht jedoch eine Vorwärts- und Rückwärtsiteration, indem es die Definition des aktuellen Index in der Liste bereitstellt und anhand seiner Position zum Element wechselt.
Quelle:
Teil 2
GO TO FULL VERSION