get
in put
HashMap?”. Here I will try to explain the internal functionality using a simple example. Without going into too much theory, we will start with an example so that you can better understand and then see how methods work in Java get
as well . put
Let's take a very simple example. We have a class Country
(English “country”), we will use the class object Country
as the key, and the name of the capital of this country as the value. Below is an example to help us understand how a key-value pair will be stored in a hash map.
1. Country.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;
}
}
If you want to understand and learn more about methods hashcode
and equals, you can follow this link .
2. HashMapStructure.java(main class)
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);
}
}
}
Now set the breakpoint to line 23 and run run -> debug as-> java application (translator's note - valid for Eclipse). The program will stop execution on line 23, after which right-click on countryCapitalMap and select watch . You will see a table like this: Here we see the following:
-
There is an array
Entry[]
of 16 cells namedtable
; -
This array stores objects of the class
Entry
. The classHashMap
has an inner class -Entry
. And instances of this class are key-value pairs. Let's take a look at the class structureEntry
: -
Every time we try to create a key-value pair in a hash map, a class object will be created for that pair
Entry
and it will be stored in the above tableEntry[]
. And now you should be wondering where exactly in this table this object will be written (in which cell). For a key in a key-value pair, a hash code is calculated using thehashcode()
. And this hash code is used to calculate the table cell numberEntry[]
; -
Now if you look at cell 10 of the table, you will see a class object
Entry
namedHashMap$Entry
; - We added 4 key-value pairs, but there are only 2 in the array!!! This is because if 2 objects have the same hash code, then they will be stored in the same cell. But how? Objects will be stored as a linked list (
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 имеет четное количество букв.
The following figure will explain the idea of a linked list: Now that you already have an understanding about the structure of hash maps, let's move on to the put
and methods get
.
Put:
Let's see how this method is used:/**
* Метод связывает указанное 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;
}
Now let's try to understand this code step by step:
-
We check the object
key
for equalitynull
. If so, then the objectkey
will be stored in locationtable[0]
because the hash code fornull
is always 0; -
Next, we call the object’s
key
methodhashcode()
, which will calculate its hash code. This hash code is used to determine the array cell where the class object will be storedEntry
. Sometimes it happens that this functionhashcode
is not written very skillfully, so the JDK developers created a different function -hash()
, which takes the previously calculated hash code as an argument. If you are interested in reading about this function in more detail, you can follow the link ; -
indexFor(hash,table.length)
used to define a specific cell in the arraytable
in which a class object will be defined to be storedEntry
; -
As we saw in our example, if two objects
key
have the same hash code (this situation is known as a collision), then they will be stored in the form of a linked list. Therefore, at this stage we iterate our list: -
if the newly calculated cell is empty, then the class object
Entry
will be saved directly into this cell; -
if this cell already contains some object, then iterates to the element whose field is
next
equal tonull
. After this, our class objectEntry
becomes next in the list; -
what if we add the same object
key
again? Logically, it should replace the old value. Yes, it will be so. During the iteration, the keys will be compared using theequals()
(key.equals(k)
) method. If the result is true, then the old value will be replaced with the value of the current objectEntry
.
Get:
Now let's take a look at the application of the method/**
* 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;
}
Now that you have an understanding of how the put method works in hashmaps, understanding how the put method works is
get
very simple. When you pass any key to a method to get a value from a hash map:
-
An object
Ekey is tested for equality null
. If so, then the value of the object stored in the cell will be returnedtable[0]
; -
The key object has a method called
hashcode()
that calculates the hash code; -
indexFor(hash,table.length)
used to determine a specific array celltable
from which to take a class objectEntry
; -
After receiving the array cell number,
table
it will iterate through the list and compare the keys using the methodequals()
. If the result is true, then the value of the object will be returnedEntry
, otherwise -null
.
Things to remember:
-
The class
HashMap
has an inner classEntry
that stores key-value pairs; -
Objects of the class
Entry
are stored in an arrayEntry[ ]
calledtable
; -
An array cell is called a bucket and stores the first element of a linked list;
-
hashcode()
The object methodkey
is used to find the bucket of this class objectEntry
; -
If two objects' keys have the same hash code, they will be stored in the same array bucket
table
; -
equals()
An object's methodkey
is used to confirm its uniqueness; -
Methods
equals()
andhashcode()
objectsvalue
are not used at all.
GO TO FULL VERSION