源码分析（一）——HashMap（基于JDK1.6）

       Java最基本的数据结构有数组和链表。

       数组的特点是空间连续（大小固定）、寻址迅速，但是插入和删除时需要移动元素，所以查询快，增加删除慢。

       链表恰好相反，可动态增加或减少空间以适应新增和删除元素，但查找时只能顺着一个个节点查找，所以增加删除快，查找慢。

       有没有一种结构综合了数组和链表的优点呢？当然有，那就是哈希表（虽说是综合优点，但实际上查找肯定没有数组快，插入删除没有链表快，一种折中的方式吧）。

       HashMap的数据结构是由Entry链表组成的数组。

       

一、HashMap定义：

public class HashMap<K,V>

           extends AbstractMap<K,V>

           implements Map<K,V>, Cloneable, Serializable

从上述定义中可以看出：

1. HashMap是继承了AbstractMap类，

2. HashMap实现了Map接口。

3. HashMap实现了Cloneable接口，即实现clone()函数。它能被克隆。

4. HashMap实现了java.io.Serializable接口，可以被序列化。

5. HashMap支持泛型。

 

 

二、HashMap基本属性：

HashMap的基本属性包括：初始容量、最大容量、装载因子、存放数据的entry数组、map大小等。

     /**
      * 默认的初始容量，必须是2的幂
      */
     static final int DEFAULT_INITIAL_CAPACITY = 16;

     /**
      * 最大容量（必须是2的幂且小于2的30次方，传入容量过大将被这个值替换）
      */
     static final int MAXIMUM_CAPACITY = 1 << 30;
    /**
      * 默认装载因子，这个后面会做解释
      */
     static final float DEFAULT_LOAD_FACTOR = 0.75f;
     /**
      * 存储数据的Entry数组，长度是2的幂。看到数组的内容了，接着看数组中存的内容就明白为什么博文开头先复习数据结构了
      */
     transient Entry[] table;
     /**
      * map中保存的键值对的数量
      */
     transient int size;
     /**
      * 需要调整大小的极限值（容量*装载因子），即map容量阀值
      */
     int threshold;
     /**
      * 装载因子
      */
     final float loadFactor;
    /**
     * map结构被改变的次数
      */
     transient volatile int modCount;

 

 

三、HashMap构造方法：

1. 第一个构造方法（不带参数）：

    /**
     * 使用默认的容量及装载因子构造一个空的HashMap
     */
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);//计算下次需要调整大小的极限值
        table = new Entry[DEFAULT_INITIAL_CAPACITY];//根据默认容量（16）初始化table
        init();
    }

 

2. 第二个构造方法（带一个参数：初始容量）：

    /**
     * 根据指定容量创建一个空的HashMap
     */
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);//调用上面的构造方法，容量为指定的容量，装载因子是默认值
    }

 

 

3. 第三个构造方法（带两个参数指定初始容量和装载因子）：

   /**
     * 根据给定的初始容量的装载因子创建一个空的HashMap
     * 初始容量小于0或装载因子小于等于0将报异常 
     */
    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);
        int capacity = 1;
        //设置capacity为大于initialCapacity且是2的幂的最小值
        while (capacity < initialCapacity)
            capacity <<= 1;
        this.loadFactor = loadFactor;
        threshold = (int)(capacity * loadFactor);
        table = new Entry[capacity];
        init();
  }

 

 4. 第四个构造方法（传入一个已有的map）：

    /**
     * 通过传入的map创建一个HashMap，容量为默认容量（16）和(map.zise()/DEFAULT_LOAD_FACTORY)+1的较大者，装载因子为默认值
     */
    public HashMap(Map<? extends K, ? extends V> m) {
        this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                      DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
        putAllForCreate(m);
    }

 上面的构造方法中调用到了init()方法，最后一个方法还调用了putAllForCreate(Map<? extends K, ? extends V> m)。init方法是一个空方法，里面没有任何内容。putAllForCreate看方法名就是创建的时候将传入的map全部放入新创建的对象中。该方法中还涉及到其他方法，将在后面介绍。

 

 

四、HashMap的Entry内部类实现：

 static class Entry<K,V> implements Map.Entry<K,V> {
          final K key;
          V value;
          Entry<K,V> next;//对下一个节点的引用（看到链表的内容，结合定义的Entry数组，是不是想到了哈希表的拉链法实现？！）
          final int hash;//哈希值
  
          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;//返回的是之前的Value
        }
 
         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();
             // Key相等且Value相等则两个Entry相等
             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;
         }
         // hashCode是Key的hashCode和Value的hashCode的异或的结果
         public final int hashCode() {
             return (key==null   ? 0 : key.hashCode()) ^
                    (value==null ? 0 : value.hashCode());
         }
         // 重写toString方法，是输出更清晰
         public final String toString() {
             return getKey() + "=" + getValue();
         }
 
         /**
          *当调用put(k,v)方法存入键值对时，如果k已经存在，则该方法被调用（为什么没有内容？）
          */
         void recordAccess(HashMap<K,V> m) {
         }
 
         /**
          * 当Entry被从HashMap中移除时被调用（为什么没有内容？）
          */
         void recordRemoval(HashMap<K,V> m) {
         }
  }

（说明：一般一个类的基本方法，包括：构造方法、equals方法、hashcode方法、toString方法）

 

 

五、HashMap的put()方法：

 public V put(K key, V value) {
          if (key == null)
              return putForNullKey(value);
          int hash = hash(key.hashCode());
          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;
             }
         }
 
         modCount++;
         addEntry(hash, key, value, i);
         return null;
    }

  当存入的key是null的时候将调用putForNUllKey方法，暂时将这段逻辑放一边，看key不为null的情况。先调用了hash(int h)方法获取了一个hash值。 

hash()：

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

 

然后调用indexFor方法返回hash值和table数组长度减1的与运算结果。

为什么使用的是length-1？因为这样可以保证结果的最大值是length-1，不会产生数组越界问题。

indexFor()：

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

 获取索引位置之后做了什么？探测table[i]所在的链表，所发现key值与传入的key值相同的对象，则替换并返回oldValue。若找不到，则通过addEntry(hash,key,value,i)添加新的对象。来看addEntry(hash,key,value,i)：

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

这就是在一个链表头部插入一个节点的过程。获取table[i]的对象e，将table[i]的对象修改为新增对象，让新增对象的next指向e。之后判断size是否到达了需要扩充table数组容量的界限并让size自增1，如果达到了则调用resize(int capacity)方法将数组容量拓展为原来的两倍。

resize()：

 void resize(int newCapacity) {
          Entry[] oldTable = table;
          int oldCapacity = oldTable.length;
         // 这个if块表明，如果容量已经到达允许的最大值，即MAXIMUN_CAPACITY，则不再拓展容量，而将装载拓展的界限值设为计算机允许的最大值。
          // 不会再触发resize方法，而是不断的向map中添加内容，即table数组中的链表可以不断变长，但数组长度不再改变
          if (oldCapacity == MAXIMUM_CAPACITY) {
              threshold = Integer.MAX_VALUE;
              return;
          }
         // 创建新数组，容量为指定的容量
         Entry[] newTable = new Entry[newCapacity];
         transfer(newTable);
         table = newTable;
         // 设置下一次需要调整数组大小的界限
         threshold = (int)(newCapacity * loadFactor);
   }

 transfer()：

  void transfer(Entry[] newTable) {
          // 保留原数组的引用到src中，
          Entry[] src = table;
          // 新容量使新数组的长度
          int newCapacity = newTable.length;
          // 遍历原数组
          for (int j = 0; j < src.length; j++) {
              // 获取元素e
              Entry<K,V> e = src[j];
             if (e != null) {
                 // 将原数组中的元素置为null
                 src[j] = null;
                 // 遍历原数组中j位置指向的链表
                 do {
                     Entry<K,V> next = e.next;
                     // 根据新的容量计算e在新数组中的位置
                     int i = indexFor(e.hash, newCapacity);
                     // 将e插入到newTable[i]指向的链表的头部
                     e.next = newTable[i];
                     newTable[i] = e;
                     e = next;
                 } while (e != null);
             }
        }
   }

 

 

 七、HashMap的putAll()方法： 

public void putAll(Map<? extends K, ? extends V> m) {
          int numKeysToBeAdded = m.size();
          if (numKeysToBeAdded == 0)
              return;
         if (numKeysToBeAdded > threshold) {
             int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
             if (targetCapacity > MAXIMUM_CAPACITY)
                 targetCapacity = MAXIMUM_CAPACITY;
             int newCapacity = table.length;
             while (newCapacity < targetCapacity)
                 newCapacity <<= 1;
             if (newCapacity > table.length)
                 resize(newCapacity);
        }
 
         for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {
             Map.Entry<? extends K, ? extends V> e = i.next();
             put(e.getKey(), e.getValue());
         }
    }

 putForNullKey()：

  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;
   }

这是一个私有方法，在put方法中被调用。它首先遍历table数组，如果找到key为null的元素，则替换元素值并返回oldValue；否则通过addEntry方法添加元素，之后返回null。

 

 putAllForCreate()：

 private void putAllForCreate(Map<? extends K, ? extends V> m) {
         for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i =      
                        m.entrySet().iterator(); i.hasNext(); ) {
             Map.Entry<? extends K, ? extends V> e = i.next();
             putForCreate(e.getKey(), e.getValue());
         }
 }

 只是调用putForCreate方法逐个元素加入。

putForCreate()：

 private void putForCreate(K key, V value) {
         int hash = (key == null) ? 0 : hash(key.hashCode());
         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 != null && key.equals(k)))) {
                 e.value = value;
                 return;
             }
         }
         createEntry(hash, key, value, i);
     }

 该方法先计算需要添加的元素的hash值和在table数组中的索引i。接着遍历table[i]的链表，若有元素的key值与传入key值相等，则替换value，结束方法。若不存在key值相同的元素，则调用createEntry创建并添加元素。

 createEntry()：

 void createEntry(int hash, K key, V value, int bucketIndex) {

      Entry<K,V> e = table[bucketIndex];

      table[bucketIndex] = new Entry<K,V>(hash, key, value, e);

      size++;

 }

 

 

八、HashMap的get()方法：  

public V get(Object key) {
         if (key == null)
             return getForNullKey();
         int hash = hash(key.hashCode());
         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.equals(k)))
                 return e.value;
         }
         return null;
    }

该方法分为key为null和不为null两块。先看不为null的情况。先获取key的hash值，之后通过hash值及table.length获取key对应的table数组的索引，遍历索引的链表，所找到key相同的元素，则返回元素的value，否者返回null。不为null的情况调用了getForNullKey()方法。

getForNullKey()：

 private V getForNullKey() {
         for (Entry<K,V> e = table[0]; e != null; e = e.next) {
             if (e.key == null)
                 return e.value;
         }
         return null;
  }

  

 

 九、HashMap判断key或value是否存在的方法：

 HashMap没有提供判断元素是否存在的方法，只提供了判断Key是否存在及Value是否存在的方法，分别是containsKey(Object key)、containsValue(Object value)。

containsKey()：

  public boolean containsKey(Object key) {
          return getEntry(key) != null;
  }
 final Entry<K,V> getEntry(Object key) {
          int hash = (key == null) ? 0 : hash(key.hashCode());
          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;
  }

containsKey(Object key)方法很简单，只是判断getEntry(key)的结果是否为null，是则返回false，否返回true。

getEntry(Object key)也没什么内容，只是根据key对应的hash值计算在table数组中的索引位置，然后遍历该链表判断是否存在相同的key值。

 containsValue()：

  public boolean containsValue(Object value) {
      if (value == null)
              return containsNullValue();
  
      Entry[] tab = table;
          for (int i = 0; i < tab.length ; i++)
              for (Entry e = tab[i] ; e != null ; e = e.next)
                  if (value.equals(e.value))
                      return true;
     return false;
  }

 private boolean containsNullValue() {
     Entry[] tab = table;
         for (int i = 0; i < tab.length ; i++)
             for (Entry e = tab[i] ; e != null ; e = e.next)
                 if (e.value == null)
                     return true;
     return false;
 }

判断一个value是否存在比判断key是否存在还要简单，就是遍历所有元素判断是否有相等的值。这里分为两种情况处理，value为null何不为null的情况，但内容差不多，只是判断相等的方式不同。

这个判断是否存在必须遍历所有元素，是一个双重循环的过程，因此是比较耗时的操作。

 

 

十、HashMap删除元素方法：

HashMap中“删除”相关的操作，有remove(Object key)和clear()两个方法。

1. remove()： 

public V remove(Object key) {

    Entry<K,V> e = removeEntryForKey(key);

    return (e == null ? null : e.value);

}

 

2. removeEntryForKey()：

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;

}

上面的这个过程就是先找到table数组中对应的索引，接着就类似于一般的链表的删除操作，而且是单向链表删除节点，很简单。

 clear()：

 public void clear() {
         modCount++;
         Entry[] tab = table;
        for (int i = 0; i < tab.length; i++)
             tab[i] = null;
         size = 0;
     }

clear()方法删除HashMap中所有的元素，这里就不用一个个删除节点了，而是直接将table数组内容都置空，这样所有的链表都已经无法访问，Java的垃圾回收机制会去处理这些链表。table数组置空后修改size为0。

 

 

十一、HashMap的3种集合：

1. keySet()：获取HashMap所有key的集合。 

public Set<K> keySet() {
      Set<K> ks = keySet;
      return (ks != null ? ks : (keySet = new KeySet()));
}

 

2. values()：获取HashMap所有value的集合。 

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();
         }
 }

 

3. entrySet()：获取所有的key-value集合。

     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();

}

    }

 

十二、与HashTable的异同：

与HashMap数据结构类似的，还有HashTable。

相同点：

1. 数据整体结构：都是Entry类链表组成的数组。

2. 实现接口：都实现了Map接口。

3. 判断元素是否存在的方法：都有判断元素是否被包含的方法。

4. 默认装载因子：都为0.75。

 

不同点：

1. 线程安全性：HashMap是HashTable的轻量级实现，HashMap是非线程安全的（异步的），而HashTable是线程安全的（同步的）。

2. 对key为null的限制：HashMap允许存储一个key为null的元素，而HashTable不允许存储key为null的元素。

3. 数组默认大小不同：HashMap默认大小为16，而HashTable默认大小为11。

4. 遍历元素方法不同：HashMap使用Iterator迭代器接口实现，而HashTable使用的是Enumeration接口实现。

5. 数组容量增长方式不同：HashMap增长为原来的2倍，HashTable增长为原来值 * 2 +1。

 

 

 

在JDK1.8中HashMap的put方法执行过程：

①.判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；

②.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③；

③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals；

④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；

⑤.遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；

⑥.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。