java HashMap内部实现原理详解_Java教程

java HashMap内部实现原理详解

2020-08-02 12:09u012926924 Java教程

这篇文章主要介绍了java HashMap内部实现原理详解的相关资料,需要的朋友可以参考下

详解HashMap内部实现原理

内部数据结构

java" id="highlighter_126320">
			
				?

									static class Entry<K,V> implements Map.Entry<K,V> {

									    final K key;

									    V value;

									    Entry<K,V> next;

									    int hash;

从上面的数据结构定义可以看出，HashMap存元素的是一组键值对的链表，以什么形式存储呢

				?

									transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

可以看出，是以数组形式储存，好的，现在我们知道，HashMap是以数组形式存储，每个数组里面是一个键值对，这个键值对还可以链接到下个键值对。如下图所示:

java HashMap内部实现原理详解

hashmap的添加

				?

									public V put(K key, V value) {

									    if (table == EMPTY_TABLE) {

									      inflateTable(threshold);

									    }

									    if (key == null)

									      return putForNullKey(value);

									    int hash = hash(key);

									    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;

									  }

这里可以看出，hashmap的添加，首先根据一个entry的hash属性去查找相应的table元素i，然后看这个位置是否有元素存在，如果没有，直接放入，如果有，遍历此次链表，加到表尾

删除

				?

									final Entry<K,V> removeEntryForKey(Object key) {

									    if (size == 0) {

									      return null;

									    }

									    int hash = (key == null) ? 0 : hash(key);

									    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;

									  }

删除的话，还是先根据hash在table数组中查找，然后再根据equals在链表中进行查找，这个也是为什么hashmap和hashset等以hash方式进行存储的数据结构要求实现两个方法hashcode和equalsd的原因

学过hash的人都知道，hash表的性能和hash冲突的发生次数有很大关系，但有不能申请过长的table表浪费空间，所以这里有了我们的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, initHashSeedAsNeeded(newCapacity));

									    table = newTable;

									    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);

									  }

这个方法会在put的时候调用,上面put的时候先调用 addEntry(hash, key, value, i);方法，然后看addEntry方法

				?

									void addEntry(int hash, K key, V value, int bucketIndex) {

									    if ((size >= threshold) && (null != table[bucketIndex])) {

									      resize(2 * table.length);

									      hash = (null != key) ? hash(key) : 0;

									      bucketIndex = indexFor(hash, table.length);

									    }

									    createEntry(hash, key, value, bucketIndex);

									  }

上面可以看出那么 HashMap 当 HashMap 中的元素个数超过数组大小 *loadFactor 时，就会进行数组扩容，loadFactor 的默认值为 0.75，这是一个折中的取值。也就是说，默认情况下，数组大小为 16，那么当 HashMap 中元素个数超过 16*0.75=12 的时候，就把数组的大小扩展为 2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知 HashMap 中元素的个数，那么预设元素的个数能够有效的提高 HashMap 的性能。

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

原文链接：http://blog.csdn.net/u012926924/article/details/50451991