Partage de technologie

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

À quoi ressemble la structure de données ArrayList sous-jacente ?

La couche inférieure d'ArrayList est implémentée sur la base de tableaux. Pour ce faire, il étend ou réduit dynamiquement la taille du tableau. Lorsque la capacité n'est pas suffisante, il créera un tableau plus grand, puis copiera les données d'origine et enfin y ajoutera les nouvelles données.

Le mécanisme d'expansion d'ArrayList est le suivant : lorsque le premier élément est ajouté, la capacité d'ArrayList est de 10 ; chaque fois qu'un nouvel élément est ajouté, si la capacité est dépassée, la capacité d'origine sera doublée, c'est-à-dire la capacité d'origine * 2 ; , si la capacité d'origine est 0, alors la nouvelle capacité est 1.

Avantages et inconvénients du mécanisme d'expansion d'ArrayList :

avantage:

1. Le mécanisme d'expansion d'ArrayList est simple à comprendre et facile à mettre en œuvre.
2. La capacité étendue doit être supérieure à la capacité d'origine, ce qui peut réduire le nombre de copies de tableau lors de l'ajout de nouveaux éléments et améliorer l'efficacité de l'ajout d'éléments.

défaut:

1. Le mécanisme d'expansion d'ArrayList entraîne un gaspillage de mémoire et peut facilement provoquer un gaspillage d'espace mémoire.
2. Lorsque la capacité est importante, chaque extension nécessite une grande quantité de mémoire et de ressources CPU, ce qui affectera les performances. Par conséquent, lors de l'utilisation d'ArrayList, la capacité initiale doit être définie de manière appropriée.

ArrayList n'est pas thread-safe

L'implémentation interne d'ArrayList est basée sur des tableaux. Lorsque plusieurs threads accèdent à la même ArrayList en même temps, une incohérence des données peut se produire. Par exemple, lorsqu'un thread lit les données d'ArrayList et qu'un autre thread y ajoute/supprime. l'ArrayList, il peut y avoir Modifier les données dans l'ArrayList, de sorte que le thread qui lit les données de l'ArrayList puisse lire des données incorrectes, provoquant une erreur de programme.

Les méthodes courantes pour résoudre l’insécurité des threads ArrayList incluent :

1. Utilisez Vector au lieu de ArrayList : Vector est synchronisé et toutes les méthodes sont modifiées par synchronisé, il est donc thread-safe ;
2. Enveloppez ArrayList dans la sécurité des threads : utilisez la méthode Collections.synchronizedList(list) pour convertir ArrayList en sécurité des threads ;
3. Utilisez CopyOnWriteArrayList : il s'agit d'une collection thread-safe et efficace. Son opération d'écriture est implémentée en copiant le tableau sous-jacent. Le coût de cette implémentation est dans une plage acceptable. Il convient aux scénarios simultanés avec plus de lecture et moins d'écriture.
4. Utilisez des verrous pour garantir la sécurité des threads : vous pouvez utiliser des mécanismes de verrouillage tels que ReentrantLock pour implémenter une ArrayList sécurisée pour les threads.

La différence entre pile et tas

• La pile est un tableau linéaire spécial. Sa caractéristique est que les données ne peuvent être insérées et supprimées qu'à une extrémité, selon le principe du premier entré, dernier sorti, dernier entré, premier sorti. Il s'agit d'une structure de stockage qui peut être utilisée pour stocker les valeurs des paramètres de fonction, les variables locales, etc.

• Un tas est une structure arborescente spéciale caractérisée par le fait que les valeurs de tous les nœuds sont supérieures ou égales aux valeurs de leurs nœuds enfants et que la valeur du nœud racine est la plus grande ou la plus petite. Le tas est une structure de stockage dynamique qui peut être utilisée pour stocker de grandes quantités de données, telles que le tri, la recherche, etc.

Couche inférieure de coroutine

L'essence d'une coroutine est un thread léger. Chaque coroutine a une pile pour stocker les fonctions et leurs paramètres, variables locales, etc. La coroutine peut être suspendue, reprise et commutée. Voici comment implémenter une coroutine de base.

Principe C# GC (garbage collection)

1. Comptage de références : lorsqu'un objet est référencé, son compteur de références est augmenté de 1. Lorsque la référence devient invalide, son compteur de références est décrémenté de 1. Si le nombre de références d'un objet devient 0, l'objet sera récupéré par le garbage collector.
2. Marquer et effacer : lorsque le garbage collector est en cours d'exécution, il parcourt les objets selon des relations de référence, marque les objets accessibles comme "vivants", marque les objets inaccessibles comme "morts", puis efface tous les objets marqués comme "morts".
3. Algorithme de copie : le garbage collector divise la mémoire disponible en deux blocs et n'utilise qu'un seul bloc à la fois. Lorsque l'espace est insuffisant, les objets survivants sont copiés dans un autre bloc d'espace, puis les objets copiés sont effacés de l'original. espace.
4. Algorithme de marquage-complément : lorsque le garbage collector est en cours d'exécution, il marquera d'abord tous les objets survivants, puis déplacera tous les objets survivants vers une extrémité pour éliminer les fragments d'espace inutilisés.

La différence entre la synchronisation d'état et la synchronisation de trame

Synchronisation d'état Il s'agit de transmettre l'état (tel que la position, la vitesse, l'accélération, etc.) de chaque machine du système multi-machines à d'autres machines dans chaque cycle de contrôle, afin que chaque machine reste synchronisée. La synchronisation d'état peut permettre d'obtenir des performances en temps réel de contrôle collaboratif multi-machines, mais comme une grande quantité de données doit être transmise à chaque cycle de contrôle, sa précision peut être relativement faible.

Synchronisation des trames Cela signifie qu'à chaque cycle de contrôle, les commandes de contrôle de chaque machine du système multi-machines sont transmises aux autres machines afin que chaque machine reste synchronisée. La synchronisation de trames peut atteindre la précision d'un contrôle collaboratif multi-machines, mais comme seul un petit nombre de commandes de contrôle est transmis dans chaque cycle de contrôle, ses performances en temps réel peuvent être relativement faibles.

Modèles de conception courants

Modèle Singleton

Modèle d'usine

Modèle composite

Modèle de proxy

Caractéristiques des listes chaînées, des arbres binaires et des tables de hachage

1. Liste chaînée :

• Il s'agit d'une structure de liste linéaire, caractérisée en ce que chaque nœud possède un pointeur pointant vers le nœud suivant, formant ainsi une liste chaînée ;
• Indépendamment de l'insertion ou de la suppression d'un nœud, il vous suffit de modifier le pointage du pointeur, et la complexité temporelle est O(1) ;
• La complexité temporelle de la recherche d'un nœud est O(n), et vous devez rechercher dans l'ordre en commençant par le nœud principal ;
• Les listes chaînées n'ont pas besoin de prendre en compte les problèmes d'allocation d'espace. Généralement, l'allocation dynamique de mémoire est utilisée pour obtenir une gestion flexible de la mémoire.

2. Arbre binaire :

• Un arbre binaire est une structure arborescente dont chaque nœud a au plus deux enfants ;
• La complexité temporelle des opérations de recherche, d'insertion et de suppression de l'arbre binaire est respectivement O(log2n), O(log2n) et O(log2n) ;
• Étant donné que chaque nœud de l'arbre binaire n'est pas stocké en continu, mais est stocké hiérarchiquement et que chaque nœud ne peut avoir que deux enfants, l'espace de stockage peut être utilisé plus efficacement.

3. Table de hachage :

• Une table de hachage est une structure de données qui mappe une clé à un emplacement dans une table pour accéder aux enregistrements afin d'accélérer les recherches ;
• La complexité temporelle de recherche de la table de hachage est O(1), et la complexité temporelle d'insertion et de suppression est O(n) ;
• La mise en œuvre d'une table de hachage nécessite un espace supplémentaire pour stocker la table de hachage elle-même, et le problème des collisions de hachage doit être résolu.

Le principe sous-jacent de HashMap

La couche inférieure de HashMap est implémentée à l'aide d'une liste chaînée de tableau (arbre rouge-noir). Elle stocke les données en fonction de la valeur hashCode de la clé. Elle peut calculer la position des données dans le tableau (conflit de hachage) en fonction du hachage. code et utilise une liste chaînée (arbre rouge-noir) pour stocker les conflits Les données. HashMap Dans Java 8, lorsque la longueur de la liste chaînée dépasse le seuil (la valeur par défaut est 8), elle sera convertie en une arborescence rouge-noir pour améliorer l'efficacité des requêtes.Lorsque la capacité n'est pas suffisante, elle s'étend automatiquement. Le facteur de charge par défaut est de 0,75 et la méthode d'extension est de 2 fois la capacité.

Comment déterminer si une liste chaînée a un cycle

1. Utilisez une table de hachage pour parcourir chaque nœud de la liste chaînée et stocker l'adresse du nœud dans la table de hachage. Si le nœud actuel existe déjà dans la table de hachage, cela signifie que la liste chaînée a un cycle ;
2. Définissez deux pointeurs, un pointeur lent se déplace d'un pas à la fois et un pointeur rapide se déplace de deux pas à la fois. Si le pointeur rapide rencontre le pointeur lent, cela signifie que la liste chaînée a un cycle.

Quels sont les scénarios d’utilisation des piles et des files d’attente ?

Fonctions avant et arrière du navigateur : les pages Web visitées par le navigateur peuvent réaliser les fonctions avant et arrière via la structure de données de la pile.

Savez-vous quelque chose sur le problème du sticky TCP ?

Le problème TCP persistant fait référence au fait que le protocole TCP ne fragmente pas les données lors de la transmission des données, ce qui fait que la quantité de données reçues par l'extrémité réceptrice est supérieure à la quantité de données envoyées par l'extrémité émettrice.

Les moyens de résoudre le problème TCP persistant sont les suivants :

1. Ajouter un délimiteur à l'extrémité émettrice : ajoutez un délimiteur à l'extrémité émettrice. Une fois que l'extrémité réceptrice a reçu le délimiteur, elle peut diviser les données en fonction du délimiteur.
2. Ajouter un en-tête à l'extrémité émettrice : l'extrémité émettrice ajoute un en-tête avant d'envoyer les données. L'en-tête contient les informations de longueur des données actuelles. L'extrémité réceptrice divise les données en fonction des informations de longueur contenues dans l'en-tête.
3. Ajoutez un tampon à l'extrémité d'envoi : avant d'envoyer des données, l'extrémité d'envoi place d'abord les données dans le tampon et n'envoie qu'une partie des données dans le tampon à chaque fois. Après avoir reçu les données, l'extrémité de réception détermine si elle doit envoyer les données. données basées sur la longueur totale des données complètes.

Comment implémenter un TCP simple en utilisant UDP

Tout d’abord, les datagrammes UDP peuvent aider à implémenter le processus de négociation à trois dans le protocole TCP/IP. Lors de la première prise de contact, un client envoie un datagramme UDP contenant une demande de prise de contact. Lorsque le serveur reçoit ce message, il répond par un message de confirmation, indiquant que le serveur a reçu la demande d'établissement de liaison du client et qu'il est prêt à fournir des services. Lors de la deuxième poignée de main, le client enverra à nouveau un datagramme UDP. Cette fois, le message contient des informations utiles, telles que l'adresse IP du client, le numéro de port, etc., afin que le serveur puisse identifier le client. Lors de la troisième poignée de main, le serveur enverra un datagramme UDP indiquant que la connexion a été établie et que le client peut commencer à envoyer des données.

Deuxièmement, les datagrammes UDP peuvent également aider à réaliser le processus de transmission de données dans le protocole TCP/IP. Lorsque le client doit envoyer des données au serveur, les données seront encapsulées dans un datagramme UDP et envoyées au serveur ; une fois que le serveur aura reçu le datagramme UDP, il analysera les données contenues dans le message et effectuera le traitement associé.

Enfin, les datagrammes UDP peuvent également aider à implémenter le processus de terminaison dans le protocole TCP/IP.Lorsque le client n'a plus besoin de communiquer avec le serveur, il peut envoyer un datagramme UDP pour indiquer que le client met fin à la connexion. Une fois que le serveur aura reçu ce message, il libérera les ressources correspondantes, complétant ainsi l'intégralité du protocole TCP/IP. .processus de connexion

Avez-vous utilisé des coroutines ? Pourquoi utiliser des coroutines ?Pourquoi les coroutines sont plus rapides

Les coroutines permettent aux programmes de basculer entre différentes tâches, améliorant ainsi l'efficacité du programme et réduisant sa durée d'exécution. Les coroutines permettent à un programme de basculer entre plusieurs tâches au lieu d'attendre la fin d'une tâche avant d'en démarrer une autre. Il peut également partager des variables entre différents threads, réduisant ainsi le temps d'exécution du programme. Pour les applications multitâches, l'utilisation de coroutines peut améliorer considérablement les performances, ce qui se traduit par des vitesses d'exécution plus rapides.

Est-il plus rapide de parcourir un tableau ou une liste chaînée de même longueur ? Pourquoi?

Les tableaux sont plus rapides, car l'adresse de chaque élément du tableau est continue et fixe, et l'adresse de l'élément suivant peut être rapidement obtenue, tandis que l'adresse de chaque élément de la liste chaînée est discontinue et vous devez parcourir le pointeur pour obtenir l'adresse de l'élément suivant, le parcours du tableau est donc plus rapide.

Parlons des fonctions virtuelles. Pourquoi avons-nous besoin de fonctions virtuelles ?

Une fonction virtuelle est une fonction spéciale qui diffère des fonctions ordinaires dans la mesure où elle est automatiquement définie par le compilateur et peut être appelée au moment de la compilation. La caractéristique d'une fonction virtuelle est que son implémentation est déterminée au moment de l'exécution et non au moment de la compilation.
L'objectif principal des fonctions virtuelles est d'atteindre le polymorphisme. Une classe abstraite peut définir plusieurs fonctions virtuelles, puis ses sous-classes peuvent implémenter ces fonctions.

Le destructeur peut-il être une fonction virtuelle ? Doit-il s'agir d'une fonction virtuelle ? Pourquoi? Quel est le problème si ce n’est pas une fonction virtuelle ?

Il n'est pas nécessaire qu'il s'agisse d'une fonction virtuelle, mais il est généralement recommandé d'utiliser une fonction virtuelle, car une fonction virtuelle peut être remplacée par une classe dérivée, afin que le destructeur de la classe dérivée puisse être exécuté correctement s'il s'agit d'une fonction virtuelle. n'est pas utilisé, le destructeur de la classe dérivée ne sera pas appelé, ce qui peut provoquer des problèmes tels que des fuites de mémoire.

Présentation du pipeline de rendu

Le pipeline de rendu est une série d'étapes utilisées pour convertir les données de scène de jeu des informations d'entrée en images affichées à l'écran.

Le processus du pipeline de rendu est divisé en trois étapes principales : l’étape de préparation, l’étape de géométrie et l’étape d’éclairage.

Lors de la phase de préparation, le moteur de jeu charge les modèles et les textures de la scène de jeu dans l'unité de traitement graphique (GPU) et organise les données pour les utiliser dans les phases ultérieures.

Au cours de la phase de géométrie, des transformations matricielles sont utilisées pour placer le modèle dans un espace tridimensionnel et convertir le modèle en une forme pouvant être prise en charge par les pixels à l'écran.

Lors de la phase d'éclairage, la source de lumière et le modèle d'éclairage sont utilisés pour calculer la valeur de couleur de chaque pixel, et l'image résultante est finalement affichée à l'écran.

Parlons des opérations d'insertion, d'interrogation et de suppression des arbres de recherche binaires, et quelle est la complexité temporelle ?

1. insérer:

• Complexité temporelle : O (log n)
• Pas:

1. Traitez le nœud à insérer comme un nouveau nœud feuille, en commençant par le nœud racine ;
2. Si la valeur du nœud à insérer est inférieure à la valeur du nœud actuel, accédez au nœud enfant gauche du nœud actuel ;
3. Si la valeur du nœud à insérer est supérieure à la valeur du nœud actuel, accédez au nœud enfant droit du nœud actuel ;
4. Si le nœud actuel n'a pas de nœuds enfants, le nœud à insérer sera le nœud enfant du nœud actuel ;
5. Sinon, répétez les étapes 2 à 4 jusqu'à ce qu'un nœud sans nœuds enfants soit trouvé et que le nœud à insérer soit utilisé comme nœud enfant de ce nœud.

Quelles sont les conditions pour que l’algorithme glouton obtienne la solution optimale ?

Les conditions permettant à l'algorithme glouton d'obtenir la solution optimale sont la « sous-structure optimale » et la « propriété de sélection gloutonne » :

1. Sous-structure optimale : la solution optimale à un problème contient les solutions optimales aux sous-problèmes du problème ;
2. Propriété de sélection gloutonne : à chaque étape, un choix optimal local est fait, et le résultat final est la solution optimale globale.