最常见的面试问题是HashMap在java中的工作原理 ,“ HashMap的get和put方法是如何在内部工作的”。在这里,我试图用一个简单的例子来解释内部功能。 HashMap 是java中最常用的Collection之一。我们将先从例子开始,而不是通过理论,以便您更好地理解,然后我们将看到get()和put()函数在java中是如何工作的。
让我们举一个非常简单的例子。我有一个 Country 类,我们将使用 Country 类对象作为键,并将其 大写名称 (字符串)作为值。下面的示例将帮助您理解,这些键值对将如何存储在 hashmap 中。
1.Country.java
package org.arpit.java2blog;
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;
}
// If length of name in country object is even then return 31(any random number) and if odd then return 95(any random number).
// This is not a good practice to generate hashcode as below method but I am doing so to give better and easy understanding of hashmap.
@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;
}
}
2. HashMapStructure.java (主班)
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 countryCapitalIter=countryCapitalMap.keySet().iterator();//put debug point at this line
while(countryCapitalIter.hasNext())
{
Country countryObj=countryCapitalIter.next();
String capital=countryCapitalMap.get(countryObj);
System.out.println(countryObj.getName()+"----"+capital);
}
}
}
现在将调试点放在第 24 行,然后右键单击 project->debug as-> java application。程序将在第 24 行停止执行,然后右键单击 countryCapitalMap 然后选择 watch。您将能够看到如下结构。
现在从上图中,您可以观察到以下几点
-
-
有一个 名为 table 的Entry [ ] 数组,大小为 16。
-
该表存储Entry 类的对象。HashMap 类有一个名为 Entry的内部类 。此条目具有键值作为实例变量。让我们看看入口类Entry Structure的结构。
static class Entry implements Map.Entry
{
final K key;
V value;
Entry next;
final int hash;
...//More code goes here
}
-
每当我们尝试将任何键值对放入 hashmap 时,Entry 类对象都会被实例化为键值,并且该对象将存储在上面提到的 Entry [ ](表)中。现在您一定想知道,上面创建的 Entry 对象将存储在哪里(在表中的确切位置)。答案是,通过调用 Hascode() 方法为键计算哈希码。此哈希码用于计算上述 Entry[] 表的索引。
-
现在,如果您在上图中的数组索引 10 处看到,它有一个名为 HashMap $ Entry的 Entry 对象 。
-
我们在Hashmap中放置了 4 个键值,但它似乎只有 2 个!!!!这是因为如果两个对象具有相同的哈希码,它们将存储在相同的索引中。现在问题来了怎么办?它以LinkedList的形式 (逻辑上)存储对象 。
那么如何计算上述国家键值对的哈希码。
Hashcode for Japan = 95 as its length is odd.
Hashcode for India =95 as its length is odd
HashCode for Russia=31 as its length is even.
HashCode for France=31 as its length is even.
下图将清楚地解释 LinkedList 的概念。
以现在如果你对 Hashmap 结构有很好的了解,让我们来看看put和get方法。
放
让我们看看 put 方法的实现:
/**
* Associates the specified value with the specified key in this map. If the
* map previously contained a mapping for the key, the old value is
* replaced.
*
* @param key
* key with which the specified value is to be associated
* @param value
* value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or <tt>null</tt>
* if there was no mapping for <tt>key</tt>. (A <tt>null</tt> return
* can also indicate that the map previously associated
* <tt>null</tt> with <tt>key</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 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;
}
现在让我们一步一步理解上面的代码
-
检查关键对象是否为空。如果 key 为 null,那么它将存储在 表[ 0 ] 中,因为 null 的哈希码始终为 0。
-
调用关键对象的hashcode()方法并计算哈希码。此哈希码用于查找用于存储 Entry 对象的数组的索引。有时可能会发生这种情况,这个哈希码函数写得不好,所以 JDK 设计者放置了另一个名为 hash() 的函数,它以上面计算的哈希值作为参数。
-
indexFor ( hash , table .length ) 用于计算表数组中的精确索引,用于存储 Entry 对象。
-
正如我们在示例中看到的,如果两个关键对象具有相同的哈希码(称为
冲突
),那么它将以链表的形式存储。所以在这里,我们将遍历链表。
-
如果在我们刚刚计算的那个索引处不存在任何元素,那么它将直接将我们的 Entry 对象放在那个索引处。
-
如果该索引处存在元素,那么它将迭代直到它获得 Entry -> next 为 null。
-
如果我们再次放置相同的键怎么办,逻辑上它应该替换旧值。是的,它会这样做。在迭代时,它将通过调用 equals ( ) 方法( key.equals(k) ) 来检查键是否相等,如果此方法返回 true,则它将值对象替换为当前 Entry 的值对象。
-
如果它没有找到重复键,那么当前 Entry 对象将成为链表中的第一个节点,并且当前 Entry -> next 将成为该索引上现有的第一个节点。
得到
让我们看看 get now 的实现:
/**
* Returns the value to which the specified key is mapped, or {@code null}
* if this map contains no mapping for the key.
*
*
* More formally, if this map contains a mapping from a key {@code k} to a
* value {@code v} such that {@code (key==null ? k==null :
* key.equals(k))}, then this method returns {@code v}; otherwise it returns
* {@code null}. (There can be at most one such mapping.)
*
*
* A return value of {@code null} does not <i>necessarily</i> indicate that
* the map contains no mapping for the key; it's also possible that the map
* explicitly maps the key to {@code null}. The {@link #containsKey
* containsKey} operation may be used to distinguish these two cases.
*
* @see #put(Object, Object)
*/
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry 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;
}
当您了解 hashmap 的 put 功能时。所以理解 get 功能非常简单。如果您传递任何键以从哈希映射中获取值对象。
-
检查关键对象是否为空。如果 key 为 null,则返回表[ 0 ]中的 Object 的值 。
-
调用关键对象的hashcode()方法并计算哈希码。
-
indexFor(hash,table.length) 用于使用生成的哈希码计算表数组中的精确索引,以获取 Entry 对象。
-
在获取到表数组的索引后,它将遍历linkedlist并通过调用equals()方法检查键是否相等,如果返回true则返回Entry对象的值,否则返回null。
要记住的要点
-
HashMap有一个名为 Entry的内部类 ,用于存储键值对。
-
上面的 Entry 对象存储在称为 table 的 Entry 中
-
表的索引在逻辑上称为桶,它存储 LinkedList的第一个元素 。
-
Key 对象的hashcode () 用于查找该 Entry 对象的桶。
-
如果两个 key object 具有相同的 hashcode ,它们将进入同一个表数组的桶中。
-
键对象的 equals ( ) 方法用于保证键对象的唯一性。
-
值对象的 equals() 和 hashcode() 方法根本没有使用
|