get
no put
HashMap?”. Aqui tentarei explicar a funcionalidade interna usando um exemplo simples. Sem entrar muito na teoria, começaremos com um exemplo para que você possa entender melhor e depois ver como funcionam os métodos get
também put
em Java . Vamos dar um exemplo muito simples. Temos uma classe Country
(“país” em inglês), usaremos o objeto de classe Country
como chave e o nome da capital deste país como valor. Abaixo está um exemplo para nos ajudar a entender como um par de valores-chave será armazenado em um mapa hash.
1. País.java
package org.arpit.javapostsforlearning;
public class Country {
String name;
long population;
public Country(String name, long population) {
super();
this.name = name;
this.population = population;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public long getPopulation() {
return population;
}
public void setPopulation(long population) {
this.population = population;
}
// если длина имени в an objectе Country - четное число,
// то возвращаем 31(любое случайное число), а если нечетное - 95 (любое случайное число).
// указанный ниже метод - это не самый лучший способ генерации хеш-codeа,
// но мы воспользуемся им для более четкого понимания хеш-карт.
@Override
public int hashCode() {
if(this.name.length()%2==0)
return 31;
else
return 95;
}
@Override
public boolean equals(Object obj) {
Country other = (Country) obj;
if (name.equalsIgnoreCase((other.name)))
return true;
return false;
}
}
Se você quiser entender e aprender mais sobre métodos hashcode
e iguais, você pode seguir este link .
2. HashMapStructure.java (classe principal)
import java.util.HashMap;
import java.util.Iterator;
public class HashMapStructure {
/**
* @author Arpit Mandliya
*/
public static void main(String[] args) {
Country india=new Country("India",1000);
Country japan=new Country("Japan",10000);
Country france=new Country("France",2000);
Country russia=new Country("Russia",20000);
HashMap<country,string> countryCapitalMap=new HashMap<country,string>();
countryCapitalMap.put(india,"Delhi");
countryCapitalMap.put(japan,"Tokyo");
countryCapitalMap.put(france,"Paris");
countryCapitalMap.put(russia,"Moscow");
Iterator<country> countryCapitalIter=countryCapitalMap.keySet().iterator();//установите
//debug-точку на этой строке(23)
while(countryCapitalIter.hasNext())
{
Country countryObj=countryCapitalIter.next();
String capital=countryCapitalMap.get(countryObj);
System.out.println(countryObj.getName()+"----"+capital);
}
}
}
Agora defina o ponto de interrupção para a linha 23 e execute run -> debug as-> java application (nota do tradutor - válida para Eclipse). O programa irá parar a execução na linha 23, após isso clique com o botão direito em countryCapitalMap e selecione watch . Você verá uma tabela como esta: Aqui vemos o seguinte:
-
Existe uma matriz
Entry[]
de 16 células chamadatable
; -
Este array armazena objetos da classe
Entry
. A classeHashMap
tem uma classe interna -Entry
. E as instâncias desta classe são pares de valores-chave. Vamos dar uma olhada na estrutura da classeEntry
: -
Cada vez que tentamos criar um par chave-valor em um mapa hash, um objeto de classe será criado para esse par
Entry
e será armazenado na tabela acimaEntry[]
. E agora você deve estar se perguntando onde exatamente nesta tabela esse objeto será escrito (em qual célula). Para uma chave em um par de valores-chave, um código hash é calculado usando o métodohashcode()
. E esse código hash é usado para calcular o número da célula da tabelaEntry[]
; -
Agora, se você olhar para a célula 10 da tabela, verá um objeto de classe
Entry
chamadoHashMap$Entry
; - Adicionamos 4 pares de valores-chave, mas existem apenas 2 no array!!! Isso ocorre porque se 2 objetos tiverem o mesmo código hash, eles serão armazenados na mesma célula. Mas como? Os objetos serão armazenados como uma lista vinculada (
LinkedList
).
static class Entry implements Map.Entry
{
final K key;
V value;
Entry next;
final int hash;
...//продолжение codeа
}
Hashcode for Japan = 95 так How длина слова Japan имеет нечетное количество букв.
Hashcode for India = 95 так How длина слова India имеет нечетное количество букв.
HashCode for Russia = 31 так How длина слова Russia имеет четное количество букв.
HashCode for France = 31 так How длина слова France имеет четное количество букв.
A figura a seguir explicará a ideia de uma lista encadeada: Agora que você já entende a estrutura dos mapas hash, vamos passar para os métodos put
e get
.
Colocar:
Vamos ver como esse método é usado:/**
* Метод связывает указанное meaning с указанным ключом в данной хэш-карте. Если
* карта до этого уже содержала некоторое meaning, соответствующее этому ключу,
* то старое meaning заменяется на указанное.
* @param key
* ключ, с которым связывается указанное meaning
* @param value
* meaning, связываемое с указанным ключом
* @возвращает meaning связанное с <tt>ключом</tt>, or <tt>null</tt>,
* если ниHowое meaning не соответствует <tt>ключу</tt>. ( Возврат <tt>null</tt>
* может так же говорить о том, что в карте заведомо <tt>null</tt> был связан с
* <tt>ключом</tt>.)
*/
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<k , V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
Agora vamos tentar entender esse código passo a passo:
-
Verificamos a
key
igualdade do objetonull
. Nesse caso, o objetokey
será armazenado no localtable[0]
porque o código hashnull
é sempre 0; -
A seguir, chamamos o
key
método do objetohashcode()
, que calculará seu código hash. Este código hash é usado para determinar a célula do array onde o objeto da classe será armazenadoEntry
. Às vezes acontece que esta funçãohashcode
não é escrita com muita habilidade, então os desenvolvedores do JDK criaram uma função diferente -hash()
, que usa o código hash calculado anteriormente como argumento. Se você estiver interessado em ler mais detalhadamente sobre esta função, pode seguir o link ; -
indexFor(hash,table.length)
usado para definir uma célula específica no arraytable
na qual um objeto de classe será definido para ser armazenadoEntry
; -
Como vimos em nosso exemplo, se dois objetos
key
tiverem o mesmo código hash (esta situação é conhecida como colisão), então eles serão armazenados na forma de uma lista encadeada. Portanto, nesta fase, iteramos nossa lista: -
se a célula recém-calculada estiver vazia, o objeto de classe
Entry
será salvo diretamente nesta célula; -
se esta célula já contém algum objeto, então itera para o elemento cujo campo é
next
igual anull
. Depois disso, nosso objeto de classeEntry
passa a ser o próximo na lista; -
e se adicionarmos o mesmo objeto
key
novamente? Logicamente, deveria substituir o valor antigo. Sim, será assim. Durante a iteração, as chaves serão comparadas usando o métodoequals()
(key.equals(k)
). Se o resultado for verdadeiro, o valor antigo será substituído pelo valor do objeto atualEntry
.
Pegar:
Agora vamos dar uma olhada na aplicação do método/**
* returns meaning, которое соответствует указанному ключу, or {@code null}, если
* данная карта не содержит пары с указанным ключом.
*
*
* <p>
* Более точно, если в данной карте содержится такой ключ {@code k}
* с соответствующим ему meaningм {@code v}, что {@code (key==null ? k==null : key.equals(k))},
* то метод возвращает {@code v}; в противном случае возвращается {@code null}.
* (может быть не более одной такой пары)
*
* </p><p>
* Возвращенное meaning {@code null} не <i>обязательно</i> говорит о том, что
* в карте нет пары с таким указанным ключом; а возможно, что в карте однозначно
* указано соответствие этого ключа со meaningм {@code null}.
* Можно воспользоваться операцией {@link #containsKey containsKey}, чтобы
* отличить эти два случая
* @see #put(Object, Object)
*/
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry<k , V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}
Agora que você entende como o método put funciona em hashmaps, entender como o método put funciona é
get
muito simples. Quando você passa qualquer chave para um método para obter um valor de um mapa hash:
-
Um objeto
Ekey é testado quanto à igualdade null
. Nesse caso, será retornado o valor do objeto armazenado na célulatable[0]
; -
O objeto chave possui um método chamado
hashcode()
que calcula o código hash; -
indexFor(hash,table.length)
usado para determinar uma célula específica da matriztable
da qual obter um objeto de classeEntry
; -
Depois de receber o número da célula da matriz,
table
ele percorrerá a lista e comparará as chaves usando o métodoequals()
. Se o resultado for verdadeiro, então o valor do objeto será retornadoEntry
, caso contrário -null
.
Coisas para lembrar:
-
A classe
HashMap
possui uma classe internaEntry
que armazena pares de valores-chave; -
Os objetos da classe
Entry
são armazenados em um arrayEntry[ ]
chamadotable
; -
Uma célula de array é chamada de bucket e armazena o primeiro elemento de uma lista vinculada;
-
O método
hashcode()
objectkey
é usado para encontrar o bucket deste objeto de classeEntry
; -
Se as chaves de dois objetos tiverem o mesmo código hash, elas serão armazenadas no mesmo bucket do array
table
; -
O método
equals()
de um objetokey
é usado para confirmar sua singularidade; -
Métodos
equals()
ehashcode()
objetosvalue
não são usados.
GO TO FULL VERSION