Hashmap
底层是数组+链表/红黑树实现的。1
2
3
4
5
6
7//成员变量
transient Node<K,V>[] table; //底层数据结构，用于存储添加到HashMap中的Key-value对
transient Set<Map.Entry<K,V>> entrySet; //返回Node实体
transient int size; //Map中的key-value对的数量
transient int modCount;
int threshold;//临界值,当超过临界值时，HashMap就该扩容
final float loadFactor;//装载因子,衡量HashMap满的程度，默认值为DEFAULT_LOAD_FACTOR=0.75f
Node是一个static内部类。多个Node以链表的形式连接起来，然后在Hashmap内用数组来保留这些链表的起点，结合了这两种数据结构，保留了各自的优点，又弥补了各自的缺点。
但是是JDK8中，如果链表长度太长就会转化为红黑树。
- Node<K,V>[] table
1
2
3
4
5
6
7
8
9static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
}
因此Hashmap的结构如下所示。
Set<Map.Entry<K,V>> entrySet
entrySet变量为EntrySet实体，Map.Entry<K,V>是一个接口，Node类就实现了该接口1
2
3
4public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}扩容机制
容量的规则为2的幂次，即capacity可以是1，2，4，8，16，32…
根据传进来的容量来找最近的2的幂次1
2
3
4
5
6
7
8
9static final int tableSizeFor(int capacity) {
int n = capacity - 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;
}
HashSet
是java中Set接口的一个实现类，底层是用Hashmap实现的，而Hashmap是数组+链表/红黑树实现的。如果链表长度大于8，就转化为红黑树，如果容量不够，则需扩容。
1 | public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable |
- 常用方法：
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
33private transient HashMap<E,Object> map;
//初始化一个空的set
public HashSet(){
map = new HashMap<>();
}
// 传入的集合添加到新的set
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);
}
// add， value值是被写死的
private static final Object PRESENT = new Object();
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
// remove，调用map的remove
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
// 遍历
Iterator it = set.iterator();
while (it.hasNext()) {
System.out.println(it.next());
}
LinkedHashSet
是HashSet的派生类。源码没什么实质性的东西，都是对HashSet的一个继承。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23public class LinkedHashSet<E> extends HashSet<E>
implements Set<E>, Cloneable, java.io.Serializable {
public LinkedHashSet(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor, true);
}
public LinkedHashSet(int initialCapacity) {
super(initialCapacity, .75f, true);
}
public LinkedHashSet() {
super(16, .75f, true);
}
public LinkedHashSet(Collection<? extends E> c) {
super(Math.max(2*c.size(), 11), .75f, true);
addAll(c);
}
public Spliterator<E> spliterator() {
return Spliterators.spliterator(this, Spliterator.DISTINCT | Spliterator.ORDERED);
}
}
TreeSet
完全依赖于TreeMap来实现。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable
{
public TreeSet() {
this(new TreeMap<E,Object>());
}
public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<>(comparator));
}
public TreeSet(Collection<? extends E> c) {
this();
addAll(c);
}
public TreeSet(SortedSet<E> s) {
this(s.comparator());
addAll(s);
}
}