HashMap源码学习及总结

前言
平时经常使用HashMap，也大致了解它的数据结构，但是一直没有一窥究竟，今天正好有时间看了下源码（确实有很多自己不懂以及可学习的地方），现在简单做些笔记

1.HashMap的数据结构


上图大致描绘了HashMap的数据结构，其基本算法如下：
当我们把一个元素a放入HashMap时，首先获取a的hashCode，然后通过hash算法得到哈希值k，最后把k散列到数组位置i上，如果该位置为空则直接插入，否则遍历这个位置上的链表(若找到相同的节点(equals方法）则更新节点，否则插入)


2.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);

     // capacity（数组容量）总是为2的幂次方，如果你传入的initialCapacity为17，capacity会被初始化为32
     int capacity = 1;
     while (capacity < initialCapacity)            
          capacity <<= 1;

     this.loadFactor = loadFactor;
     // 阀值 = 容量 * 负载因子（当map中元素个数超过阀值时，会自动做一次扩容以及rehash）
     threshold = (int)(capacity * loadFactor);
     table = new Entry[capacity];
     init();
}

public HashMap() {
     // 默认负载因子为0.75
     this.loadFactor = DEFAULT_LOAD_FACTOR;
     // 默认阀值为 12 （16*0.75） 
     threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); 
     // 默认容量为16
     table = new Entry[DEFAULT_INITIAL_CAPACITY]; 
     init();
}

3.HashMap中put方法的实现

public V put(K key, V value) {
     if (key == null)
          return putForNullKey(value);
     // 下面两步通过hash得到key，并散列到数组位置i上
     int hash = hash(key.hashCode());
     int i = indexFor(hash, table.length);
    
     // 循环遍历下标为i的链表
     for (Entry<K,V> e = table[i]; e != null; e = e.next) {
          Object k;
          // 若当前key在链表中存在，则update value
          if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
               V oldValue = e.value;
               e.value = value;
               e.recordAccess(this);
               return oldValue;  // return oldValue
          }
     }

     // 若当前key在链表中不存在，则插入
     modCount++;
     addEntry(hash, key, value, i);
     return null;
}

我们再看下addEntry方法：

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);
     // 如果此时元素个数达到map的阀值，则resize->rehash
     if (size++ >= threshold)
          resize(2 * table.length);
}

void resize(int newCapacity) {
     Entry[] oldTable = table;
     int oldCapacity = oldTable.length;
     // 若原来数组容量已经为MAXIMUM_CAPACITY，则此次仅仅扩大容量至Integer.MAX_VALUE，而不做rehash
     if (oldCapacity == MAXIMUM_CAPACITY) {
          threshold = Integer.MAX_VALUE;
          return;
     }
    
     Entry[] newTable = new Entry[newCapacity];
     // rehash
     transfer(newTable);
     table = newTable;
     // 重新计算map的阀值
     threshold = (int)(newCapacity * loadFactor);
}

最后看一下传说中的rehash

void transfer(Entry[] newTable) {
     // newTable是新的数组(扩容过)，src是老的数组
     Entry[] src = table;
     int newCapacity = newTable.length;
     // 循环每个数组下表所对应的链表做rehash
     for (int j = 0; j < src.length; j++) {
          Entry<K,V> e = src[j];
          if (e != null) {
               src[j] = null;
               do {
                    Entry<K,V> next = e.next;
                    int i = indexFor(e.hash, newCapacity);
                    e.next = newTable[i]; // 链表插入总是插在链表头
                    newTable[i] = e;
                    e = next;
               } while (e != null);
          }
     }
}

4.HashMap中的get方法

public V get(Object key) {
     if (key == null)
          return getForNullKey();
     // 通过hash得到key在数组中index，然后循环遍历
     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;
}

5.简单总结：
1.capacity：table容量，它的值总是2的幂次方，所以即使你设置初始化容量为17，它的也会自动扩容到32；
2.threshold：HashMap中元素个数阀值，当超过这个阀值的时候，HashMap会自动扩容一倍，然后对其中的元素做一次rehash，所以为了避免HashMap反复的做rehash（这个严重会影响hashmap的性能），我们应该在使用前给出一个合理的初始容量（通常这个又是很难做到的）；
3.loadFactor：负载因子，刚才我说了阀值threshold的作用，但是这个值是如何确定的呢，它等于：capacity * loadFactor;
4.hashCode方法与equals方法：通常我们看到一些文章都会说，如果你重写了equals方法一定也要重写hashCode方法，反之亦然，但是为什么要这样呢？ 其实我觉的这两个方法本身没有多大的关系，但是因为Set，Map这些集合的关系，这两个方法被紧密的绑定在一起；在Set和Map集合中，当我们判断两个key或者两个元素是否相同的时候，首先比较它们的hashcode值是否相同，若不相同，则判定这两个元素不相同，否则再进行equals方法的比较；若重写了equals方法而未重写hashcode方法，那么即使你认为是相同的元素对于Set和Map来讲也是不同的，并且当你设计一些公用类的时候，你无法预测别人是否会将这些类作为元素放入Set和Map中，所以建议最好重写hashCode和equals方法；
5. 遗留问题：代码中一些java关键字的学习；hash算法；一些内部类譬如EntrySet