Hashtables fornecem uma maneira útil de otimizar o desempenho do aplicativo.
Hashtables não são um conceito novo na área de informática. Eles foram projetados para acelerar o processamento do computador, que é muito lento para os padrões atuais, e permitem que você encontre rapidamente uma entrada específica ao consultar muitas entradas de dados. Embora as máquinas modernas sejam milhares de vezes mais rápidas, as tabelas hash ainda são uma ferramenta útil para obter o melhor desempenho de seus aplicativos.
Imagine que você tem um arquivo de dados contendo cerca de mil registros – digamos, registros de clientes de uma pequena empresa – e um programa que lê os registros na memória para processamento. Cada registro contém um número de identificação do cliente exclusivo de cinco dígitos, nome do cliente, endereço, saldo da conta, etc. Suponha que os registros não sejam classificados por número de identificação do cliente. Portanto, se o programa quiser usar o número do cliente como "chave" para localizar um registro de cliente específico, a única maneira de encontrá-lo é pesquisar cada registro consecutivamente. Às vezes, ele encontrará o registro que você precisa rapidamente, mas às vezes, antes de o programa encontrar o registro que você precisa, ele quase procurou o último registro. Se você quiser pesquisar entre 1.000 registros, encontrar qualquer registro exigirá que o programa verifique uma média de 500,5 ((1.000 + 1)/2) registros. Se você precisa pesquisar dados com frequência, talvez precise de uma maneira mais rápida de localizar um registro.
Uma maneira de acelerar sua pesquisa é dividir os registros em partes para que, em vez de pesquisar em uma lista grande, você pesquise em várias listas curtas. Para nossos números numéricos de identificação de cliente, você pode criar 10 listas: uma lista para números de identificação começando com 0, uma lista para números de identificação começando com 1 e assim por diante. Portanto, para encontrar o número de identificação do cliente 38016, você só precisa pesquisar na lista que começa com 3. Se houver 1.000 registros e o comprimento médio de cada lista for 100 (1.000 registros divididos em 10 listas), o número médio de comparações para procurar um registro cai para cerca de 50 (veja a Figura 1).
É claro que se cerca de um em cada dez números de clientes começar com 0, outro décimo começar com 1 e assim por diante, então essa abordagem funcionaria bem. Se 90% dos números de clientes começassem com 0, então essa lista teria 900 registros, exigindo uma média de 450 comparações por pesquisa. Além disso, 90% das pesquisas que o programa precisa realizar são para números que começam com 0. Portanto, o número médio de comparação está muito além do escopo de simples operações matemáticas.
Seria melhor se pudéssemos distribuir os registros em nossas listas de tal forma que cada lista tivesse aproximadamente as mesmas entradas, independentemente da distribuição dos números nos valores-chave. Precisamos de uma maneira de combinar o número de clientes e distribuir melhor os resultados. Por exemplo, poderíamos pegar cada dígito do número, multiplicá-lo por algum número grande (que varia dependendo da posição do dígito), somar os resultados para produzir um total, dividir esse número por 10 e fornecer o restante como índice valor (índice). Quando um registro é lido, o programa executa esta função hash no número do cliente para determinar a qual lista o registro pertence. Quando o usuário precisa fazer uma consulta, a mesma função hash é usada como “chave” para o número do cliente para que a lista correta possa ser pesquisada. Uma estrutura de dados como essa é chamada de hashtable.
Tabelas hash em Java
Java contém duas classes, java.util.Hashtable e java.util.HashMap , que fornecem um mecanismo hashtable multifuncional. As duas classes são muito semelhantes e geralmente fornecem a mesma interface pública. Mas eles têm algumas diferenças importantes, das quais falarei mais tarde.
Os objetos Hashtable e HashMap permitem combinar uma chave e um valor e inserir o par chave/valor na tabela usando o método put (). Você pode então obter o valor chamando o método get(), passando a chave como parâmetro. Chave e valor podem ser quaisquer objetos, desde que atendam a dois requisitos básicos. Observe que como chaves e valores devem ser objetos, os tipos primitivos devem ser convertidos em objetos usando métodos como Integer(int).
Para usar um objeto de uma classe específica como chave, a classe deve fornecer dois métodos, equals() e hashCode(). Esses dois métodos estão em java.lang.Object , portanto, todas as classes podem herdar esses dois métodos; no entanto, a implementação desses dois métodos na classe Object geralmente é inútil;
O método Equals() compara seu objeto com outro objeto e retorna verdadeiro se os dois objetos representarem a mesma informação. Este método também procura garantir que ambos os objetos pertençam à mesma classe. Object.equals() retorna verdadeiro se os dois objetos de referência forem objetos idênticos, o que explica por que esse método geralmente não é adequado. Na maioria dos casos, você precisa comparar campo por campo, por isso consideramos objetos diferentes que representam os mesmos dados como iguais.
O método HashCode() gera um valor int executando uma função hash usando o conteúdo do objeto. Hashtable e HashMap usam esse valor para descobrir em qual bucket (ou lista) um par chave/valor está.
Como exemplo, podemos olhar a classe String, pois ela possui métodos próprios que implementam esses dois métodos. String.equals() compara dois objetos String caractere por caractere e retorna verdadeiro se as strings forem iguais:
Copie o código do código da seguinte forma:
String meuNome = "Einstein";
//O seguinte teste é
// sempre verdadeiro
if (meuNome.equals("Einstein") )
{...
String.hashCode() executa uma função hash em uma string. O código numérico de cada caractere da string é multiplicado por 31 e o resultado depende da posição do caractere na string. Os resultados desses cálculos são então somados para dar um total. Esse processo pode parecer complicado, mas garante uma melhor distribuição de valores. Ele também demonstra até onde você pode ir ao desenvolver seu próprio método hashCode(), confiante de que o resultado é único.
Por exemplo, suponha que eu queira usar uma tabela hash para implementar um catálogo de livros e usar o número ISBN do livro como chave de pesquisa para pesquisar. Posso usar a classe String para transportar os detalhes e ter os métodos equals() e hashCode() prontos (veja a Listagem 1). Podemos adicionar pares chave/valor à tabela hash usando o método put () (veja a Listagem 2).
O método Put () aceita dois parâmetros, ambos do tipo Object. O primeiro parâmetro é chave; o segundo parâmetro é valor. O método Put () chama o método hashCode() da chave e divide o resultado pelo número de listas na tabela. Use o restante como um valor de índice para determinar a qual lista o registro será adicionado. Observe que a chave é única na tabela; se você chamar put () com uma chave existente, a entrada correspondente será modificada para que se refira a um novo valor e o valor antigo será retornado (quando a chave não existir na tabela). , put () retorna um valor nulo).
Para ler um valor da tabela, usamos a chave de pesquisa com o método get(). Ele retorna uma referência de objeto convertida para o tipo correto:
Copie o código do código da seguinte forma:
LivroRecord br =
(BookRecord)isbnTable.get(
“0-345-40946-9”);
Sistema.out.println(
"Autor: " + br.autor
+ "Título: " + br.título);
Outro método útil é remove(), que é usado quase da mesma forma que get(). Ele remove a entrada da tabela e a retorna ao programa de chamada.
sua própria aula
Se quiser usar um tipo primitivo como chave, você deve criar um objeto do mesmo tipo. Por exemplo, se você quiser usar uma chave inteira, você deve usar o construtor Integer(int) para gerar um objeto a partir de um inteiro. Todas as classes wrapper, como Integer, Float e Boolean, tratam valores primitivos como objetos e sobrecarregam os métodos equals() e hashCode(), para que possam ser usados como chaves. Muitas outras classes fornecidas no JDK são assim (até mesmo as classes Hashtable e HashMap implementam seus próprios métodos equals() e hashCode()), mas você deve verificar a documentação antes de usar objetos de qualquer classe como chaves hashtable. Também é necessário verificar a fonte da classe para ver como equals() e hashCode() são implementados. Por exemplo, Byte, Character, Short e Integer retornam o valor inteiro representado como um código hash. Isso pode ou não atender às suas necessidades.
Usando tabelas hash em Java
Se você deseja criar uma tabela hash que use objetos de uma classe definida como chaves, certifique-se de que os métodos equals() e hashCode() dessa classe forneçam valores úteis. Primeiro observe a classe que você estende para determinar se sua implementação atende às suas necessidades. Caso contrário, você deve sobrecarregar o método.
A restrição básica de design de qualquer método equals() é que ele deve retornar verdadeiro se o objeto passado para ele pertencer à mesma classe e seus campos de dados forem definidos com valores que representam os mesmos dados. Você também deve certificar-se de que, se passar um argumento vazio para o método, seu código retorne
Copie o código do código da seguinte forma:
falso: booleano público igual a (Objeto o)
{
if ((o == nulo)
|| !(ou instância da minhaClasse))
{
retornar falso;
}
// Agora compare os campos de dados...
Além disso, existem algumas regras que você deve ter em mente ao projetar um método hashCode(). Primeiro, o método deve retornar o mesmo valor para um objeto específico, independentemente de quantas vezes o método é chamado (é claro, desde que o conteúdo do objeto não mude entre as chamadas. Ao usar um objeto como chave de tabela hash, isso deve ser evitado). Segundo, se dois objetos definidos pelo seu método equals() forem iguais, eles também deverão gerar o mesmo código hash. Terceiro, e isso é mais uma diretriz do que um princípio, você deve tentar projetar seu método de modo que ele produza resultados diferentes para diferentes conteúdos de objetos. Não importa se ocasionalmente objetos diferentes geram o mesmo código hash. No entanto, se o método só puder retornar valores no intervalo de 1 a 10, então apenas 10 listas poderão ser usadas, independentemente de quantas listas estejam na tabela hash.
Outro fator a ter em mente ao projetar equals() e hashCode() é o desempenho. Cada chamada para put () ou get() envolve chamar hashCode() para encontrar a lista correta. Quando get() verifica a lista para encontrar a chave, ele chama equals() para cada elemento da lista. Implemente esses métodos para que eles sejam executados da maneira mais rápida e eficiente possível, especialmente se você planeja disponibilizar sua classe publicamente, porque outros usuários podem querer usar sua classe em um aplicativo de alto desempenho onde a velocidade de execução é importante.
Desempenho da tabela hash
O principal fator que afeta a eficiência da hashtable é o comprimento médio das listas na tabela, pois o tempo médio de pesquisa está diretamente relacionado a esse comprimento médio. Obviamente, para reduzir o comprimento médio, é necessário aumentar o número de listas na tabela hash. Você obterá a melhor eficiência de pesquisa se o número de listas for tão grande que a maioria ou todas as listas contenham apenas um registro; No entanto, isso pode estar indo longe demais. Se a sua tabela hash tiver muito mais listas do que entradas de dados, não há necessidade de fazer esse custo de memória e, em alguns casos, é impossível que as pessoas aceitem essa abordagem.
No nosso exemplo anterior, sabíamos antecipadamente quantos registros tínhamos, 1.000. Sabendo disso, podemos decidir quantas listas nossa tabela hash deve conter para alcançar o melhor compromisso entre velocidade de pesquisa e eficiência de uso de memória. No entanto, em muitos casos, você não sabe antecipadamente quantos registros serão processados; o arquivo do qual os dados são lidos pode crescer continuamente ou o número de registros pode mudar significativamente de um dia para o outro.
As classes Hashtable e HashMap resolvem esse problema estendendo dinamicamente a tabela à medida que as entradas são adicionadas. Ambas as classes possuem construtores que aceitam o número inicial de listas na tabela e um fator de carga como parâmetro:
tabela de hash pública (
int capacidade inicial,
fator de carga flutuante)
HashMap público (
int capacidade inicial,
fator de carga flutuante)
Multiplique esses dois números para calcular um valor crítico. Cada vez que uma nova entrada é adicionada à tabela hash, a contagem é atualizada e, quando a contagem excede um valor crítico, a tabela é redefinida (rehash). (O tamanho da lista é aumentado para duas vezes o tamanho anterior mais 1, e todas as entradas são movidas para a lista correta.) O construtor padrão define a capacidade inicial como 11 e o fator de carga como 0,75, portanto, o valor crítico é 8. Quando o nono registro é adicionado à tabela, a tabela hash é redimensionada para ter 23 listas e o novo valor crítico será 17 (a parte inteira de 23*0,75). Você pode ver que o fator de carga é um limite superior no número médio de listas em uma tabela hash, o que significa que, por padrão, uma tabela hash raramente tem muitas listas contendo mais de um registro. Compare nosso exemplo original, onde tínhamos 1.000 registros espalhados por 10 listas. Se usarmos os valores padrão, esta tabela será expandida para conter mais de 1.500 listas. Mas você pode controlar isso. Se o número de listas multiplicado pelo fator de carga for maior que o número de entradas que você está processando, a tabela nunca será refeita, portanto podemos seguir o exemplo abaixo:
Copie o código do código da seguinte forma:
// A tabela não será refeita até que seja
// tem 1.100 entradas (10*110):
Tabela de hash minhaHashTable =
nova tabela de hash (10, 110,0F);
Você provavelmente não deseja fazer isso, a menos que não queira economizar memória para listas vazias e não se importe com o tempo extra de pesquisa, o que pode ser o caso em sistemas embarcados. No entanto, esta abordagem pode ser útil porque a reinicialização é computacionalmente cara e garante que a reinicialização nunca ocorra.
Observe que embora chamar put () possa fazer com que a tabela cresça (aumentar o número de listas), chamar remove() não terá o efeito oposto. Portanto, se você tiver uma tabela grande e excluir a maioria das entradas dela, acabará com uma tabela grande, mas quase toda vazia.
Hashtable e HashMap
Existem três diferenças importantes entre as classes Hashtable e HashMap. A primeira diferença é principalmente por razões históricas. Hashtable é baseado na antiga classe Dictionary e HashMap é uma implementação da interface Map introduzida em Java 1.2.
Talvez a diferença mais importante seja que os métodos do Hashtable são síncronos, enquanto os métodos do HashMap não são. Isso significa que, embora você possa usar um Hashtable em um aplicativo multithread sem realizar nenhuma ação especial, você deve fornecer sincronização externa para um HashMap da mesma forma. Um método conveniente é usar o método estáticosyncedMap() da classe Collections, que cria um objeto Map thread-safe e o retorna como um objeto encapsulado. Os métodos deste objeto permitem acessar o HashMap subjacente de forma síncrona. O resultado disso é que você não pode interromper a sincronização no Hashtable quando não precisa dela (como em um aplicativo de thread único), e a sincronização adiciona muita sobrecarga de processamento.
A terceira diferença é que apenas o HashMap permite usar valores nulos como chave ou valor de uma entrada da tabela. Apenas um registro em um HashMap pode ser uma chave vazia, mas qualquer número de entradas pode ser um valor vazio. Isso significa que se a chave de pesquisa não for encontrada na tabela, ou se a chave de pesquisa for encontrada, mas for um valor nulo, então get() retornará nulo. Se necessário, use o método containerKey() para distinguir entre as duas situações.
Algumas informações sugerem que quando a sincronização for necessária, use Hashtable, caso contrário, use HashMap. No entanto, como o HashMap pode ser sincronizado quando necessário, o HashMap tem mais funções do que o Hashtable e não é baseado em uma classe antiga, algumas pessoas pensam que o HashMap é preferido ao Hashtable em várias situações.
Sobre propriedades
Às vezes, você pode querer usar uma tabela hash para mapear strings de chave para strings de valor. Existem alguns exemplos de strings de ambiente em DOS, Windows e Unix. Por exemplo, a string de chave PATH é mapeada para a string de valor C:/WINDOWS;C:/WINDOWS/SYSTEM. Hashtables são uma maneira simples de representá-los, mas Java oferece outra maneira.
A classe Java .util.Properties é uma subclasse de Hashtable projetada para uso com chaves e valores String. O uso do objeto Properties é semelhante ao uso do Hashtable, mas a classe adiciona dois métodos que economizam tempo que você deve conhecer.
O método Store() salva o conteúdo de um objeto Properties em um arquivo em um formato legível. O método Load() é exatamente o oposto, usado para ler o arquivo e definir o objeto Properties para conter chaves e valores.
Observe que, como Properties estende Hashtable, você pode usar o método put () da superclasse para adicionar chaves e valores que não são objetos String. Isto não é aconselhável. Além disso, se você usar store() com um objeto Properties que não contém um objeto String, store() falhará. Como alternativa para put () e get(), você deve usar setProperty() e getProperty(), que usam parâmetros String.
Ok, espero que agora você saiba como usar hashtables para acelerar seu processamento