大纲：
- 1.何为HashMap？
- 2.数据结构&基本原理
- 3.初始化&put&get过程
1、何为HashMap?
- 基于哈希表（散列表）的Map接口实现
- 保证线程安全的方法：Map map = Collections.synchronizedMap(new HashMap()); 或 ConcurrentHashMap
- java.util.HashMap、java.util.concurrent.ConcurrentHashMap
- http://androidxref.com/7.1.1_r6/xref/libcore/ojluni/src/main/java/java/util/HashMap.java
2、数据结构&基本原理
- 基于数组、单链表；Key对象的散列码hashCode决定了其数组位置、通过单链表解决hash冲突（链表法、非开放地址法）。
- transient HashMapEntry<K,V>[] table.
- 730 static class HashMapEntry<K,V> implements Map.Entry<K,V> {
- 731 final K key;
- 732 V value;
- 733 HashMapEntry<K,V> next;
- 734 int hash;
3、初始化&put&get过程
一些变量：
- final float loadFactor = DEFAULT_LOAD_FACTOR;//负载系数，默认0.75
- int threshold;//阈值，下次resize的门槛值，(capacity * loadFactor)
- transient int size;//key-value数目
- transient int modCount;//结构化修改次数
初始化：
- 274 private void inflateTable(int toSize) {
- 275 // Find a power of 2 >= toSize
- 276 int capacity = roundUpToPowerOf2(toSize);
- 277
- 278 // Android-changed: Replace usage of Math.min() here because this method is
- 279 // called from the <clinit> of runtime, at which point the native libraries
- 280 // needed by Float.* might not be loaded.
- 281 float thresholdFloat = capacity * loadFactor;
- 282 if (thresholdFloat > MAXIMUM_CAPACITY + 1) {
- 283 thresholdFloat = MAXIMUM_CAPACITY + 1;
- 284 }
- 285
- 286 threshold = (int) thresholdFloat;
- 287 table = new HashMapEntry[capacity];//初始化
- 288 }
put过程：
- 417 public V put(K key, V value) {
- 418 if (table == EMPTY_TABLE) {
- 419 inflateTable(threshold);
- 420 }
- 421 if (key == null)
- 422 return putForNullKey(value);//支持key==null的情况
- 423 int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);//获取hash值
- 424 int i = indexFor(hash, table.length);//获取索引位置
- 425 for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) {
- 426 Object k;
- 427 if (e.hash==hash && ((k = e.key) == key || key.equals(k))) {
//链表中，找到key，则更新value
- 428 V oldValue = e.value;
- 429 e.value = value;
- 430 e.recordAccess(this);
- 431 return oldValue;
- 432 }
- 433 }
- 434
- 435 modCount++;
- 436 addEntry(hash, key, value, i);
- 437 return null;
- 438 }
获取hash值
- 47 public static int singleWordWangJenkinsHash(Object k) {
- 48 int h = k.hashCode();
- 49
- 50 h += (h << 15) ^ 0xffffcd7d;
- 51 h ^= (h >>> 10);
- 52 h += (h << 3);
- 53 h ^= (h >>> 6);
- 54 h += (h << 2) + (h << 14);
- 55 return h ^ (h >>> 16);
- 56 }
获取索引位置
- 305 static int indexFor(int h, int length) {
- 306 // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
- 307 return h & (length-1);//因为length必须是2的n次方，length - 1 = 0**011**11
- 308 }
- 806 void addEntry(int hash, K key, V value, int bucketIndex) {
- 807 if ((size >= threshold) && (null != table[bucketIndex])) {
- 808 resize(2 * table.length); //达到阈值时，扩容至2倍，后面详述
- 809 hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
- 810 bucketIndex = indexFor(hash, table.length);
- 811 }
- 812
- 813 createEntry(hash, key, value, bucketIndex);
- 814 }
- 824 void createEntry(int hash, K key, V value, int bucketIndex) {
//形成单链表，最新entry在table[]槽位，将原来的e传给最新entry.next
- 825 HashMapEntry<K,V> e = table[bucketIndex];
- 826 table[bucketIndex] = new HashMapEntry<>(hash, key, value, e);
- 827 size++;
- 828 }
- 503 void resize(int newCapacity) {
- 504 HashMapEntry[] oldTable = table;
- 505 int oldCapacity = oldTable.length;
- 506 if (oldCapacity == MAXIMUM_CAPACITY) {
- 507 threshold = Integer.MAX_VALUE;
- 508 return;
- 509 }
- 510
- 511 HashMapEntry[] newTable = new HashMapEntry[newCapacity]; //重新生成table
- 512 transfer(newTable);//搬迁数据
- 513 table = newTable;
- 514 threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
- 515 }
- 520 void transfer(HashMapEntry[] newTable) {
- 521 int newCapacity = newTable.length;
- 522 for (HashMapEntry<K,V> e : table) {
//将链表中的entry，可能通过indexFor解决之前的冲突，从而放入新数组table的槽位中，从而提升查询速度；故loadFactor越小，查询速度越快。
- 523 while(null != e) {
- 524 HashMapEntry<K,V> next = e.next;
- 525 int i = indexFor(e.hash, newCapacity);
- 526 e.next = newTable[i];
- 527 newTable[i] = e;
- 528 e = next;
- 529 }
- 530 }
- 531 }
get过程：
- 345 public V get(Object key) {
- 346 if (key == null)
- 347 return getForNullKey();
- 348 Entry<K,V> entry = getEntry(key);
- 349
- 350 return null == entry ? null : entry.getValue();
- 351 }
- 388 final Entry<K,V> getEntry(Object key) {
- 389 if (size == 0) {
- 390 return null;
- 391 }
- 392
//当无hash冲突时，get的时间复杂度为(1)，不然只能沿着链表挨个查找
- 393 int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
- 394 for (HashMapEntry<K,V> e = table[indexFor(hash, table.length)];
- 395 e != null;
- 396 e = e.next) {
- 397 Object k;
- 398 if (e.hash == hash &&
- 399 ((k = e.key) == key || (key != null && key.equals(k))))
- 400 return e;
- 401 }
- 402 return null;
- 403 }
