江苏龙网

  1. 首页 > 人文 > >

精英联盟总队|面试官：说一下HashMap原理，为什么会产生死循环( 二 )

[] table ， 这个数组 ， 那么它又是如何定义的呢？
static class Entry implements Map.Entry {final K key;V value;Entry next;int hash;/*** Creates new entry.*/Entry(int h, K k, V v, Entry n) {value = http://kandian.youth.cn/index/v;next = n;key = k;hash = h;}......}Entry 是 HashMap 中的一个内部类 ， 从它的成员变量很容易看出：
① key 就是写入时的键 。
② value 自然就是值 。
③ 开始的时候就提到 HashMap 是由数组和链表组成 ， 所以这个 next 就是用于实现链表结构 。
④ hash 存放的是当前 key 的 hashcode 。
知晓了基本结构 ， 那来看看其中重要的put、get方法 。
4、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 e = table[i]; e != null; e = e.next) {Object k;if (e.hash == hashe.value = http://kandian.youth.cn/index/value;e.recordAccess(this);return oldValue;}}modCount++;addEntry(hash, key, value, i);return null;}① 如果 key 为空 ， 则 put 一个空值进去 。
② 根据 key 计算出 hashcode 。
③ 根据计算出的 hashcode 定位出所在桶 。
④ 如果桶是一个链表则需要遍历判断里面的 hashcode、key 是否和传入 key 相等 ， 如果相等则进行覆盖 ， 并返回原来的值 。
⑤ 如果桶是空的 ， 说明当前位置没有数据存入；新增一个 Entry 对象写入当前位置 。
void addEntry(int hash, K key, V value, int bucketIndex) {if ((size >= threshold)hash = (null != key) ? hash(key) : 0;bucketIndex = indexFor(hash, table.length);}createEntry(hash, key, value, bucketIndex);}void createEntry(int hash, K key, V value, int bucketIndex) {Entry e = table[bucketIndex];table[bucketIndex] = new Entry<>(hash, key, value, e);size++;}① 当调用 addEntry 写入 Entry 时需要判断是否需要扩容 。
② 如果需要就进行两倍扩充 ， 并将当前的 key 重新 hash 并定位 。
③ 而在 createEntry 中会将当前位置的桶传入到新建的桶中 ， 如果当前桶有值就会在该位置形成链表 。 新new的Entry会加到链表的头部 。
5、get 方法public V get(Object key) {if (key == null)return getForNullKey();Entry entry = getEntry(key);return null == entry ? null : entry.getValue();}final Entry getEntry(Object key) {int hash = (key == null) ? 0 : hash(key);for (Entry e = table[indexFor(hash, table.length)];e != null;e = e.next) {Object k;if (e.hash == hash}return null;}① 首先也是根据 key 计算出 hashcode ， 然后定位到具体的桶中 。
② 判断该位置是否为链表 。
③ 不是链表就根据 key、key 的 hashcode 是否相等来返回值 。
④ 为链表则需要遍历直到 key 及 hashcode 相等时候就返回值 。
⑤ 啥都没取到就直接返回 null。
6、并发场景下出现死循环多线程同时put时 ， 如果同时调用了resize操作 ， 可能会导致循环链表产生 ， 进而使得后面get的时候 ， 会死循环 。 下面详细阐述循环链表如何形成的 。
resize函数
数组扩容函数 ， 主要的功能就是创建扩容后的新数组 ， 并且将调用transfer函数将旧数组中的元素迁移到新的数组 。
void resize(int newCapacity) {Entry[] oldTable = table;int oldCapacity = oldTable.length;if (oldCapacity == MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return;} //创建一个新的Hash TableEntry[] newTable = new Entry[newCapacity];//将Old Hash Table上的数据迁移到New Hash Table上transfer(newTable);table = newTable;threshold = (int)(newCapacity * loadFactor);}


推荐阅读


上一篇：丈农尺|“驴皮冻”和“燕口水”之争，谁会赢？，又一滋补品爆火

下一篇：光明网社会|但投入结构仍有不足，我国科技经费投入规模稳步增加