O que eles podem perguntar em uma entrevista: Estruturas de dados em Java. Parte 2

PARTE 1 Agora estamos falando da base que todo desenvolvedor Java deve conhecer. Sobre aquele conhecimento clássico a partir do qual tudo começa. Hoje eu gostaria de abordar um dos tópicos fundamentais de qualquer estrutura de dados de entrevistas em Java . Então, em vez de rodeios, vamos começar. Veja a continuação da lista de perguntas que podem ser feitas sobre esse assunto durante uma entrevista.

6. Conte-nos sobre a lista

Lista é uma interface que representa uma estrutura ordenada de objetos, chamada lista. O “truque” dessa estrutura é que os elementos contidos na Lista podem ser inseridos, modificados ou deletados por índice, ou seja, o identificador interno da Lista . Em outras palavras, índice significa: “quantos elementos estão no início da lista”. O primeiro elemento List possui índice 0, o segundo possui índice 1 e assim por diante. Portanto, o quinto elemento está a quatro elementos do início da lista. Conforme mencionado acima, a ordem em que os itens são adicionados a uma lista é importante. É por isso que a estrutura de dados é chamada de lista . Listamos métodos exclusivos desta estrutura que visam trabalhar com elementos por índice:

• get - retorna o elemento na posição especificada (por valor de índice),
• remover - remove o elemento na posição especificada,
• set - substitui o elemento na posição especificada pelo elemento especificado no método.

As principais implementações são ArrayList e LinkedList . Falaremos mais sobre eles um pouco mais tarde. Vector é uma lista thread-safe, portanto, cada método nesta classe é sincronizado. Mas lembre-se de que se quiser proteger algumas ações da lista, você estará sincronizando toda uma sequência de operações. E sincronizar operações individuais é menos seguro e muito mais lento. É claro que o Vector também possui sobrecarga de bloqueio, mesmo que você não precise do bloqueio. Portanto, esta classe agora é considerada obsoleta e não é utilizada. A propósito: ArrayList é semelhante a Vector , mas não usa bloqueio, por isso é usado em todos os lugares. Stack é uma subclasse da classe Vector com um construtor padrão e todos os métodos da classe Vector , além de alguns próprios (falaremos sobre eles mais tarde). Por exemplo, você pode imaginar o processo como uma pilha de pastas com documentos. Você coloca uma pasta no topo da pilha e só pode pegar essas pastas na ordem inversa, começando do topo. Na verdade, este é um mecanismo do tipo LIFO , ou seja, Last In First Out , o último a chegar é o primeiro a sair. A pilha implementa seus próprios métodos:

• push - adiciona o elemento passado ao topo da pilha;
• peek – retorna o elemento que está no topo da pilha;
• pop - também retorna o elemento que está no topo da pilha, mas o remove;
• vazio - verifica se a pilha está vazia - verdadeiro ou não - falso ;
• search - pesquisa na pilha um determinado elemento. Se um elemento for encontrado, seu número de sequência relativo ao topo da pilha será retornado. Se o elemento não for encontrado, o valor -1 será retornado.

No momento, a subclasse Stack não é realmente usada devido à sua simplicidade e inflexibilidade, mas, mesmo assim, você pode encontrá-la. Por exemplo, quando você recebe algum erro e no console você vê uma pilha de mensagens sobre isso. Você pode ler mais sobre pilha e fila neste artigo .

7. Conte-nos sobre o Mapa

Conforme afirmado acima, um Mapa é uma coleção que possui uma estrutura separada de interfaces e suas implementações. É separado porque aqui os valores não são armazenados um de cada vez, mas em um par “chave-valor”. Métodos básicos de mapa :

• put(K key, V value) - adicionando um elemento ao Mapa;
• get(Object key) - procura um valor por chave;
• containsKey(Object key) — verifica no Mapa a presença desta chave;
• containsValue(Object value) - verifica no Mapa a presença deste valor;
• remove(Object key) - removendo um valor por sua chave.

Como você pode ver, a maioria das operações funciona usando uma chave. Via de regra, objetos imutáveis ​​são escolhidos como chaves . Um exemplo típico deste objeto é String . Implementações básicas de mapas :

1. HashMap - projetado para armazenar valores em ordem aleatória, mas permite pesquisar rapidamente os elementos do mapa. Permite especificar uma chave usando a palavra-chave nula , mas não mais de uma vez, porque pares com as mesmas chaves são escritos um sobre o outro. A principal condição é a singularidade das chaves: os valores podem ser repetidos (pode haver vários valores nulos).
2. LinkedHashMap é um análogo do HashMap que armazena valores na ordem em que foram adicionados. Assim, como LinkedList , ele possui um cabeçalho - o cabeçalho de uma lista duplamente vinculada. Quando inicializado, aponta para si mesmo.

   LinkedHashMap também possui um accessOrder que especifica como os elementos serão acessados ​​quando o iterador for usado. Se accessOrder for falso, o acesso será realizado na ordem em que os elementos foram inseridos. Se for verdade, os elementos estarão na ordem do último acesso (o último elemento acessado será colocado no final).

3. TreeMap é um mapa que classifica os elementos por valores-chave. Semelhante a TreeSet , mas para pares baseados em valores-chave. Para definir regras de classificação do TreeMap , as chaves devem implementar a interface Comparable . Caso contrário, deve haver um Comparador orientado a chave (aquele especificado no construtor TreeMap ), um TreeSet - implementado com um objeto TreeMap dentro, no qual, de fato, toda a mágica acontece.

   Você pode ler mais sobre classificação no TreeMap usando árvores vermelhas e pretas no artigo sobre os recursos do TreeMap .

4. Hashtable é semelhante a HashMap , mas não permite que nulos sejam armazenados como chaves ou valores. Ele é cuidadosamente sincronizado do ponto de vista multithreading, o que por sua vez significa que é seguro do ponto de vista multithreading. Mas esta implementação está desatualizada e lenta, então agora você não verá Hashtable em projetos mais ou menos novos.

8. ArrayList versus LinkedList. Qual é preferível usar?

Esta questão é talvez a mais popular em estruturas de dados e traz consigo algumas armadilhas. Antes de responder, vamos aprender mais sobre essas estruturas de dados. ArrayList implementa a interface List e opera em um array interno que é expandido conforme necessário. Quando o array interno está completamente preenchido e um novo elemento precisa ser inserido, um novo array é criado com tamanho (oldSize * 1.5) +1. Depois disso, todos os dados do array antigo serão copiados para o novo + novo elemento, e o antigo será excluído pelo coletor de lixo . O método add adiciona um elemento à última célula vazia do array. Ou seja, se já tivermos 3 elementos ali, ele irá adicionar o próximo à 4ª célula. Vejamos o desempenho dos métodos básicos:

• get(int index) - pegar um elemento em um array por índice é o mais rápido em O(1) ;
• add(Object obj) - se houver espaço suficiente no array interno para um novo elemento, então com uma inserção normal O(1) será gasto tempo , já que a adição é direcionada para a última célula.

  Se precisarmos criar um novo array e copiar o conteúdo nele, então nosso tempo será diretamente proporcional ao número de elementos no array O(n) ;

• remove(int index) - ao remover um elemento, por exemplo, do meio, obteremos o tempo O(n/2), pois precisaremos mover os elementos à direita dele uma célula para trás. Assim, se excluir do início da lista, então O(n), do final - O(1);
• add(int index, Object obj) - uma situação semelhante à exclusão: ao adicionar ao meio, precisaremos mover os elementos da direita uma célula para frente, então o tempo é O(n/2). Claro, desde o início - O(n), desde o final - O(1);
• set(int index, Object obj) - aqui a situação é diferente, pois você só precisa encontrar o elemento desejado e escrever sobre ele sem mover o resto, então O(1).

Leia mais sobre ArrayList neste artigo . LinkedList implementa duas interfaces ao mesmo tempo - List e Queue e, portanto, possui propriedades e métodos inerentes a ambas as estruturas de dados. Da Lista ele obteve acesso ao elemento por índice, da Fila - a presença de “cabeça” e “cauda”. Internamente, é implementado como uma estrutura de dados que representa uma lista duplamente vinculada. Ou seja, cada elemento possui uma ligação com o próximo e o anterior, exceto a “cauda” e a “cabeça”.

• get(int index) - ao buscar um elemento que está no meio da lista, ele inicia a busca por todos os elementos na ordem até encontrar o desejado. Logicamente, a busca deve levar O(n/2) , mas o LinkedList também tem cauda, ​​então a busca é realizada simultaneamente de ambos os lados. Consequentemente, o tempo é reduzido para O(n/4) .

  Se o elemento estiver próximo ao início ou ao final da lista, então o tempo será O(1) ;

• add(Object obj) - ao adicionar um novo elemento, o elemento “cauda” terá um link para o próximo elemento adicionado, e o novo receberá um link para este elemento anterior e se tornará o novo “cauda”. Conseqüentemente, o tempo será O(1) ;
• remove(int index) - lógica semelhante ao método get(int index) . Para remover um elemento do meio da lista, primeiro você deve localizá-lo. Isso é novamente O(n/4) , enquanto a exclusão em si não leva nada, pois apenas altera o ponteiro dos objetos vizinhos (eles começam a se referir um ao outro). Se o elemento estiver no início ou no final, então novamente - O(1) ;
• add(int index, Object obj) e set(int index, Object obj) - os métodos terão uma complexidade de tempo idêntica a get(int index) , já que a maior parte do tempo é gasto procurando o elemento. Portanto, para o meio da lista - O(n/4) , para o início - O(1).

Mais informações sobre como trabalhar com LinkedList são descritas neste artigo . Vejamos tudo isso em uma tabela: Como você provavelmente já entendeu, é impossível responder a esta pergunta de forma inequívoca. Afinal, em situações diferentes eles trabalham em velocidades diferentes. Portanto, quando lhe for feita uma pergunta como esta, você deve perguntar imediatamente em que esta lista se concentrará e quais operações serão realizadas com mais frequência. A partir disso, dê uma resposta, mas com explicações de por que isso acontece. Vamos resumir nossa comparação: ArrayList:

• a melhor escolha se a operação mais frequente for a busca de um elemento, sobrescrevendo um elemento;
• a pior escolha se a operação for inserção e exclusão no início-meio, pois ocorrerão as operações de deslocamento dos elementos à direita.

Lista vinculada:

• a melhor escolha se nossa operação frequente for inserção e exclusão no início-meio;
• pior escolha se a operação mais comum for a pesquisa.

9. Como os elementos são armazenados em um HashMap?

A coleção HashMap contém uma tabela Node[] de matriz interna , cujas células também são chamadas de buckets . O nó contém:

• chave - link para a chave,
• valor - referência ao valor,
• hash - valor de hash,
• next - link para o próximo nó .

Uma célula do array table[] pode conter uma referência a um objeto Node com um link para o próximo elemento Node , e pode ter um link para outro, e assim por diante... Como resultado, esses elementos Node podem formar um lista vinculada individualmente , com elementos com link para o próximo. Neste caso, o valor hash dos elementos da mesma cadeia é o mesmo. Após uma breve digressão, vamos ver como os elementos são armazenados em um HashMap :

1. A chave é verificada para null . Se for null , então key será armazenado na célula table[0] porque o código hash para null é sempre 0.
2. Se a chave não for null , então o método hashcode() do objeto chave é chamado , que retornará seu código hash. Este código hash é usado para determinar a célula do array onde o objeto Node será armazenado.
3. A seguir, esse hashcode é colocado no método hash() interno , que calcula o hashcode, mas dentro do tamanho do array table[] .
4. Em seguida, dependendo do valor do hash, o Node é colocado em uma célula específica no array table[] .
5. Se a célula table[] usada para salvar o elemento Node atual não estiver vazia, mas já tiver algum elemento, então os elementos Node serão iterados sobre o próximo valor até que o último elemento seja alcançado. Ou seja, aquele cujo próximo campo é null .

   Durante esta pesquisa, a chave do objeto Node protegido é comparada com as chaves daqueles que estão sendo pesquisados:

   • se uma correspondência for encontrada, a pesquisa terminará e o novo Node substituirá o Node em que a correspondência foi encontrada (apenas o seu campo de valor será substituído );
   • se nenhuma correspondência de chave for encontrada, o novo nó se tornará o último da lista e o anterior terá um próximo link para ele.

A questão surge frequentemente durante as entrevistas: o que é um conflito ? A situação em que uma célula do array table[] armazena não um elemento, mas uma cadeia de dois ou mais, é chamada de colisão . Em casos normais onde apenas um elemento é armazenado em uma única célula table[] , o acesso aos elementos de um HashMap tem complexidade de tempo O(1) constante . Mas quando uma célula com o elemento desejado contém uma cadeia de elementos ( colisão ), então O(n) , já que neste caso o tempo é diretamente proporcional ao número de elementos que estão sendo ordenados.

10. Explique o iterador

No diagrama de mapeamento da hierarquia da Coleção acima, a interface da Coleção era onde toda a hierarquia começava, mas na prática não é bem assim. A coleção herda de uma interface com um método iterator() , que retorna um objeto que implementa a interface Iterator<E> . A interface do Iterador é semelhante a esta:

public interface Iterator <E>{

    E next();
    boolean hasNext();
    void remove();
}

next() - chamando este método, você pode obter o próximo elemento. hasNext() - permite descobrir se existe um próximo elemento e se o final da coleção foi atingido. E quando ainda houver elementos, hasNext() retornará true . Normalmente, hasNext() é chamado antes do método next() , já que next() lançará uma NoSuchElementException quando atingir o final da coleção . remove() - Remove o elemento que foi recuperado pela última chamada para next() . O objetivo do Iterator é iterar sobre os elementos. Por exemplo:

Set<Integer> values = new TreeSet<>();
  values.add(5);
values.add(3);
values.add(6);
values.add(8);
values.add(2);
values.add(4);
values.add(1);
values.add(7);

Iterator<Integer> iter = values.iterator();
while(iter.hasNext()){
  System.out.println(iter.next());
}

Na verdade, o loop for-each é implementado internamente usando um iterador. Você pode ler mais sobre isso aqui . List fornece sua própria versão de um iterador, mas uma versão mais legal e sofisticada - ListIterator . Esta interface estende o Iterator e possui métodos adicionais:

• hasPrevious retornará true se houver um elemento anterior na coleção, false caso contrário;
• anterior retorna o elemento atual e passa para o anterior; se não houver nenhum, uma NoSuchElementException será lançada;
• add irá inserir o objeto passado antes do elemento a ser retornado pela próxima chamada para next() ;
• set atribui ao elemento atual uma referência ao objeto passado;
• nextIndex retorna o índice do próximo elemento. Se não existir, o tamanho da lista será retornado;
• previousIndex retorna o índice do elemento anterior. Se não houver nenhum, o número -1 será retornado.

Bem, isso é tudo para mim hoje. Espero que depois de ler este artigo você esteja ainda mais perto do seu sonho acalentado - tornar-se um desenvolvedor.