SF Technology-Interview

Obwohl dies ist eine äußerst häufige Frage im Vorstellungsgespräch, aber während des Vorstellungsgesprächs haben viele Studenten sie immer noch nicht gut beantwortet. Die n-te Potenz von 2 wird in der Antwort erwähnt. Der Interviewer wird wahrscheinlich weiterhin verwandte Fragen stellen. Wenn es noch unklar ist, wird empfohlen, HashMap systematisch zu studieren. 🎜

Ich habe bereits zwei Artikel auf meinem Blog gepostet: 🎜 blockquote >

HashMapDer Prozess des Hinzufügens eines Elements

HashMapDer Prozess des Hinzufügens von Elementen in put kann in die folgenden 9 Schritte unterteilt werden: 🎜

• 1. Rufen Sie bei Verwendung der put()-Methode direkt die putVal()
• 2 auf. Stellen Sie beim Putten zunächst fest, ob das Array leer ist, und führen Sie, wenn es leer ist, eine Größenänderungsoperation durch
• 3 . Indizieren Sie das Array mit einem Hash. Die Länge -1 wird mit dem Hash-Wert des Schlüssels verknüpft, um den Index im Array zu erhalten. Wenn die durch den Index angegebene Position leer ist, bedeutet dies, dass sie eingefügt werden kann und ein neuer Knoten eingefügt werden kann direkt
• 4. Bestimmen Sie den aktuellen Schlüssel. Wenn er vorhanden ist, ersetzen Sie ihn. Wenn die Ersetzung erfolgreich ist, geben Sie den alten Wert zurück. 5. Wenn der Schlüssel nicht vorhanden ist ist ein Baumtyp. Wenn es sich um einen Baumtyp handelt, fügen Sie ihn gemäß der Baumoperation hinzu In der verknüpften Liste wird dann die Schleifenverarbeitungslogik eingegeben
• 7 Nachdem Sie die Schleifenlogik eingegeben haben, prüfen Sie zunächst, ob der nächste Knoten des Kollisionsknotens leer ist leer, fügen Sie den neuen Knoten in
• 8 ein. Beurteilen Sie nach dem Einfügen, ob die aktuelle verknüpfte Liste die maximal zulässige Länge der verknüpften Liste von 8 überschreitet. Wenn sie überschritten wird, wird sie zum Einfügen in einen rot-schwarzen Baum konvertiert
• 9. Wenn die Indextabelle der Karte leer ist oder die aktuelle Indextabellenlänge weniger als 64 beträgt (die maximale Index-Array-Tabellenlänge für die Rot-Schwarz-Baumkonvertierung), führen Sie andernfalls einfach den Größenänderungsvorgang aus Der kollidierte Knoten ist nicht leer. Fügen Sie dann einfach den Knoten hinzu und fügen Sie ihn entlang des Baums des kollidierten Knotens ein
• Sie können den Blog-Beitrag auf meinem Blog lesen: Drei Jahre essentieller HashMap-Quellcode: http://www .woaijava.cc/blog/ 211
• Was ist ein rot-schwarzer Baum und was sind seine Eigenschaften?

Der Red Black Tree ist ein spezialisierter AVL-Baum (Balanced Binary Tree). Er verwendet bestimmte Operationen, um das Gleichgewicht des binären Suchbaums während Einfüge- und Löschvorgängen aufrechtzuerhalten und so eine höhere Suchleistung zu erzielen.

Es gibt 5 Merkmale rot-schwarzer Bäume:

Die Knoten sind rot oder schwarz.

Der Wurzelknoten ist schwarz.
Alle Blätter sind schwarz (Blätter sind NIL-Knoten)

• Die beiden untergeordneten Knoten jedes roten Knotens sind schwarz. (Es kann nicht auf allen Pfaden von jedem Blatt zur Wurzel zwei aufeinanderfolgende rote Knoten geben.)

• Alle Pfade von jedem Knoten zu jedem seiner Blätter enthalten die gleiche Anzahl schwarzer Knoten.

Tatsächlich ist diese Frage nicht schwierig. Was selten vorkommt, ist, dass einige Interviewer nach der Funktionsweise rot-schwarzer Bäume fragen, nach links und rechts drehen ... Ich habe Hunderte von Menschen interviewt und nur einen Nur wenige können es sagen.

Die Eigenschaften des B+-Baums, wie viele Schichten, wie viele Daten können maximal gespeichert werden?

Die Eigenschaften des B+-Baums sind nur

• 1 haben eine Indexfunktion, das heißt, Nicht-Blattknoten können nur Schlüssel, aber keinen Wert speichern
• 2 Alle Blattknoten des Baums bilden eine geordnete verknüpfte Liste, und alle Daten können in der Reihenfolge der Schlüsselsortierung durchlaufen werden .

B+-Bäume sind normalerweise 1-spurig und 3-schichtig.

InnoDB-SeitengrößeDer Standardwert ist 16 KB:

• Angenommen, die Größe eines Datensatzes beträgt 1 KB, dann können 16 Datenelemente auf einer Datenseite gespeichert werden (andere Datenstrukturen auf der Seite werden ignoriert)
• Angenommen, der Primärschlüssel ist int und die Zeigergröße beträgt 6B, dann kann eine Indexseite 16KB/(4B+6B)≈1638 Indizes 16KB/(4B+6B)≈1638个索引

所以，两层的B+树可以存储：16*1638=26208条数据；三层的B+树可以存储：16*1638*1638=42928704条数据。

MySQL的索引为什么使用B+树而不使用跳表？

B+树是多叉树结构，每个结点都是一个16k的数据页，能存放较多索引信息，所以扇出很高。三层左右就可以存储2kw

Ein zweischichtiger B+-Baum kann also Folgendes speichern: 16*1638=26208 Datenstücke; der dreischichtige B+-Baum kann Folgendes speichern: 16*1638*1638=42928704 Datenstücke. 🎜🎜🎜🎜Warum verwendet der Index von MySQL einen B+-Baum anstelle einer Sprungtabelle? 🎜🎜🎜🎜🎜B+-Baum🎜 ist eine Multi-Tree-Struktur. Jeder Knoten ist eine 16-KByte-Datenseite, die mehr Indexinformationen speichern kann, sodass der Fan-Out sehr hoch ist. 🎜Drei Ebenen🎜 können gespeichert werdenSprungliste ist eine verknüpfte Listenstruktur, ein Datenelement ist ein Knoten. Wenn die unterste Ebene gespeichert werden soll2kw Daten, und jede Abfrage muss den Effekt einer 2kw数据，且每次查询都要能达到二分查找的效果，2kw大概在2的24次方左右，所以，跳表大概高度在24层左右。最坏情况下，这24层数据会分散在不同的数据页里，也即是查一次数据会经历24次磁盘IO。

因此存放同样量级的数据，B+树的高度比跳表的要少，如果放在MySQL数据库上来说，就是磁盘IO次数更少，因此B+树查询更快。

而针对写操作，B+树需要拆分合并索引数据页，跳表则独立插入，并根据随机函数确定层数，没有旋转和维持平衡的开销，因此跳表的写入性能会比B+树要好。

其实，MySQL的存储引擎是可以换的，以前mysql 5.5是myisam，后来才有的innodb，它们底层索引用的都是B+树。也就是说，你完全可以造一个索引为跳表的存储引擎装到MySQL里。事实上，facebook造了个rocksDB的存储引擎，里面就用了跳表。直接说结论，它的写入性能确实是比innodb要好，但读性能确实比innodb要差不少。感兴趣的话，可以在文章最后面的参考资料里看到他们的性能对比数据。

Redisbinären Suche erzielen, 2kw ist ungefähr 2 hoch 24 ist ungefähr, also liegt die ungefähre Höhe des Sprungtisches bei ungefähr 24. Etage

. Im schlimmsten Fall sind diese 24 Datenschichten auf verschiedene Datenseiten verteilt, was bedeutet, dass eine Datenabfrage

24 Festplatten-IOs

erfordert. 🎜🎜Um die gleiche Datenmenge zu speichern, ist die Höhe des B+-Baums geringer als die der Skip-Tabelle. Wenn er in einer MySQL-Datenbank platziert wird, bedeutet dies, dass 🎜die Anzahl der Festplatten-IOs geringer ist, also der B+-Baum Abfrage ist schneller🎜. 🎜🎜Für 🎜Schreibvorgänge🎜 muss der B+-Baum Indexdatenseiten teilen und zusammenführen, und die Sprungtabelle wird unabhängig eingefügt, und die Anzahl der Ebenen wird basierend auf einer Zufallsfunktion bestimmt , also 🎜die Schreibleistung der Skip-Tabelle ist besser als die des B+-Baums. 🎜🎜🎜Tatsächlich kann die 🎜Speicher-Engine von MySQL geändert werden🎜 Bisher war MySQL 5.5 myisam, das später kaminnodb, ihre zugrunde liegenden Indizes verwenden alle 🎜B+tree🎜. Mit anderen Worten: Sie können eine Speicher-Engine vollständig mit einem Skip-Table-Index erstellen und in MySQL installieren. Tatsächlich rocksDBs Speicher-Engine, die 🎜hopping Table 🎜 verwendet . Fazit: Seine 🎜Schreibleistung🎜 ist tatsächlich besser als die von Innodb, aber seine 🎜Leseleistung🎜 ist tatsächlich viel schlechter als die von Innodb. Wenn Sie interessiert sind, können Sie die Leistungsvergleichsdaten in den 🎜Referenzen🎜 am Ende des Artikels einsehen. 🎜

🎜🎜Redis Warum Sprunglisten anstelle von B+-Bäumen oder Binärbäumen verwenden? 🎜🎜🎜🎜Denn das Prinzip des B+-Baums besteht darin, dass Blattknoten Daten speichern und Nicht-Blattknoten Indizes speichern können. Dadurch wird die Knotengröße auf die Größe der Festplattenseite festgelegt der Festplattenvorverarbeitung. Jedes Mal, wenn eine Festplattenseite gelesen wird, wird ein ganzer Knoten gelesen. Jeder Blattknoten verfügt außerdem über Zeiger auf den vorherigen und nächsten Knoten, um Festplatten-IO zu minimieren. Da das Lesen von Daten im Speicher ein Millionstel der Zeit beträgt, die für das Lesen von E/A von der Festplatte benötigt wird, und Redis Daten im Speicher verarbeitet und keine E/A erfordert, werden Sprungtabellen verwendet

Was ist bei der Indexerstellung zu beachten?

Diese Frage kann auch verwendet werden, wenn Sie fragen, welche SQL-Optimierungen Sie kennen.

• Die am besten geeigneten Spalten für die Indizierung sind die Spalten, die nach dem Schlüsselwort WHERE 子句中的列，或连接子句中的列，而不是出现在 SELECT erscheinen.
• Je größer die Kardinalität der Indexspalte ist, desto besser ist der Indexierungseffekt.
• Das Erstellen zusammengesetzter Indizes je nach Situation kann die Abfrageeffizienz verbessern.
• Vermeiden Sie die Erstellung zu vieler Indizes, da diese zusätzlichen Speicherplatz beanspruchen und die Effizienz von Schreibvorgängen verringern.
• Wählen Sie für den Primärschlüssel einen möglichst kurzen Datentyp, um die Festplattennutzung des Index effektiv zu reduzieren und die Abfrageeffizienz zu verbessern.
• Beim Indizieren von Zeichenfolgen sollten Sie eine Präfixlänge anpassen, was viel Indexplatz sparen kann.

Wenn die Datenmenge in einer einzelnen Tabelle mehrere zehn Millionen überschreitet, wie kann sie dann optimiert werden?

1. Berücksichtigen Sie beim Entwerfen der Datenbank und beim Erstellen der Tabelle: Eine einzelne Tabelle sollte nicht zu viele Felder enthalten. Je mehr Indizes, desto besser Wenn die an den Befehlen WHERE und ORDER BY beteiligten Spalten indiziert werden, können Sie mit EXPLAIN prüfen, ob ein Index oder ein vollständiger Tabellenscan verwendet wird. Wählen Sie den entsprechenden Datentyp aus der entsprechende Indextyp usw.

2. Beim Schreiben von SQL müssen Sie darauf achten, dass die Anzahl der Seiten nicht zu groß ist * indem Sie das langsame Abfrageprotokoll aktivieren, die zu findenden Felder auflisten usw.

3. Auswahl der Speicher-Engine: MyISAM eignet sich für SELECT-intensive Tabellen, während InnoDB für INSERT- und UPDATE-intensive Tabellen geeignet ist.

4. Unterdatenbank und Untertabelle, zum Beispiel: Unterdatenbank Es wird empfohlen, eine Unterdatenbank wirklich zu trennen, was ebenfalls hohe Entwicklungskosten mit sich bringt. Das ist den Gewinn nicht wert! Es wird nicht empfohlen, Tabellenaufteilung zu verwenden, um eine große Tabelle gemäß dem oben genannten Prozess zu optimieren, die Abfrage jedoch immer noch hängen bleibt, dann die Tabelle in mehrere Tabellen aufzuteilen, eine Abfrage in mehrere Abfragen aufzuteilen und dann die kombinierte Abfrage zurückzugeben Ergebnisse an den Benutzer. Die Tabellenaufteilung wird in vertikale und horizontale Aufteilung unterteilt. Als Aufteilungselement wird normalerweise ein bestimmtes Feld verwendet. Beispielsweise wird das ID-Feld verwendet, um die Tabelle in 100 Tabellen aufzuteilen: Der Tabellenname lautet tableName_id%100. Allerdings: Untertabellen erfordern eine Änderung des Quellprogrammcodes, was viel Arbeit in die Entwicklung mit sich bringt und die Entwicklungskosten erheblich erhöht. Daher ist sie nur für die Berücksichtigung der Existenz einer großen Datenmenge in der frühen Entwicklungsphase geeignet und leistet gute Arbeit bei der Untertabellenverarbeitung und ist nicht für Anwendungen geeignet. Es wäre zu teuer, Änderungen vorzunehmen, nachdem es online gegangen ist.

5. Hardware-Upgrade, diese Methode ist die einfachste, aber relativ teuer, daher ist der Chef nicht dazu bereit.

6. Datenbank-Upgrade, zum Beispiel: Ersetzen Sie die MySQL-Datenbank durch eine Big-Data-Engine, um Daten zu verarbeiten, oder ersetzen Sie sie durch Alibaba Cloud. POLARDB ist die relationale verteilte Cloud-native Datenbank der nächsten Generation, die zu 100 % kompatibel ist mit MySQL und verfügt über die höchste Speicherkapazität, die bis zu 100 T erreichen kann, und die Leistung ist bis zu sechsmal so hoch wie die von MySQL.

Eine Tabelle a mit 5 Millionen Daten und eine Tabelle b mit 3 Millionen Daten sind über den Fremdschlüssel tid verknüpft. Wie können wir die 200 Datensätze von 50000 bis 50200, die die Bedingungen erfüllen, schnell abfragen?

Methode 1: Wenn die TID von Tabelle A selbstansteigend und kontinuierlich ist, ist die ID von Tabelle B der Index. Die SQL-Anweisung lautet wie folgt.

select * from a,b where a.tid = b.id and a.tid>500000 limit 200;

Nach dem Login kopieren

Methode 2: Wenn die tid von Tabelle a nicht kontinuierlich ist, müssen Sie einen abdeckenden Index verwenden. tid ist entweder der Primärschlüssel oder ein Hilfsindex, und die id von Tabelle b muss ebenfalls einen Index haben. Die SQL-Anweisung lautet wie folgt.

select * from b, (select tid from a limit 50000,200) a where b.id = a.tid;

Nach dem Login kopieren

Sprechen wir über das Speichermodell von JVM

Zu den JVM-Speicherstrukturen gehören: Programmzähler, Heap-Speicher, Methodenbereich und Stapel (Stapel der Java Virtual Machine und lokaler Methodenstapel).

Das Programmzählerregister ist ein kleiner Speicherplatz. Seine Funktion kann als Zeilennummernanzeige des vom aktuellen Thread ausgeführten Bytecodes betrachtet werden. Im konzeptionellen Modell der virtuellen Maschine (nur ein konzeptionelles Modell, verschiedene virtuelle Maschinen können auf effizientere Weise implementiert werden) ändert der Bytecode-Interpreter den Wert dieses Zählers, um den nächsten Schritt auszuwählen, der ausgeführt werden muss B. Bytecode-Anweisungen, Verzweigungen, Schleifen, Sprünge, Ausnahmebehandlung und Thread-Wiederherstellung, sind alle auf diesen Zähler angewiesen, um abgeschlossen zu werden.

Der Heapspeicher ist der größte Teil der JVM und besteht aus der jungen Generation und der alten Generation. Der Speicher der jungen Generation ist standardmäßig in den Eden-Raum, den From Survivor Space und den To Survivor Space unterteilt wird entsprechend dem Verhältnis von 8:1:1 ;

Der Methodenbereich speichert Klasseninformationen, Konstanten, statische Variablen und andere Daten. Zur Unterscheidung vom Java-Heap verfügt der Methodenbereich auch über einen Alias -Heap (Nicht-Heap); der Stapel ist in einen Java Virtual Machine-Stapel unterteilt. Der lokale Methodenstapel wird hauptsächlich für die Methodenausführung verwendet. Der Methodenbereich kann als Spezifikation verstanden werden, und seine Implementierung ist beispielsweise die permanente Generierung und der Metaraum.

Java Virtual Machine Stacks (Java Virtual Machine Stacks) sind ebenfalls Thread-privat, Sein Lebenszyklus ist der gleiche wie der des Threads. Der Stapel der virtuellen Maschine beschreibt das Speichermodell der Java-Methodenausführung: Bei der Ausführung jeder Methode wird gleichzeitig ein Stapelrahmen (Stack Frame) erstellt, um Informationen wie lokale Variablentabellen, Operationsstapel, dynamische Links und Methodenausgänge zu speichern , usw. Der Prozess vom Aufruf jeder Methode bis zum Abschluss der Ausführung entspricht dem Prozess, bei dem ein Stapelrahmen vom Stapel verschoben und aus dem Stapel im Stapel der virtuellen Maschine herausgenommen wird.

Native Methodenstapel und der Stapel der virtuellen Maschine spielen eine sehr ähnliche Rolle. Der einzige Unterschied besteht darin, dass der Stapel der virtuellen Maschine der virtuellen Maschine zur Ausführung von Java-Methoden (dh Bytecode) dient, während der Stapel der nativen Methode die nativen Methoden bedient von der virtuellen Maschine verwendet. Die Spezifikation der virtuellen Maschine schreibt die Sprache, Verwendung und Datenstruktur der Methoden im lokalen Methodenstapel nicht vor, sodass bestimmte virtuelle Maschinen sie frei implementieren können.

Warum wird der Survivor-Bereich benötigt?

Wenn es keinen Survivor gibt, werden die überlebenden Objekte jedes Mal, wenn ein Minor GC im Eden-Bereich durchgeführt wird, an die alte Generation gesendet. Dadurch ist die alte Generation schnell aufgefüllt und löst Major GC aus (da Major GC normalerweise von Minor GC begleitet wird, kann dies auch als Auslösung von Full GC angesehen werden). Der Speicherplatz der alten Generation ist viel größer als der der neuen Generation, und ein vollständiger GC dauert viel länger als ein kleiner GC.

Der Interviewer fragt sich möglicherweise: Was sind die Nachteile einer langen Ausführungszeit?

Häufiges vollständiges GC nimmt viel Zeit in Anspruch und beeinträchtigt die Ausführungs- und Reaktionsgeschwindigkeit großer Programme.

Wenn der Platz der alten Generation vergrößert wird, können mehr überlebende Objekte die alte Generation füllen. Obwohl die Häufigkeit der vollständigen GC mit zunehmendem Speicherplatz der alten Generation verringert wird, dauert die Ausführung einer vollständigen GC länger.

Wenn der Platz der alten Generation reduziert wird, wird die alte Generation zwar bald mit überlebenden Objekten gefüllt, obwohl die für die vollständige GC erforderliche Zeit verkürzt wird, und die Häufigkeit der vollständigen GC nimmt zu.

Der Sinn der Existenz von Survivor besteht also darin, die Anzahl der an die alte Generation gesendeten Objekte zu reduzieren und dadurch das Auftreten von Full GC zu reduzieren. Durch die Vorabprüfung von Survivor wird sichergestellt, dass nur Objekte an die neue Generation gesendet werden, die nach 16 Minor GCs überleben können das Alter.

Haben Sie mich etwas zu fragen?

Einige Interviewer stellen diese Frage höflich und schenken Ihrer Antwort keine große Aufmerksamkeit, da das Interview zu diesem Zeitpunkt wahrscheinlich cool ist.

Wenn jedoch die Möglichkeit besteht, eine Frage zu stellen, denken die meisten Leute immer noch, dass Sie gut sind und die Wahrscheinlichkeit, zugelassen zu werden, sehr hoch ist, sodass Sie immer noch sorgfältig antworten müssen sich gut benehmen.

Diese Frage mag entbehrlich erscheinen, ist aber tatsächlich sehr kritisch. Im Allgemeinen mögen Interviewer keine Leute, die „

Kein Problem

“ sagen, weil sie großen Wert auf die Persönlichkeit und Innovationsfähigkeit der Mitarbeiter legen. Unternehmen mögen es nicht, wenn Arbeitssuchende Fragen zu persönlichen Vorteilen stellen: Gibt es in Ihrem Unternehmen Schulungsprogramme für neue Mitarbeiter? Oder was ist der Werbemechanismus Ihres Unternehmens? Das Unternehmen wird Sie willkommen heißen, weil es Ihre Leidenschaft für das Lernen und Ihre Loyalität gegenüber dem Unternehmen sowie Ihren Ehrgeiz zeigt.