1. Map
1.1 HashMap 和 Hashtable 的区别
- 线程是否安全:
HashMap
是非线程安全的,Hashtable
是线程安全的,因为Hashtable
内部的方法基本都经过synchronized
修饰。(如果你要保证线程安全的话就使用ConcurrentHashMap
吧!); - 效率: 因为线程安全的问题,
HashMap
要比Hashtable
效率高一点。另外,Hashtable
基本被淘汰,不要在代码中使用它; - 对 Null key 和 Null value 的支持:
HashMap
可以存储 null 的 key 和 value,但 null 作为键只能有一个,null 作为值可以有多个;Hashtable 不允许有 null 键和 null 值,否则会抛出NullPointerException
。 - 初始容量大小和每次扩充容量大小的不同: ① 创建时如果不指定容量初始值,
Hashtable
默认的初始大小为 11,之后每次扩充,容量变为原来的 2n+1。HashMap
默认的初始化大小为 16。之后每次扩充,容量变为原来的 2 倍。② 创建时如果给定了容量初始值,那么Hashtable
会直接使用你给定的大小,而HashMap
会将其扩充为 2 的幂次方大小(HashMap
中的tableSizeFor()
方法保证,下面给出了源代码)。也就是说HashMap
总是使用 2 的幂作为哈希表的大小,后面会介绍到为什么是 2 的幂次方。 - 底层数据结构: JDK1.8 以后的
HashMap
在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为 8)时,将链表转化为红黑树(将链表转换成红黑树前会判断,如果当前数组的长度小于 64,那么会选择先进行数组扩容,而不是转换为红黑树),以减少搜索时间(后文中我会结合源码对这一过程进行分析)。Hashtable
没有这样的机制。
HashMap
中带有初始容量的构造函数:
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);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
下面这个方法保证了 HashMap
总是使用 2 的幂作为哈希表的大小。
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
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;
}
1.2 HashMap 和 HashSet 区别
如果你看过 HashSet
源码的话就应该知道:HashSet
底层就是基于 HashMap
实现的。(HashSet
的源码非常非常少,因为除了 clone()
、writeObject()
、readObject()
是 HashSet
自己不得不实现之外,其他方法都是直接调用 HashMap
中的方法。
方法都是直接调用 HashMap
中的方法。
HashMap | HashSet |
---|---|
实现了 Map 接口 | 实现 Set 接口 |
存储键值对 | 仅存储对象 |
调用 put() 向 map 中添加元素 | 调用 add() 方法向 Set 中添加元素 |
HashMap 使用键(Key)计算 hashcode | HashSet 使用成员对象来计算 hashcode 值,对于两个对象来说 hashcode 可能相同,所以equals() 方法用来判断对象的相等性 |
1.3 HashMap 和 TreeMap 区别
TreeMap
和HashMap
都继承自AbstractMap
,但是需要注意的是TreeMap
它还实现了NavigableMap
接口和SortedMap
接口。
实现 NavigableMap
接口让 TreeMap
有了对集合内元素的搜索的能力。
实现SortedMap
接口让 TreeMap
有了对集合中的元素根据键排序的能力。默认是按 key 的升序排序,不过我们也可以指定排序的比较器。示例代码如下:
/**
* @author shuang.kou
* @createTime 2020年06月15日 17:02:00
*/
public class Person {
private Integer age;
public Person(Integer age) {
this.age = age;
}
public Integer getAge() {
return age;
}
public static void main(String[] args) {
TreeMap<Person, String> treeMap = new TreeMap<>(new Comparator<Person>() {
@Override
public int compare(Person person1, Person person2) {
int num = person1.getAge() - person2.getAge();
return Integer.compare(num, 0);
}
});
treeMap.put(new Person(3), "person1");
treeMap.put(new Person(18), "person2");
treeMap.put(new Person(35), "person3");
treeMap.put(new Person(16), "person4");
treeMap.entrySet().stream().forEach(personStringEntry -> {
System.out.println(personStringEntry.getValue());
});
}
}
person1
person4
person2
person3
可以看出,TreeMap
中的元素已经是按照 Person
的 age 字段的升序来排列了。
上面,我们是通过传入匿名内部类的方式实现的,你可以将代码替换成 Lambda 表达式实现的方式:
TreeMap<Person, String> treeMap = new TreeMap<>((person1, person2) -> {
int num = person1.getAge() - person2.getAge();
return Integer.compare(num, 0);
});
综上,相比于HashMap
来说 TreeMap
主要多了对集合中的元素根据键排序的能力以及对集合内元素的搜索的能力。
1.4 HashSet 如何检查重复?
当你把对象加入
HashSet
时,HashSet
会先计算对象的hashcode
值来判断对象加入的位置,同时也会与其他加入的对象的hashcode
值作比较,如果没有相符的hashcode
,HashSet
会假设对象没有重复出现。但是如果发现有相同hashcode
值的对象,这时会调用equals()
方法来检查hashcode
相等的对象是否真的相同。如果两者相同,HashSet
就不会让加入操作成功。
在 JDK1.8 中,HashSet
的add()
方法只是简单的调用了HashMap
的put()
方法,并且判断了一下返回值以确保是否有重复元素。直接看一下HashSet
中的源码:
// Returns: true if this set did not already contain the specified element
// 返回值:当 set 中没有包含 add 的元素时返回真
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
而在HashMap
的putVal()
方法中也能看到如下说明:
// Returns : previous value, or null if none
// 返回值:如果插入位置没有元素返回null,否则返回上一个元素
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
...
}
也就是说,在 JDK1.8 中,实际上无论HashSet
中是否已经存在了某元素,HashSet
都会直接插入,只是会在add()
方法的返回值处告诉我们插入前是否存在相同元素。
1.5 HashMap 的底层实现
1.5.1 JDK1.8 之前
JDK1.8 之前 HashMap
底层是 数组和链表 结合在一起使用也就是 链表散列。HashMap 通过 key 的 hashcode
经过扰动函数处理过后得到 hash 值,然后通过 (n - 1) & hash
判断当前元素存放的位置(这里的 n 指的是数组的长度),如果当前位置存在元素的话,就判断该元素与要存入的元素的 hash 值以及 key 是否相同,如果相同的话,直接覆盖,不相同就通过拉链法解决冲突。
所谓扰动函数指的就是 HashMap 的 hash
方法。使用 hash
方法也就是扰动函数是为了防止一些实现比较差的 hashCode()
方法 换句话说使用扰动函数之后可以减少碰撞。
JDK 1.8 HashMap 的 hash 方法源码:
JDK 1.8 的 hash 方法 相比于 JDK 1.7 hash 方法更加简化,但是原理不变。
static final int hash(Object key) {
int h;
// key.hashCode():返回散列值也就是hashcode
// ^:按位异或
// >>>:无符号右移,忽略符号位,空位都以0补齐
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
对比一下 JDK1.7 的 HashMap 的 hash 方法源码.
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);
}
相比于 JDK1.8 的 hash 方法 ,JDK 1.7 的 hash 方法的性能会稍差一点点,因为毕竟扰动了 4 次。
所谓 “拉链法” 就是:将链表和数组相结合。也就是说创建一个链表数组,数组中每一格就是一个链表。若遇到哈希冲突,则将冲突的值加到链表中即可。
1.5.2 JDK1.8 之后
相比于之前的版本, JDK1.8 之后在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为 8)(将链表转换成红黑树前会判断,如果当前数组的长度小于 64,那么会选择先进行数组扩容,而不是转换为红黑树)时,将链表转化为红黑树,以减少搜索时间。
TreeMap、TreeSet 以及 JDK1.8 之后的 HashMap 底层都用到了红黑树。红黑树就是为了解决二叉查找树的缺陷,因为二叉查找树在某些情况下会退化成一个线性结构。
我们来结合源码分析一下 HashMap
链表到红黑树的转换。
1、 putVal
方法中执行链表转红黑树的判断逻辑。
链表的长度大于 8 的时候,就执行 treeifyBin
(转换红黑树)的逻辑。
// 遍历链表
for (int binCount = 0; ; ++binCount) {
// 遍历到链表最后一个节点
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 如果链表元素个数大于等于TREEIFY_THRESHOLD(8)
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;
}
2、treeifyBin
方法中判断是否真的转换为红黑树。
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 判断当前数组的长度是否小于 64
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
// 如果当前数组的长度小于 64,那么会选择先进行数组扩容
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
// 否则才将列表转换为红黑树
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
将链表转换成红黑树前会判断,如果当前数组的长度小于 64,那么会选择先进行数组扩容,而不是转换为红黑树。
1.6 HashMap 的长度为什么是 2 的幂次方
为了能让 HashMap 存取高效,尽量较少碰撞,也就是要尽量把数据分配均匀。我们上面也讲到了过了,Hash 值的范围值-2147483648 到 2147483647,前后加起来大概 40 亿的映射空间,只要哈希函数映射得比较均匀松散,一般应用是很难出现碰撞的。但问题是一个 40 亿长度的数组,内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算,得到的余数才能用来要存放的位置也就是对应的数组下标。这个数组下标的计算方法是“ (n - 1) & hash
”。(n 代表数组长度)。这也就解释了 HashMap 的长度为什么是 2 的幂次方。