个人学习HashMap

素颜马尾好姑娘i 2022-05-28 14:18 411阅读 0赞

HashMap是Map的一个实现类，Map是个双列集合，是一种键Key-值Value的数据结构。 实现了Map接口的所有方法， 而且允许key为null， value也为null。   
HashMap与HashTable基本上就是一样的， 唯一的区别就是HashTable是线程安全的， 而HashMap不是(这跟ArrayList和Vector的区别是一样的)。

HashMap不保证map的顺序， key-value 是”随机”的存放在map中的。

hashmap本质数据加链表。根据key取得hash值，然后计算出数组下标，如果多个key对应到同一个下标，就用链表串起来，新插入的在前面。

看3段重要代码摘要：

a：

**\[java\]**  [view plain][]  [copy][view plain]

1.  public HashMap(int initialCapacity, float loadFactor) \{  
2.      int capacity = 1;  
3.      while (capacity < initialCapacity)  
4.          capacity <<= 1;  
5.    
6.      this.loadFactor = loadFactor;  
7.      threshold = (int)(capacity \* loadFactor);  
8.      table = new Entry\[capacity\];  
9.      init();  
10. \}

有3个关键参数：  
capacity：容量，就是数组大小  
loadFactor：比例，用于扩容  
threshold:=capacity\*loadFactor   最多容纳的Entry数，如果当前元素个数多于这个就要扩容（capacity扩大为原来的2倍）

**\[java\]**  [view plain][]  [copy][view plain]

1.  public V get(Object key) \{  
2.      if (key == null)  
3.          return getForNullKey();  
4.      int hash = hash(key.hashCode());  
5.      for (Entry<K,V> e = table\[indexFor(hash, table.length)\];  
6.           e != null;  
7.           e = e.next) \{  
8.          Object k;  
9.          if (e.hash == hash && ((k = e.key) == key || key.equals(k)))  
10.             return e.value;  
11.     \}  
12.     return null;  
13. \}

根据key算hash值，再根据hash值取得数组下标，通过数组下标取出链表，遍历链表用equals取出对应key的value。

**\[java\]**  [view plain][]  [copy][view plain]

1.  public V put(K key, V value) \{  
2.          if (key == null)  
3.              return putForNullKey(value);  
4.          int hash = hash(key.hashCode());  
5.          int i = indexFor(hash, table.length);  
6.          for (Entry<K,V> e = table\[i\]; e != null; e = e.next) \{  
7.              Object k;  
8.              if (e.hash == hash && ((k = e.key) == key || key.equals(k))) \{  
9.                  V oldValue = e.value;  
10.                 e.value = value;  
11.                 e.recordAccess(this);  
12.                 return oldValue;  
13.             \}  
14.         \}  
15.   
16.         modCount++;  
17.         addEntry(hash, key, value, i);  
18.         return null;  
19.     \}

从数组（通过hash值）取得链表头，然后通过equals比较key，如果相同，就覆盖老的值，并返回老的值。（该key在hashmap中已存在）

否则新增一个entry，返回null。新增的元素为链表头，以前相同数组位置的挂在后面。

另外：modCount是为了避免读取一批数据时，在循环读取的过程中发生了修改，就抛异常

if (modCount != expectedModCount)  
                throw new ConcurrentModificationException();

下面看添加一个map元素

**\[html\]**  [view plain][]  [copy][view plain]

1.  void addEntry(int hash, K key, V value, int bucketIndex) \{  
2.      Entry<K,V> e = table\[bucketIndex\];  
3.      table\[bucketIndex\] = new Entry<K,V>(hash, key, value, e);  
4.      if (size++ >= threshold)  
5.          resize(2 \* table.length);  
6.  \}

新增后，如果发现size大于threshold了，就resize到原来的2倍

**\[java\]**  [view plain][]  [copy][view plain]

1.  void resize(int newCapacity) \{  
2.    
3.      Entry\[\] newTable = new Entry\[newCapacity\];  
4.      transfer(newTable);  
5.      table = newTable;  
6.      threshold = (int)(newCapacity \* loadFactor);  
7.  \}

新建一个数组，并将原来数据转移过去

**\[java\]**  [view plain][]  [copy][view plain]

1.  void transfer(Entry\[\] newTable) \{  
2.          Entry\[\] src = table;  
3.          int newCapacity = newTable.length;  
4.          for (int j = 0; j < src.length; j++) \{  
5.              Entry<K,V> e = src\[j\];  
6.              if (e != null) \{  
7.                  src\[j\] = null;  
8.                  do \{  
9.                      Entry<K,V> next = e.next;  
10.                     int i = indexFor(e.hash, newCapacity);  
11.                     e.next = newTable\[i\];  
12.                     newTable\[i\] = e;  
13.                     e = next;  
14.                 \} while (e != null);  
15.             \}  
16.         \}  
17.     \}

将原来数组中的链表一个个取出，然后遍历链表中每个元素，重新计算index并放入新数组。每个处理的也放链表头。

在取出原来数组链表后，将原来数组置空（为了大数据量复制时更快的被垃圾回收？）

还有两点注意：

static class Entry<K,V> implements Map.Entry<K,V>是hashmap的静态内部类，iterator之类的是内部类，因为不是每个元素都需要持有map的this指针。

HashMap把  transient Entry\[\] table;等变量置为transient，然后override了readObject和writeObject，自己实现序列化。

[view plain]: https://blog.csdn.net/zldeng19840111/article/details/6703104#