深入淺析java 中HashMap的實(shí)現(xiàn)原理

 /**

   * The table, resized as necessary. Length MUST Always be a power of two.

   */
    transient Entry[] table;

// 存儲(chǔ)時(shí):
int hash = key.hashCode(); // 這個(gè)hashCode方法這里不詳述,只要理解每個(gè)key的hash是一個(gè)固定的int值
int index = hash % Entry[].length;
Entry[index] = value;

// 取值時(shí):
int hash = key.hashCode();
int index = hash % Entry[].length;
return Entry[index];

 public V put(K key, V value) {

    if (key == null)

      return putForNullKey(value); //null總是放在數(shù)組的第一個(gè)鏈表中

    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;

      //如果key在鏈表中已存在，則替換為新value

      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;

  }

 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);//參數(shù)e, 是Entry.next

  //如果size超過threshold，則擴(kuò)充table大小。再散列

  if (size++ >= threshold)

      resize(2 * table.length);

}

public V get(Object key) {

    if (key == null)

      return getForNullKey();

    int hash = hash(key.hashCode());

    //先定位到數(shù)組元素，再遍歷該元素處的鏈表

    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;

}

 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;

  }

 


  private V getForNullKey() {

    for (Entry<K,V> e = table[0]; e != null; e = e.next) {

      if (e.key == null)

        return e.value;

    }

    return null;

  } 

 /**

   * Returns index for hash code h.

   */

  static int indexFor(int h, int length) {

    return h & (length-1);

  }

 public HashMap(int initialCapacity, float loadFactor) {

    ..... 


    // Find a power of 2 >= initialCapacity 

    int capacity = 1;

    while (capacity < initialCapacity)

      capacity <<= 1;


    this.loadFactor = loadFactor;

    threshold = (int)(capacity * loadFactor);

    table = new Entry[capacity];

    init();

  } 

  /**

   * Rehashes the contents of this map into a new array with a

   * larger capacity. This method is called automatically when the

   * number of keys in this map reaches its threshold.

   *

   * If current capacity is MAXIMUM_CAPACITY, this method does not

   * resize the map, but sets threshold to Integer.MAX_VALUE.

   * This has the effect of preventing future calls.

   *

   * @param newCapacity the new capacity, MUST be a power of two;

   *    must be greater than current capacity unless current

   *    capacity is MAXIMUM_CAPACITY (in which case value

   *    is irrelevant).

   */

  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 {

          Entry<K,V> next = e.next;

          //重新計(jì)算index

          int i = indexFor(e.hash, newCapacity);

          e.next = newTable[i];

          newTable[i] = e;

          e = next;

        } while (e != null);

      }

    }

  }