­

HashMap源码分析（jdk7）

  • 2019 年 10 月 3 日
  • 筆記

HashMap?????

? jdk1.7?HashMap????+???????????hash????????????????????????????Key???????????????1.7????????????

? ??????????????????????????????????key?????????????1.8?????????????+??+????????????????8???????????.????????????? ????jdk8??HashMap

? ?????????????????Entry???????????Entry??????(?1.8?Entry???Node??????Map.Entry)?

//hash?????Node,???Map.Entry  static class Entry<K,V> implements Map.Entry<K,V> {      final K key;      V value;      Entry<K,V> next;      int hash;      //Entry??????key?hash?key?value?next?????      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;      }      //equals??      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;      }      //??Object?hashCode      public final int hashCode() {          return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());      }        public final String toString() {          return getKey() + "=" + getValue();      }        //??put?k?v????????key???Entry??????????????????      void recordAccess(HashMap<K,V> m) {      }        //???????entry????????      void recordRemoval(HashMap<K,V> m) {      }  }

HashMap??????????

//??????????=16  static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16    //???? = 1 << 30  static final int MAXIMUM_CAPACITY = 1 << 30;    //??????.??HashMap??????????HashMap??? > DEFAULT_LOAD_FACTOR *  //DEFAULT_INITIAL_CAPACITY = 0.75F * 16  static final float DEFAULT_LOAD_FACTOR = 0.75f;    //?????table??  static final Entry<?,?>[] EMPTY_TABLE = {};    //table[]????????EMPTY_TABLE?????????put?????resize???2?????  transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;    //map???????? != table.length  transient int size;    //??????size??????????resize??  //?????threshold=capacity*loadFactor  int threshold;    //hashTable?????  final float loadFactor;    /**       * The number of times this HashMap has been structurally modified       * Structural modifications are those that change the number of mappings in       * the HashMap or otherwise modify its internal structure (e.g.,       * rehash).  This field is used to make iterators on Collection-views of       * the HashMap fail-fast.  (See ConcurrentModificationException).       */  transient int modCount;    //hashSeed????key?hash????key?hashCode????????  //hashSeed?????????????????hash??  //???0?????????  transient int hashSeed = 0;

HashMap?????

? ????HashMap????????????????

//(1)??????  //??????table?????????DEFAULT_INITIAL_CAPACITY=16??????DEFAULT_LOAD_FACTOR=0.75F  public HashMap() {      this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);  }
//(2)???????????  //??????table??????????????initialCapacity??????DEFAULT_LOAD_FACTOR=0.75F  public HashMap(int initialCapacity) {      this(initialCapacity, DEFAULT_LOAD_FACTOR);  }
//(3)????????????????  //??????table???????????initialCapacity??????loadFactor  public HashMap(int initialCapacity, float loadFactor) {      //????????????????<0?????      if (initialCapacity < 0)          throw new IllegalArgumentException("Illegal initial capacity: " +                                             initialCapacity);      //??initialCapacity???????????=MAXIMUM_CAPACITY      if (initialCapacity > MAXIMUM_CAPACITY)          initialCapacity = MAXIMUM_CAPACITY;      //????????????????      if (loadFactor <= 0 || Float.isNaN(loadFactor))          //<0????Float??????????          throw new IllegalArgumentException("Illegal load factor: " +                                             loadFactor);      //????????????map???????      this.loadFactor = loadFactor;      threshold = initialCapacity;      //init????????????????????????????      init();  }

? ?????3?????????????????????????????table????????????????threshold????????????(???????????????????????)???put???????????jdk8????????????.

//(4)?????map????  //??????map?????????????????map??????????+1?????????  public HashMap(Map<? extends K, ? extends V> m) {      //???map.size()/0.75+1 ? 16????????      this(Math.max(              (int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,                    DEFAULT_INITIAL_CAPACITY),           DEFAULT_LOAD_FACTOR);      inflateTable(threshold);      //????map??????????????HashMap?      putAllForCreate(m);  }

? ?????????put?????inflateTable????????????????????table??????putAllForCreate?????map?????????????????????????threshold????????????????????????

(1)inflateTable????

? ?????????????????????????????????????????????????????put???????????table?????

private void inflateTable(int toSize) {      //?????number????2???????MAXIMUM_CAPACITY,??jdk8?????tabSizeFor???      int capacity = roundUpToPowerOf2(toSize);      //??????(??*????)?(????+1)??????      threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);      //??table??      table = new Entry[capacity];      initHashSeedAsNeeded(capacity);  }

(2)roundUpToPowerOf????

private static int roundUpToPowerOf2(int number) {      //number >= 0???????      //(1)number >= ????????????      //(2)0 =< number <= 1???1      //(3)1 < number < ?????      return number >= MAXIMUM_CAPACITY          ? MAXIMUM_CAPACITY          : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;  }  //????jdk8??tabSizeFor???????  public static int highestOneBit(int i) {      //?????i>0,??i?????0?????>>???????>>>????0?      //?????????i=5=0101      i |= (i >>  1); //?1?i>>1=0010??2?i= 0101 | 0010 = 0111      i |= (i >>  2); //?1?i>>2=0011??2?i= 0111 | 0011 = 0111      i |= (i >>  4); //?1?i>>4=0000??2?i= 0111 | 0000 = 0111      i |= (i >>  8); //?1?i>>8=0000??2?i= 0111 | 0000 = 0111      i |= (i >> 16); //?1?i>>16=0000??2?i= 0111 | 0000 = 0111      return i - (i >>> 1); //?1?0111>>>1=0011?2?0111-0011=0100=4      //??????4?      //?????roundUpToPowerOf2????????highestOneBit?????? << 1 ??????????4<<1=8.??????number???2??  }

(3)putAllForCreate????

? ??????????map????????????map???????????????????

private void putAllForCreate(Map<? extends K, ? extends V> m) {      //??????????map???????????map????putForCreate?????      for (Map.Entry<? extends K, ? extends V> e : m.entrySet())          putForCreate(e.getKey(), e.getValue());  }

? putForCreate??????

private void putForCreate(K key, V value) {      //??key???null????null?????hash?0????????????hash()????hash?      int hash = null == key ? 0 : hash(key);      //?????????hash????table??????      int i = indexFor(hash, table.length);      for (Entry<K,V> e = table[i]; e != null; e = e.next) {          Object k;          //hash???key???????????????          if (e.hash == hash &&              ((k = e.key) == key || (key != null && key.equals(k)))) {              e.value = value;              return;          }      }      //????????????key????????key????????????????????      createEntry(hash, key, value, i);  }

(4)createEntry????

void createEntry(int hash, K key, V value, int bucketIndex) {      //??????????????????key??????????????????????????      //bucket???????      Entry<K,V> e = table[bucketIndex];      /*Entry(int h, K k, V v, Entry<K,V> n) {value = v;next = n;key = k;hash = h;}*/      table[bucketIndex] = new Entry<>(hash, key, value, e);//Entry???????????????????????      size++;//???hash??????1  }

HashMap???????????

? 1.7????hash?????1.8??????????hash???????put???????get?????remove??????????indexFor?????????????????

(1)hash??

final int hash(Object k) {      int h = hashSeed;      //???0???0????key?String?????stringHash32??hash??      if (0 != h && k instanceof String) {          return sun.misc.Hashing.stringHash32((String) k);      }      //????????key?hashCode???????????hashCode?????????????hash??????      //????????????????????????????????????????????????????      //???????????      h ^= k.hashCode();      h ^= (h >>> 20) ^ (h >>> 12);      return h ^ (h >>> 7) ^ (h >>> 4);  }

? ??????????????key?hashCode???????????????????map?put??Key-Value??Key???“fsmly”???????????????????????hashcode???????“0000_0000_0011_0110_0100_0100_1001_0010”?????map???table?????16??????index????10???15???????32??“00000000000000000000000000001111”???????????????????????28?????????????????0???????????0????????put?Entry????????key?hashCode?????????????????????????

? ??map?????????????????????????????????hashCode??????????????JDK7??????????????????????????????????.???????????????hashCode???????????hash????

? ???????????????key?hash????????indexFor?????table????????????????????hash??length-1?????????2^n????????????????????????16?len-1=15,?????1111????????????????????????hashCode????????????????????????????????????????????hash????????Java?????hash????????????????hash()????

(2)indexFor??

static int indexFor(int h, int length) {      //????hash & (n - 1)??????      return h & (length-1);  }

??????????key?hash??map?????length-1??????????put?Entry?table?????????????????hash????????????????????

HashMap?put????

(1)put??

public V put(K key, V value) {      //????Hash Map????????????(???map?)????table???????????      //?????????????????????????map??????put?????table?{}?      //????????????table?????      if (table == EMPTY_TABLE) {          //??inflateTable????table??????table?????          //???threshold????2???????MAXIMUM_CAPACITY          inflateTable(threshold);      }      //??key?null?????????null?K-V??????putForNullKey??      if (key == null)          return putForNullKey(value);        //??put???key?hash?      int hash = hash(key);      //??hash??table??????????      int i = indexFor(hash, table.length);      //???????indexFor(hash, table.length)????1.7???????hash???????      //????????????????????i?????????????hash?????      for (Entry<K,V> e = table[i]; e != null; e = e.next) {          Object k;          //hash????key?????????oldValue?value          if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {              V oldValue = e.value;              e.value = value;              //??????????              e.recordAccess(this);              return oldValue;          }      }      //??key????????????????key????????????table[i]?????        //??modCount????????????????      modCount++;      //???????key?????????????      addEntry(hash, key, value, i);      return null;  }

(2)putForNullKey????

? ???????key?null?????????key?null??????table[0]?????????????????table[0]?head????????????????key?null???????????????value???????????????????table[0]????

//??table???key?null???Entry???????value????  private V putForNullKey(V value) {      //?table[0]????      for (Entry<K,V> e = table[0]; e != null; e = e.next) {          //key?null          if (e.key == null) {              //?value????????value              V oldValue = e.value;              e.value = value;              e.recordAccess(this);              return oldValue; //????          }      }      modCount++;      //?????0?????????????      addEntry(0, null, value, 0);      return null;  }

(3)addEntry????

? addEntry??????????????size????????????????????????????????????????????table??????????????

/*      hashmap??????????????????????????????????????????????????????????????????.??????????????????????????????????????O(1)???????????????????????????????????????????????????????.  */  void addEntry(int hash, K key, V value, int bucketIndex) {      //???????      //?size??????      //?????????table??????null      if ((size >= threshold) && (null != table[bucketIndex])) {          //????????????          resize(2 * table.length);          //??????????          //????null?key?hash???null??0          hash = (null != key) ? hash(key) : 0;          //??hash????          bucketIndex = indexFor(hash, table.length);      }      //?????????????????????????????Entry??      createEntry(hash, key, value, bucketIndex);  }

(4)??put???????

  1. ????????????????inflateTable????.
  2. ????key???null???null???putForNullKey????put.??????HashMap??key?null??????table????0??
  3. ??hash()????key????????????hash??????????&??????????
  4. ???????????????key?hash???key?hash???key?equals??true??????? value
  5. ?????????????????????

HashMap?resize????

(1)resize?????

void resize(int newCapacity) {      //??map???table??????      Entry[] oldTable = table;      //???table?????????      int oldCapacity = oldTable.length;      //???table????????????????????????      if (oldCapacity == MAXIMUM_CAPACITY) {          threshold = Integer.MAX_VALUE;          return;      }      //??????????????????????????      Entry[] newTable = new Entry[newCapacity];      //??transfer      transfer(newTable, initHashSeedAsNeeded(newCapacity));      //table??????      table = newTable;      //????      threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);  }

(2)transfer????

? transfer?????????Entry?????????????????????????

void transfer(Entry[] newTable, boolean rehash) {      //??????      int newCapacity = newTable.length;      //?????      for (Entry<K,V> e : table) {          while(null != e) {              Entry<K,V> next = e.next;              if (rehash) {                  //????hash?                  e.hash = null == e.key ? 0 : hash(e.key);              }              //??????????hash????indexFor????????              int i = indexFor(e.hash, newCapacity);              //?????????????????a->b->c;women              //?1?????????????????e.next=null;newTable[i]=e;e=e.next              //?2??????????????????e.next=head;newTable[i]=e??????????????????????;e=e.next              //?3????????????????????????????????????????????????????              e.next = newTable[i];              newTable[i] = e;              e = next;          }      }  }

? ?????????????????hash?????????table??????????????????????????????table????4??????entry1->entry2->entry3,????????????????4??????????????

(3)resize??????

  1. ? ????????????????2???????????????????
  2. ??transfer???entry???table??????????????????
  3. ?table????table?????

HashMap?get????

//get?????????getEntry???????null?????entry?value  public V get(Object key) {      if (key == null)          return getForNullKey();      Entry<K,V> entry = getEntry(key);      return null == entry ? null : entry.getValue();  }

? ?????get??????getEntry???Entry???????Entry?value????????getEntry?????

getEntry??

//??getEntry???  final Entry<K,V> getEntry(Object key) {      //????????null      if (size == 0) {          return null;      }      //?????key???hash???????      int hash = (key == null) ? 0 : hash(key);      //???????????????????Entry      for (Entry<K,V> e = table[indexFor(hash, table.length)];           e != null;           e = e.next) {          Object k;          //hash???key?????          if (e.hash == hash &&              ((k = e.key) == key || (key != null && key.equals(k))))              return e;      }      return null;  }

getForNullKey??

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

jdk7?????????

? (1)???put???key?null????putForNullKey?????????HashMap??null??Key

? (2)???table??????????key?hashcode???hash()??????hash????length-1??&???length-1???????1??????????????????????2???????
? (3)???get??put??resize?????????key?hashcode??hash?????????hashcode????????HashMap????????(?String??)??Key.
? (4)HashMap?????????????????????????????????????????????????ConcurrentHashMap????????????????????
? (5)???????HashMap??????????
? (6)HashMap??????16??????8???????6???????????;?32???????????

jdk7?????????????

? ?????resize????????????????????resize?????????????????????????????????resize??????????

Entry<K,V> next = e.next;  //??????hash?index?????...  e.next = newTable[i];  newTable[i] = e;  e = next;

? resize??????transfer????????????????????????????????thread1?thread2???resize???.

? (1)resize?????table???2,?????????entry4???????

? (2)????thread1???? Entry<K,V> next = e.next;?????????????????????????

? (3)??????????thread2?????thread2???transfer?????entry3?entry4???????????????????????entry1?entry2??????????????

(4)??thread1?????????entry1???????????e?Entry2????????next??Thread2??????Entry1

  • ???? newTalbe[i] = e;?thread1?????e????entry1
  • ???e = next????e???entry2?next????entry2?
  • ???????next = e.next???next=entry2.next=entry1??thread2?????????next???entry1

?????

? (5)thread1??????entry2??????newTable[1]??????????????e?next

?6?e.next = newTable[1] ?? entry1.next ??? entry2,????????entry2.next ?????entry1(thread2???????entry2->entry1,????thread2???????)? ???????????

VirMach 便宜 VPS

QNews

QNews