O começo do caminho
Hoje gostaria de falar sobre um tema tão interessante como o “
Java Collections Framework ” ou, em termos simples, sobre coleções. A maior parte do trabalho do código consiste em processar dados de uma forma ou de outra. Obtenha uma lista de usuários, uma lista de endereços, etc. De alguma forma, classifique-os, faça uma pesquisa, compare-os. É por isso que o conhecimento de coleções é considerado uma habilidade essencial. É por isso que quero falar sobre isso. Além disso, uma das perguntas mais comuns nas entrevistas com desenvolvedores Java são sobre coleções. Por exemplo, “desenhe uma hierarquia de coleções”. O compilador online nos ajudará em nosso caminho. Por exemplo, você pode usar " Tutorialspoint
Online Java Compiler " ou
Repl.it. O caminho para conhecer qualquer estrutura de dados começa com variáveis comuns (Variáveis). No site da Oracle, diversos tópicos são representados como “caminhos” ou Trilhas. Então, o caminho para conhecer Java se chama “
Trilha: Aprendendo a Linguagem Java: Índice ”. E o básico da linguagem (ou seja, noções básicas da linguagem) começa com variáveis. Portanto, vamos escrever um código simples:
public static void main(String[] args) {
String user = "Max";
System.out.println("Hello, " + user);
}
É bom em tudo, exceto que entendemos que esse código é bom e bonito apenas para uma variável. O que fazer se houver vários deles? Arrays foram inventados para armazenar dados de um tipo. No mesmo Trail da Oracle há uma seção separada dedicada a arrays. Esta seção é chamada: "
Arrays ". Trabalhar com arrays também é bastante simples:
import java.util.Arrays;
class Main {
public static void main(String[] args) {
String[] users = new String[2];
users[0] = "Max";
users[1] = "John";
System.out.println("Hello, " + Arrays.toString(users));
}
}
Matrizes resolvem o problema de armazenar vários valores em um só lugar. Mas impõe uma limitação: o tamanho do array é constante. Se, como no exemplo, dissermos que tamanho = 2, então é igual a dois. Isso é tudo. Se quisermos um array maior, precisamos criar uma nova instância. Além disso, encontrar um elemento também é algo complicado para um array. Existe um método
Arrays.binarySearch, mas essa busca só funciona em um array ordenado (para um array não classificado, o resultado é indefinido ou simplesmente imprevisível). Ou seja, a pesquisa nos obrigará a ordenar a cada vez. A exclusão também limpa apenas o valor. Portanto, ainda não sabemos quantos dados estão realmente no array, sabemos apenas quantas células estão no array. Para atualizar seu conhecimento sobre arrays:
E como consequência do desenvolvimento da linguagem Java, surgiu o Java Collections Framework no JDK 1.2, do qual falaremos hoje.
Coleção
Comece a custear desde o início. Por que coleções? O próprio termo vem de coisas como “Teoria dos Tipos” e “Tipos de Dados Abstratos”. Mas se você não olhar para nenhum assunto elevado, então, quando temos várias coisas, podemos chamá-las de “coleção de coisas”. Aqueles que coletam itens. Em geral, a própria palavra coletar vem do Lat. collectio "reunindo, coletando." Ou seja, uma coleção é uma coleção de algo, um contêiner para alguns elementos. Portanto, temos uma coleção de elementos. O que podemos querer fazer com isso:
Como você pode ver, podemos querer coisas bastante lógicas. Também entendemos que podemos querer fazer algo com múltiplas coleções:
Conseqüentemente, os desenvolvedores Java escreveram a interface java.util.Collection para descrever esse comportamento geral para todas as coleções . A interface Collection é onde todas as coleções se originam. Coleção é uma ideia, é uma ideia de como todas as coleções deveriam se comportar. Portanto, o termo “Coleção” é expresso como uma interface. Naturalmente, uma interface precisa de implementações. A interface
java.util.Collectionpossui uma classe abstrata
AbstractCollection, ou seja, alguma “coleção abstrata”, que representa o esqueleto para outras implementações (conforme escrito no JavaDoc acima da classe
java.util.AbstractCollection). Falando sobre coleções, vamos voltar e lembrar que queremos iterá-las. Isso significa que queremos iterar os elementos um por um. Este é um conceito muito importante. Portanto, a interface
Collectioné herdada do
Iterable. Isso é muito importante porque... em primeiro lugar, tudo o que é Iterável deve ser capaz de retornar um Iterador com base em seu conteúdo. E em segundo lugar, tudo que é Iterable pode ser usado em loops
for-each-loop. E é com a ajuda de um iterador que
AbstractCollectionmétodos como
contains,, são implementados . E o caminho para entender as coleções começa com uma das estruturas de dados mais comuns – uma lista, ou seja, .
toArrayremoveList
Listas
Assim, as listas ocupam um lugar importante na hierarquia das coleções:
Como podemos ver, as listas implementam a interface
java.util.List . As listas expressam que temos uma coleção de elementos organizados em alguma sequência, um após o outro. Cada elemento possui um índice (como em um array). Normalmente, uma lista permite ter elementos com o mesmo valor. Como dissemos acima,
Listele conhece o índice do elemento. Isso permite obter (
get) um elemento por índice ou definir um valor para um índice específico (
set). Os métodos de coleção
add,
addAll,
removepermitem especificar o índice a partir do qual executá-los. Além disso, y
Listpossui sua própria versão de um iterador chamado
ListIterator. Este iterador conhece o índice do elemento, portanto pode iterar não apenas para frente, mas também para trás. Pode até ser criado a partir de um local específico da coleção. Entre todas as implementações, existem duas mais comumente utilizadas:
ArrayListe
LinkedList. Primeiro,
ArrayListé uma lista (
List) baseada em um array (
Array). Isso permite que você obtenha "acesso aleatório"
aos elementos. Acesso aleatório é a capacidade de recuperar imediatamente um elemento por índice, em vez de percorrer todos os elementos até encontrar o elemento com o índice desejado. É o array como base que permite que isso seja alcançado. Pelo contrário,
LinkedListé uma lista vinculada. Cada entrada em uma lista vinculada é representada no formulário
Entry, que armazena os próprios dados, bem como um link para o próximo (próximo) e anterior (anterior)
Entry. Assim
LinkedListimplementa o "Acesso Sequencial
" . É claro que para encontrar o 5º elemento teremos que ir do primeiro ao último elemento, pois não temos acesso direto ao quinto elemento. Só podemos acessá-lo a partir do 4º elemento. A diferença em seu conceito é dada abaixo:
No trabalho, como você entende, também há uma diferença. Por exemplo, adicionando elementos. Os
LinkedListelementos são simplesmente conectados como elos de uma corrente. Mas
ArrayListarmazena elementos em um array. E um array, como sabemos, não pode alterar seu tamanho. Como funciona, então
ArrayList? E funciona de forma muito simples. Quando o espaço no array acaba, ele aumenta 1,5 vezes. Aqui está o código do zoom:
int newCapacity = oldCapacity + (oldCapacity >> 1); Outra diferença na operação é qualquer deslocamento de elementos. Por exemplo, ao adicionar ou remover elementos do meio. Para remover de
LinkedListum elemento, basta remover as referências a este elemento. No caso de,
ArrayListsomos forçados a deslocar os elementos a cada vez usando o
System.arraycopy. Assim, quanto mais elementos, mais ações deverão ser realizadas. Uma descrição mais detalhada pode ser encontrada nestes artigos:
Tendo examinado ArrayList, não podemos deixar de lembrar seu “predecessor”, a classe
java.util.Vector . A diferença
Vectoré
ArrayListque os métodos de trabalho com a coleção (adicionar, excluir, etc.) são sincronizados. Ou seja, se um thread (
Thread) adicionar elementos, os outros threads esperarão até que o primeiro thread termine seu trabalho. Como a segurança do thread geralmente não é necessária, é recomendável usar a classe nesses casos
ArrayList, conforme declarado explicitamente no JavaDoc da classe
Vector. Além disso,
Vectoraumenta seu tamanho não em 1,5 vezes,
ArrayListmas em 2 vezes. Caso contrário, o comportamento é o mesmo -
Vectoro armazenamento de elementos na forma de uma matriz fica oculto e a adição/remoção de elementos tem as mesmas consequências que em
ArrayList. Na verdade,
Vectornos lembramos disso por um motivo. Se olharmos no Javadoc, veremos em "Subclasses diretas conhecidas" uma estrutura como
java.util.Stack . A pilha é uma estrutura interessante que é uma
last-in-first-outestrutura LIFO (último a entrar, primeiro a sair). Pilha traduzida do inglês é uma pilha (como uma pilha de livros, por exemplo). A pilha implementa métodos adicionais:
peek(look, look),
pop(push),
push(push). O método
peeké traduzido como olhar (por exemplo,
espiar dentro da bolsa é traduzido como “
olhar dentro da bolsa ”, e
espiar pelo buraco da fechadura é traduzido como “
espiar pelo buraco da fechadura ”). Este método permite que você olhe para o “topo” da pilha, ou seja, obtenha o último elemento sem removê-lo (ou seja, sem removê-lo) da pilha. O método
pushempurra (adiciona) um novo elemento na pilha e o retorna, e o método do elemento
popempurra (remove) e retorna o removido. Em todos os três casos (ou seja, peek, pop e push), trabalhamos apenas com o último elemento (ou seja, o “topo da pilha”). Esta é a principal característica da estrutura da pilha. A propósito, existe uma tarefa interessante para entender pilhas, descrita no livro “A Programmer's Career” (Cracking Coding Interview). Existe uma tarefa interessante onde usando a estrutura “stack” (LIFO) você precisa implementar a “fila ”Estrutura (FIFO). Deveria ficar assim:
Uma análise desta tarefa pode ser encontrada aqui: "
Implement A Queue Using Stacks - The Queue ADT ("Implement Queue Using Stacks" on LeetCode) ". Assim, passamos suavemente para uma nova estrutura de dados - uma fila.
Fila
Uma fila é uma estrutura que conhecemos da vida. Filas para lojas, para médicos. Quem chegou primeiro (First In) será o primeiro a sair da fila (First Out). Em Java, uma fila é representada pela interface
java.util.Queue . De acordo com o Javadoc da fila, a fila adiciona os seguintes métodos:
Como você pode ver, existem métodos de pedido (a falha em executá-los acarreta uma exceção) e existem métodos de solicitação (a incapacidade de executá-los não leva a erros). Também é possível obter o elemento sem removê-lo (espiada ou elemento). A interface da fila também possui um sucessor útil -
Deque . Esta é a chamada “fila bidirecional”. Ou seja, tal fila permite utilizar essa estrutura tanto do início quanto do final. A documentação diz que "Deques também pode ser usado como pilhas LIFO (Last-In-First-Out). Esta interface deve ser usada preferencialmente à classe Stack legada.", ou seja, é recomendado usar implementações Deque em vez de Pilha. O Javadoc mostra quais métodos a interface Deque descreve:
Vamos ver quais implementações existem. E veremos um fato interessante - o LinkedList entrou no campo das filas. Ou seja, o LinkedList implementa
List, e
Deque. Mas também existem “só filas”, por exemplo
PriorityQueue. Ela não é lembrada com frequência, mas em vão. Em primeiro lugar, você não pode usar "objetos não comparáveis" nesta fila, ou seja, ou Comparator deve ser especificado ou todos os objetos devem ser comparáveis. Em segundo lugar, "esta implementação fornece tempo O(log(n)) para os métodos de enfileiramento e desenfileiramento". A complexidade logarítmica existe por uma razão. Implementado PriorityQueue com base no heap. O Javadoc diz: "Fila prioritária representada como um heap binário balanceado". O próprio armazenamento para isso é um array regular. Que cresce quando necessário. Quando o heap é pequeno, aumenta 2 vezes. E então em 50%. Comentário do código: "Duplique o tamanho se for pequeno; caso contrário, aumente 50%". A fila de prioridade e o heap binário são um tópico separado. Então, para mais informações:
Uma implementação
java.util.Dequepoderia ser a classe
java.util.ArrayDeque . Ou seja, as listas podem ser implementadas usando uma lista vinculada e uma matriz, e as filas também podem ser implementadas usando uma matriz ou uma lista vinculada. As interfaces
Queueand
Dequepossuem descendentes que representam a "fila de bloqueio":
BlockingQueuee
BlockingDeque. Aqui está a mudança de interface em comparação com as filas normais:
Vejamos alguns exemplos de bloqueio de filas. Mas eles são interessantes. Por exemplo, BlockingQueue é implementado por:
PriorityBlockingQueue ,
SynchronousQueue , ArrayBlockingQueue,
DelayQueue ,
LinkedBlockingQueue . Mas
BlockingDequeeles implementam tudo, desde os Collection Frameworks padrão
LinkedBlockingDeque. Cada fila é o tópico de uma revisão separada. E no âmbito desta revisão, representaremos a hierarquia de classes não apenas com
List, mas também com
Queue:
Como podemos ver no diagrama, as interfaces e classes do Java Collections Framework estão altamente interligadas. Vamos adicionar outro ramo da hierarquia -
Set.
Definir
Set– traduzido como “conjunto”. Difere de uma fila e de uma lista
Setpor sua maior abstração sobre o armazenamento de elementos.
Set- como uma bolsa de objetos, onde não se sabe como os objetos estão localizados e em que ordem estão dispostos. Em Java, tal conjunto é representado pela interface
java.util.Set . Como diz a documentação,
Setesta é uma "coleção que não contém elementos duplicados". Curiosamente, a interface em si
Setnão adiciona novos métodos à interface
Collection, mas apenas esclarece os requisitos (sobre o que não deve conter duplicatas). Além disso, segue-se da descrição anterior que você não pode simplesmente
Setobter um elemento dela. Iterator é usado para obter elementos.
Settem várias outras interfaces associadas a ele. O primeiro é
SortedSet. Como o nome sugere,
SortedSetindica que tal conjunto está classificado e, portanto, os elementos implementam a interface
Comparableou são especificados
Comparator. Além disso,
SortedSetoferece vários métodos interessantes:
Além disso, existem métodos
first(menor elemento por valor) e
last(maior elemento por valor). Há
SortedSetum herdeiro -
NavigableSet. O objetivo desta interface é descrever os métodos de navegação necessários para identificar com mais precisão os elementos apropriados. O interessante é
NavigableSetque ele adiciona ao iterador usual (que vai do menor para o maior) um iterador de ordem inversa -
descendingIterator. Além disso,
NavigableSetpermite utilizar o método
descendingSetpara obter uma visão de si mesmo (View), em que os elementos estão na ordem inversa. Isso é chamado
Viewporque através do elemento resultante você pode alterar os elementos do original
Set. Ou seja, em essência, é uma representação dos dados originais de uma forma diferente, e não uma cópia deles. Curiosamente,
NavigableSetassim como
Queue, podem lidar com elementos
pollFirst(mínimos) e (máximos).
pollLastOu seja, ele pega esse elemento e o retira do conjunto. Que tipo de implementações existem? Em primeiro lugar, a implementação mais famosa é baseada em código hash -
HashSet . Outra implementação igualmente conhecida é baseada em uma árvore vermelha e preta -
TreeSet . Vamos completar nosso diagrama:
Dentro das coleções, resta ordenar a hierarquia - os eremitas. O que à primeira vista fica de lado -
java.util.Map.
Mapas
Mapas são uma estrutura de dados na qual os dados são armazenados por chave. Por exemplo, a chave pode ser um ID ou código de cidade. E é por esta chave que os dados serão pesquisados. É interessante que os cartões sejam exibidos separadamente. De acordo com os desenvolvedores (consulte "
Perguntas frequentes sobre design de API de coleções Java "), o mapeamento de valores-chave não é uma coleção. E os mapas podem ser pensados mais rapidamente como uma coleção de chaves, uma coleção de valores, uma coleção de pares chave-valor. Este é um animal tão interessante. Quais métodos os cartões oferecem? Vejamos a interface da API Java
java.util.Map . Porque Como os mapas não são coleções (eles não herdam de Coleções), eles não contêm um arquivo
contains. E isso é lógico. Um mapa consiste em chaves e valores. Qual destes o método deve verificar
containse como não se confundir? Portanto, a interface
Mappossui duas versões diferentes:
containsKey(contém uma chave) e
containsValue(contém um valor). Usá-lo
keySetpermite que você obtenha um conjunto de chaves (a mesma
Set). E usando o método
valuespodemos obter uma coleção de valores no mapa. As chaves no mapa são únicas, o que é enfatizado pela estrutura de dados
Set. Os valores podem ser repetidos, o que é enfatizado pela estrutura de dados da Coleção. Além disso, usando o método
entrySetpodemos obter um conjunto de pares chave-valor. Você pode ler mais sobre quais implementações de cartão existem nas análises mais detalhadas:
Eu também gostaria de ver o que é
HashMapmuito semelhante a
HashSete
TreeMapa
TreeSet. Eles ainda têm interfaces semelhantes:
NavigableSetand
NavigableMap,
SortedSetand
SortedMap. Portanto, nosso mapa final ficará assim:
Podemos terminar com o fato interessante de que a coleção
Setutiliza internamente
Map, onde os valores somados são chaves, e o valor é o mesmo em todos os lugares. Isso é interessante porque
Mapnão é uma coleção e retorna
Set, que é uma coleção, mas na verdade é implementada como
Map. Um pouco surreal, mas foi assim que aconteceu)
Conclusão
A boa notícia é que esta revisão termina aqui. A má notícia é que este é um artigo muito revisado. Cada implementação de cada uma das coleções merece um artigo separado, e também para cada algoritmo escondido dos nossos olhos. Mas o objetivo desta revisão é lembrar o que são e quais são as conexões entre as interfaces. Espero que, após uma leitura cuidadosa, você consiga desenhar um diagrama das coleções de memória.
Bem, como sempre, alguns links:
#Viacheslav
GO TO FULL VERSION