1. Map接口
1. 常用实现类
-
HashMap
- 它根据key的hashCode值存储数据,大多数情况下可以直接定位到它的值,因而具有很快的访问速度,但遍历顺序却不确定
- 最多只允许一条记录的key为null,允许多条记录的value为null
-
非线程安全,即任一时刻可以有多个线程同时写HashMap,可能会导致数据的不一致。如果需要满足线程安全,可以用 ConcurrentHashMap或者
Collections.synchronizedMap
方法使HashMap具有线程安全的能力
-
LinkedHashMap
- LinkedHashMap是HashMap的一个子类,保存了记录的插入顺序,在用Iterator遍历LinkedHashMap时,先得到的记录肯定是先插入的,也可以在构造时带参数,按照访问次序排序
-
TreeMap
- TreeMap实现SortedMap接口,能够把它保存的记录根据键排序,默认是按键值的升序排序,也可以指定排序的比较器,当用Iterator遍历TreeMap时,得到的记录是排过序的。如果使用排序的映射,建议使用TreeMap。
- 在使用TreeMap时,key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator,否则会在运行时抛出
java.lang.ClassCastException
-
Hashtable
- Hashtable是遗留类(不建议在新代码中使用),很多映射的常用功能与HashMap类似,不同的是它继承自Dictionary类,并且是线程安全的,任一时间只有一个线程能写Hashtable,并发性不如ConcurrentHashMap,因为ConcurrentHashMap引入了分段锁
- 不需要线程安全的场合可以用HashMap替换,需要线程安全的场合可以用ConcurrentHashMap替换
Note: 对于上述四种Map类型的类,要求映射中的key是不可变对象。不可变对象是该对象在创建后它的哈希值不会被改变。如果对象的哈希值发生变化,Map对象很可能就定位不到映射的位置了。
2. equals() vs hashCode()
1. equals
- 判断两个对象是否相等,Object默认实现为判断两个对象地址是否相等
-
==
判断两个对象地址是否相等,即两个对象是否是同一个对象
2. hashCode
- 获取哈希码,仅当创建某个类的散列表时才有作用
- 如果两个对象相等,那么哈希码一定相同;如果两个对象哈希码相等,对象不一定相等。即equals相同,hashCode一定相同;hashCode相同,equals不一定相同
3. 重写equals方法
-
自反性:对于任何非
null
的引用值x,x.equals(x)
必须返回true
-
对称性:对于任何非
null
的引用值x
和y
,当且仅当x.equals(y)
返回true
时,y.equals(x)
必须返回true
-
传递性: 对于任何非
null
的引用值x
,y
和z
,如果x.equals(y)
返回true
,并且y.equals(z)
也返回true
,那么x.equals(z)
也必须返回true
-
一致性:对于任何非
null
的引用值x和y, 只要equals的比较操作在对象中所用的信息没有被修改,多次调用x.equals(y)
就会一致的返回true
,或者一致的返回false
- 对于任何非
null
的引用值x
,x.equals(null)
必须返回false
例子:
39 @Override
40 public boolean equals(Object obj){
41 if(obj == null){
42 return false;
43 }
44
45 //如果是同一个对象返回true,反之返回false
46 if(this == obj){
47 return true;
48 }
49
50 //判断是否类型相同
51 if(this.getClass() != obj.getClass()){
52 return false;
53 }
54
55 Person person = (Person)obj;
56 return name.equals(person.name) && age==person.age;
57 }
4. 重写hashCode方法
- hashCode 方法与 equals 方法应使用相同的字段,这样可以实现第一条约定。
- 若 hashCode 方法使用的字段总体上呈某种概率分布,则可利用概率论的知识构造出总体呈均匀分布的散列码。
工具:
· ^ //异或运算符
·<< or >> or >>> //左移运算符或右移运算符
·13、17、31、1231、1237 //重写 hashCode 方法时常用的素数
·hashCode() //每一个类都自带的方法
·Objects.hashCode(Object o) //return o != null ? o.hashCode() : 0;
·Objects.hash(Object... values) //return Arrays.hashCode(values);
·Arrays.hashCode(Object[] a) 及其重载方法
·包装器的静态方法 hashCode
3. HashMap
1. 数据结构(数组 + 链表/红黑树)
1. 数组
- 存储区间连续
- 寻址容易(O(1)),插入、删除困难(O(n))
2. 链表
- 存储区间离散
- 寻址困难(O(n)),插入、删除容易(O(1))
3. 红黑树
- O(logn)
4. Node
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; //用来定位数组索引位置
final K key;
V value;
Node<K,V> next; //链表的下一个node
Node(int hash, K key, V value, Node<K,V> next) { ... }
public final K getKey(){ ... }
public final V getValue() { ... }
public final String toString() { ... }
public final int hashCode() { ... }
public final V setValue(V newValue) { ... }
public final boolean equals(Object o) { ... }
}
5. 一个实例
map.put("美团","小美");
- 调用”美团”这个key的hashCode()方法得到其hashCode 值(该方法适用于每个Java对象)
- 然后再通过Hash算法的后两步运算(高位运算和取模运算,下文有介绍)来定位该键值对的存储位置,有时两个key会定位到相同的位置,表示发生了Hash碰撞。当然Hash算法计算结果越分散均匀,Hash碰撞的概率就越小,map的存取效率就会越高。
如果哈希桶数组很大,即使较差的Hash算法也会比较分散,如果哈希桶数组数组很小,即使好的Hash算法也会出现较多碰撞,所以就需要在空间成本和时间成本之间权衡,其实就是在根据实际情况确定哈希桶数组的大小,并在此基础上设计好的hash算法减少Hash碰撞。那么通过什么方式来控制map使得Hash碰撞的概率又小,哈希桶数组(Node[] table)占用空间又少呢?答案就是好的Hash算法和扩容机制。
6. 几个参数
int threshold; // 所能容纳的key-value对极限
final float loadFactor; // 负载因子
int modCount;
int size;
- HashMap数组长度默认容量length为16(必须是2的n次方【合数】),loadFactor为负载因子(默认0.75),threshold是HashMap能容纳的最大键值对个数,
threshold = length * loadFactor
。 - 当实际存储的键值对个数size超过threshold时,需要重新resize(扩容),扩容后HashMap容量length是之前的2倍(实现位操作等同于取模的基础)。
- modCount记录HashMap内部结构发生变化的次数,主要用于迭代的快速失败。
2. 确认哈希桶数组索引位置
方法一:
static final int hash(Object key) { //jdk1.8 & jdk1.7
int h;
// h = key.hashCode() 为第一步 取hashCode值
// h ^ (h >>> 16) 为第二步 高位参与运算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
方法二:
static int indexFor(int h, int length) { //jdk1.7的源码,jdk1.8没有这个方法,但是实现原理一样的
return h & (length-1); //第三步 取模运算
}
-
取key的hashCode值
-
高位运算
JDK1.8中,优化了高位运算的算法,主要是从速度、功效、质量来考虑的,这么做可以在数组table的length比较小的时候,也能保证考虑到高低Bit都参与到Hash的计算中,同时不会有太大的开销。
-
取模运算
在length总是2的n次方的前提下,
h & (length -1)
(按位与)运算等价于h % length
(取模)运算,但&比%有更高的效率。
3. Put
- 判断键值对数组table[i]是否为空或为null,否则执行resize()进行扩容;
- 根据键值key计算hash值得到插入的数组索引i,如果table[i]==null,直接新建节点添加,转向6,如果table[i]不为空,转向3;
- 判断table[i]的首个元素是否和key一样,如果相同直接覆盖value,否则转向4,这里的相同指的是hashCode以及equals;
- 判断table[i] 是否为treeNode,即table[i] 是否是红黑树,如果是红黑树,则直接在树中插入键值对,否则转向5;
- 遍历table[i],判断链表长度是否大于8,大于8的话把链表转换为红黑树,在红黑树中执行插入操作,否则进行链表的插入操作;遍历过程中若发现key已经存在直接覆盖value即可;
- 插入成功后,判断实际存在的键值对数量size是否超多了最大容量threshold,如果超过,进行扩容。
4. 扩容机制
当HashMap中实际存储的键值对个数size超过threshold时,需要重新resize(扩容)。
- 创建一个新的哈希桶,将旧的哈希桶中的数据复制到新的哈希桶中,扩容过程涉及到rehash、复制数据,非常耗性能(建议提前预估HashMap大小,减少扩容带来的性能损耗)
- 扩容后HashMap容量length是之前的2倍,最大是2^30
1 void resize(int newCapacity) { //传入新的容量
2 Entry[] oldTable = table; //引用扩容前的Entry数组
3 int oldCapacity = oldTable.length;
4 if (oldCapacity == MAXIMUM_CAPACITY) { //扩容前的数组大小如果已经达到最大(2^30)了
5 threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1),这样以后就不会扩容了
6 return;
7 }
8
9 Entry[] newTable = new Entry[newCapacity]; //初始化一个新的Entry数组
10 transfer(newTable); //!!将数据转移到新的Entry数组里
11 table = newTable; //HashMap的table属性引用新的Entry数组
12 threshold = (int)(newCapacity * loadFactor);//修改阈值
13 }
1 void transfer(Entry[] newTable) {
2 Entry[] src = table; //src引用了旧的Entry数组
3 int newCapacity = newTable.length;
4 for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
5 Entry<K,V> e = src[j]; //取得旧Entry数组的每个元素
6 if (e != null) {
7 src[j] = null;//释放旧Entry数组的对象引用(for循环后,旧的Entry数组不再引用任何对象)
8 do {
9 Entry<K,V> next = e.next;
10 int i = indexFor(e.hash, newCapacity); //!!重新计算每个元素在数组中的位置
11 e.next = newTable[i]; //标记[1]
12 newTable[i] = e; //将元素放在数组上
13 e = next; //访问下一个Entry链上的元素
14 } while (e != null);
15 }
16 }
17 }
5. Fast-fail
在使用迭代器的过程中如果HashMap被修改,那么ConcurrentModificationException
将被抛出,也即Fast-fail策略。
6. JDK1.8的优化
- 头插法 -> 尾插法(避免多线程环境环形链表,造成死循环)
- 链表(时间复杂度:O(n)) -> 红黑树(时间复杂度:O(logn))
- 我们使用的是2次幂的扩展(指长度扩为原来2倍),所以,无需重新计数hash,元素的位置要么是在原位置,要么是在原位置再移动2次幂的位置
7. 线程安全性
HashMap线程不安全,多线程环境会造成死循环(JDK1.8修复),多线程环境建议使用ConcurrentHashMap。
因为在 put 元素的时候,如果触发扩容操作,也就是 rehash ,就会将原数组的内容重新 hash 到新的扩容数组中,但是在扩容这个过程中,其他线程也在进行 put 操作,如果这两个元素 hash 值相同,可能出现同时在同一数组下用链表表示,造成闭环,导致在get时会出现死循环,所以HashMap是线程不安全的。
1. ConcurrentHashMap(推荐)
-
key、value都不为空,否则抛出
NullPointerException
-
支持通过Iterator遍历同时修改HashMap
-
延迟初始化,在
put
时才初始化哈希桶(initTable
) -
Segment
分段锁(继承ReentrantLock可重入锁
):将整个哈希桶分解成多个Segment对象,每个Segment对象可以看作是一个细粒度的哈希桶;理论上可支持concurrencyLevel(等于Segment的个数)个线程安全的并发读写。
-
JDK1.8实现
-
Segment
分段锁 ->CAS
机制(效率高,但CPU资源消耗多) +synchroized
(自旋次数超过阈值时切换位互斥锁) -
CAS(Compare and Swap)机制
CAS 通过将内存中的值与期望值进行比较,只有在两者相等时才会对内存中的值进行修改,CAS 是在保证性能的同时提供并发场景下的线程安全性。
- 原子操作的一种,能保证一次读写操作是原子的
- AtomicInteger
- 缺点
- 循环检查的时间可能较长,不过可以限制循环检查的次数
- 只能对一个共享变量执行原子操作
- 存在 ABA 问题(ABA 问题是指在 CAS 两次检查操作期间,目标变量的值由 A 变为 B,又变回 A,但是 CAS 看不到这中间的变换,对它来说目标变量的值并没有发生变化,一直是 A,所以 CAS 操作会继续更新目标变量的值。)
-
2. CollectionUtils.synchronizedMap()
- 粗粒度的同步方式,在高并发情况下,性能比较低下
-
SynchronizedMap
静态内部类,Object mutex
互斥锁,put
、get
、size
等各种方法加上synchronized
关键字
3. HashTable
- 遗留类,建议用ConcurrentHashMap替换
- 粗粒度的同步方式,在高并发情况下,性能比较低下
-
put
、get
、size
等各种方法加上synchronized
关键字
4. LinkedHashMap
- 有序(插入顺序或访问顺序)
- 线程不安全
1. 基本结构
- HashMap + LinkedList
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {
/**
* The head of the doubly linked list.
* 双向链表的头节点
*/
private transient Entry<K,V> header;
/**
* The iteration ordering method for this linked hash map: true
* for access-order, false for insertion-order.
* true表示最近最少使用次序,false表示插入顺序
*/
private final boolean accessOrder;
}
- 元素
private static class Entry<K,V> extends HashMap.Entry<K,V> {
// These fields comprise the doubly linked list used for iteration.
Entry<K,V> before, after;
Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
super(hash, key, value, next);
}
...
}