集合类(一)

HashMap/HashSet/HashTable

HashMap

存储＜K,V＞的容器，并且保证其中的K是唯一的(可以为null)，线程不安全

定义

继承AbstractMap，实现Map

1
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

底层存储

Java8中，HashMap底层实际上是基于一个Node类型的数组

1
transient Node<K,V>[] table;

属性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//默认初始容量(即桶的数量): 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认装载因子
//此值表示当前容量的HashMap装entry满的程度，当entry数量大于当前容量与装载因子的乘积时，HashMap就会进行rehash操作。
//也就是HashMap会扩充容量，扩充容量之后整个HashMap就会重建
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//当桶中的元素大于此阀值时使用树代替单向链表，即红黑树
static final int TREEIFY_THRESHOLD = 8;
//当桶中的元素小于此阀值时，树转成单向链表
static final int UNTREEIFY_THRESHOLD = 6;
//HashMap中所有元素总数小于此值时，即使桶中元素超过TREEIFY_THRESHOLD，也不转成树
static final int MIN_TREEIFY_CAPACITY = 64;

构造函数

1
2
3
4
5
6
7
8
9
10
11
12
	
//默认构造方法，装载因子设置为默认值0.75
public HashMap()
//指定初始容量和加载因子
public HashMap(int initialCapacity, float loadFactor)
//指定初始容量
public HashMap(int initialCapacity)
//使用一个Map来初始化一个HashMap
public HashMap(Map<? extends K, ? extends V> m)

底层存储结构

resize与树化的缘由：随着结点的增多，单个桶中的元素越来越大，即链表的长度越来越长，导致链表的相关操作的性能越来越差

resize

1
2
3
//当HashMap的size达到此值时就要进行resize操作
//计算方式: capacity * load factor -> 即容量*装填因子
int threshold;

具体resize方法可查看具体源码

1
final Node<K, V>[] resize()

容量不能超过MAXIMUM_CAPACITY上限，新容量为旧容量的2倍，新阀值为旧阀值的2倍

树化

当HashMap的容量大于MIN_TREEIFY_CAPACITY 并且桶中元素数量大于等于TREEIFY_THRESHOLD 时，
该桶中的元素结构就会由链表结构转成树结构以提高性能

具体可查看树化函数源码

1
2
3
4
//保证桶中元素和HashMap容量同时满足条件才对相应桶进行树化，否则只进行resize操作
final void treeifyBin(Node<K,V>[] tab, int hash)
//具体树化算法
final void treeify(Node<K,V>[] tab)

把链表中每个结点都替换成树结点，实际上是创建一个新链表，结点类型由Node变为TreeNode

put(key,value)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
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;
	// 如果Node节点数组为空或者节点数目为0，则进行resize操作
	if ((tab = table) == null || (n = tab.length) == 0)
		n = (tab = resize()).length;
	// 通过(n-1)&hash查找hash表中的数组索引，该计算方式可保证查找的位置不会大于数组长度
	// 若为null，则在该索引位置创建新的节点
	if ((p = tab[i = (n - 1) & hash]) == null)
		tab[i] = newNode(hash, key, value, null);
	else {
		Node<K,V> e; K k;
		// 要查询的节点已存在，直接覆盖value
		if (p.hash == hash &&
			((k = p.key) == key || (key != null && key.equals(k))))
			e = p;
		// 红黑树情况，则调用红黑树中的putTreeVal方法获取要查询的节点
		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) {
				    // e为空，表示已到表尾也没有找到key值相同节点，则新建节点
					p.next = newNode(hash, key, value, null);
					// 链表长度 >= TREEIFY_THRESHOLD - 1，改为红黑树存储
					if (binCount >= TREEIFY_THRESHOLD - 1)
						treeifyBin(tab, hash);
					break;
				}
				// key已经存在直接覆盖value
				if (e.hash == hash &&
					((k = e.key) == key || (key != null && key.equals(k))))
					break;
				p = e;
			}
		}
		//更新hash值和key值均相同的节点Value值
		if (e != null) { 
			V oldValue = e.value;
			if (!onlyIfAbsent || oldValue == null)
				e.value = value;
			afterNodeAccess(e);
			return oldValue;
		}
	}
	//修改次数增加1  
	++modCount;
	//超过最大容量，resize()扩容操作
	if (++size > threshold)
		resize();
	afterNodeInsertion(evict);
	return null;
}

get(Object key)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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;
	//(n - 1) & hash得到对象的保存位
	if ((tab = table) != null && (n = tab.length) > 0 &&
		(first = tab[(n - 1) & hash]) != null) {
		if (first.hash == hash && // always check first node
			((k = first.key) == key || (key != null && key.equals(k))))
			return first;
		if ((e = first.next) != null) {
		    //红黑树情况
			if (first instanceof TreeNode)
				return ((TreeNode<K,V>)first).getTreeNode(hash, key);
			//链表情况
			do {
				if (e.hash == hash &&
					((k = e.key) == key || (key != null && key.equals(k))))
					return e;
			} while ((e = e.next) != null);
		}
	}
	return null;
}

HashSet

元素唯一且无序

定义

继承AbstractSet，实现Set

1
public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable

属性

1
2
3
private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public HashSet() {
	map = new HashMap<>();
}
public HashSet(Collection<? extends E> c) {
	map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
	addAll(c);
}
public HashSet(int initialCapacity, float loadFactor) {
	map = new HashMap<>(initialCapacity, loadFactor);
}
public HashSet(int initialCapacity) {
	map = new HashMap<>(initialCapacity);
}
/**
 * 底层使用LinkedHashMap，其他几个都是HashMap
 * dummy参数，仅仅是为了区别于上面第3个构造方法
 * 访问权限是包权限，不对外公开，实际上这个构造方法在LinkedHashSet被使用到
 */
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
	map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

常用方法

基本都是基于HashMap的操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 *往集合中新增元素，map.put(e, PRESENT)会返回map中插入前旧的value，即如果key已经存在，
 *那么返回PRESENT否则返回NULL。从这里可以看出，如果新增的key已存在add方法会返回false。
 */
public boolean add(E e) {
	return map.put(e, PRESENT) == null;
}
//删除集合中的元素，返回删除的元素，如果删除的元素不存在则返回false
public boolean remove(Object o) {
	return map.remove(o) == PRESENT;
}
//迭代器
public Iterator<E> iterator() {
	return map.keySet().iterator();
}

HashTable

与HashMap相比，HashTable中的key和value都不允许为null
线程安全，类中大部分方法都为synchronized修饰的方法

定义

继承Dictionary，实现Map

1
public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, java.io.Serializable

具体内部实现，参阅源码。。