HashMap 是 Java 开发过程中常用的工具类之一, 也是面试过程中常问的内容, 此篇文件通过作者自己的理解和网上众多资料对其进行一个解析. 作者本地的 JDK 版本为 64 位的 1.8.0_171. 参考资料推荐以下两篇文章:
https://www.cnblogs.com/little-fly/p/7344285.html
https://monkeysayhi.github.io/2017/08/26/HashMap 实现原理 https://monkeysayhi.github.io/2017/08/26/HashMap实现原理
数据结构
结合上图及源码可以看出, HashMap 底层数据结构为 Node 类型数组, Node 类型为 HashMap 的内部类, 数据结构为链表.
- /**
- * The table, initialized on first use, and resized as
- * necessary. When allocated, length is always a power of two.
- * (We also tolerate length zero in some operations to allow
- * bootstrapping mechanics that are currently not needed.)
- */
- transient Node<K,V>[] table;
- /**
- * Basic hash bin node, used for most entries. (See below for
- * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
- */
- static class Node<K,V> implements Map.Entry<K,V> {
- final int hash;
- final K key;
- V value;
- Node<K,V> next;
- Node(int hash, K key, V value, Node<K,V> next) {
- this.hash = hash;
- this.key = key;
- this.value = value;
- this.next = next;
- }
- public final K getKey() { return key; }
- public final V getValue() { return value; }
- public final String toString() { return key + "=" + value; }
- public final int hashCode() {
- return Objects.hashCode(key) ^ Objects.hashCode(value);
- }
- public final V setValue(V newValue) {
- V oldValue = value;
- value = newValue;
- return oldValue;
- }
- public final boolean equals(Object o) {
- if (o == this)
- return true;
- if (o instanceof Map.Entry) {
- Map.Entry<?,?> e = (Map.Entry<?,?>)o;
- if (Objects.equals(key, e.getKey()) &&
- Objects.equals(value, e.getValue()))
- return true;
- }
- return false;
- }
- }
初始大小
HashMap 默认的初始大小为 16, 如有特殊情况下需要自定义初始化大小时可调用 HashMap(int initialCapacity) 方法进行自定义.
- /**
- * The default initial capacity - MUST be a power of two.
- */
- static final int DEFAULT_INITIAL_CAPACITY = 1 <<4; // aka 16
- /**
- * Constructs an empty <tt>HashMap</tt> with the specified initial
- * capacity and the default load factor (0.75).
- *
- * @param initialCapacity the initial capacity.
- * @throws IllegalArgumentException if the initial capacity is negative.
- */
- public HashMap(int initialCapacity) {
- this(initialCapacity, DEFAULT_LOAD_FACTOR);
- }
负载因子
负载因子默认为 0.75, 当 HashMap 当前已使用容量大于当前大小 * 负载因子时, 自动扩容一倍空间, 如有特殊情况下需要自定义初始化大小时可调用 以下方法进行自定义.
- /**
- * The load factor used when none specified in constructor.
- */
- static final float DEFAULT_LOAD_FACTOR = 0.75f;
- /**
- * Constructs an empty <tt>HashMap</tt> with the specified initial
- * capacity and load factor.
- *
- * @param initialCapacity the initial capacity
- * @param loadFactor the load factor
- * @throws IllegalArgumentException if the initial capacity is negative
- * or the load factor is nonpositive
- */
- public HashMap(int initialCapacity, float loadFactor) {
- if (initialCapacity <0)
- throw new IllegalArgumentException("Illegal initial capacity:" +
- initialCapacity);
- if (initialCapacity> MAXIMUM_CAPACITY)
- initialCapacity = MAXIMUM_CAPACITY;
- if (loadFactor <= 0 || Float.isNaN(loadFactor))
- throw new IllegalArgumentException("Illegal load factor:" +
- loadFactor);
- this.loadFactor = loadFactor;
- this.threshold = tableSizeFor(initialCapacity);
- }
树型阀值
树型阀值这个名字是作者根据字面意思自己翻译的, 大家看看就好了, 对应参数为 TREEIFY_THRESHOLD, 之前提到过 HashMap 的结构为 Node 型数组, 而 Node 的数据结构为链表, 树型阀值就是当链表长度超过这个值时, 将 Node 的数据结构修改为红黑树 https://blog.csdn.net/u011240877/article/details/53329023 , 以便优化查找时间, 默认值为 8
- /**
- * The bin count threshold for using a tree rather than list for a
- * bin. Bins are converted to trees when adding an element to a
- * bin with at least this many nodes. The value must be greater
- * than 2 and should be at least 8 to mesh with assumptions in
- * tree removal about conversion back to plain bins upon
- * shrinkage.
- */
- static final int TREEIFY_THRESHOLD = 8;
初始化
HashMap 提供以下四种构造方法进行初始化, 前三种主要区别在于设置以上介绍的几个参数, 第四种方法为通过其他 Map 实现创建 HashMap.
- /**
- * Constructs an empty <tt>HashMap</tt> with the specified initial
- * capacity and load factor.
- *
- * @param initialCapacity the initial capacity
- * @param loadFactor the load factor
- * @throws IllegalArgumentException if the initial capacity is negative
- * or the load factor is nonpositive
- */
- public HashMap(int initialCapacity, float loadFactor) {
- if (initialCapacity <0)
- throw new IllegalArgumentException("Illegal initial capacity:" +
- initialCapacity);
- if (initialCapacity> MAXIMUM_CAPACITY)
- initialCapacity = MAXIMUM_CAPACITY;
- if (loadFactor <= 0 || Float.isNaN(loadFactor))
- throw new IllegalArgumentException("Illegal load factor:" +
- loadFactor);
- this.loadFactor = loadFactor;
- this.threshold = tableSizeFor(initialCapacity);
- }
- /**
- * Constructs an empty <tt>HashMap</tt> with the specified initial
- * capacity and the default load factor (0.75).
- *
- * @param initialCapacity the initial capacity.
- * @throws IllegalArgumentException if the initial capacity is negative.
- */
- public HashMap(int initialCapacity) {
- this(initialCapacity, DEFAULT_LOAD_FACTOR);
- }
- /**
- * Constructs an empty <tt>HashMap</tt> with the default initial capacity
- * (16) and the default load factor (0.75).
- */
- public HashMap() {
- this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
- }
- /**
- * Constructs a new <tt>HashMap</tt> with the same mappings as the
- * specified <tt>Map</tt>. The <tt>HashMap</tt> is created with
- * default load factor (0.75) and an initial capacity sufficient to
- * hold the mappings in the specified <tt>Map</tt>.
- *
- * @param m the map whose mappings are to be placed in this map
- * @throws NullPointerException if the specified map is null
- */
- public HashMap(Map<? extends K, ? extends V> m) {
- this.loadFactor = DEFAULT_LOAD_FACTOR;
- putMapEntries(m, false);
- }
设置 HashMap 的值
put 方法是 HashMap 中使用率非常高的 API 之一, 其源码实现如下, 通过源码我们可以发现其原理主要分为以下两步:
对 key 进行 hash 运算, 然后再与当前 map 最后一个下标进行与运算确定其在数组中的位置, 正是因为这个算法, 我们可以得知 HashMap 中元素是无序的.
确定其下标以后, 如果当前位置为空则直接赋值, 如果不为空则放到下一个节点, 如果当前为链表且添加元素后的长度达到树型阀值, 则将链表转换为红黑树
- /**
- * Associates the specified value with the specified key in this map.
- * If the map previously contained a mapping for the key, the old
- * value is replaced.
- *
- * @param key key with which the specified value is to be associated
- * @param value value to be associated with the specified key
- * @return the previous value associated with <tt>key</tt>, or
- * <tt>null</tt> if there was no mapping for <tt>key</tt>.
- * (A <tt>null</tt> return can also indicate that the map
- * previously associated <tt>null</tt> with <tt>key</tt>.)
- */
- public V put(K key, V value) {
- return putVal(hash(key), key, value, false, true);
- }
- /**
- * Implements Map.put and related methods
- *
- * @param hash hash for key
- * @param key the key
- * @param value the value to put
- * @param onlyIfAbsent if true, don't change existing value
- * @param evict if false, the table is in creation mode.
- * @return previous value, or null if none
- */
- final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
- boolean evict) {
- Node<K,V>[] tab; Node<K,V> p; int n, i;
- if ((tab = table) == null || (n = tab.length) == 0)
- n = (tab = resize()).length;
- if ((p = tab[i = (n - 1) & hash]) == null)
- tab[i] = newNode(hash, key, value, null);
- else {
- Node<K,V> e; K k;
- if (p.hash == hash &&
- ((k = p.key) == key || (key != null && key.equals(k))))
- e = p;
- else if (p instanceof TreeNode)
- e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
- else {
- for (int binCount = 0; ; ++binCount) {
- if ((e = p.next) == null) {
- p.next = newNode(hash, key, value, null);
- if (binCount>= TREEIFY_THRESHOLD - 1) // -1 for 1st
- treeifyBin(tab, hash);
- break;
- }
- if (e.hash == hash &&
- ((k = e.key) == key || (key != null && key.equals(k))))
- break;
- p = e;
- }
- }
- if (e != null) { // existing mapping for key
- V oldValue = e.value;
- if (!onlyIfAbsent || oldValue == null)
- e.value = value;
- afterNodeAccess(e);
- return oldValue;
- }
- }
- ++modCount;
- if (++size> threshold)
- resize();
- afterNodeInsertion(evict);
- return null;
- }
获取 HashMap 中的值
get 方法同样是 HashMap 中常用的 API 之一, 参照其源码, 其原理与 put 方法正好相反, 分为以下两个部分:
根据 key 的 hash 运算值获取数组中对应下标的内容
循环链表或红黑树, 然后匹配 value 值直至获得对应的值或返回 null
- /**
- * Returns the value to which the specified key is mapped,
- * or {@code null} if this map contains no mapping for the key.
- *
- * <p>More formally, if this map contains a mapping from a key
- * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
- * key.equals(k))}, then this method returns {@code v}; otherwise
- * it returns {@code null}. (There can be at most one such mapping.)
- *
- * <p>A return value of {@code null} does not <i>necessarily</i>
- * indicate that the map contains no mapping for the key; it's also
- * possible that the map explicitly maps the key to {@code null}.
- * The {@link #containsKey containsKey} operation may be used to
- * distinguish these two cases.
- *
- * @see #put(Object, Object)
- */
- public V get(Object key) {
- Node<K,V> e;
- return (e = getNode(hash(key), key)) == null ? null : e.value;
- }
- /**
- * Implements Map.get and related methods
- *
- * @param hash hash for key
- * @param key the key
- * @return the node, or null if none
- */
- final Node<K,V> getNode(int hash, Object key) {
- Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
- if ((tab = table) != null && (n = tab.length)> 0 &&
- (first = tab[(n - 1) & hash]) != null) {
- if (first.hash == hash && // always check first node
- ((k = first.key) == key || (key != null && key.equals(k))))
- return first;
- if ((e = first.next) != null) {
- if (first instanceof TreeNode)
- return ((TreeNode<K,V>)first).getTreeNode(hash, key);
- do {
- if (e.hash == hash &&
- ((k = e.key) == key || (key != null && key.equals(k))))
- return e;
- } while ((e = e.next) != null);
- }
- }
- return null;
- }
- /**
- * Calls find for root node.
- */
- final TreeNode<K,V> getTreeNode(int h, Object k) {
- return ((parent != null) ? root() : this).find(h, k, null);
- }
来源: https://www.cnblogs.com/aotian/p/9491346.html