哈希如何帮助存储和检索HashMap中的值?

发布时间:2020-06-01 15:48:45 作者:鸽子
来源:亿速云 阅读:218

HashMap问题在工作面试中很常见。 这是HashMaps在Java内部如何工作的一些深入说明。

HashMap在内部如何工作已成为几乎所有访谈中的一个普遍问题。 几乎每个人都知道如何使用HashMap或HashMap与Hashtable之间的区别。 但是,当问题为“ HashMap如何在内部工作?”时,许多人会失败。

这个问题的答案是,它基于哈希原理工作,但听起来并不那么简单。 哈希是一种使用算法将唯一代码分配给变量或属性的机制,从而可以轻松进行检索。 真正的哈希机制在应用于同一对象时应始终返回相同的hashCode()。

然后是一个问题:“哈希如何帮助存储和检索HashMap中的值?” 许多人会说该值将存储在存储桶中,并使用键进行检索。 如果你认为这是有效的,那么你绝对是错误的。 为了证明这一点,让我们看一下HashMap类:

/**
     * The table, resized as necessary. Length MUST Always be a power of two.
     */
     transient Entry[] table;

那么HashMap中Entry []的用途是什么? HashMap将对象存储为Entry实例,而不是键和值。

什么是入门班?

HashMap有一个称为Entry Class的内部类,其中包含键和值。 还有一个叫做next的东西,稍后你将了解。

 static class Entry<K,V> implements Map.Entry<K,V> 
 {
     final K key;
     V value;
     Entry<K,V> next;
     final int hash;
     ........
 }

你知道HashMap将Entry实例存储在数组中,而不是作为键值对存储。 为了存储值,你将使用HashMap的put()方法。 让我们深入研究一下,看看它是如何工作的。

Put()方法如何在内部工作?
该代码将如下所示:

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;
 }

首先,它检查给定的密钥是否为null。如果给定键为null,则它将存储在零位置,因为null的哈希码将为零。

然后通过调用hashcode方法将哈希码应用于键.hashCode()。为了在数组范围内获得值,调用了hash(key.hashCode()),它对哈希码执行一些移位操作。
indexFor()方法用于获取存储Entry对象的确切位置。

接下来是最重要的部分-如果两个不同的对象具有相同的哈希码(例如Aa和BB将具有相同的哈希码),它将存储在同一存储桶中吗?为了解决这个问题,让我们考虑一下数据结构中的LinkedList。它将具有“下一个”属性,该属性将始终指向下一个对象,与Entry类中的下一个属性指向下一个对象的方式相同。使用这种方法,具有相同哈希码的不同对象将彼此相邻放置。

对于Collision,HashMap检查下一个属性的值。如果为null,则将Entry对象插入该位置。如果下一个属性不为null,则它将保持循环运行,直到下一个属性为null,然后将Entry对象存储在那里。

如何在HashMap中防止重复密钥?

众所周知,HashMap不允许重复键,即使当我们插入具有不同值的相同键时,也仅返回最新值。

import java.util.HashMap;
import java.util.Map;
public class HashMapEg {
 public static void main(String[] args) {
  Map map = new HashMap();
  map.put(1, "sam");
  map.put(1, "Ian");
  map.put(1, "Scott");
  map.put(null, "asdf");
  System.out.println(map);
 }
}

对于上面的代码,你将获得输出{null = asdf,1 = Scott},因为值sam和Ian将被替换为Scott。 那么,这是怎么发生的呢?

LinkedList中的所有Entry对象将具有相同的哈希码,但是HashMap使用equals()。 此方法检查相等性,因此如果key.equals(k)为true,它将替换Entry类中的值对象而不是键。 这样,可以防止插入重复密钥。

Get()方法如何在内部工作?

将使用put()方法中几乎相同的逻辑来检索值。

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;
 }

如果两个键具有相同的Hashcode会发生什么?

此处将使用相同的冲突解决机制。 key.equals(k)将一直检查到它为true,如果为true,则返回它的值。

推荐阅读:
  1. HashMap中的equals()和hashCode()有什么不同?
  2. 全域哈希和完全哈希

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

java hashmap 的值

上一篇:dns是什么?

下一篇:android基础二之ToggleButton

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》