Map提供了一种映射关系，其中的元素是以键值对（key-value）的形式存储的，能够实现根据key快速查找value
Map中的键值对以Entry类型的对象实例形式存在
键（key值）不可重复，value值可以
Map支持泛型，形式如：Map<K,V>
map中常用的方法
Object put(Object key,Object value) 将指定的值与此映射中的指定键相关联
void putAll(Map t) 将映射t中所有映射关系复制到此映射中
Object get(Object key) 返回此映射中映射到指定键的值
Object remove(Object key) 若存在此键的映射关系,将其从映射中移除
boolean containsKey(Object key) 若此映射包含指定键的映射关系，返回 true
boolean containsValue(Object value) 若此映射为指定值映射一个或多个键,返回 true
int size() 返回此映射中的键-值映射对数
void clear() 从此映射中移除所有映射关系
boolean isEmpty() 若此映射未包含键-值映射关系,返回 true
Set keySet() 返回此映射中包含的键的 set 视图
HashMap
- HashMap是Map的一个重要实现类，也是最常用的，基于哈希表实现。
- HashMap是基于哈希表实现的，每一个元素是一个key-value对，其内部通过单链表解决冲突问题，容量不足（超过了阀值）时，同样会自动增长。
- HashMap中的Entry对象是无序列的
- key值和value值都可以为null，但是一个HashMap只能有一个key值为null的映射（key值不可重复，key为null的键值对永远都放在以table[0]为头结点的链表中。
- HashMap是非线程安全的，只是用于单线程环境下，多线程环境下可以采用concurrent并发包下的concurrentHashMap。
- HashMap 实现了Serializable接口，因此它支持序列化，实现了Cloneable接口，能被克隆。
HashMap存数据的过程是：
HashMap内部维护了一个存储数据的Entry数组，HashMap采用链表解决冲突，每一个Entry本质上是一个单向链表。当准备添加一个key-value对时，首先通过hash(key)方法计算hash值，然后通过indexFor(hash,length)求该key-value对的存储位置，计算方法是先用hash&0x7FFFFFFF后，再对length取模，这就保证每一个key-value对都能存入HashMap中，当计算出的位置相同时，由于存入位置是一个链表，则把这个key-value对插入链表头。
Hashtable
- Hashtable同样是基于哈希表实现的，同样每个元素是一个key-value对，其内部也是通过单链表解决冲突问题，容量不足（超过了阀值）时，同样会自动增长。
- Hashtable也是JDK1.0引入的类，是线程安全的，能用于多线程环境中。
- Hashtable同样实现了Serializable接口，它支持序列化，实现了Cloneable接口，能被克隆。
HashTable和HashMap区别
- 继承的父类不同
Hashtable继承自Dictionary类，而HashMap继承自AbstractMap类。但二者都实现了Map接口。 - HashMap是非线程安全的，Hashtable是线程安全的
- 是否提供contains方法。
HashMap把Hashtable的contains方法去掉了，改成containsValue和containsKey，因为contains方法容易让人引起误解。
Hashtable则保留了contains，containsValue和containsKey三个方法，其中contains和containsValue功能相同。 - key和value是否允许null值。
其中key和value都是对象，并且不能包含重复key，但可以包含重复的value。
Hashtable中，key和value都不允许出现null值。但是如果在Hashtable中有类似put(null,null)的操作，编译同样可以通过，因为key和value都是Object类型，但运行时会抛出NullPointerException异常，这是JDK的规范规定的。
HashMap中，null可以作为键，这样的键只有一个；可以有一个或多个键所对应的值为null。当get()方法返回null值时，可能是 HashMap中没有该键，也可能使该键所对应的值为null。因此，在HashMap中不能由get()方法来判断HashMap中是否存在某个键， 而应该用containsKey()方法来判断。 - 两个遍历方式的内部实现上不同
Hashtable、HashMap都使用了 Iterator。而由于历史原因，Hashtable还使用了Enumeration的方式 。 - 哈希值的使用不同，HashTable直接使用对象的hashCode。而HashMap重新计算hash值。
hashCode是jdk根据对象的地址或者字符串或者数字算出来的int类型的数值。 - HashTable在不指定容量的情况下的默认容量为11，而HashMap为16，Hashtable不要求底层数组的容量一定要为2的整数次幂，而HashMap则要求一定为2的整数次幂。
Hashtable扩容时，将容量变为原来的2倍加1，而HashMap扩容时，将容量变为原来的2倍。
Hashtable和HashMap它们两个内部实现方式的数组的初始大小和扩容的方式。HashTable中hash数组默认大小是11，增加的方式是 old*2+1。
详解HashMap
先来了解几种数据结构
数组
WX20200304-010410.png
数组的本质就是一块连续的内存，存放着具有共同特性的内存。因为是一块连续的内存，所以就可以快速的定位，可以以数组的下标直接对其操作。
优点：连续的内存，通过下标可以快速寻址。
缺点：数组的添加操作就是直接在数组后添加数据，但是如果在数组中间部分添加数据，那么就需要讲所插入节点的位置后面的数据向后移，这样会导致插入十分麻烦。也就是说插入节点困难。
单链表
WX20200304-011323.png
单链表的数据节点是由一个数据节点和一个next指针组成，有Head和Tail分别指向单链表的头部和尾部。所以插入的时候，只要将最后一个指针指向新插入的节点就可以了。如果在中间添加节点，只需要将所插入节点的上一个节点的指针指向新插入的节点，并且将新插入的节点的指针指向原链表中的下一个节点。
优点：插入和删除数据方便。
缺点：查询某一个数据是否存在单链表中，将会遍历这个单链表，这样就会很慢。也就是说查询效率低。
- HashMap的数据结构包括了初始数组，单链表，红黑树；
- 插入数据的时候使用pos = key%size来进行插入数据，来建立数组位置和key之间的关系；
- 当两个或两个以上的key，key相同且key值不同的时候（发生冲突），就会挂在数组初始化位置的链表后；
- 当某个节点后出现过多的链表节点的时候，就会转变成红黑树以提高效率；
HashMap源码分析
hash算法介绍
散列表，又叫哈希表，他是机遇快速存取的角度设计的，也是一种典型的以空间换时间的做法。该数据结构可以理解为一个线性表，但是其中的元素不是紧密排列的，而是可能存在空隙。
散列表（Hash table，也叫哈希表），是根据关键码值（key value）而直接进行访问的数据结构，也就是说，它通过把关键码值映射到表中的一个位置来访问记录，以加快查找速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
我们基于一种结果尽可能随机平均分布的固定函数H为每个元素安排存储位置，这样就可以避免遍历性质的线性搜索，以达到快速存取。但是由于此随机性，也必然导致一个问题就是冲突。所谓冲突，即两个元素通过散列函数H得到的地址相同，那么这两个元素称为“同义词”
说一下HashMap的几个重要的成员变量：
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
*/
static final int MIN_TREEIFY_CAPACITY = 64;
HashMap的构造函数
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
//负载因子的赋值操作
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//初始化容量
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
//判断容量
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
这里要说的是最后一个构造方法含有两个参数的里面，tableSizeFor(initialCapacity)这个方法。
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
//举例
// n == 12 - 1 = 11
int n = cap - 1;
// 0000 1011 == 11;
// 0000 0101 == 5;右移一位,或操作就是
//0000 1111 == 15；
//之后再次根据移位操作，算出结果
//这样操作就可以做到，不管传过来什么值，都能得到它小于哪个2的次方
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
hash(key)方法
在源码中有很多地方都调用了这个方法，那么它都做了什么操作呢？先看一下源码
//获取key的hash值
static final int hash(Object key) {
int h;
//首先，如果key是空的，那么就返回0，如果不为空的话，先调用key的hashCode()方法得到hashCode值，并且异或 hashCode值的高位
//hashcode是int类型，二进制32位，右移16位之后，相当于拿出了高位的16位
//目的：尽可能的提高hash的随机性
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
HashMap的put方法详解
public V put(K key, V value) {
//根据传入参数key，获取hashcode值
//
return putVal(hash(key), key, value, false, true);
}
//当在put()方法调用这个函数的时候，onlyIfAbsent传的值是false，evict传的值是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;
//判断table是否为空或长度为0
if ((tab = table) == null || (n = tab.length) == 0)
//初始化table
n = (tab = resize()).length;
//n - 1并与hash进行与运算得到i
//i就是元素在tab数组中存储的位置
//p = tab[i],从hashmap的结构中可以看出，得到的是一个链表后对象
//判断这个链表对象是否为空
//(n - 1) & hash 求余运算，目的就是优化运算速度
if ((p = tab[i = (n - 1) & hash]) == null)
//为空的话，就创建节点，直接存放到这个位置
tab[i] = newNode(hash, key, value, null);
else {
// tab[i]有元素的情况
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//这段代码说明，当传入的hash值与得到的p的hash值相同，并且元素的key值也相同，或者key不为空他俩是否相同
//如果这些都相同，那么就说明传入的元素和查找到的元素是同一个，那么直接赋值
e = p;
//不是上述情况的话，首先判断p的结构，是否是树结构（jdk1.8加入了红黑树优化方案）
else if (p instanceof TreeNode)
//基于红黑树的插入逻辑
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//链表插入元素
for (int binCount = 0; ; ++binCount) {
//判断p的下一个元素是否是空的
//为空的话，它的下一个元素的值，就是传入的这个
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;
}
}
//判断插入的值是否存在HashMap中
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;
}
HashMap的扩容
final Node<K,V>[] resize() {
//数组初始值
Node<K,V>[] oldTab = table;
//扩容前的变量初始化
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
//扩容后的变量初始化
int newCap, newThr = 0;
if (oldCap > 0) {
//判断是否大于容量的最大值，如果大于的话，则说明没办法扩容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// oldCap << 1，左移一位，相当于乘以2，等于新的容量。
//判断是否小于最大值，并且大于它的初始容量
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//老的容量乘以2，这样就得到了新的容量
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
//调用带制定初始容量的构造方法，会进入到这个分支
newCap = oldThr;
else { // zero initial threshold signifies using defaults
//调用的是无参的构造方法，就会进入到这个分支
newCap = DEFAULT_INITIAL_CAPACITY;
//负载因子*初始化容量 = 阈值
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//将新计算出的阈值赋值
threshold = newThr;
//创建一个新的，容量是之前2倍的数组
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//准备重新对元素进行定位
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//开始循环的时候，获取第j个位置的元素
if ((e = oldTab[j]) != null) {
//清空原数组
oldTab[j] = null;
//判断原有j位置上的元素是否有元素
if (e.next == null)
//重新计算位置，进行元素保存
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
//红黑树的拆分
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
//遍历链表，将链表节点按照顺序进行分组
//原理就是判断目前的节点的链表的每一个元素
//是否还在原来的位置上，将在的元素头尾相连
//不在的元素放到它应该到的节点的位置上
next = e.next;
if ((e.hash & oldCap) == 0) {
//old链表添加到一组
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
//元素计算之后，不在原位置
else {
//new链表添加到一组
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
//原位置j + 原容量 = 新的位置
newTab[j + oldCap] = hiHead;
}
}
}
}
}
//扩容之后的数组返回
return newTab;
}
HashMap的删除remove方法
先看源码
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
代码中可以看到调用了removeNode()这个方法，再来看一下这个方法
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
//p就是元素要存储的位置
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
//hash没有冲突的情况
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//定位删除的节点Node
node = p;
//有冲突，不只是一个元素在同一个位置
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
//红黑树，定位删除元素
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
//链表，定位删除元素
do {
//把链表的每一个元素逐个对比，是相同的退出循环，否则继续比较
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
//node就是要删除的元素
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
//红黑树删除节点
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
//链表删除节点
tab[index] = node.next;
else
//数组中p位置的对象下一个元素 = 删除元素的下一个元素
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
HashMap的遍历
先看一下关键的源码
public Set<K> keySet() {
Set<K> ks = keySet;
if (ks == null) {
ks = new KeySet();
keySet = ks;
}
return ks;
}
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
if (modCount != expectedModCount)
//报错的原因。动态的对HashMap的长度进行修改，会报这个异常
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
if ((next = (current = e).next) == null && (t = table) != null) {
//寻找数组中下一个hash槽中不为空的节点
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
Node是什么
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
源码中的next是一个指针，意味着这是一个单链表结构。
