深入JDK源码之HashMap类

基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作,并允许使用 null 值和 null 键。(除了非同步和允许使用 null 之外,HashMap 类与 Hashtable 大致相同。)此类不保证映射的顺序,特别是它不保证该顺序恒久不变。

此实现假定哈希函数将元素适当地分布在各桶之间,可为基本操作(get 和 put)提供稳定的性能。迭代 collection 视图所需的时间与 HashMap 实例的“容量”(桶的数量)及其大小(键-值映射关系数)成比例。所以,如果迭代性能很重要,则不要将初始容量设置得太高(或将加载因子设置得太低)。

HashMap的实例有两个参数影响其性能:初始容量加载因子容量是哈希表中桶的数量,初始容量只是哈希表在创建时的容量。加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时,则要对该哈希表进行 rehash 操作(即重建内部数据结构),从而哈希表将具有大约两倍的桶数。

通常,默认加载因子 (0.75) 在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销,但同时也增加了查询成本(在大多数 HashMap 类的操作中,包括 get 和 put 操作,都反映了这一点)。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子,以便最大限度地减少 rehash 操作次数。如果初始容量大于最大条目数除以加载因子,则不会发生 rehash 操作。

如果很多映射关系要存储在 HashMap 实例中,则相对于按需执行自动的 rehash 操作以增大表的容量来说,使用足够大的初始容量创建它将使得映射关系能更有效地存储。

HashMap的数据结构

HashMap用了一个名字为table的Entry类型数组;数组中的每一项又是一个Entry链表。 在此输入图片描述

// 默认的初始化大小
  static final int DEFAULT_INITIAL_CAPACITY = 16;
  // 最大的容量
  static final int MAXIMUM_CAPACITY = 1 << 30;
  // 负载因子
  static final float DEFAULT_LOAD_FACTOR = 0.75f;
  // 储存key-value键值对的数组,一个键值对对象映射一个Entry对象
  transient Entry[] table;
  // 键值对的数目
  transient int size;
  // 调整HashMap大小门槛,该变量包含了HashMap能容纳的key-value对的极限,它的值等于HashMap的容量乘以负载因子
  int threshold;
  // 加载因子
  final float loadFactor;
  // HashMap结构修改次数,防止在遍历时,有其他的线程在进行修改
  transient volatile int modCount;
  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
      int capacity = 1;
      // 使得capacity 的大小为2的幂,至于为什么,请看下面
      while (capacity < initialCapacity)
          capacity <<= 1;
 
      this.loadFactor = loadFactor;
      threshold = (int) (capacity * loadFactor);
      table = new Entry[capacity];
      init();
  }

 

下面是用于包装key-value映射关系的Entry,它是HashMap的静态内部类:

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

 

HashMap的put和get及remove方法

// 根据key获取value
  public V get(Object key) {
      if (key == null)
          return getForNullKey();
      //根据key的hashCode值计算它的hash码
      int hash = hash(key.hashCode());
      //直接取出table数组中指定索引处的值
      for (Entry<K, V> e = table[indexFor(hash, table.length)];
      e != null;
      //搜索该Entry链的下一个Entry
      e = e.next) {
          Object k;
          //如果该Entry的key与被搜索key相同
          if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
              return e.value;
      }
      return null;
  }
 
  private V getForNullKey() {
      //key为null,hash码为0,也就是说key为null的Entry位于table[0]的Entry链上
      for (Entry<K, V> e = table[0]; e != null; e = e.next) {
          if (e.key == null)
              return e.value;
      }
      return null;
  }
  public V put(K key, V value) {
      if (key == null)
          return putForNullKey(value);
      //根据key的hashCode值计算它的hash码
      int hash = hash(key.hashCode());
      //搜索指定hash值对应table中的索引值
      int i = indexFor(hash, table.length);
      for (Entry<K, V> e = table[i]; e != null; e = e.next) {
          Object k;
          //如果找到指定key与需要放入的key相等(hash值相同,通过equals比较返回true)
          if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
              V oldValue = e.value;
              //新的值覆盖旧值
              e.value = value;
              //这个方法是个空方法,可能是表示个标记,字面意思是表示记录访问
              e.recordAccess(this);
              //返回旧值
              return oldValue;
          }
      }
 
      modCount++;
      //如果i处索引处的Entry为null,表示此处还没有Entry
      //将key、value添加到i索引处
      addEntry(hash, key, value, i);
      return null;
  }
 
  //key=null的键值对,默认存放table[0]的Entry链
  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) {
      Entry<K, V> e = table[bucketIndex];
      table[bucketIndex] = new Entry<K, V>(hash, key, value, e);
      if (size++ >= threshold)
          resize(2 * table.length);
  }
  //根据键值移除key-value映射对象
  public V remove(Object key) {
      Entry<K, V> e = removeEntryForKey(key);
      return (e == null ? null : e.value);
  }
 
  final Entry<K, V> removeEntryForKey(Object key) {
      int hash = (key == null) ? 0 : hash(key.hashCode());
      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;
  }

 

HashMap的hash算法和size大小调整

static int hash(int h) {//这里不是很懂,得向他人请教
        // 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);
    }
 
    /**
     * Returns index for hash code h.
     */
    // 根据hash码求的数组小标并返回,当length为2的幂时,h & (length-1)等价于h%(length-1),这里也就是为什么前面说table的长度必须是2的幂
    static int indexFor(int h, int length) {
        return h & (length - 1);
    }
    // 调整大小
    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);
        table = newTable;
        threshold = (int) (newCapacity * loadFactor);
    }
 
    /**
     * Transfers all entries from current table to newTable.
     */
    void transfer(Entry[] newTable) {
        Entry[] src = table;
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) {
            Entry<K, V> e = src[j];
            if (e != null) {
                src[j] = null;
                do {   
                                        //注意这里哈,HashMap不保证顺序恒久不变
                                        //在这里可以找到答案
                    Entry<K, V> next = e.next;
                    int i = indexFor(e.hash, newCapacity);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                } while (e != null);
            }
        }
    }

 

HashMap与Set的关系

Set代表一种集合元素无序、集合元素不可重复的集合。如果只考察HashMap中的key,不难发现集合中的key有一个特征:所有的key不能重复,key之间无序。具备了Set的特征,所有的key集合起来组成一个Set集合。同理所有的Entry集合起来,也是一个Set集合。而value是可以重复的,不能组成一个Set集合,在HashMap源代码中提供了values()方法把value集合起来组成Collection集合。

private abstract class HashIterator<E> implements Iterator<E> {
       Entry<K, V> next; // next entry to return
       int expectedModCount; // For fast-fail
       int index; // current slot
       Entry<K, V> current; // current entry
 
       HashIterator() {
           expectedModCount = modCount;
           if (size > 0) { // advance to first entry
               Entry[] t = table;
               while (index < t.length && (next = t[index++]) == null)
                   ;
           }
       }
 
       public final boolean hasNext() {
           return next != null;
       }
 
       final Entry<K, V> nextEntry() {
           if (modCount != expectedModCount)
               throw new ConcurrentModificationException();
           Entry<K, V> e = next;
           if (e == null)
               throw new NoSuchElementException();
 
           if ((next = e.next) == null) {
               Entry[] t = table;
               while (index < t.length && (next = t[index++]) == null)
                   ;
           }
           current = e;
           return e;
       }
 
       public void remove() {
           if (current == null)
               throw new IllegalStateException();
           if (modCount != expectedModCount)
               throw new ConcurrentModificationException();
           Object k = current.key;
           current = null;
           HashMap.this.removeEntryForKey(k);
           expectedModCount = modCount;
       }
 
   }
    private final class ValueIterator extends HashIterator<V> {
       public V next() {
           return nextEntry().value;
       }
   }
 
   private final class KeyIterator extends HashIterator<K> {
       public K next() {
           return nextEntry().getKey();
       }
   }
 
   private final class EntryIterator extends HashIterator<Map.Entry<K, V>> {
       public Map.Entry<K, V> next() {
           return nextEntry();
       }
   }
   Iterator<K> newKeyIterator() {
       return new KeyIterator();
   }
   Iterator<V> newValueIterator() {
       return new ValueIterator();
   }
   Iterator<Map.Entry<K, V>> newEntryIterator() {
       return new EntryIterator();
   }
   // Views
 
   private transient Set<Map.Entry<K, V>> entrySet = null;
    //把所有的key集合成Set集合
   public Set<K> keySet() {
       Set<K> ks = keySet;
       return (ks != null ? ks : (keySet = new KeySet()));
   }
 
   private final class KeySet extends AbstractSet<K> {
       public Iterator<K> iterator() {
           return newKeyIterator();
       }
 
       public int size() {
           return size;
       }
 
       public boolean contains(Object o) {
           return containsKey(o);
       }
 
       public boolean remove(Object o) {
           return HashMap.this.removeEntryForKey(o) != null;
       }
 
       public void clear() {
           HashMap.this.clear();
       }
   }
   //把所有的values集合成Collection集合
   public Collection<V> values() {
       Collection<V> vs = values;
       return (vs != null ? vs : (values = new Values()));
   }
 
   private final class Values extends AbstractCollection<V> {
       public Iterator<V> iterator() {
           return newValueIterator();
       }
       public int size() {
           return size;
       }
       public boolean contains(Object o) {
           return containsValue(o);
       }
 
       public void clear() {
           HashMap.this.clear();
       }
   }
     //把所有的Entry对象集合成Set集合
   public Set<Map.Entry<K, V>> entrySet() {
       return entrySet0();
   }
 
   private Set<Map.Entry<K, V>> entrySet0() {
       Set<Map.Entry<K, V>> es = entrySet;
       return es != null ? es : (entrySet = new EntrySet());
   }
 
   private final class EntrySet extends AbstractSet<Map.Entry<K, V>> {
       public Iterator<Map.Entry<K, V>> iterator() {
           return newEntryIterator();
       }
       public boolean contains(Object o) {
           if (!(o instanceof Map.Entry))
               return false;
           Map.Entry<K, V> e = (Map.Entry<K, V>) o;
           Entry<K, V> candidate = getEntry(e.getKey());
           return candidate != null && candidate.equals(e);
       }
       public boolean remove(Object o) {
           return removeMapping(o) != null;
       }
       public int size() {
           return size;
       }
       public void clear() {
           HashMap.this.clear();
       }
   }

 

Fail-Fast策略(速错)

HashMap不是线程安全的,因此如果在使用迭代器的过程中有其他线程修改了map,那么将抛ConcurrentModificationException,这就是所谓fail-fast策略(速错),这一策略在源码中的实现是通过modCount域,modCount顾名思义就是修改次数,对HashMap内容的修改都将增加这个值,那么在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount。在迭代过程中,判断modCount跟expectedModCount是否相等,如果不相等就表示已经有其他线程修改了。

private abstract class HashIterator<E> implements Iterator<E> {
       Entry<K, V> next; // next entry to return
       int expectedModCount; // For fast-fail
       int index; // current slot
       Entry<K, V> current; // current entry
 
       HashIterator() {
           expectedModCount = modCount;
           if (size > 0) { // advance to first entry
               Entry[] t = table;
               while (index < t.length && (next = t[index++]) == null)
                   ;
           }
       }
 
       public final boolean hasNext() {
           return next != null;
       }
 
       final Entry<K, V> nextEntry() {
           if (modCount != expectedModCount)
               throw new ConcurrentModificationException();
           Entry<K, V> e = next;
           if (e == null)
               throw new NoSuchElementException();
 
           if ((next = e.next) == null) {
               Entry[] t = table;
               while (index < t.length && (next = t[index++]) == null)
                   ;
           }
           current = e;
           return e;
       }
 
       public void remove() {
           if (current == null)
               throw new IllegalStateException();
           if (modCount != expectedModCount)
               throw new ConcurrentModificationException();
           Object k = current.key;
           current = null;
           HashMap.this.removeEntryForKey(k);
           expectedModCount = modCount;
       }
 
   }

 

共有 0 条评论

 Top