深入JDK源码之HashMap类

y37f 9年前

基于哈希表的 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链表。
深入JDK源码之HashMap类

// 默认的初始化大小      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;          }        }