JDK源码分析之集合04HashMap

一、前言

    HashMap是常用的Map实现类,其中可以保存一个key为null的键值对和任意多个key!=null但是value为null的键值对。

二、HashMap源代码分析

2.1、类的继承关系

//Map中定义了Map必须支持的一些操作,abstractMap中添加了其默认实现 public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>,         Cloneable, Serializable

2.2内部类

static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; int hash;   /** * Creates new entry. */ Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; }   public final K getKey() { return key; }   public final V getValue() { return value; }   public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; }   public final boolean equals(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry e = (Map.Entry)o; Object k1 = getKey(); Object k2 = e.getKey(); if (k1 == k2 || (k1 != null && k1.equals(k2))) { Object v1 = getValue(); Object v2 = e.getValue(); if (v1 == v2 || (v1 != null && v1.equals(v2))) return true; } return false; }   public final int hashCode() { return (key==null ? 0 : key.hashCode()) ^ (value==null ? 0 : value.hashCode()); }   public final String toString() { return getKey() + "=" + getValue(); }   /** * This method is invoked whenever the value in an entry is * overwritten by an invocation of put(k,v) for a key k that's already * in the HashMap. */ void recordAccess(HashMap<K,V> m) { }   /** * This method is invoked whenever the entry is * removed from the table. */ void recordRemoval(HashMap<K,V> m) { } }

此内部类定义了一个节点模型;每个节点中包含了:key、value、hash值和指向下一个节点的引用。为HashMap内部存储的数据结构

2.3私有属性

// 默认初始化容量;必须为2的n次幂     static final int DEFAULT_INITIAL_CAPACITY = 16;     // HashMap的最大容量,为2的30次幂     static final int MAXIMUM_CAPACITY = 1 << 30;     // 默认因子     static final float DEFAULT_LOAD_FACTOR = 0.75f;      // Entry数组,用于保存元素;长度必须为2的n次幂     transient Entry<K, V>[] table;      // map中元素的个数     transient int size;      /**      * The next size value at which to resize (capacity * load factor).      * 改变size的阈值=capacity*factor      */     int threshold;      /**      * The load factor for the hash table.      */     final float loadFactor;     // 结构改变的次数     transient int modCount;      /**      * The default threshold of map capacity above which alternative hashing is      * used for String keys. Alternative hashing reduces the incidence of      * collisions due to weak hash code calculation for String keys.      * <p/>      * This value may be overridden by defining the system property      * {@code jdk.map.althashing.threshold}. A property value of {@code 1}      * forces alternative hashing to be used at all times whereas {@code -1}      * value ensures that alternative hashing is never used.      */     static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

2.4构造函数

// 使用 默认的capacity和factor创建空的HashMap     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);          // Find a power of 2 >= initialCapacity         // 找到第一个大于initialCapacity的2的整次幂         int capacity = 1;         while (capacity < initialCapacity)             capacity <<= 1;          this.loadFactor = loadFactor;         // 确定阈值         threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);         // 初始化hash表         table = new Entry[capacity];         useAltHashing = sun.misc.VM.isBooted()                 && (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);         init();     }

此构造函数为核心构造函数,其他构造函数最终都是调用此函数实现

2.5、核心函数

1、get()函数

/**      * Returns the value to which the specified key is mapped, or {@code null}      * if this map contains no mapping for the key.      */     // 返回值为null可能有两种情况:1不存在key-value对;2、key指向null     public V get(Object key) {         // 两种情况key==null和非null         if (key == null)             return getForNullKey();         Entry<K, V> entry = getEntry(key);          return null == entry ? null : entry.getValue();     }      private V getForNullKey() {         for (Entry<K, V> e = table[0]; e != null; e = e.next) {             if (e.key == null)                 return e.value;         }         return null;     }      final Entry<K, V> getEntry(Object key) {         // 先获取key对应的hash值,若key为null,则hash值为0         int hash = (key == null) ? 0 : hash(key);         // 获取table的index=hash&table.length-1         for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {             Object k;             // 判断是否为指定key的map对:1、hash值相等;2、key为同个对象或者值相等             if (e.hash == hash                     && ((k = e.key) == key || (key != null && key.equals(k))))                 return e;         }         return null;     }

2、put()函数

// 添加键值对,如果之前已存在,则覆盖之前的值     public V put(K key, V value) {         if (key == null)             return putForNullKey(value);         // 先获取key对应的hash值         int hash = hash(key);         // 然后获取hash值对应的index=hash&table.lenth-1         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;             }         } //如果索引处的Entry对象为null,则添加一个元素         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;     }     void addEntry(int hash, K key, V value, int bucketIndex) {         if ((size >= threshold) && (null != table[bucketIndex])) {             // 调整map的size             resize(2 * table.length);             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<K, V> e = table[bucketIndex]; //新添加的元素指向之前的元素         table[bucketIndex] = new Entry<>(hash, key, value, e);         size++;     }

说明:当HashMap添加元素时,如果key==null,则存放在table中0索引处,如果0索引出的链表中存在key==null的节点,则将此节点的值更新成最新值,如果不存在,则在链表的首部添加一个key为null的节点。如果key!=null,会首先调用hash()函数获取hash值,然后将调用indexFor函数获取存放table数组中的索引值;其中indexFor函数代码如下:

static int indexFor(int h, int length) { return h & (length-1); }

此处获取table数组index的方法设计较为巧妙:上面提到length必须为2的n此幂,因此在length大小合法的情况下值肯定是最高位为1其余低位为0,而length-1则为00..111…1的形式,再&h则可以保证所取的index一定是在table.length范围之内的。获取索引值后,对此索引出的链表遍历,如果链表中已经存在hash值相等切key相等则将原先的值覆盖,否则在链表的开头添加一个节点。其中在添加节点的时候会先判断table的大小有没有超过阈值且将要添加的table的index位置不为null,如果两者都满足,则调整table的大小重新获取索引值。

通过上面对put函数的分析,我们可以看出HashMap内部是使用数据+链表的数据结构保存数据的,数组中的每一个index位置都保存了一个链表。其中key==null的元素统一保存在数组索引为0的链表中,但是索引为0的链表中之多有一个节点,当第二次添加key==null的元素时会将之前的节点值覆盖;当key!=null时,通过对key的hash值运算得到索引,当hash值相等时索引的值也是相等的,当索引值相等,但是key不等的时候,就会在同一个索引位置添加多个元素,从而产生链表。另外在HashMap中存取元素都是使用hash值进行定位的,所以效率相对要高。

3、removeEntryForKey(Object key)函数

removeEntryForKey函数可以将指定key值的键值对删除,其代码如下:

final Entry<K,V> removeEntryForKey(Object key) { 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; }

删除键值对的步骤是:先找到键值对所在的table的index,然后用删除节点的方式删除键值对。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java爬坑系列

【Java入门提高篇】Day26 Java容器类详解(八)HashSet源码分析

  前面花了好几篇的篇幅把HashMap里里外外说了个遍,大家可能对于源码分析篇已经讳莫如深了。

714
来自专栏后端之路

使用HashMap的HashSet

背景 由于HashMap的源码我们已经分析过了原来你是这样的HashMap(1.7) 那么基于已经有的容器我们要如何做HashSet的实现呢? 以下我们将简单描...

2759
来自专栏互扯程序

Java集合深度解析之HashMap

HashMap简介 HashMap是基于哈希表实现的,每一个元素是一个key-value对,其内部通过单链表解决冲突问题,容量不足(超过了阀值)时,同样会自动增...

3415
来自专栏移动开发的那些事儿

数据结构?从HashMap的源码分析开始!

首先,先看下inflateTable方法,这个是初始化HashMap里面的线性表的空间:

581
来自专栏向治洪

从代码层读懂HashMap的实现原理

概述  Hashmap继承于AbstractMap,实现了Map、Cloneable、java.io.Serializable接口。它的key、value都可以...

2748
来自专栏编程札记

java之hashtable和hashmap

1475
来自专栏冰枫

JDK1.8 LinkedHashMap的实现原理

LinkedHashMap,顾名思义连接的HashMap,它继承了HashMap,HashMap为了避免碰撞,因此用拉链法解决冲突,读过HashMap源码的读者...

67213
来自专栏后端之路

原来你是这样的LinkedHashMap之简单缓存实现

本篇介绍一下LinkedHashMap 背景 开发者需要基于插入顺序的容器(很常见的需求),而hashMap是不支持这种操作的【hashMap的iterator...

1828
来自专栏移动开发面面观

HashTable,HashMap与ConcurrentHashMap源码分析

1125
来自专栏java工会

Java HashMap 简介与工作原理

20110

扫码关注云+社区