Java中的HashMap的基本操作以及源码分析、Hashtable的基本操作以及源码分析、ConcurrentHashMap略解
文章目录
1.Map集合
1.1 Map集合的描述、常用方法
Collection接口的特点是每次进行单个元素的保存，如果现在需要进行一对对象的保存就只能使用Map集合完成，但是Map本身是一个接口，要使用Map需要通过子类进行对象实例化、Map的常用子类有：HashMap、Hashtable、TreeMap、ConcurrentHashMap
Map接口中的常用方法:
| 常用方法 | 描述 |
|---|---|
| public V put(K key,V value) | 向Map中追加数据 |
| public V get(Object key) | 根据key取得对应的value、如果没有返回null |
| public Set keySet() | 取得所有的key信息、key不能重复 |
| public Collection values() | 取得所有的value信息 、可以重复 |
| public V remove(Object key) | 根据key值删除指定的value值 |
| public Set<Map.Entry<K,V>> entrySet() | 将Map集合变为Set集合 |
1.2 HashMap子类
产生版本:JDK1.2
包:java.util
定义:HashMap<K,V> hashMap = new HashMap<>(); Map<Integer,String> hashMap = new HashMap<>();
1.2.1 HashMap的基本操作
import java.util.HashMap;
public class Test{
public static void main(String[] args) {
HashMap<Integer,String> hashMap
= new HashMap<>();
//1.向Map集合中添加元素
hashMap.put(1,"apple");
hashMap.put(4,"orange");
hashMap.put(3,"pig");
hashMap.put(2,"banana");
//2.向集合中添加Key值相同的元素 ---相当于覆盖
hashMap.put(2,"miao");
//3.根据Key值取得Value值
System.out.println(hashMap.get(2));
//4.向集合中添加value值相等的元素----允许value值相等
hashMap.put(5,"apple");
System.out.println(hashMap.get(5));
//5.获取所有的key值 返回值是Set集合
System.out.println(hashMap.keySet());
//6.获取所有的value值----返回值是Collection集合
System.out.println(hashMap.values());
//7.根据Key值删除元素
System.out.println(hashMap.remove(4));
//8.添加空值
hashMap.put(null,null);
//9.打印集合的长度
System.out.println(hashMap.size());
//打印Map集合
System.out.println(hashMap);
}
}
输出结果:
miao
apple
[1, 2, 3, 4, 5]
[apple, miao, pig, orange, apple]
orange
5
{null=null, 1=apple, 2=miao, 3=pig, 5=apple}
总结:
- HashMap可以存放空值（Key、Value均可以为空）
- Key值不可以重复
- Value值可以重复
1.2.2 HashMap的源码分析
首先我们需要明确,HashMap可以看作是数组和链表组成的复合产物，数组被分为一个个桶，通过哈希值决定了键值对在这个数组里的寻址，哈希值相同的键值对，则以链表或者红黑树的形式存储
成员变量、树化阈值:
| 成员变量 | 描述 |
|---|---|
| static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; | 默认的初始化容量为16(桶的个数) |
| static final float DEFAULT_LOAD_FACTOR = 0.75f; | 默认的负载因子为0.75 |
| static final int TREEIFY_THRESHOLD = 8 | 树化阈值 |
| static final int MIN_TREEIFY_CAPACITY = 64 | 树化要求的最少哈希表的数量 |
| static final int UNTREEIFY_THRESHOLD = 6 | 解树化阈值、resize阶段 |
树化总结:
当桶中链表元素个数超过8并且哈希表中的所有元素个数超过64，此时会将桶中的链表转为红黑树结构，否则，只是简单的进行扩容操作而已。
为什么要进行树化:
当桶中链表长度太长会大大影响查找速度，因此将其树化来提高查找指定节点的速度。
构造方法:
无参构造
//仅仅将默认负载因子赋值
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)若构造方法传入一个非2^n 的数值、调用此方法返回一个距离initialCapacity最近的2^n 的数值。
例如:传15 返16 传31返32 传100 返128
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) {
//1.刚开始:Node<K,V>[] table=null、如果桶未被初始化调用resize初始化
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//2.根据哈希函数计算出该元素存放位置的下标
//2.1如果该桶下还没有存放元素 将要保存的元素作为桶的头结点保存
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//2.2如果该桶下已经存放元素
else {
Node<K,V> e; K k;
//2.2.1 如果要保存的结点的key值与该链表的头结点相同 直接替换
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//2.2.2 如果桶中元素已经树化、按照树的方式存储结点
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//2.2.3 如果桶中的元素没有被树化、按照链表的形式存储新结点
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;
}
//链表中遇到相同的key 替换其value
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//替换value值
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//fail-fast
++modCount;
//添加结点后 整个HashMap的元素个数若要超过容量时，调用resize方法进行扩容操作
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
put总结:
1.若HashMap还未初始化、调用resize进行初始化操作
2.调用哈希函数，根据key值取得要存储的桶下标
2.1 若桶中元素为空，将结点直接作为桶的头结点保存
2.2 若桶中元素不为空
2.2.1 若树化，使用树的方式添加新节点
2.2.2 若没有树化，将新节点以链表的形式尾插、将元素添加后判断链表的个数是否达到树化阈值8，如果达到了尝试进行树化操作
2.3 在插入的过程中如果遇到有相同的key结点 直接替换其value值
3.添加元素后哈希表的个数+1,并且若超过threshold（容量负载因子=160.75 = 12）调用resize进行扩容操作
get方法:
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//1. 如果哈希表不为空、桶的长度大于0、桶的头结点不为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//1.1 如果要找的元素就是桶的头结点直接返回
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//1.2 如果要找的元素不是桶的头结点
if ((e = first.next) != null) {
//1.2.1 如果此时已经被树化 按照树化的方式查找结点
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
//1.2.2 按照链表的方式查找结点
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
get总结:
1.若哈希表已经初始化、并且桶的首节点不为空
1.1 查找节点的key值刚好等于首节点，直接返回首节点
1.2 进行桶元素的遍历、查找指定结点
1.2.1 若树化，按照树的方式查找
1.2.2 按照链表方式查找
2.哈希表为空或者桶的首节点为空直接返回null
哈希算法:
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
扩容机制resize:
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
//1.当前表是否初始化 oldCap=0表示没有初始化
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold; //容量*负载因子
int newCap, newThr = 0;
//2.哈希表不为空
if (oldCap > 0) {
//2.1 哈希表已经达到最大值
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//2.2 哈希表没有达到最大值 哈希表新长度 = 旧长度的二倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
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) {
//修改新的threshold值
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//将哈希表指向扩容后的新表
//如果oldTab=null 不用挪动元素
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
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) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
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;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
扩容机制resize() :
1.判断哈希表是否初始化，若还未初始化，进行初始化操作
2.若表已经初始化、将原哈希表按照2倍的形式扩容
3.扩容后进行原表元素的移动
3.1 若桶中结点已经树化、调用树的方式移动元素（在移动过程中发现红黑树结点<=6，会将红黑树解除树化、还原为链表）
3.2 若还未树化 调用链表的方式移动元素
1.2.3 HashMap的性能问题
1.多线程场景下、由于条件竞争、很容易造成死锁（比如多个线程都在一个桶里面移动元素）
所以在多线程的场景下避免使用HashMap
2.扩容后调整元素是一个比较耗时的过程、所以在能预估存储元素的前提下，尽量自定义初始化容量减少扩容的过程)
1.3 Hashtable子类
产生版本:JDK1.0
包:java.util
定义：Hashtable<K,V> hashtable = new Hashtable<>(); Map<K,V> hashtable = new Hashtable<>();
1.3.1 Hashtable的基本操作
import java.util.Hashtable;
public class Test{
public static void main(String[] args) {
Hashtable<Integer,String> hashtable
= new Hashtable<>();
//1.向Map集合中添加元素
hashtable.put(100,"gy");
hashtable.put(1,"apple");
hashtable.put(4,"orange");
hashtable.put(3,"pig");
hashtable.put(2,"banana");
//2.向集合中添加Key值相同的元素 ---相当于覆盖
hashtable.put(2,"miao");
//3.根据Key值取得Value值
System.out.println(hashtable.get(2));
//4.向集合中添加value值相等的元素----允许value值相等
hashtable.put(5,"apple");
System.out.println(hashtable.get(5));
//5.获取所有的key值
System.out.println(hashtable.keySet());
//6.获取所有的value值
System.out.println(hashtable.values());
//7.根据Key值删除元素
System.out.println(hashtable.remove(4));
//8.打印集合的长度
System.out.println(hashtable.size());
//打印Map集合
System.out.println(hashtable);
}
}
运行结果:
miao
apple
[5, 4, 3, 2, 1, 100]
[apple, orange, pig, miao, apple, gy]
orange
5
{5=apple, 3=pig, 2=miao, 1=apple, 100=gy}
总结:
- Hashtable不允许存放null值
- Key值不可以重复
- value值可以重复
1.3.2 Hashtable的源码分析
初始化策略:
当产生Hashtable对象时就将哈希表初始化
public Hashtable() {
this(11, 0.75f);
}
public Hashtable(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal Load: "+loadFactor);
if (initialCapacity==0)
initialCapacity = 1;
this.loadFactor = loadFactor;
table = new Entry<?,?>[initialCapacity];
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}
在方法上使用内建锁将整个哈希表上锁
public synchronized V put(K key, V value)
public synchronized V get(Object key)
public synchronized V remove(Object key)
1.3.3 Hashtable的性能问题
在方法上使用内建锁将整个哈希表上锁（即使线程1 在第一个桶上操作 其余所有的桶均不能操作）性能较低
1.4Hashtable与HashMap的区别
| 区别 | HashMap | Hashtable |
|---|---|---|
| 推出版本 | JDK1.2 | JDK1.0 |
| 性能 | 异步处理、性能高 | 同步处理、性能低 |
| 安全性 | 非线程安全 | 线程安全 |
| null | 允许存放null | key和null都不允许为空 |
1.4 ConcurrentHashMap
JDK1.7实现
基于分段锁Segement实现，并且每个Segment都是ReentrantLock的子类
结构上:
将哈希表拆分为16个Segement、每个Segment下又是小的哈希表
关于锁:
将原先整表的一把锁细粒度化为每个Segement的一把锁，并且不同的Segement间互不干扰
扩容机制:
Segement初始化之后无法扩容(默认初始化为16)，扩容实际上是Segement对应的每个小哈希表，并且不同Segement之间扩容完全隔离
JDK1.8
结构上:
与HashMap基本一样，也是哈希表+红黑树的底层实现，原先的Segement仍然保留，但是没有实际意义，仅仅用作序列化
关于锁:
将原先锁一片区域再次细粒度化为只锁桶中的头结点
使用CAS+同步代码块
JDK1.7与JDK1.8比较
为何JDK8中又重新使用synchronized内建锁？
synchronized基于JVM
RenntrankLock基于AQS
在现版本中，内建锁与lock锁的性能基本差不多,甚至在低竞争场景下还会优于lock
使用synchronized可以节省大量内存空间，这是相较于ReentrantLoxk最大的优势