HashMap是我们最常见也是最长使用的数据结构之一,它的功能强大、用处广泛。而且也是面试常见的考查知识点。常见问题可能有HashMap存储结构是什么样的?HashMap如何放入键值对、如何获取键值对应的值以及如何删除一个键值对。今天我们就来看看HashMap底层的实现原理。下面我们就开始进入正题,分析一下hashmap源码的实现原理。
我们提供的服务有:网站设计、网站建设、微信公众号开发、网站优化、网站认证、格尔木ssl等。为近1000家企事业单位解决了网站和推广的问题。提供周到的售前咨询和贴心的售后服务,是有科学管理、有技术的格尔木网站制作公司
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); table = new Entry[DEFAULT_INITIAL_CAPACITY]; init(); }
HashMap的构造方法有好几个,在这里我们就不一一介绍,只说一下我们最常见的HashMap无参构造方法。上面的构造方法中,有几个变量需要我们这里说明一下:
loadFactor:加载因子,默认值为0.75;
threshold:threshold是一个阈值,初始值为默认为16*0.75。当hashmap中存放键值对数量大于该值时,表示hashmap容量大小需要扩充,一般容量会翻倍。
table:table其实是一个Entry类型的数组,在hashmap中我们利用数组和链表来解决hash冲突,这里的table数组用于存放冲突链表的头结点。
另外在HahsMap中,我们通过数组加链表的方式来存储Entry节点(Entry数据结构用于存储键值对)。这里所谓的数组即是上面提到的table,它是一个Entry数组,table对象中节点初始化值均为null,当我们新插入的节点第一次散列到该位置时,会将节点插入到table中对应位置。如果后续存在散列位置相同的节点,会以链表的方式解决hash冲突。示意图如下:
put方法是我们最常用方法,我们利用该方法将键值对放入HashMap集合中,那么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; }private V putForNullKey(V value) { for (Entry<K,V> e = table[0]; e != null; e = e.next) { if (e.key == null) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(0, null, value, 0); return null; }
if (key == null) return putForNullKey(value);
如果当前传入的key值为null,执行putForNullKey()方法;当key值为null时,hash值为0,将其保存到以table[0]为开头的链表中去。遍历链表,如果存在某节点的key值为null,则用新value直接将其替换。如果未找到key值为null的节点,调用addEntry()方法插入一个key为null的新节点。addEntry方法我们会在后文中介绍。
int hash = hash(key.hashCode());int i = indexFor(hash, table.length);
为什么这里还要对key的hashCode值再调用一次哈希算法呢?简单来说就是为了让传递进来的key散落位置可以更加均匀,具体原因就不在本文中介绍了,网上有很多资料可供借鉴。
接着调用indexFor方法计算当前key值散落在table中的位置,其实就是key%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; } }
遍历以table[i]为头结点的链表,查找是否已经有相同的key值的节点存在于链表中。判断条件为if (e.hash == hash && ((k = e.key) == key || key.equals(k)))。这个判断条件十分重要,我们来仔细分析下。首先是e.hash == hash:之前我们已经计算出了当前待处理节点的hash值,并保存在变量hash中,在此我们需要比较当前链表遍历节点key的hash值(e.hash)和hash是否相等。如果我们去看一下addEntry()方法我们会发现,Entry节点的存储位置实际上是由key的hash值来决定的。如果key的hash相同,那么他们的存储位置也相同。(k = e.key) == key || key.equals(k))。先简单的说一下”==”和”equals”的意义,”==”是引用一致性判断,而equals是内容一致性判断。这里的意思也就是说如果两个key对象指向的是同一个对象,或者他们就是同一个对象,则返回true。总结一下,如果hash值相同,则key值相同或是同一个对象的引用,则表示hashmap中存在以key为键值的Entry节点。
如果判断if (e.hash == hash && ((k = e.key) == key || key.equals(k)))判断条件返回为true,则用新值替换老值。
如果没有找到相同的key值,则调用addEntry()方法新增一个指定key和value的Entry节点。
void addEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<K,V>(hash, key, value, e); if (size++ >= threshold) resize(2 * table.length); }
接下来继续看addEntry()方法,假设当前节点为插入到table[bucketIndex]位置的第一个节点
Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
在Entry类的构造方法中有这样一句代码:
next = e;
即当前新建的entry节点将指向Entry构造方法传递过来的Entry节点e,此时e保存的值为头结点的值,也就是null。该节点创建完之后,又被赋值给table[bucketIndex],相当于链表的头结点了保存了最新插入的节点。如下图所示我们在table[i]位置插入了Entry
Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
此时table[buckertIndex]中存放的节点为
新建一个Entry节点,key=”key2”,value=”value2”,同时该entry节点next值指向
另外在addEntry方法中有如下两句代码
if (size++ >= threshold) resize(2 * table.length);
size的值为当前hashMap中存储的节点个数,threshold是一个阈值。如果hashMap中存储的节点个数大于等于threshold,表示我们需要对当前hashMap进行扩容了。每一次扩充容量为之前容量的2倍。我们来看一下resize()方法。
void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity]; transfer(newTable); table = newTable; threshold = (int)(newCapacity * loadFactor); } void transfer(Entry[] newTable) { Entry[] src = table; int newCapacity = newTable.length; for (int j = 0; j < src.length; j++) { Entry<K,V> e = src[j]; if (e != null) { src[j] = null; do { Entry<K,V> next = e.next; int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } while (e != null); } } }
关键代码是这一段
Entry[] newTable = new Entry[newCapacity];transfer(newTable); table = newTable;
如果resize()之前Entry数组的大小为A,那么newTable数组的大小为2A
transfer(newTable)方法用于将原先entry[]数组中的节点转移到newTable数组中,下面我们来看下transfer()方法具体干了什么。
将原来的table数组赋值给src数组
获取newTable数组的长度,这里为table数组长度的2倍
循环遍历src数组,执行下面的操作
a. 取src[j]节点的值赋值给e
b. 如果e节点不为null,将src[j]的值置为null
我们来举两个简单的例子说明一下tranfer到底干了什么:
当src[j]不为空时,比方说src[j]中保存的Entry节点key=”key2”,value=”value2”,src[j]指向的下一个节点key=”key1”,value=”value1”,如下图所示:
最开始的时候newTable[]中并没有存放任何Entry节点,只是单纯的进行了初始化。结合上面代码,我们可以看到此时e = entry2节点,next节点值为entry1
利用indexFor重新计算出e节点的散列位置。e节点的next指向被初始化后的newTable[i]节点,同时newTabel[i]的值也被赋值为e节点
最后执行e = next;此时e等于entry1
形成节点的示意图如下:
接着执行
next = e.next,此时e的next节点为null,next =null;
利用indexFor计算出新的散列位置,比如说新的散列位置为j,此时以newTable[j]为头节点的链表中已经存在了两个节点。如下图所示:
我们将待处理的节点entry节点插入后会变成什么样呢?
简单的来说resize方法就是去逐个遍历table[i]后面的Entry节点链表,利用indexFor方法重新结算节点的散落位置,并将其插入到以newTable[]为头结点的链表中去。
说完了put我们再来看一下get方法
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; }private V getForNullKey() { for (Entry<K,V> e = table[0]; e != null; e = e.next) { if (e.key == null) return e.value; } return null; }
理解了put方法时如何往hashmap中放入键值对的,那么get()方法也就很好理解了。我们来具体看看get()方法的实现。
如果key值为null,执行getForNullKey()方法。当key值为null时,新的键值对会放到table[0]处,所以我们先去遍历table[0]位置的节点链表,查看是否有key值为null的节点。如果有的话,直接返回value。如果找不到key为null的节点,返回null。
如果key值不为null,利用indexFor方法找到当前key所处的table[i]位置,遍历table[i]位置的节点链表。根据e.hash == hash && ((k = e.key) == key || key.equals(k))来判断是否有相同key值的节点。如果当前位置链表中存在key值相同的Entry节点,返回Entry节点保存的value。如果找不到key值匹配的Entry节点,返回null。
public V remove(Object key) { Entry<K,V> e = removeEntryForKey(key); return (e == null ? null : e.value); }final Entry<K,V> removeEntryForKey(Object key) { int hash = (key == null) ? 0 : hash(key.hashCode()); int i = indexFor(hash, table.length); Entry<K,V> prev = table[i]; Entry<K,V> e = prev; while (e != null) { Entry<K,V> next = e.next; Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { modCount++; size--; if (prev == e) table[i] = next; else prev.next = next; e.recordRemoval(this); return e; } prev = e; e = next; } return e; }
别看remove方法这么长,其实它的逻辑很简单
通过hash()和IndexFor()方法找到当前Entry节点的散列位置i,prev节点为当前节点的上一个节点(初始值为table[i]节点),e节点表示当前节点。
比较待删除节点的key值和当前节点的key值是否相符。如果找不到相符的节点,返回null;
如果有相符的节点,且为头结点,e节点的下一个节点将被赋值给table[i];
如果有相匹配的节点,并且不为头结点,则prev节点不再指向e,而是指向e.next,也即是prev.next = e.next;相当于一个断链操作;
如果让你写一个hashmap的遍历代码,估计大部分人写出下面这段代码。可是HashMap的遍历过程到底是怎么样的,为什么我们每次取值的时候都使用iter.next()来取值的呢?下面我们就来看看HashMap的遍历实现。
Itreator iter = map.entrySet().itreator(); while(iter.hashNext()){ Map.entry<k,v> entry = (Map.entry<k,v>) iter.next(); }
HashMap类中有一个私有类EntrySet,它继承自AbstractSet类。EntrySet类中有一个iterator()方法,也就是我们上面在遍历hashMap所调用的iterator()方法,它会返回一个Iterator对象。
我们来看看iterator方法:
public Iterator<Map.Entry<K,V>> iterator() { return newEntryIterator(); }
iterator()方法中调用了newEntryIterator()方法,接着进入newEntryIterator()方法看看。
Iterator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); }
newEntryIterator方法又创建了一个EntryIterator对象并返回。这个EntryIterator很关键,我们来具体看看这个类。
private final class EntryIterator extends HashIterator<Map.Entry<K,V>> { public Map.Entry<K,V> next() { return nextEntry(); } }
EntryIterator类继承自HashItertor类,而且HashIterator类只有一个方法next()。既然EntryIterator继承自HashIterator类,那么EntryIterator到底继承了父类的哪些对象,默认实现了父类的哪些方法呢?我们再看看HashIterator类。
private abstract class HashIterator<E> implements Iterator<E> { Entry<K,V> next; // next entry to return int expectedModCount; // For fast-fail int index; // current slot Entry<K,V> current; // current entry HashIterator() { expectedModCount = modCount; if (size > 0) { // advance to first entry Entry[] t = table; while (index < t.length && (next = t[index++]) == null) ; } } }
HashIterator类中有四个属性,它们的用处代码注释已经简单明了的介绍了。值得注意的是HashIterator()提供了一个无参的构造方法,然而他并没有对所有的属性进行初始化,在这里我们需要明确的是index的值将会被赋为0。同时后面还有一大段,它干了什么呢?
首先是Entry[] t = table;将当前存储头结点的Entry[]数组table赋值给t;
接着执行一个while循环
while (index < t.length && (next = t[index++]) == null)
当index大于table的长度,或者当前t[index]位置保存的节点不为空时,将会结束while循环。也就是说该循环目的是为了找出table[]数组中第一个存储了Entry对象的位置,并用index变量记录该位置。
我们再总结一下!当Itreator iter = map.entrySet().itreator();这句代码结束之后,我们获得了一个Iterator对象,这个对象保存了当前hashMap的modCount值,index用于标识table[]数组中第一个不为null的位置,同时next的初始值也等同于table[index]的值。
while(iter.hashNext())
当前对象实际上为HashIterator对象,HashIterator对象的hasNext()方法十分的简单
public final boolean hasNext() { return next != null; }
Map.entry<k,v> entry = (Map.entry<k,v>) iter.next();
再梳理一下逻辑,EntryIterator 有一个方法next
public Map.Entry<K,V> next() { return nextEntry(); }final Entry<K,V> nextEntry() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); Entry<K,V> e = next; if (e == null) throw new NoSuchElementException(); if ((next = e.next) == null) { Entry[] t = table; while (index < t.length && (next = t[index++]) == null) ; } current = e; return e; }
如果modCount值不等于expectedModCount,表示在当前遍历过程中,HashMap可能被其他线程修改过,我们需要抛出ConcurrentModificationException异常,这也就是我们常说fast-fail。同时新建一个Entry节点e,赋值为next(第一次进来是next指向的就是table[]数组中第一个不为null的头结点)。
如果说当前节点的下一个节点为null,相当于遍历到了当前table[i]所指向链表的最后一个节点。此时我们应当去寻找table数组中下一个头结点不为null的位置。
执行while (index < t.length && (next = t[index++]) == null) 找到下一个不为null的头结点,并保存到next节点中。
返回当前节点e
分享名称:HashMap源码阅读与解析
标题链接:https://www.cdcxhl.com/article30/gshpso.html
成都网站建设公司_创新互联,为您提供定制网站、网页设计公司、网站设计、关键词优化、、网站排名
声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联