Estrutura de coleções Java - Java collections framework
A estrutura de coleções Java é um conjunto de classes e interfaces que implementam estruturas de dados de coleção comumente reutilizáveis .
Embora referido como uma estrutura , funciona como uma biblioteca . A estrutura de coleções fornece interfaces que definem várias coleções e classes que as implementam.
Diferenças de matrizes
Coleções e matrizes são semelhantes, pois ambas contêm referências a objetos e podem ser gerenciadas como um grupo. No entanto, ao contrário dos arrays, as coleções não precisam ser atribuídas a uma determinada capacidade quando instanciadas. As coleções também podem aumentar e diminuir de tamanho automaticamente quando os objetos são adicionados ou removidos. As coleções não podem conter elementos de tipo de dados básicos (tipos primitivos), como int, long ou double; em vez disso, eles contêm classes de invólucro, como Integer, Long ou Double.
História
As implementações de coleção nas versões pré- JDK 1.2 da plataforma Java incluíam algumas classes de estrutura de dados, mas não continham uma estrutura de coleções. Os métodos padrão para agrupar objetos Java eram por meio das classes array, Vector e Hashtable, que infelizmente não eram fáceis de estender e não implementavam uma interface de membro padrão.
Para atender à necessidade de estruturas de dados de coleta reutilizáveis , vários frameworks independentes foram desenvolvidos, sendo os mais utilizados o pacote Doug Lea 's Collections e a ObjectSpace Generic Collection Library (JGL), cujo objetivo principal era a consistência com a C ++ Standard Template Library (STL) .
A estrutura de coleções foi projetada e desenvolvida principalmente por Joshua Bloch e introduzida no JDK 1.2 . Ele reutilizou muitas ideias e classes do pacote Coleções de Doug Lea , que foi descontinuado como resultado. A Sun Microsystems optou por não usar as idéias de JGL, porque queria uma estrutura compacta e a consistência com C ++ não era um de seus objetivos.
Mais tarde, Doug Lea desenvolveu um pacote de simultaneidade , compreendendo novas classes relacionadas à coleção. Uma versão atualizada desses utilitários de simultaneidade foi incluída no JDK 5.0 a partir do JSR 166 .
Arquitetura
Quase todas as coleções em Java são derivadas da interface java.util.Collection. Coleção define as partes básicas de todas as coleções. A interface indica os métodos add () e remove () para adicionar e remover de uma coleção, respectivamente. Também é necessário o método toArray (), que converte a coleção em uma matriz simples de todos os elementos da coleção. Finalmente, o método contains () verifica se um elemento especificado está na coleção. A interface Collection é uma subinterface de java.lang.Iterable, portanto, qualquer Collection pode ser o destino de uma instrução for-each. (A interface Iterable fornece o método iterator () usado por instruções for-each.) Todas as coleções têm um iterador que passa por todos os elementos da coleção. Além disso, a coleção é genérica. Qualquer coleção pode ser escrita para armazenar qualquer classe. Por exemplo, Collection <String> pode conter strings e os elementos da coleção podem ser usados como strings sem a necessidade de conversão. Observe que os colchetes angulares <> podem conter um argumento de tipo que especifica qual tipo a coleção contém.
Três Tipos de Coleção
Existem três tipos genéricos de coleção: listas ordenadas, dicionários / mapas e conjuntos.
Listas ordenadas permitem que o programador insira itens em uma determinada ordem e recupere esses itens na mesma ordem. Um exemplo é uma lista de espera. As interfaces básicas para listas ordenadas são chamadas de Lista e Fila.
Dicionários / mapas armazenam referências a objetos com uma chave de pesquisa para acessar os valores do objeto. Um exemplo de chave é um cartão de identificação. A interface básica para dicionários / mapas é chamada de Mapa.
Conjuntos são coleções não ordenadas que podem ser iteradas e contêm cada elemento no máximo uma vez. A interface básica para conjuntos é chamada de Conjunto.
Interface de lista
As listas são implementadas na estrutura de coleções por meio da interface java.util.List. Ele define uma lista como essencialmente uma versão mais flexível de um array. Os elementos têm uma ordem específica e são permitidos elementos duplicados. Os elementos podem ser colocados em uma posição específica. Eles também podem ser pesquisados na lista. Dois exemplos de classes concretas que implementam List são:
- java.util.ArrayList, que implementa a lista como uma matriz. Sempre que funções específicas para uma lista são necessárias, a classe move os elementos dentro do array para fazer isso.
- java.util.LinkedList. Esta classe armazena os elementos em nós em que cada um tem um ponteiro para o nó anterior e o próximo na lista. A lista pode ser percorrida seguindo os ponteiros e os elementos podem ser adicionados ou removidos simplesmente alterando os ponteiros para colocar o nó em seu devido lugar.
Classe de pilha
As pilhas são criadas usando java.util.Stack. A pilha oferece métodos para colocar um novo objeto na pilha (método push ()) e obter objetos da pilha (método pop ()). Uma pilha retorna o objeto de acordo com o último a entrar, primeiro a sair (LIFO), por exemplo, o objeto que foi colocado por último na pilha é retornado primeiro. java.util.Stack é uma implementação padrão de uma pilha fornecida por Java. A classe Stack representa uma pilha de objetos último a entrar, primeiro a sair (LIFO). Ele estende a classe java.util.Vector com cinco operações que permitem que um vetor seja tratado como uma pilha. As operações usuais de push e pop são fornecidas, bem como um método para espiar o item superior da pilha, um método para testar se a pilha está vazia e um método para pesquisar um item na pilha e descobrir a que distância ele é do topo. Quando uma pilha é criada pela primeira vez, ela não contém itens.
Interfaces de fila
A interface java.util.Queue define a estrutura de dados da fila, que armazena os elementos na ordem em que são inseridos. Novas adições vão para o final da linha e os elementos são removidos da frente. Ele cria um sistema primeiro a entrar, primeiro a sair. Essa interface é implementada por java.util.LinkedList, java.util.ArrayDeque e java.util.PriorityQueue. LinkedList, é claro, também implementa a interface List e também pode ser usada como uma. Mas também possui os métodos Queue. ArrayDeque implementa a fila como um array. LinkedList e ArrayDeque também implementam a interface java.util.Deque, dando a ela mais flexibilidade.
java.util.Queue pode ser usado de forma mais flexível com sua subinterface, java.util.concurrent.BlockingQueue. A interface BlockingQueue funciona como uma fila normal, mas as adições e remoções da fila estão bloqueando. Se remove for chamado em uma fila vazia, ele pode ser configurado para aguardar um tempo especificado ou indefinidamente para que um item apareça na fila. Da mesma forma, adicionar um item está sujeito a uma restrição de capacidade opcional na fila e o método pode esperar que o espaço fique disponível na fila antes de retornar.
java.util.PriorityQueue implementa java.util.Queue, mas também o altera. Em vez de os elementos serem ordenados na ordem em que são inseridos, eles são ordenados por prioridade. O método usado para determinar a prioridade é o método compareTo () nos elementos ou um método fornecido no construtor. A classe cria isso usando um heap para manter os itens classificados.
Interfaces de fila dupla (deque)
A interface java.util.Queue é expandida pela subinterface java.util.Deque. Deque cria uma fila dupla. Enquanto uma fila normal só permite inserções na parte traseira e remoções na frente, o deque permite que as inserções ou remoções ocorram tanto na frente quanto atrás. Um deque é como uma fila que pode ser usada para frente ou para trás, ou ambos ao mesmo tempo. Além disso, tanto um iterador para frente quanto um para trás podem ser gerados. A interface Deque é implementada por java.util.ArrayDeque e java.util.LinkedList.
A interface java.util.concurrent.BlockingDeque funciona de maneira semelhante a java.util.concurrent.BlockingQueue. São fornecidos os mesmos métodos de inserção e remoção com limites de tempo para aguardar a inserção ou remoção. No entanto, a interface também oferece a flexibilidade de um deque. As inserções e remoções podem ocorrer em ambas as extremidades. A função de bloqueio é combinada com a função deque.
Definir interfaces
A interface java.util.Set do Java define o conjunto. Um conjunto não pode conter elementos duplicados. Além disso, o conjunto não tem uma ordem definida. Como tal, os elementos não podem ser encontrados por índice. Set é implementado por java.util.HashSet, java.util.LinkedHashSet e java.util.TreeSet. HashSet usa uma tabela de hash. Mais especificamente, ele usa um java.util.HashMap para armazenar os hashes e elementos e para evitar duplicatas. java.util.LinkedHashSet estende isso criando uma lista duplamente vinculada que vincula todos os elementos por sua ordem de inserção. Isso garante que a ordem de iteração no conjunto seja previsível. java.util.TreeSet usa uma árvore red – black implementada por um java.util.TreeMap. A árvore vermelho-preto garante que não haja duplicatas. Além disso, permite que TreeSet implemente java.util.SortedSet.
A interface java.util.Set é estendida pela interface java.util.SortedSet. Ao contrário de um conjunto regular, os elementos em um conjunto classificado são classificados, pelo método compareTo () do elemento ou por um método fornecido ao construtor do conjunto classificado. O primeiro e o último elemento do conjunto classificado podem ser recuperados e os subconjuntos podem ser criados por meio de valores mínimo e máximo, bem como no início ou no final do início ou no final do conjunto classificado. A interface SortedSet é implementada por java.util.TreeSet.
java.util.SortedSet é estendido ainda mais por meio da interface java.util.NavigableSet. É semelhante ao SortedSet, mas existem alguns métodos adicionais. Os métodos floor (), roof (), lower () e higher () localizam um elemento no conjunto que está próximo ao parâmetro. Além disso, é fornecido um iterador descendente sobre os itens do conjunto. Tal como acontece com SortedSet, java.util.TreeSet implementa NavigableSet.
Interfaces de mapa
Os mapas são definidos pela interface java.util.Map em Java. Mapas são estruturas de dados simples que associam uma chave a um elemento. Isso permite que o mapa seja muito flexível. Se a chave for o código hash do elemento, o mapa é essencialmente um conjunto. Se for apenas um número crescente, torna-se uma lista. Os mapas são implementados por java.util.HashMap, java.util.LinkedHashMap e java.util.TreeMap. HashMap usa uma tabela hash . Os hashes das chaves são usados para localizar os elementos em vários baldes. LinkedHashMap estende isso criando uma lista duplamente vinculada entre os elementos, permitindo que eles sejam acessados na ordem em que foram inseridos no mapa. TreeMap, em contraste com HashMap e LinkedHashMap, usa uma árvore vermelho-preto. As chaves são usadas como valores para os nós na árvore e os nós apontam para os elementos no mapa.
A interface java.util.Map é estendida por sua subinterface, java.util.SortedMap. Essa interface define um mapa que é classificado pelas chaves fornecidas. Usando, mais uma vez, o método compareTo () ou um método fornecido no construtor para o mapa classificado, os pares de elemento-chave são classificados pelas chaves. A primeira e a última chave do mapa podem ser chamadas. Além disso, os submapas podem ser criados a partir de chaves mínimas e máximas. SortedMap é implementado por java.util.TreeMap.
A interface java.util.NavigableMap estende java.util.SortedMap de várias maneiras. Os métodos podem ser chamados para encontrar a chave ou a entrada do mapa mais próxima da chave fornecida em qualquer direção. O mapa também pode ser revertido e um iterador na ordem reversa pode ser gerado a partir dele. É implementado por java.util.TreeMap.
Extensões para a estrutura de coleções Java
A estrutura de coleções Java é estendida pela biblioteca Apache Commons Collections, que adiciona tipos de coleção, como uma bolsa e mapa bidirecional, bem como utilitários para criar uniões e interseções.
O Google lançou suas próprias bibliotecas de coleções como parte das bibliotecas de goiaba .