Compartilhamento de tecnologia

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

Qual é a aparência da estrutura de dados ArrayList subjacente?

A camada inferior do ArrayList é implementada com base em arrays. Isso é feito expandindo ou reduzindo dinamicamente o tamanho do array. Quando a capacidade não for suficiente, ele criará um array maior, copiará os dados originais e, finalmente, adicionará os novos dados a ele.

O mecanismo de expansão do ArrayList é: quando o primeiro elemento é adicionado, a capacidade do ArrayList é 10 cada vez que um novo elemento é adicionado, se a capacidade for ultrapassada, a capacidade original será duplicada, ou seja, a capacidade original * 2; , se a capacidade original for 0, a nova capacidade será 1.

Vantagens e desvantagens do mecanismo de expansão ArrayList:

vantagem:

1. O mecanismo de expansão ArrayList é simples de entender e fácil de implementar.
2. A capacidade expandida deve ser maior que a capacidade original, o que pode reduzir o número de cópias do array ao adicionar novos elementos e melhorar a eficiência da adição de elementos.

deficiência:

1. O mecanismo de expansão ArrayList leva ao desperdício de memória e pode facilmente causar desperdício de espaço de memória.
2. Quando a capacidade é grande, cada expansão requer uma grande quantidade de memória e recursos de CPU, o que afetará o desempenho. Portanto, ao usar ArrayList, a capacidade inicial precisa ser definida adequadamente.

ArrayList não é thread-safe

A implementação interna de ArrayList é baseada em arrays. Quando vários threads acessam o mesmo ArrayList ao mesmo tempo, pode ocorrer inconsistência de dados. Por exemplo, quando um thread está lendo os dados do ArrayList e outro thread está adicionando/excluindo dados. no ArrayList, pode haver alteração dos dados no ArrayList, para que o thread que lê os dados do ArrayList possa ler dados incorretos, causando um erro no programa.

Os métodos comuns para resolver a insegurança do thread ArrayList incluem:

1. Use Vector em vez de ArrayList: Vector é sincronizado e todos os métodos são modificados por sincronizados, portanto é thread-safe;
2. Envolva ArrayList em thread safety: Use o método Collections.synchronizedList(list) para converter ArrayList em thread safety;
3. Use CopyOnWriteArrayList: É uma coleção eficiente e segura para threads. Sua operação de escrita é implementada copiando o array subjacente. O custo desta implementação está dentro de um intervalo aceitável.
4. Use bloqueios para obter segurança de thread: você pode usar mecanismos de bloqueio como ReentrantLock para implementar um ArrayList seguro para thread.

A diferença entre pilha e heap

• A pilha é uma tabela linear especial. Sua característica é que os dados só podem ser inseridos e excluídos em uma extremidade, com base no princípio primeiro a entrar, último a sair, último a entrar, primeiro a sair. É uma estrutura de armazenamento que pode ser usada para armazenar valores de parâmetros de função, variáveis ​​locais, etc.

• Um heap é uma estrutura de árvore especial caracterizada pelo fato de que os valores de todos os nós são maiores ou iguais aos valores de seus nós filhos e o valor do nó raiz é o maior ou o menor. O heap é uma estrutura de armazenamento dinâmica que pode ser usada para armazenar grandes quantidades de dados, como classificação, pesquisa, etc.

Camada inferior da corrotina

A essência de uma corrotina é um thread leve. Cada corrotina possui uma pilha para armazenar funções e seus parâmetros, variáveis ​​locais, etc. A corrotina pode ser suspensa, retomada e trocada.

Princípio C# GC (coleta de lixo)

1. Contagem de referência: quando um objeto é referenciado, sua contagem de referência é aumentada em 1. Quando a referência se torna inválida, sua contagem de referência é diminuída em 1. Se a contagem de referência de um objeto chegar a 0, o objeto será recuperado pelo coletor de lixo.
2. Marcar e limpar: quando o coletor de lixo está em execução, ele percorre objetos de acordo com relacionamentos de referência, marca objetos acessíveis como "vivos", marca objetos inacessíveis como "mortos" e, em seguida, limpa todos os objetos marcados como "mortos".
3. Algoritmo de cópia: O coletor de lixo divide a memória disponível em dois blocos e usa apenas um bloco por vez. Quando o espaço é insuficiente, os objetos sobreviventes são copiados para outro bloco de espaço e, em seguida, os objetos copiados são apagados do original. espaço.
4. Algoritmo de complemento de marcação: quando o coletor de lixo está em execução, ele primeiro marca todos os objetos sobreviventes e, em seguida, move todos os objetos sobreviventes para uma extremidade para limpar fragmentos de espaço não utilizados.

A diferença entre sincronização de status e sincronização de quadros

Sincronização de estado Refere-se à transmissão do status (como posição, velocidade, aceleração, etc.) de cada máquina do sistema multimáquina para outras máquinas em cada ciclo de controle, para que cada máquina permaneça sincronizada. A sincronização de estado pode alcançar o desempenho em tempo real do controle colaborativo de várias máquinas, mas como uma grande quantidade de dados precisa ser transmitida em cada ciclo de controle, sua precisão pode ser relativamente baixa.

Sincronização de quadros Isso significa que em cada ciclo de controle, os comandos de controle de cada máquina do sistema multimáquina são transmitidos para outras máquinas para que cada máquina permaneça sincronizada. A sincronização de quadros pode atingir a precisão do controle colaborativo de várias máquinas, mas como apenas um pequeno número de comandos de controle é transmitido em cada ciclo de controle, seu desempenho em tempo real pode ser relativamente baixo.

Padrões de design comuns

Padrão Singleton

Padrão de fábrica

Padrão Composto

Padrão de proxy

Características de listas vinculadas, árvores binárias e tabelas hash

1. Lista vinculada:

• É uma estrutura de lista linear, que se caracteriza por cada nó possuir um ponteiro apontando para o próximo nó, formando assim uma lista encadeada;
• Independentemente de inserir ou excluir um nó, basta alterar a orientação do ponteiro, e a complexidade de tempo é O(1);
• A complexidade de tempo para encontrar um nó é O(n), e você precisa pesquisar em ordem, começando no nó principal;
• As listas vinculadas não precisam considerar problemas de alocação de espaço. Geralmente, a alocação dinâmica de memória é usada para obter gerenciamento flexível de memória.

2. Árvore binária:

• Uma árvore binária é uma estrutura em árvore com cada nó tendo no máximo dois filhos;
• A complexidade de tempo das operações de busca, inserção e exclusão da árvore binária é O(log2n), O(log2n) e O(log2n) respectivamente;
• Como cada nó da árvore binária não é armazenado continuamente, mas hierarquicamente, e cada nó pode ter apenas dois filhos, o espaço de armazenamento pode ser usado de forma mais eficiente.

3. Tabela hash:

• Uma tabela hash é uma estrutura de dados que mapeia uma chave para um local em uma tabela para acessar registros e acelerar pesquisas;
• A complexidade do tempo de pesquisa da tabela hash é O(1), e a complexidade do tempo de inserção e exclusão é O(n);
• A implementação de uma tabela hash requer espaço adicional para armazenar a própria tabela hash, e o problema de colisões de hash precisa ser resolvido.

O princípio subjacente do HashMap

A camada inferior do HashMap é implementada usando uma lista vinculada de array (árvore vermelha e preta). Ela armazena dados de acordo com o valor hashCode da chave. Ele pode calcular a posição dos dados na matriz (conflito de hash) com base no hash. código e usa uma lista vinculada (árvore vermelha e preta) para armazenar os conflitos. HashMap Em Java 8, quando o comprimento da lista vinculada exceder o limite (o padrão é 8), ela será convertida em uma árvore vermelha e preta para melhorar a eficiência da consulta.Quando a capacidade não for suficiente, ela será expandida automaticamente. O fator de carga padrão é 0,75 e o método de expansão é 2 vezes a capacidade.

Como determinar se uma lista vinculada tem um ciclo

1. Use uma tabela hash para percorrer cada nó na lista vinculada e armazenar o endereço do nó na tabela hash. Se o nó atual já existir na tabela hash, significa que a lista vinculada possui um ciclo;
2. Defina dois ponteiros, um ponteiro lento move-se um passo de cada vez e um ponteiro rápido move-se dois passos de cada vez. Se o ponteiro rápido encontrar o ponteiro lento, significa que a lista vinculada tem um ciclo.

Quais são os cenários de uso de pilhas e filas?

As funções de avanço e retrocesso do navegador: As páginas da web visitadas pelo navegador podem realizar as funções de avanço e retrocesso por meio da estrutura de dados da pilha.

Você sabe alguma coisa sobre o problema do tcp sticky?

O problema TCP sticky refere-se ao fato de que o protocolo TCP não fragmenta os dados ao transmiti-los, fazendo com que a quantidade de dados recebidos pelo terminal receptor seja maior do que a quantidade de dados enviados pelo terminal emissor.

As maneiras de resolver o problema persistente do TCP são:

1. Adicione um delimitador no final do envio: Adicione um delimitador no final do envio Depois que o final do recebimento receber o delimitador, ele poderá dividir os dados com base no delimitador.
2. Adicione um cabeçalho na extremidade de envio: A extremidade de envio adiciona um cabeçalho antes de enviar os dados. O cabeçalho contém as informações de comprimento dos dados atuais.
3. Adicione um buffer no final do envio: antes de enviar os dados, o final do envio primeiro coloca os dados no buffer e envia apenas uma parte dos dados no buffer de cada vez. Depois de receber os dados, o final do recebimento determina se deseja enviar os dados. dados com base no comprimento total dos dados completos.

Como implementar um TCP simples usando UDP

Em primeiro lugar, os datagramas UDP podem ajudar a implementar o processo de handshake triplo no protocolo TCP/IP. No primeiro handshake, um cliente envia um datagrama UDP contendo uma solicitação de handshake. Ao receber esta mensagem, o servidor responderá com uma mensagem de confirmação, indicando que o servidor recebeu a solicitação de handshake do cliente e está pronto para fornecer serviços. No segundo handshake, o cliente enviará novamente um datagrama UDP. Desta vez a mensagem contém algumas informações úteis, como endereço IP do cliente, número da porta, etc., para que o servidor possa identificar o cliente. No terceiro handshake, o servidor enviará um datagrama UDP indicando que a conexão foi estabelecida e o cliente pode iniciar o envio de dados.

Em segundo lugar, os datagramas UDP também podem ajudar a realizar o processo de transmissão de dados no protocolo TCP/IP. Quando o cliente precisar enviar dados ao servidor, os dados serão encapsulados em um datagrama UDP e enviados ao servidor após o servidor receber o datagrama UDP, ele analisará os dados contidos na mensagem e realizará o processamento relacionado;

Finalmente, os datagramas UDP também podem ajudar a implementar o processo de encerramento da conexão no protocolo TCP/IP.Quando o cliente não precisar mais se comunicar com o servidor, ele poderá enviar um datagrama UDP para indicar que o cliente está encerrando a conexão. Após o servidor receber esta mensagem, ele liberará os recursos correspondentes, completando assim todo o protocolo TCP/IP. processo de conexão

Você usou corrotinas? Por que usar corrotinas?Por que as corrotinas são mais rápidas

As corrotinas permitem que os programas alternem entre diferentes tarefas, melhorando assim a eficiência do programa e reduzindo o tempo de execução do programa. As corrotinas permitem que um programa alterne entre várias tarefas em vez de esperar que uma tarefa seja concluída antes de iniciar outra. Ele também pode compartilhar variáveis ​​entre diferentes threads, reduzindo assim o tempo de execução do programa. Para aplicativos multitarefa, o uso de corrotinas pode melhorar significativamente o desempenho, resultando em velocidades de execução mais rápidas.

É mais rápido percorrer uma matriz ou uma lista vinculada do mesmo comprimento? Por que?

Matrizes são mais rápidas, porque o endereço de cada elemento da matriz é contínuo e fixo, e o endereço do próximo elemento pode ser obtido rapidamente, enquanto o endereço de cada elemento da lista vinculada é descontínuo e você precisa percorrer o ponteiro para obter o endereço do próximo elemento, para que o array Traversing seja mais rápido.

Vamos falar sobre funções virtuais. Por que precisamos de funções virtuais?

Uma função virtual é uma função especial que difere das funções comuns porque é definida automaticamente pelo compilador e pode ser chamada em tempo de compilação. A característica de uma função virtual é que sua implementação é determinada em tempo de execução e não em tempo de compilação.
O principal objetivo das funções virtuais é alcançar o polimorfismo. Uma classe abstrata pode definir múltiplas funções virtuais e então suas subclasses podem implementar essas funções.

O destruidor pode ser uma função virtual? Tem que ser uma função virtual? Por que? Qual é o problema se não for uma função virtual?

Não precisa ser uma função virtual, mas geralmente é recomendado usar uma função virtual, porque uma função virtual pode ser substituída por uma classe derivada, para que o destruidor da classe derivada possa ser executado corretamente se uma função virtual. não for usado, o destruidor da classe derivada não será chamado, o que pode causar problemas como vazamentos de memória.

Apresentando o pipeline de renderização

O pipeline de renderização é uma série de etapas usadas para converter dados da cena do jogo de informações de entrada em imagens exibidas na tela.

O processo do pipeline de renderização é dividido em três etapas principais: etapa de preparação, etapa de geometria e etapa de iluminação.

Na fase de preparação, o motor de jogo carrega os modelos e texturas da cena do jogo na unidade de processamento gráfico (GPU) e organiza os dados para uso nas fases subsequentes.

Durante o estágio de geometria, transformações de matriz são usadas para colocar o modelo no espaço tridimensional e converter o modelo em uma forma que possa ser suportada por pixels na tela.

Na fase de iluminação, a fonte de luz e o modelo de iluminação são usados ​​para calcular o valor da cor de cada pixel, e a imagem resultante é finalmente exibida na tela.

Vamos falar sobre as operações de inserção, consulta e exclusão de árvores binárias de pesquisa e qual é a complexidade do tempo?

1. inserir:

• Complexidade de tempo: O (log n)
• Passos:

1. Trate o nó a ser inserido como um novo nó folha, começando pelo nó raiz;
2. Se o valor do nó a ser inserido for menor que o valor do nó atual, vá para o nó filho esquerdo do nó atual;
3. Se o valor do nó a ser inserido for maior que o valor do nó atual, vá para o nó filho direito do nó atual;
4. Se o nó atual não tiver nós filhos, o nó a ser inserido será o nó filho do nó atual;
5. Caso contrário, repita as etapas 2 a 4 até que um nó sem nós filhos seja encontrado e o nó a ser inserido seja usado como nó filho desse nó.

Quais são as condições para o algoritmo ganancioso obter a solução ótima?

As condições para o algoritmo ganancioso obter a solução ótima são a "subestrutura ótima" e a "propriedade de seleção gananciosa":

1. Subestrutura ótima: A solução ótima para um problema contém as soluções ótimas para os subproblemas do problema;
2. Propriedade de seleção gananciosa: em cada etapa, uma escolha ótima local é feita e o resultado final é a solução ótima global.