【定义】

HashMap是一个散列表，存储的内容是键值对（key-value）映射。

【内容】

1、继承关系：

public class HashMapextends AbstractHashMap implements Map,Cloneable,Serializable
Cloneable接口：克隆一个HashMap对象并返回；
Serializable接口：分别实现了串行读取、写入功能。
串行写入函数是writeObject()，它的作用是将HashMap的“总的容量，实际容量，所有的Entry”都写入到输出流中。
而串行读取函数是readObject()，它的作用是将HashMap的“总的容量，实际容量，所有的Entry”依次读出。

image.png
table用来初始化（必须是二的n次幂）
image.png
用来放缓存
image.png
HashMap中存储的数量
image.png
用来记录HashMap的修改次数
image.png
用来调整大小下一个容量的值计算方式为（容量*负载因子）
image.png
哈希表的加载因子
image.png

2、基本属性：

static final int DEFAULT_INITIAL_CAPACITY=1<<4; //默认初始化大小16
image.png
static final float DEFAULT_LOAD_FACTOR =0.75f; //负载因子0.75
image.png
static final Entry<?,?>[] EMPTY_TABLE=[];//初始化的默认数组

transient int size;//HashMap中元素的数量
int threshold;//判断是否需要调整HashMap的容量

HashMap的扩容操作是一项非常耗时的任务，所以如果能估算Map的容量，最好给它一个默认初始值，避免进行多次扩容。HashMap的线程是不安全的，多线程环境中推荐是concurrentHashMap。

3、数据存储结构

HashMap采用Entry数组来存储key-value对，每一个键值对组成了一个Entry实体，Entry类实际上是一个单向的链表结构，它具有Next指针，可以连接下一个Entry实体，以此来解决Hash冲突的问题。
数组存储区间是连续的，占用内存严重，故空间复杂度很大。但数组的二分查找时间复杂度小，为O(1)；数组的特点是：寻址容易，插入和删除困难。
链表存储区间离散，占用内存比较宽松，故空间复杂度很小，但时间复杂度很大，达O(N)；链表的特点是：寻址困难，插入和删除容易。
image.png
image.png
image.png

数组+链表组成；
HashMap里面实现一个静态内部类Entry，其重要属性hash，key，value，next。
数组中存储的是最后插入的元素；
public V put(K key, V value) {
if (key == null)
return putForNullKey(value); //null总是放在数组的第一个链表中 int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
//遍历链表 for (Entry 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 e = table[bucketIndex];
table[bucketIndex] = new Entry(hash, key, value, e); //参数e, 是Entry.next
//如果size超过threshold，则扩充table大小。再散列 if (size++ >= threshold)
resize(2 * table.length);
}

4、构造方法：

HashMap()//无参构造方法
image.png
HahsMap(int initialCapacity)//指定初始容量的构造方法
image.png
HashMap(int initialCapacity,float loadFactor)//指定初始化容量和负载因子。
image.png
HashMap（Map<? extends K,?extends V> m）//指定集合，转化为HashMap
image.png
image.png
HashMap提供了四个构造方法，构造方法中 ，依靠第三个方法来执行的，但是前三个方法都没有进行数组的初始化操作，即使调用了构造方法此时存放HaspMap中数组元素的table表长度依旧为0 。在第四个构造方法中调用了inflateTable()方法完成了table的初始化操作，并将m中的元素添加到HashMap中。

5、添加方法：

在该方法中，添加键值对时，首先进行table是否初始化的判断，如果没有进行初始化（分配空间，Entry[]数组的长度）。然后进行key是否为null的判断，如果key==null ,放置在Entry[]的0号位置。计算在Entry[]数组的存储位置，判断该位置上是否已有元素，如果已经有元素存在，则遍历该Entry[]数组位置上的单链表。判断key是否存在，如果key已经存在，则用新的value值，替换点旧的value值，并将旧的value值返回。如果key不存在于HashMap中，程序继续向下执行。将key-vlaue, 生成Entry实体，添加到HashMap中的Entry[]数组中。

  1.    public V put(K key, V value) {
  2.         return putVal(hash(key), key, value, false, true);
  3.     }
  5.     final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
  6.                    boolean evict) {
  7.         Node<K,V>[] tab; Node<K,V> p; int n, i;
  8.         if ((tab = table) == null || (n = tab.length) == 0)
  9.             n = (tab = resize()).length;
  10.         if ((p = tab[i = (n - 1) & hash]) == null)
  11.             tab[i] = newNode(hash, key, value, null);
  12.         else {
  13.             Node<K,V> e; K k;
  14.             if (p.hash == hash &&
  15.                 ((k = p.key) == key || (key != null && key.equals(k))))
  16.                 e = p;
  17.             else if (p instanceof TreeNode)
  18.                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  19.             else {
  20.                 for (int binCount = 0; ; ++binCount) {
  21.                     if ((e = p.next) == null) {
  22.                         p.next = newNode(hash, key, value, null);
  23.                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  24.                             treeifyBin(tab, hash);
  25.                         break;
  26.                     }
  27.                     if (e.hash == hash &&
  28.                         ((k = e.key) == key || (key != null && key.equals(k))))
  29.                         break;
  30.                     p = e;
  31.                 }
  32.             }
  33.             if (e != null) { // existing mapping for key
  34.                 V oldValue = e.value;
  35.                 if (!onlyIfAbsent || oldValue == null)
  36.                     e.value = value;
  37.                 afterNodeAccess(e);
  38.                 return oldValue;
  39.             }
  40.         }
  41.         ++modCount;
  42.         if (++size > threshold)
  43.             resize();
  44.         afterNodeInsertion(evict);
  45.         return null;
  46.     }

6、addEntry()

添加到方法的具体操作，在添加之前先进行容量的判断，如果当前容量达到了阈值，并且需要存储到Entry[]数组中，先进性扩容操作，空充的容量为table长度的2倍。重新计算hash值，和数组存储的位置，扩容后的链表顺序与扩容前的链表顺序相反。然后将新添加的Entry实体存放到当前Entry[]位置链表的头部。在1.8之前，新插入的元素都是放在了链表的头部位置，但是这种操作在高并发的环境下容易导致死锁，所以1.8之后，新插入的元素都放在了链表的尾部。

  1. /*
  2. * hash hash值 
  3. * key 键值 
  4. * value value值 
  5. * bucketIndex Entry[]数组中的存储索引
  6. * / 
  7. void addEntry(int hash, K key, V value, int bucketIndex) {
  8.      if ((size >= threshold)&& (null != table[bucketIndex])) {
  9.          resize(2 * table.length); //扩容操作，将数据元素重新计算位置后放入newTable中，链表的顺序与之前的顺序相反
  10.          hash = (null != key) ? hash(key): 0;
  11.          bucketIndex = indexFor(hash,table.length);
  12.      }
  13. createEntry(hash,key, value, bucketIndex);
  14. }
  15. void createEntry(int hash, K key, V value, int bucketIndex) {
  16.     Entry<K,V> e = table[bucketIndex];
  17.     table[bucketIndex] = new Entry<>(hash, key, value, e);
  18.     size++;
  19. }

7、获取方法：get

在get方法中，首先计算hash值，然后调用indexFor()方法得到该key在table中的存储位置，得到该位置的单链表，遍历列表找到key和指定key内容相等的Entry，返回entry.value值。

  1. public V get(Object key) {
  2.         Node<K,V> e;
  3.         return (e = getNode(hash(key), key)) == null ? null : e.value;
  4.     }
  6. final Node<K,V> getNode(int hash, Object key) {
  7.   Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
  8.      if ((tab = table) != null && (n = tab.length) > 0 &&
  9.          (first = tab[(n - 1) & hash]) != null) {
  10.           if (first.hash == hash && // always check first node
  11.                ((k = first.key) == key || (key != null && key.equals(k))))
  12.                return first;
  13.           if ((e = first.next) != null) {
  14.               if (first instanceof TreeNode)
  15.                   return ((TreeNode<K,V>)first).getTreeNode(hash, key);
  16.               do {
  17.                   if (e.hash == hash &&
  18.                       ((k = e.key) == key || (key != null && key.equals(k))))
  19.                       return e;
  20.               } while ((e = e.next) != null);
  21.           }
  22.       }
  23.     return null;
  24. }

8、删除方法

删除操作，先计算指定key的hash值，然后计算出table中的存储位置，判断当前位置是否Entry实体存在，如果没有直接返回，若当前位置有Entry实体存在，则开始遍历列表。定义了三个Entry引用，分别为pre, e ,next。 在循环遍历的过程中，首先判断pre 和 e 是否相等，若相等表明，table的当前位置只有一个元素，直接将table[i] = next = null 。若形成了pre -> e -> next 的连接关系，判断e的key是否和指定的key 相等，若相等则让pre -> next ,e 失去引用。

  1. public V remove(Object key) {
  2.      Entry<K,V> e =removeEntryForKey(key);
  3.      return (e == null ? null :e.value);
  4. }
  6. final Entry<K,V> removeEntryForKey(Object key) {
  7.      if (size == 0) {
  8.          return null;
  9.      }
  10.      int hash = (key == null) ? 0 :
  11. hash(key);
  12.      int i = indexFor(hash,
  13. table.length);
  14.      Entry<K,V> prev =table[i];
  15.      Entry<K,V> e = prev;
  16. while(e != null) {
  17.          Entry<K,V> next =e.next;
  18.          Object k;
  19.          if (e.hash == hash&&((k = e.key) == key || (key!= null && key.equals(k)))) {
  20.              modCount++;
  21.              size--;
  22.              if (prev == e)
  23.                  table[i] =next;
  24.              else
  25.                  prev.next =next;            
  26. e.recordRemoval(this);
  27.              return e;
  28.          }
  29.          prev = e;
  30.          e = next;
  31.     }
  32. return e;
  33. }

9、JDK1.8版本中的改变

（1）采用数组+链表+红黑树实现

在Jdk1.8中HashMap的实现方式做了一些改变，但是基本思想还是没有变得，只是在一些地方做了优化，下面来看一下这些改变的地方,数据结构的存储由数组+链表的方式，变化为数组+链表+红黑树的存储方式，当链表长度超过阈值（8）时，将链表转换为红黑树。在性能上进一步得到提升。
当链表的值超过8则会转红黑树(1.8新增)
image.png
当链表的值小于6则会从红黑树转回链表
image.png
当Map里面的数量超过这个值时，表中的桶才能进行树形化 ，否则桶内元素太多时会扩容，而不是树形化 为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 TREEIFY_THRESHOLD
image.png
image.png
*HashMap为什么要使用红黑树呢
因为Map中桶的元素初始化是链表保存的，其查找性能是O(n)，而树结构能将查找性能提升到O(log(n))。当链表长度很小的时候，即使遍历，速度也非常快，但是当链表长度不断变长，肯定会对查询性能有一定的影响，所以才需要转成树。至于为什么阈值是8，我想，去源码中找寻答案应该是最可靠的途径。

（2）put方法：

 public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

如果存在key节点，返回旧值，如果不存在则返回Null。

10、HashMap与HashTable的相同点和不同点

相同点：

HashMap和Hashtable都是存储“键值对(key-value)”的散列表，而且都是采用拉链法实现的。
存储的思想都是：通过table数组存储，数组的每一个元素都是一个Entry；而一个Entry就是一个单向链表，Entry链表中的每一个节点就保存了key-value键值对数据。
添加key-value键值对：首先，根据key值计算出哈希值，再计算出数组索引(即，该key-value在table中的索引)。然后，根据数组索引找到Entry(即，单向链表)，再遍历单向链表，将key和链表中的每一个节点的key进行对比。若key已经存在Entry链表中，则用该value值取代旧的value值；若key不存在Entry链表中，则新建一个key-value节点，并将该节点插入Entry链表的表头位置。
删除key-value键值对：删除键值对，相比于“添加键值对”来说，简单很多。首先，还是根据key计算出哈希值，再计算出数组索引(即，该key-value在table中的索引)。然后，根据索引找出Entry(即，单向链表)。若节点key-value存在与链表Entry中，则删除链表中的节点即可。

不同点：

（1）线程安全：

两者最主要的区别在于Hashtable是线程安全，而HashMap则非线程安全。
Hashtable的实现方法里面都添加了synchronized关键字来确保线程同步，因此相对而言HashMap性能会高一些，我们平时使用时若无特殊需求建议使用HashMap，在多线程环境下若使用HashMap需要使用Collections.synchronizedMap()方法来获取一个线程安全的集合。

（2）针对null的不同

HashMap可以使用null作为key，而Hashtable则不允许null作为key
虽说HashMap支持null值作为key，不过建议还是尽量避免这样使用，因为一旦不小心使用了，若因此引发一些问题，排查起来很是费事。

（3）继承结构不同

HashMap是对Map接口的实现，HashTable实现了Map接口和Dictionary抽象类。

（4）初识容量与扩容不同

HashMap的初始容量为16，Hashtable初始容量为11，两者的填充因子默认都是0.75。
HashMap扩容时是当前容量翻倍即:capacity2，Hashtable扩容时是容量翻倍+1即:capacity2+1。

（5）两者计算hash的方法不同

Hashtable计算hash是直接使用key的hashcode对table数组的长度直接进行取模

int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;

HashMap计算hash对key的hashcode进行了二次hash，以获得更好的散列值，然后对table数组长度取摸。

int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h

12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
static int indexFor(int h, int length) {
return h & (length-1);

11、对外接口：

clear()：清空HashMap。它是通过将所有的元素设为null来实现的；
containsKey()：判断HashMap是否包含key；
containsValue()：判断HashMap是否包含“值为value”的元素；
entrySet()、values()、keySet()：返回“HashMap中所有对应的集合”，它是一个集合；
get()：获取key对应的value；
put()：对外提供接口，让HashMap对象可以通过put()将“key-value”添加到HashMap中；
putAll()：将”m”的全部元素都添加到HashMap中；
remove()：删除“键为key”元素。

【总结】

总的来说，HashMap就是数组+链表的组合实现，每个数组元素存储一个链表的头结点，本质上来说是哈希表“拉链法”的实现。
HashMap的链表元素对应的是一个静态内部类Entry，Entry主要包含key，value，next三个元素
主要有put和get方法，put的原理是，通过hash%Entry.length计算index，此时记作Entry[index]=该元素。如果index相同
就是新入的元素放置到Entry[index]，原先的元素记作Entry[index].next
get就比较简单了，先遍历数组，再遍历链表元素。
null key总是放在Entry数组的第一个元素
解决hash冲突的方法：链地址法
再散列rehash的过程：确定容量超过目前哈希表的容量，重新调整table 的容量大小，当超过容量的最大值时，取 Integer.Maxvalue

ConcurrentHashMap

image.png
image.png

put思路：
put(key ,value)
int hashcode = hash(key);
int index =hsahcode % table.length;

// 1、插入到头部；2、移动
table[index] = new Entry(key,value,table[index]);

get(周瑜)思路：
int hashcode = hash(key);
int index = hashcode %table.length

为什么要用2的次方数

为了下标取值符合要求

为什么要右移以及异或

image.png

源码分析

image.png
image.png
image.png
image.png