最代码广告位
kaka的gravatar头像
kaka2014-06-03 13:59:02

通过java HashMap的存取方式来学习Hash存储机制

最近重新开始看一遍java基础,从源码读起,坚持把自己在阅读中的总结分享上来。下面是HashMap的一些总结。

HashMap的构造方法:

无参构造方法:会使用默认的初始容量和加载因子初始化map,默认初始化大小是16,加载因子0.75f

当哈希表中的条目数超出了加载因子与当前容量的乘积时,则要对该哈希表进行 rehash 操作(即重建内部数据结构),从而哈希表将具有大约两倍的桶数。

 /**
  * The default initial capacity - MUST be a power of two.
  */
 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
 /**
  * The load factor used when none specified in constructor.
  */
 static final float DEFAULT_LOAD_FACTOR = 0.75f;
 public HashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
 }

自定义初始化大小

  /**
     * 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 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;
        threshold = initialCapacity;
        init();
    }

总结:当 创建 HashMap 时,有一个默认的负载因子(load factor),其默认值为 0.75,这是时间和空间成本上一种折衷:增大负载因子可以减少 Hash 表(就是那个 Entry 数组)所占用的内存空间,但会增加查询数据的时间开销,而查询是最频繁的的操作(HashMap 的 get() 与 put() 方法都要用到查询);减小负载因子会提高数据查询的性能,但会增加 Hash 表所占用的内存空间。我们可以在创建 HashMap 时根据实际需要适当地调整 load factor 的值;如果程序比较关心空间开销、内存比较紧张,可以适当地增加负载因子;如果程序比较关心时间开销,内存比较宽裕则可以适当的减少负载因子。通常情况 下,无需改变负载因子的值。

 

HashMap最常用的put方法,代码如下:

 

 /**
     * 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) {
        //如果数组为空,初始化
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        //如果key为空,则调用putForNullKey进行处理
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);//计算key的hashcode值
        int i = indexFor(hash, table.length);//计算key在hash表中的索引,此处的table是一个Entry<k,v>数组
        //遍历数组,比较Entry是否一致(hash值相等,即在hash表中的同一位置),并且key值相等,则直接用新的value替换旧的value并返回value,key值不用替换。如果不满足条件,则将key和value添加到i索引处
        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++;
       //将key和value添加到i索引处
        addEntry(hash, key, value, i);
        return null;
    }

上面的put方法中用到了一个重要的内部类HashMap$Entry,每个 Entry 其实就是一个 key-value 对。从上面程序中可以看出:当系统决定存储 HashMap 中的 key-value 对时,完全没有考虑 Entry 中的 value,仅仅只是根据 key 来计算并决定每个 Entry 的存储位置。当决定了 key 的存储位置之后,value 随之保存在那里即可,Entry源码如下:

 static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;//key值
        V value;//value值
        Entry<K,V> next;//Entry链指向
        int hash;//key的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 Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
        }

        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) {
        }
    }

put方法中调用了一个计算Hash码的方法hash()来返回key的哈希码,这个方法是一个纯粹的数学计算,其方法如下:

  final int hash(Object k) {
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }

        h ^= k.hashCode();

        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }
 

对于任意给定的对象,只要它的 hashCode() 返回值相同,那么程序调用 hash(int h) 方法所计算得到的 Hash 码值总是相同的。接下来程序会调用 indexFor(int h, int length) 方法来计算该对象应该保存在 table 数组的哪个索引处。indexFor(int h, int length) 方法的代码如下:

//h为key的hash值,length为数组的长度
static int indexFor(int h, int length) 
{ 
    return h & (length-1); 
}

 

这个方法非常巧妙,它总是通过 h &(table.length -1) 来得到该对象的保存位置,而HashMap底层数组的长度总是2的n次方,这一点可参看前面关于HashMap构造器的介绍。

当length总是2的倍数时,h&(length-1)将是一个非常巧妙的设计:假设 h=5,length=16, 那么h&(length - 1) 将得到5;如果h=6,length=16, 那么h&(length - 1)将得到6 ;如果h=15,length=16, 那么h&(length - 1)将得到15;但是当h=16时 ,length=16时,那么h&(length - 1)将得到0了;当 h=17 时 , length=16 时,那么h&(length - 1) 将得到1了……这样保证计算得到的索引值总是位于 table 数组的索引之内。

从put 方法的源代码可以看出,当程序试图将一个 key-value 对放入 HashMap 中时,程序首先根据该 key 的 hashCode() 返回值决定该 Entry 的存储位置:如果两个 Entry 的 key 的 hashCode() 返回值相同,那它们的存储位置相同。存储位置相同会分为两种情况:

(1).如果这两个 Entry 的 key 通过 equals 比较返回 true,新添加 Entry 的 value 将覆盖集合中原有 Entry 的 value,但 key 不会覆盖。

(2).如果这两个 Entry 的 key 通过 equals 比较返回 false,新添加的 Entry 将与集合中原有 Entry 形成 Entry 链,而且新添加的 Entry 位于 Entry 链的头部——具体说明继续看 addEntry() 方法的说明。

存储位置不同,则将key和value直接添加到i索引处。

addEntyr方法,源码如下:

   void addEntry(int hash, K key, V value, int bucketIndex) {
       //如果容量大于阈值,并且索引bucketIndex处的元素不为空       
       if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);//扩容为原来数组长度的两倍
            hash = (null != key) ? hash(key) : 0;//重新计算key的hash值
            bucketIndex = indexFor(hash, table.length);//重新计算元素在新table中的索引
        }
        //创建新的entry对象并放到table的bucketIndex索引处,并让新的entry指向原来的entry
        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++;
    }

上面createEntry方法包含了一个非常优雅的设计:总是将新添加的 Entry 对象放入 table 数组的 bucketIndex 索引处——如果 bucketIndex 索引处已经有了一个 Entry 对象,那新添加的 Entry 对象指向原有的 Entry 对象(产生一个 Entry 链),如果 bucketIndex 索引处没有 Entry 对象,上面程序 e 变量是 null,也就是新放入的 Entry 对象指向 null,也就是Entry内部类中的next属性为null,也就是没有产生 Entry 链。,可以对比Entry类看。

解释几个名词:

桶:对 于 HashMap 及其子类而言,它们采用 Hash 算法来决定集合中元素的存储位置。当开始初始化 HashMap 时,会创建一个长度为 capacity 的 Entry 数组,这个数组里可以存储元素的位置被称为“桶(bucket)”,每个 bucket 都有其指定索引,系统可以根据其索引快速访问该 bucket 里存储的元素。

Entry链:无论何时,HashMap 的每个“桶”只存储一个元素(也就是一个 Entry),由于 Entry 对象可以包含一个引用变量(就是 Entry 构造器的的最后一个参数next)用于指向下一个 Entry,因此可能出现的情况是:HashMap 的 bucket 中只有一个 Entry,但这个 Entry 指向另一个 Entry ——这就形成了一个 Entry 链。下图为我简单的画了一个HashMap的存储结构:

HashMap存储结构图

通过java HashMap的存取方式来学习Hash存储机制

HashMap最常用的get方法,源码如下:

 public V get(Object key) {
      //如果key为null,则调用getForNullKey获得value
      if (key == null)
          return getForNullKey();
      //否则调用getEntry方法
      Entry<K,V> entry = getEntry(key);

      return null == entry ? null : entry.getValue();
 }
   
 final Entry<K,V> getEntry(Object key) {
        if (size == 0) {
            return null;
        }
        //计算key的hash值
        int hash = (key == null) ? 0 : hash(key);
        //直接通过key的hash值获取该Entry在数组中的下标,从而获取该Entry对象并遍历entry链,直到找到相等的key,然后取出该key对应的value。
        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 != null && key.equals(k))))
                return e;
        }
        return null;
 }

从上面代码中可以看出,如果 HashMap 的每个 bucket 里只有一个 Entry 时,HashMap 可以根据索引、快速地取出该 bucket 里的 Entry;在发生“Hash 冲突”的情况下,单个 bucket 里存储的不是一个 Entry,而是一个 Entry 链,只能按顺序遍历每个 Entry,直到找到想搜索的 Entry 为止——如果恰好要搜索的 Entry 位于该 Entry 链的最末端(该 Entry 是最早放入该 bucket 中),那必须循环到最后才能找到该元素。所以,当 HashMap 的每个 bucket 里存储的 Entry 只是单个 Entry ,也就是没有通过指针产生 Entry 链时,此时的 HashMap 具有最好的性能:当程序通过 key 取出对应 value 时,只要先计算出该 key 的 hashCode() 返回值,在根据该 hashCode 返回值找出该 key 在 table 数组中的索引,然后取出该索引处的 Entry,最后返回该 key 对应的 value 即可。


最代码官方编辑于2016-10-28 9:35:02


打赏

顶部客服微信二维码底部
>扫描二维码关注最代码为好友扫描二维码关注最代码为好友