1. 首页
  2. IT资讯

HashMap是这样在Java中工作的

“u003Cp class=”pgc-end-literature”u003EHashMap问题在求职面试中很常见。这里有一些关于hashmap在Java内部如何工作的深入解释。u003Cu002Fpu003Eu003Cpu003EHashMap在内部如何工作已成为几乎所有访谈中的一个普遍问题。几乎每个人都知道如何使用HashMap或HashMap和Hashtable之间的区别。但是,当问题为" HashMap如何在内部工作?"时,许多人会不知道了。u003Cu002Fpu003Eu003Cpu003E这个问题的答案是,它是基于哈希原则工作的,但它并不像听起来那么简单。哈希是一种使用算法为变量或属性分配唯一代码的机制,以便于检索。真正的哈希机制应该总是返回相同的hashCode(),当它应用于相同的对象时。u003Cu002Fpu003Eu003Cpu003E接下来的问题是,"散列如何帮助在HashMap中存储和检索值?"许多人会说,值将存储在bucket中,并使用键检索。如果你认为它是这样工作的,那你就大错特错了。为了证明这一点,让我们看看HashMap类:u003Cu002Fpu003Eu003Cpreu003Eu003Ccodeu003Eu002F** * The table, resized as necessary. Length MUST Always be a power of two. *u002F transient Entry[] table;u003Cu002Fcodeu003Eu003Cu002Fpreu003Eu003Cpu003Eu003Cbru002Fu003Eu003Cu002Fpu003Eu003Cpu003E那么HashMap中的Entry[]有什么用呢?HashMap将对象存储为条目实例,而不是键和值。u003Cu002Fpu003Eu003Ch1 class=”pgc-h-arrow-right”u003E什么是入门级?u003Cu002Fh1u003Eu003Cpu003EHashMap有一个名为Entry类的内部类,其中包含键和值。还有一个叫做next的东西,你稍后就会知道。u003Cu002Fpu003Eu003Cpu003Eu003Cbru002Fu003Eu003Cu002Fpu003Eu003Cpreu003Eu003Ccodeu003E static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; final int hash; …….. }u003Cu002Fcodeu003Eu003Cu002Fpreu003Eu003Cpu003E你应该知道HashMap将Entry实例存储在数组中,而不是作为键值对存储。为了存储值,都是使用HashMap的put()方法。让我们深入研究一下,看看它是如何工作的。u003Cu002Fpu003Eu003Ch1 class=”pgc-h-arrow-right”u003EPut()方法如何在内部工作?u003Cu002Fh1u003Eu003Cpu003E代码如下:u003Cu002Fpu003Eu003Cpreu003Eu003Ccodeu003Epublic 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; }u003Cu002Fcodeu003Eu003Cu002Fpreu003Eu003Cpu003E首先,它检查给定的密钥是否为null。如果给定键为null,则它将存储在零位置,因为null的Hashcode将为零。u003Cu002Fpu003Eu003Cpu003E然后,通过调用hashcode方法将hashcode应用于键. hashcode()。为了获得数组范围内的值,将调用hash(key.hashCode()),它将对hashcode执行一些移位操作。u003Cu002Fpu003Eu003Cpu003EindexFor()方法用于获取存储条目对象的确切位置。u003Cu002Fpu003Eu003Cpu003E接下来是最重要的部分——如果两个不同的对象具有相同的hashcode(例如Aa和BB将具有相同的hashcode),那么它会存储在同一个bucket中吗?为了处理这个问题,让我们考虑数据结构中的LinkedList。它将有一个"next"属性,它总是指向下一个对象,就像条目类中的下一个属性指向下一个对象一样。使用具有相同hashcode的不同对象将彼此放置在一起。u003Cu002Fpu003Eu003Cpu003E在发生冲突的情况下,HashMap将检查下一个属性的值。如果为空,则将条目对象插入该位置。如果下一个属性不为空,那么它将保持循环运行,直到下一个属性为空,然后将条目对象存储在那里。u003Cu002Fpu003Eu003Ch1 class=”pgc-h-arrow-right”u003E如何在HashMap中防止重复键?u003Cu002Fh1u003Eu003Cpu003E众所周知,HashMap不允许重复键,即使在插入具有不同值的相同键时,也只返回最新的值。u003Cu002Fpu003Eu003Cpreu003Eu003Ccodeu003Eimport 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); }}u003Cu002Fcodeu003Eu003Cu002Fpreu003Eu003Cpu003E对于上面的代码,将得到输出{null=asdf, 1=Scott},因为sam和Ian的值将被Scott替换。这是怎么发生的呢?u003Cu002Fpu003Eu003Cpu003ELinkedList中的所有条目对象都有相同的hashcode,但HashMap使用equals()。这个方法检查相等性,因此如果key.equals(k)为真,它将替换Entry类中的值对象,而不是键。通过这种方式,它可以防止插入重复的键。u003Cu002Fpu003Eu003Ch1 class=”pgc-h-arrow-right”u003EGet()方法如何在内部工作?u003Cu002Fh1u003Eu003Cpu003E将使用put()方法中应用的几乎相同的逻辑来检索值。u003Cu002Fpu003Eu003Cpreu003Eu003Ccodeu003Epublic 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; }u003Cu002Fcodeu003Eu003Cu002Fpreu003Eu003Cpu003E首先,它获取传递的密匙对象的散列码,并查找bucket位置。u003Cu002Fpu003Eu003Col start=”1″u003Eu003Cliu003E如果找到了正确的bucket,它将返回该值。u003Cu002Fliu003Eu003Cliu003E如果没有找到匹配,则返回null。u003Cu002Fliu003Eu003Cliu003E如果两个键具有相同的Hashcode会发生什么?u003Cu002Fliu003Eu003Cu002Folu003Eu003Cpu003E这里将使用相同的冲突解决机制。key.equals(k)将检查,直到它为真,如果为真,它将返回它的值。u003Cu002Fpu003Eu003Cpu003E望本文能阐明麻烦的HashMap内部机制。学习愉快!u003Cu002Fpu003E”

原文始发于:HashMap是这样在Java中工作的

主题测试文章,只做测试使用。发布者:程序员,转转请注明出处:http://www.cxybcw.com/26682.html

联系我们

13687733322

在线咨询:点击这里给我发消息

邮件:1877088071@qq.com

工作时间:周一至周五,9:30-18:30,节假日休息

QR code