Análise de perguntas e respostas de entrevistas para desenvolvedor Java. Parte 10

Olá! Quantas horas são necessárias para se tornar um mestre em alguma coisa? Muitas vezes ouvi algo como: “Para se tornar um mestre em qualquer coisa, você precisa gastar 10.000 horas”. Um número assustador, não é? No entanto, eu me pergunto se isso é verdade? E estou constantemente tentando descobrir quantas horas já investi no domínio da arte da programação. E quando eu cruzar essas estimadas 10.000 horas e me tornar um mestre, sentirei essa diferença? Ou já passei por cima deles há muito tempo sem perceber? De uma forma ou de outra, para se tornar um programador, você não precisa investir tanto tempo. O principal é usá-lo com sabedoria. Seu objetivo principal é passar na entrevista. E nas entrevistas para recém-chegados, a primeira coisa que perguntam é teoria, então você deve ser forte nisso. Na verdade, ao se preparar para a entrevista, sua tarefa é descobrir todas as suas lacunas na teoria básica de um desenvolvedor Java e cobri-las com conhecimento. E hoje vou te ajudar nesse assunto, pois estou aqui para continuar analisando as dúvidas mais populares. Então vamos continuar!

89. Qual a diferença entre ArrayList e LinkedList?

Esta é uma das perguntas mais populares junto com a pergunta sobre a estrutura interna do HashMap . Nenhuma entrevista está completa sem ele e, portanto, a resposta deve “rebater nos seus dentes”. Além do óbvio - nomes diferentes - eles diferem na estrutura interna. Anteriormente, examinamos a estrutura interna de ArrayList e LinkedList , portanto não entrarei em detalhes de sua implementação. Deixe-me lembrá-lo de que ArrayList é implementado com base em um array interno, que é aumentado conforme necessário de acordo com a fórmula:

<размерТекущегоМассива> * 3 / 2  + 1

Ao mesmo tempo, LinkedList é implementado com base em uma lista duplamente vinculada interna, ou seja, cada elemento possui um link para o anterior e o próximo, excluindo valores que são o início/fim da lista. As pessoas gostam de fazer esta pergunta no formato: “Qual é melhor - ArrayList ou LinkedList ?”, na esperança de pegar você. Afinal, se você apontar uma delas como resposta, será a resposta errada. Em vez disso, você deve esclarecer de que situação específica está falando - acesso ao índice ou inserção no meio de uma lista. Dependendo da resposta, você poderá explicar sua escolha. Descrevi anteriormente como ArrayList e LinkedList funcionam em uma situação ou outra. Vamos resumir isso colocando-os na mesma página para comparação: Adicionando um elemento (add)

1. Добавление нового element без указания индекса How местоположения будет происходить автоматически в конец обоих списков. В LinkedList новый элемент станет новым хвостом (происходит только перезаписывание пары ссылок — алгоритмическая сложность O(1)).

   В ArrayList будет добавлен новый элемент в последнюю пустую ячейку массива — O(1).

2. Добавление element по индексу How правило подразумевает вставку примерно в середину списка. В LinkedList сперва будет вестись поиск нужного места с помощью перебора элементов с “хвоста” и “головы” — O(n/2), а после — вставка значения путем переопределения ссылок элементов, между которыми вставляется новый — O(1). Суммарная алгоритмическая сложность данного действия будет O(n/2).

   ArrayList в данной ситуации по индексу находит элемент — O(1), и все элементы справа (включая элемент, который уже хранится по данному индексу) двигаются на одну единицу вправо (при этом возможно понадобится создание нового списка и копирование элементов в него) — O(n/2). Суммарная сложность — O(n/2).

3. Добавление element в начало списка в LinkedList будет ситуация схожая с добавлением в конец: новый элемент станет новой “головой” — O(1), в то же время когда ArrayList-у нужно будет двигать все элементы вправо — O(n).

Resumindo: no LinkedList, a complexidade algorítmica variará de O(1) a O(n/2) . Ou seja, quanto mais próxima a inserção estiver do final ou início da lista, mais rápida ela será. Ao mesmo tempo, para ArrayList varia de O(1) a O(n) : quanto mais próxima a inserção estiver do final da lista, mais rápida ela será. Definir um elemento (conjunto) Esta operação escreve um elemento na posição especificada na lista, substituindo o anterior, se houver. No LinkedList, esta operação será semelhante à adição, porque A maior dificuldade aqui é encontrar o elemento. A reescrita de um elemento ocorrerá reescrevendo um par de links, então também aqui a complexidade algorítmica variará de O(1) a O(n/2) dependendo da distância da posição do final ou início da lista. Nesse momento, a célula necessária será encontrada no ArrayList para esta operação de índice e um novo elemento será gravado nela. A pesquisa de índice, como esta operação, tem uma complexidade algorítmica de O(1) . Pegar um elemento por índice (get) No LinkedList, pegar um elemento ocorrerá de acordo com o mesmo princípio da busca por outras operações - dependendo da distância do final ou do início, ou seja, de O(1) para O(n/2) . Em ArrayList , como disse anteriormente, encontrar um elemento em um array por índice tem complexidade O(1) . Remover um elemento por índice (remover) Para LinkedList, seu princípio de funcionamento também funciona aqui: primeiro o elemento é encontrado e depois os links são sobrescritos - os vizinhos do elemento passam a se referir entre si, perdendo referências a este elemento, que será posteriormente excluído pelo coletor de lixo. Ou seja, a complexidade algorítmica ainda é a mesma - de O(1) a O(n/2) . Para ArrayList , esta operação é mais semelhante à operação de adição de um novo elemento (add). Primeiro, o elemento necessário é encontrado - O(1) , depois ele é removido e todos os elementos que estavam à direita dele são movidos uma unidade para a esquerda para fechar a lacuna resultante. A operação de exclusão terá a mesma complexidade algorítmica que a operação de adição - de O(1) a O(n) . Quanto mais próxima a exclusão estiver do final da lista, menor será a complexidade algorítmica dela. Na verdade, essas foram todas as operações principais. Deixe-me lembrá-lo: ao comparar essas duas listas, você precisa esclarecer de que situação específica estamos falando, e então poderá responder de forma inequívoca à pergunta feita.

90. Qual a diferença entre ArrayList e HashSet?

Se ArrayList e LinkedList pudessem ser comparados em termos de operações - o que é melhor - então não seria tão fácil comparar ArrayList com HashSet , porque essas são coleções completamente diferentes. Você pode comparar um prato doce com outro, mas funcionará com um prato de carne - eles são muito diferentes. Porém, tentarei dar algumas diferenças entre eles:

• ArrayList implementa a interface List , enquanto HashSet implementa a interface Set ;

• Em ArrayList, o acesso é possível pelo índice do elemento: a operação get tem uma complexidade algorítmica de O(1) , e em HashSet o elemento requerido só pode ser obtido por força bruta, e isso é de O(1) a O(n) ;

• ArrayList permite elementos duplicados. Em um HashSet, todos os elementos são únicos: adicionar um elemento a um HashSet cujo análogo já esteja presente na coleção não funcionará (as duplicatas são verificadas usando hashcode, daí o nome desta coleção);

• ArrayList é implementado usando um array interno e HashSet é implementado usando um HashMap interno ;

• Um ArrayList mantém a ordem de inserção dos elementos, enquanto um HashSet é um conjunto não ordenado e não mantém a ordem dos elementos;

• ArrayList permite qualquer número de valores vazios (nulos), apenas um valor nulo pode ser inserido em um HashSet (afinal, a unicidade dos elementos).

91. Por que existe tanta variedade de implementações de array dinâmico em Java?

Bem, esta é mais uma questão filosófica. Bem, por que eles criam tantas novas tecnologias diferentes? Para o conforto. Na verdade, é o mesmo com um grande número de implementações de array dinâmico. Nenhum deles pode ser considerado o melhor ou ideal. Cada um tem uma vantagem em alguma situação específica. E a nossa tarefa é conhecer as suas diferenças, os seus pontos fortes/fracos: para podermos utilizar o mais adequado na situação certa.

92. Por que existe tanta variedade de implementações de armazenamento de valores-chave em Java?

Aqui a situação é a mesma das implementações de array dinâmico. Não existe ninguém melhor: cada um tem pontos fortes e fracos. E nós, é claro, devemos aproveitar ao máximo os nossos pontos fortes. Exemplo: o pacote concorrente, que contém muitas tecnologias multithread, possui suas próprias coleções Concurrent . O mesmo ConcurrentHashMap tem uma vantagem na segurança do trabalho multithread com dados em comparação com um HashMap normal , mas em um ambiente não multithread ele perde velocidade. Pois bem, implementações, que não são as mais fortes em nenhuma situação, estão gradativamente deixando de ser utilizadas. Exemplo: Hashtable foi originalmente planejado para ser um HashMap thread-safe , mas ConcurrentHashMap o superou em um ambiente multithread e Hashtable acabou sendo esquecido e não é mais usado.

93. Como ordenar uma coleção de elementos?

A primeira coisa a dizer é que a classe do elemento da coleção deve implementar a interface Comparable e seu método compareTo . Ou você precisa de uma classe que implemente o Comaprator com seu método comparador . Você pode ler mais sobre eles neste post . Ambos os métodos especificam como os objetos de um determinado tipo devem ser comparados. Ao classificar, isso é extremamente importante, porque você precisa entender o princípio pelo qual os elementos podem ser comparados. A principal forma de fazer isso é implementar Comparable , implementado diretamente na classe que você deseja ordenar. Ao mesmo tempo, o uso do Comparador é menos comum. Digamos que você esteja usando uma classe de alguma biblioteca que não possui uma implementação Comparable , mas precisará classificá-la de alguma forma. Sem poder alterar o código desta classe (exceto estendendo-o), você pode escrever uma implementação de Comparator , na qual você indica em qual princípio deseja comparar objetos desta classe. E mais um exemplo. Digamos que você precise de princípios diferentes para classificar objetos do mesmo tipo, então você escreve vários Comparadores que usa em situações diferentes. Como regra, muitas classes prontas para uso já implementam a interface Comparable - a mesma String . Na verdade, ao usá-los, você não precisa se preocupar em como compará-los. Você apenas os pega e usa. A primeira e mais óbvia forma é utilizar uma coleção do tipo TreeSet ou TreeMap , que armazena os elementos em ordem já ordenada de acordo com o comparador de classe do elemento. Lembre-se de que TreeMap classifica chaves, mas não valores. Se você usar a implementação Comparator em vez de Comparable , precisará passar seu objeto para o construtor da coleção na criação:

TreeSet treeSet = new TreeSet(customComparator);

Mas e se você tiver um tipo diferente de coleção? Como resolver isso? Nesse caso, o segundo método da classe de utilitário Collections é adequado - o método sort() . É estático, então tudo que você precisa é o nome da classe e um método para o qual a lista necessária é passada. Por exemplo:

Collections.sort(someList);

Se você não estiver usando Comparable , mas sim uma implementação de Comparator , você precisa passá-lo como segundo parâmetro:

Collections.sort(someList, customComparator);

Como resultado, a ordem interna dos elementos da lista passada mudará: ela será classificada de acordo com o comparador de elementos. Observo que a lista de elementos transferida deve ser mutável, ou seja, mutável, caso contrário o método não funcionará e uma UnsupportedOperationException será lançada . Como terceira forma, você pode usar a operação Stream sort , que classifica os elementos da coleção se a implementação Comparable for usada :

someList = someList.stream().sorted().collect(Collectors.toList());

se Comparador :

someList = someList.stream().sorted(customComparator).collect(Collectors.toList());

Você pode ler mais sobre o Stream neste artigo . O quarto método é implementar manualmente a classificação, como classificação por bolha ou classificação por mesclagem .

ClassObject. Igual e HashCode

94. Dê uma breve descrição do objeto de classe em Java

Na segunda parte da análise já falamos sobre os métodos da classe Object , e vou lembrar que a classe Object é a progenitora de todas as classes em Java. Possui 11 métodos, que, respectivamente, são herdados por todas as classes. Informações sobre todos os 11 métodos podem ser encontradas na segunda parte da discussão.

95. Para que servem Equals e HashCode em Java?

hashCode() é um método da classe Object que é herdado por todas as classes. Sua tarefa é gerar algum número que represente um objeto específico. Um exemplo de utilização deste método é seu uso em um HashMap em um objeto chave para determinar ainda mais o hashcode local, que determinará a célula do array interno (bucket) na qual o par será armazenado. Falamos detalhadamente sobre o trabalho do HashMap na parte 9 da análise , então não vamos nos alongar muito sobre isso. Além disso, via de regra, este método é usado no método equals() como uma de suas principais ferramentas para determinar a identidade de objetos. equals() é um método da classe Object cuja função é comparar objetos e determinar se eles são iguais ou não. Este método é usado em todos os lugares onde precisamos comparar objetos, porque a comparação usual usando == não é adequada para objetos, porque compara apenas links para eles.

96. Conte-nos sobre o contrato entre Equals e HashCode em Java?

A primeira coisa que direi é que para que os métodos equals() e hashCode() funcionem corretamente , eles precisam ser substituídos corretamente. Depois disso eles deverão seguir as regras:

• objetos idênticos para os quais a comparação via igual retorna verdadeiro devem ter códigos hash idênticos;
• objetos com os mesmos códigos hash podem nem sempre ser iguais.

Neste ponto faremos uma pausa até a próxima parte da análise!