get
dans put
HashMap ? Ici, je vais essayer d'expliquer la fonctionnalité interne à l'aide d'un exemple simple. Sans entrer trop dans la théorie, nous commencerons par un exemple afin que vous puissiez mieux comprendre puis voir comment fonctionnent les méthodes en Java get
également . put
Prenons un exemple très simple. Nous avons une classe Country
(« country ») en anglais, nous utiliserons l'objet classe Country
comme clé, et le nom de la capitale de ce pays comme valeur. Vous trouverez ci-dessous un exemple pour nous aider à comprendre comment une paire clé-valeur sera stockée dans une carte de hachage.
1. Pays.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;
}
}
Si vous souhaitez comprendre et en savoir plus sur les méthodes hashcode
et les égaux, vous pouvez suivre ce lien .
2. HashMapStructure.java (classe principale)
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);
}
}
}
Maintenant, définissez le point d'arrêt sur la ligne 23 et exécutez run -> debug as-> java application (note du traducteur - valable pour Eclipse). Le programme arrêtera l'exécution à la ligne 23, après quoi faites un clic droit sur countryCapitalMap et sélectionnez watch . Vous verrez un tableau comme celui-ci : Ici, nous voyons ce qui suit :
-
Il existe un tableau
Entry[]
de 16 cellules nommétable
; -
Ce tableau stocke les objets de la classe
Entry
. La classeHashMap
a une classe interne -Entry
. Et les instances de cette classe sont des paires clé-valeur. Jetons un coup d'oeil à la structure des classesEntry
: -
Chaque fois que nous essayons de créer une paire clé-valeur dans une carte de hachage, un objet de classe sera créé pour cette paire
Entry
et il sera stocké dans le tableau ci-dessusEntry[]
. Et maintenant, vous devriez vous demander où exactement dans ce tableau cet objet sera écrit (dans quelle cellule). Pour une clé dans une paire clé-valeur, un code de hachage est calculé à l'aide duhashcode()
. Et ce code de hachage est utilisé pour calculer le numéro de cellule du tableauEntry[]
; -
Maintenant, si vous regardez la cellule 10 du tableau, vous verrez un objet de classe
Entry
nomméHashMap$Entry
; - Nous avons ajouté 4 paires clé-valeur, mais il n'y en a que 2 dans le tableau !!! En effet, si 2 objets ont le même code de hachage, ils seront alors stockés dans la même cellule. Mais comment? Les objets seront stockés sous forme de liste chaînée (
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 имеет четное количество букв.
La figure suivante expliquera l'idée d'une liste chaînée : Maintenant que vous avez déjà une compréhension de la structure des cartes de hachage, passons aux méthodes put
et get
.
Mettre:
Voyons comment cette méthode est utilisée :/**
* Метод связывает указанное 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;
}
Essayons maintenant de comprendre ce code étape par étape :
-
Nous vérifions l'
key
égalité de l'objetnull
. Si tel est le cas, l'objetkey
sera stocké dans l'emplacementtable[0]
car le code de hachagenull
est toujours 0 ; -
Ensuite, nous appelons la
key
méthode de l’objethashcode()
, qui calculera son code de hachage. Ce code de hachage est utilisé pour déterminer la cellule du tableau où l'objet de classe sera stockéEntry
. Parfois, il arrive que cette fonctionhashcode
ne soit pas écrite de manière très habile, c'est pourquoi les développeurs du JDK ont créé une fonction différente -hash()
, qui prend le code de hachage précédemment calculé comme argument. Si vous souhaitez en savoir plus sur cette fonction, vous pouvez suivre le lien ; -
indexFor(hash,table.length)
utilisé pour définir une cellule spécifique dans le tableautable
dans laquelle un objet de classe sera défini pour être stockéEntry
; -
Comme nous l'avons vu dans notre exemple, si deux objets
key
ont le même code de hachage (cette situation est appelée collision), alors ils seront stockés sous la forme d'une liste chaînée. Par conséquent, à ce stade, nous réitérons notre liste : -
si la cellule nouvellement calculée est vide, alors l'objet de classe
Entry
sera enregistré directement dans cette cellule ; -
si cette cellule contient déjà un objet, alors itère jusqu'à l'élément dont le champ est
next
égal ànull
. Après cela, notre objet de classeEntry
devient le prochain dans la liste ; -
et si nous ajoutions
key
à nouveau le même objet ? Logiquement, elle devrait remplacer l'ancienne valeur. Oui, il en sera ainsi. Lors de l'itération, les clés seront comparées en utilisant la méthodeequals()
(key.equals(k)
). Si le résultat est vrai, alors l'ancienne valeur sera remplacée par la valeur de l'objet actuelEntry
.
Obtenir:
Voyons maintenant l'application de la méthode/**
* 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;
}
Maintenant que vous comprenez le fonctionnement de la méthode put dans les hashmaps, comprendre comment fonctionne la méthode put est
get
très simple. Lorsque vous transmettez une clé à une méthode pour obtenir une valeur à partir d'une carte de hachage :
-
Un objet
Ekey est testé pour l'égalité null
. Si tel est le cas, alors la valeur de l'objet stocké dans la cellule sera renvoyéetable[0]
; -
L'objet clé possède une méthode appelée
hashcode()
qui calcule le code de hachage ; -
indexFor(hash,table.length)
utilisé pour déterminer une cellule de tableau spécifiquetable
à partir de laquelle prendre un objet de classeEntry
; -
Après avoir reçu le numéro de cellule du tableau,
table
il parcourra la liste et comparera les clés en utilisant la méthodeequals()
. Si le résultat est vrai, alors la valeur de l'objet sera renvoyéeEntry
, sinon -null
.
Choses dont il faut se rappeler:
-
La classe
HashMap
possède une classe interneEntry
qui stocke les paires clé-valeur ; -
Les objets de la classe
Entry
sont stockés dans un tableauEntry[ ]
appelétable
; -
Une cellule de tableau est appelée compartiment et stocke le premier élément d’une liste chaînée ;
-
La méthode
hashcode()
objetkey
est utilisée pour trouver le bucket de cet objet de classeEntry
; -
Si les clés de deux objets ont le même code de hachage, elles seront stockées dans le même bucket de tableau
table
; -
La méthode
equals()
d'un objetkey
est utilisée pour confirmer son unicité ; -
Les méthodes
equals()
ethashcode()
les objetsvalue
ne sont pas du tout utilisés.
GO TO FULL VERSION