Java的容器类,在程序中经常被用,而且也是在面试中经常被问到的部分,笔者近段就被问到过n次了,所以这里就根据网上的一些资料,并结合着openJDK的源码对这些容器类好好总结一下。

Java中的容器

在Java(以JDK1.7为例)中,如果一个程序包含固定数量的且生命周期已知的对象,那么我们可以使用数组来保存这些对象。但是一般情况下,我们在写程序时不知道需要保存多少个对象,对于这种情况,Java的实用类库中提供了一套相当完整的容器类来解决这个问题,其中基本的类型是:

  1. List
  2. Set
  3. Map

这些容器类也称为集合类。

对于它们之间的联系:我是这样理解的,首先Map是一个K-V对的集合(关联数组):

  1. key的集合组成了一个Set,因为key是不允许重复的,且Map不会保存key的插入顺序,所以key可组成一个set;
  2. value的集合组成了一个List,因为value是完全可以重复的,Map会根据key的值来获取value,这些value(如果当key是int型时)就组成了一个List(当然List并不是根据Map实现的)。

上面的三种集合类只是提供了三个基本的接口,实际使用的集合类主要还是在它们的子类,下面这个图比较清楚地介绍了这三种容器类的常用子类(图片来自StackOverFlow

collection

注:图片并没有把所有的继承与接口实现全部表示出来,只是列出了主要的部分,比如:class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable,而class AbstractSet<E> extends AbstractCollection<E> implements Set,而AbstractCollection<E> implements Collection,全部的继承与接口实现机制比较复杂,这里只画出了它们的主要部分,这样方便我们看到这些集合类之间的联系与区别。

对于集合类的分析,这里我们主要从以下几个部分去分析:

  1. 原理:底层如何实现;
  2. 性能:分析这个集合类在具体操作上的复杂度
    • 插入:插入是如何实现的,性能如何;
    • 删除:删除是如何实现的,性能如何;
    • 读取:读取是如何实现的,性能如何;
  3. 其他:比如集合类存储对象时,HashMap里需要重写hash()equals()等性质。

List

首先这里先介绍一下List集合类,List集合存储的是对象的引用或者基本数据类型,而且存储都是有序的,并且可以重复。下面分别介绍三种常见的List类。

ArrayList

源码可以参考ArrayList,我们这里主要摘取几块重要的部分(并非全部代码)

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
private static final int DEFAULT_CAPACITY = 10; // 默认的数组长度
private static final Object[] EMPTY_ELEMENTDATA = {};
private transient Object[] elementData; // transient关键字主要是用于定制序列化方面

private int size;

// 知道数组长度的情况下初始化数组
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
this.elementData = new Object[initialCapacity];
}

public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA;
}

// 动态增加数组的长度,每次动态增加(oldCapacity >> 1)
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}

// 获取元素,先检查index是否在范围,然后直接以数组的方式取出
public E get(int index) {
rangeCheck(index);

return elementData(index);
}

// 修改给定位置的一个元素值
public E set(int index, E element) {
rangeCheck(index);

E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}

// 在list的最后添加一个元素
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}

// 在给定位置添加一个元素(随机插入),这时候需要将该位置后面的所有元素移位
public void add(int index, E element) {
rangeCheckForAdd(index);

ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
size++;
}

// 移出给定位置的一个元素(随机删除),这时候也需要将该位置后面的所有元素移位
public E remove(int index) {
rangeCheck(index);

modCount++;
E oldValue = elementData(index);

int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
elementData[--size] = null; // clear to let GC do its work

return oldValue;
}

// 移出第一个符合要求的元素(需要从最前面开始遍历list)
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
}

通过对代码的分析,下面总结一下ArrayList(测试代码):

  • 原理:基于数组来实现(顺序存储的线性表)
  • 特点:
    1. 动态数组,每次插入时都会检查数组长度是否够用,不够用时需要进行扩大,每次会将数组的长度增加$\frac{N}{2}$,也就是新建一个数组,然后将原来数组的元素拷贝进去;
    2. ArrayList是List接口的可变数组的实现;
    3. 非同步;
    4. 添加、删除操作时,每次都需要把该索引右边的数组整体移动,性能较差,所以ArrayList更擅长随机访问数组,但是在数组中间进行插入或删除元素时较慢;
    5. 内部实现时,使用了transient修饰数组,这保证系统序列化ArrayList对象时不会直接序列化elementData数组,而是通过ArrayList提供的writeObjectreadObject方法定制序列化。

Vector

源码可以参考Vector,我们这里主要摘取几块重要的部分(并非全部代码)

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
public class Vector<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{

protected Object[] elementData;

protected int elementCount;

protected int capacityIncrement; // 数组动态增加时的步长

private static final long serialVersionUID = -2767605614048989439L;

// 初始化list,可以设置步长
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}

public Vector(int initialCapacity) {
this(initialCapacity, 0);
}

public Vector() {
this(10);
}

// 在list最后添加元素
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}

// 在给定位置添加元素
public void add(int index, E element) {
insertElementAt(element, index);
}

// 随机插入元素的实际操作方法,这里也需要移动整个数组
public synchronized void insertElementAt(E obj, int index) {
modCount++;
if (index > elementCount) {
throw new ArrayIndexOutOfBoundsException(index + " > " + elementCount);
}
ensureCapacityHelper(elementCount + 1);
System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
elementData[index] = obj;
elementCount++;
}

// 删除给定位置的元素,也需要整体移动数组
public synchronized E remove(int index) {
modCount++;
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
E oldValue = elementData(index);

int numMoved = elementCount - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
elementData[--elementCount] = null; // Let gc do its work

return oldValue;
}

// 获取给定位置的元素
public synchronized E get(int index) {
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);

return elementData(index);
}

E elementData(int index) {
return (E) elementData[index];
}

Vector与ArrayLis很相似,ArrayList与Vector的大部分方法都是相同,只是Vector添加了synchronized,也就是说,Vector是ArrayList的线程安全版本,但是在序列化方面,ArrayList比Vector更安全。

  • 原理:基于数组实现
  • 特点:
    1. 同步的(方法大都是synchronized的);
    2. 每次扩大时可以通过参数设置扩大的步长;
    3. 对于Vector,没有使用transient修饰数组,而且Vector只提供了一个writeObject方法,并未完全实现定制序列化。

它有一个子类为Stack(线程安全),对于栈,不要求线程安全时,可以使用ArrayDeque实现。

LinkedList

源码可以参考LinkedList,我们这里主要摘取几块重要的部分(并非全部代码)

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
transient int size = 0;

transient Node<E> first; // 指向第一个节点

transient Node<E> last; // 指向最后一个节点

public LinkedList() {
}

public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}

private void linkFirst(E e) {} // 将元素e添加到list的头部

//调用上一个私有方法
public void addFirst(E e) {
linkFirst(e);
}

void linkLast(E e) {} // 将元素添加到list的尾部

// 在节点succ前添加一个元素e
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}

// 删除头节点
private E unlinkFirst(Node<E> f) {}

// 删除尾节点
private E unlinkLast(Node<E> l) {}

// 在list尾部添加元素的实际操作
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}

// 在list最后面添加元素
public boolean add(E e) {
linkLast(e);
return true;
}

// 给定位置添加元素
public void add(int index, E element) {
checkPositionIndex(index);

if (index == size)
linkLast(element);
else
linkBefore(element, node(index)); //调用这个方法
}

// 删除给定的节点
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;

if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}

if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}

x.item = null;
size--;
modCount++;
return element;
}

// 根据索引返回该位置的Node(这个方法会经常调用,通过遍历的方法找到该位置)
Node<E> node(int index) {
// assert isElementIndex(index);

if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}

// 删除指定位置的元素
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}

// 返回指定位置的元素
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
}
  • 原理:基于双向链表实现的(链式存储的线性表)
  • 特点:
    1. 在获取元素的索引时,需要去遍历链表来获取索引(也就是node()方法)。
    2. 它的插入和删除操作比ArrayList更加高效(主要是对于List中间的删除或添加,因为ArrayList需要整体移动右边数组),也正是由于它是基于链表实现的,所以随机访问的效率要比ArrayList差。
    3. 非同步;
    4. 实现了List和Deque接口,既可以做双向链表使用,又可以做队列使用,还可以做栈使用;
    5. 也可以进行定制序列化。

Deque接口是双端队列,既可以作为栈也可以作为队列。

关于LinkedList,笔者做一个test,使用LinkedList分别做链表、队列和栈,参考测试代码

Notice: fail-fast 机制是java集合(Collection)中的一种错误机制。 当多个线程对同一个集合的内容进行操作时,就可能会产生 fail-fast 事件(ConcurrentModificationException)。fail-fast机制,是一种错误检测机制。它只能被用来检测错误,因为JDK并不保证fail-fast机制一定会发生。若在多线程环境下使用 fail-fast机制的集合,建议使用java.util.concurrent包下的类去取代java.util包下的类。

Map

Map一种经常用的容器类型,它存储的是K-V键值对。

HashMap

先讲一下最常用的HashMap吧,还是看一下主要的源码,可以参考HashMap,这里摘取几块重要的部分(并非全部代码)

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable{

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认的长度,这里是16,要求必须是2的次方

static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默认的负载因子

static final Entry<?,?>[] EMPTY_TABLE = {};

transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

transient int size; // map中的长度

final float loadFactor;

// 根据给定大小和负载因子初始化map
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;
threshold = initialCapacity;
init();
}

public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

/// 添加KV对
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { // key相等(hash值还有实际值相等)时,替换value
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i); // 将<key, value>添加到i索引处
return null;
}

// 将KV对添加到给定位置的Entry链上
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}

// 根据key获取相应的value值
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}

// 根据key找到给KV对象
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}

// 根据key删除该元素
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}

// 实际删除该Entry链元素的实际操作
final Entry<K,V> removeEntryForKey(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
while (e != null) {
Entry<K,V> next = e.next;
Object k;
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
}

在Google上找到了一张关于关于HashMap数据存储图,如下所示

hashmap

  • 原理: 基于拉链法的散列表(数组和链表的结合),数组的每个元素都是一个链表的引用,对象的存储位置跟key的hash值有关。
  • 特点:
    1. 允许存放null键和null值;
    2. HashMap数组的长度总是2的n次方(这样才能高效地利用数组空间的存储);
    3. 当key的hash值相同,而值不同时,会添加到链表里,key值相同时,就会覆盖原kv对的value值;
    4. java.util.HashMap不是线程安全的,因此如果在使用迭代器的过程中有其他线程修改了map,那么将抛出ConcurrentModificationException,这就是所谓fail-fast策略;
    5. HashMap在底层吧K-V当成一个整体进行处理,这个整体就是一个Entry对象。
  • 缺点: Hashmap数据有可能出现分布不均匀的情况这样就会影响查询效率,这跟HashCode算法和具体数据有关系,一般需要重写HashCode算法。
  • 性能
    1. 负载因子loadFactor定义为:散列表的实际元素数目(n)/ 散列表的总容量(initialCapacity),当loadFactor达到指定值或者0.75时候,HashMap的总容量自动扩展一倍,以此类推。
    2. 负载因子衡量的是一个散列表的空间的使用程度,负载因子越大表示散列表的装填程度越高,反之愈小。
    3. 负载因子是对时间和空间成本上的一种折衷。增大负载因袭可以减少Hash表所占用的内存空间,但会增加查询时间,而查询是HashMap中对频繁的操作;减少负载因子会提高数据查询的性能,但会增加Hash表所占用的内存空间。

Hashtable

还是看一下主要的源码,可以参考Hashtable,这里摘取几块重要的部分(并非全部代码)

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, java.io.Serializable {

private transient Entry<K,V>[] table;

private transient int count;

private int threshold;

private float loadFactor;

private transient int modCount = 0;

private static final long serialVersionUID = 1421746759512286392L;

static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

// 创建Hashtable
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);
initHashSeedAsNeeded(initialCapacity);
}

public Hashtable(int initialCapacity) {
this(initialCapacity, 0.75f);
}

// 默认是11,与有所HashMap不同
public Hashtable() {
this(11, 0.75f);
}

// 查看是否包含某个KV对
public synchronized boolean containsKey(Object key) {
Entry tab[] = table;
int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return true;
}
}
return false;
}

// 根据key查找KV对的value值
public synchronized V get(Object key) {
Entry tab[] = table;
int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return e.value;
}
}
return null;
}

// 能分配的最大数组长度
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

// 增加数组的长度
protected void rehash() {
int oldCapacity = table.length;
Entry<K,V>[] oldMap = table;

// overflow-conscious code
int newCapacity = (oldCapacity << 1) + 1;
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (oldCapacity == MAX_ARRAY_SIZE)
// Keep running with MAX_ARRAY_SIZE buckets
return;
newCapacity = MAX_ARRAY_SIZE;
}
Entry<K,V>[] newMap = new Entry[newCapacity];

modCount++;
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
boolean rehash = initHashSeedAsNeeded(newCapacity);

table = newMap;

for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry<K,V> old = oldMap[i] ; old != null ; ) {
Entry<K,V> e = old;
old = old.next;

if (rehash) {
e.hash = hash(e.key);
}
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = newMap[index];
newMap[index] = e;
}
}
}

// 添加元素,与HashMap类似
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}

// Makes sure the key is not already in the hashtable.
Entry tab[] = table;
int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
V old = e.value;
e.value = value;
return old;
}
}

modCount++;
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();

tab = table;
hash = hash(key);
index = (hash & 0x7FFFFFFF) % tab.length;
}

// Creates the new entry.
Entry<K,V> e = tab[index];
tab[index] = new Entry<>(hash, key, value, e);
count++;
return null;
}

// 删除元素,如果该key不存在,则返回null
public synchronized V remove(Object key) {
Entry tab[] = table;
int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index], prev = null ; e != null ; prev = e, e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
count--;
V oldValue = e.value;
e.value = null;
return oldValue;
}
}
return null;
}
}
  • 原理:数组+链表(与HashMap一样)
  • 特点:
    1. 和HashMap一样,Hashtable也是一个基于拉链法实现的散列表,它存储的内容是键值对;
    2. Hashtable继承于Dictionary类,实现了Map, Cloneable, java.io.Serializable接口;
    3. 线程安全;
    4. 比较老的类,命名也没有遵循现在Java的驼峰法;
    5. Hashtable的key和value都不允许为null;

LinkedHashMap

还是看一下主要的源码,可以参考LinkedList,这里摘取几块重要的部分(并非全部代码)

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
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>{ // 继承HashMap

private static final long serialVersionUID = 3801124242820219131L;

private transient Entry<K,V> header; // 头元素

private final boolean accessOrder; // 设置迭代顺序,可以设置插入顺序(false)或者访问顺序(true)

public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}

public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}

public LinkedHashMap() {
super();
accessOrder = false;
}

public LinkedHashMap(Map<? extends K, ? extends V> m) {
super(m);
accessOrder = false;
}

public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}

@Override
void init() {
header = new Entry<>(-1, null, null, null);
header.before = header.after = header;
}

// 实际上调用HashMap的方法
public V get(Object key) {
Entry<K,V> e = (Entry<K,V>)getEntry(key);
if (e == null)
return null;
e.recordAccess(this);
return e.value;
}
}

LinkedHashMap的数据的存储方式如下图所示(图片来自LinkedHashMap):

LinkedHashMap

Note:途中蓝色箭头的指针是Entry对象的next指针,而黑色箭头的指针是双向链表的beforeafter指针。

  • 原理:数组+双向链表(有before、after两个指针,所以可以保留插入或访问顺序)
  • 特点:
    1. LinkedHashMap是HashMap的一个子类,它保留插入的顺序, 如果需要输出的顺序和输入时的相同,那么就选用LinkedHashMap;
    2. LinkedHashMap实现与HashMap的不同之处在于,LinkedHashMap维护着一个运行于所有条目的双向链接列表。此链接列表定义了迭代顺序,该迭代顺序可以是插入顺序或者是访问顺序;
    3. 非同步的。如果多个线程同时访问链接的哈希映射,而其中至少一个线程从结构上修改了该映射,则它必须保持外部同步;
    4. 根据链表中元素的顺序可以分为:按插入顺序的链表,和按访问顺序(调用get方法)的链表。默认是按插入顺序排序;
    5. 如果指定按访问顺序排序,那么调用get方法后,会将这次访问的元素移至链表尾部,不断访问可以形成按访问顺序排序的链表;
    6. 底层使用哈希表与双向链表来保存所有元素。其基本操作与父类HashMap相似,它通过重写父类相关的方法,来实现自己的链接列表特性;
    7. LinkedHashMap定义了排序模式accessOrder,该属性为boolean型变量,对于访问顺序,为true;对于插入顺序,则为false。一般情况下,不必指定排序模式,其迭代顺序即为默认为插入顺序;
    8. LinkedHashMap通过继承hashMap中的Entry,并添加两个属性Entry before,after,和header结合起来组成一个双向链表,来实现按插入顺序或访问顺序排序;
    9. 允许使用null值和null键;

关于迭代顺序可以参考测试代码

ConcurrentHashMap

对于线程安全的情况,在不考虑性能问题的时候,我们的解决方案有Hashtable或者Collections.synchronizedMap(hashMap),这两种方式基本都是对整个hash表结构做锁定操作的,这样在锁表的期间,别的线程就需要等待了,无疑性能不高。 但是Java为我们提供了封装好的线程安全的集合类,这些类在java.util.concurrent包内,这里我们介绍一个常用的map子类——ConcurrentHashMap。

源码,可以参考ConcurrentHashMap,这里就不再介绍 ConcurrentHashMap的源码了。

先看一下ConcurrentHashMap的结构,如下图所示

concurrenthashmap

在ConcurrentHashMap内有几个重要的内部类分别是:

  1. HashEntry类:用来封装散列映射表中的键值对,HashEntry的学习可以类比着 HashMap中的Entry。我们的存储键值对的过程中,散列的时候如果发生“碰撞”,将采用拉链法来处理碰撞:把碰撞的 HashEntry 对象链接成一个链表;
  2. Segment类:Segment 的类定义为static final class Segment<K,V> extends ReentrantLock implements Serializable,其继承于 ReentrantLock类,从而使得 Segment对象可以充当锁的角色。Segment中包含HashEntry的数组,其可以守护其包含的若干个桶(HashEntry的数组)。Segment 在某些意义上有点类似于 HashMap了,都是包含了一个数组,而数组中的元素可以是一个链表。
  • 原理:数组+链表,每个数组元素是一个类似于HashMap结构的segment,每个segment又是一个数组和链表的形式,这样在对某个segment操作时,就可以锁住该segment,不影响对其他segment的操作。
  • 特点:
    1. ConcurrentHashMap的实现是依赖于Java内存模型;
    2. 本质也是数组和链表,ConcurrentHashMap数据结构为一个Segment数组,Segment的数据结构为HashEntry的数组,而HashEntry存的是我们的键值对,可以构成链表,默认的Segment是16个,通过key的hash值与16取余确定在哪个桶。
    3. ConcurrentHashMap的结构中包含的Segment的数组,在默认的并发级别会创建包含16个Segment对象的数组。
    4. 执行put方法的时候,会需要加锁来完成,在put操作时锁定的是一个Segment而不是整个ConcurrentHashMap。
    5. ConcurrentHashMap不允许空值。该方法首先有一个Segment的引用s,然后会通过hash()方法对key进行计算,得到哈希值;继而通过调用Segment的put(K key, int hash, V value, boolean onlyIfAbsent)方法进行存储操作。
    6. 在理想状态下,ConcurrentHashMap 可以支持 16 个线程执行并发写操作(如果并发级别设置为 16),及任意数量线程的读操作。

ConcurrentHashMap 的高并发性主要来自于三个方面:

  1. 用分离锁实现多个线程间的更深层次的共享访问。
  2. 用 HashEntery 对象的不变性来降低执行读操作的线程在遍历链表期间对加锁的需求。
  3. 通过对同一个 Volatile 变量的写 / 读访问,协调不同线程间读 / 写操作的内存可见性。

TreeMap

还是看一下主要的源码,可以参考TreeMap,这里摘取几块重要的部分(并非全部代码)

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable{

private final Comparator<? super K> comparator; // 比较器,不设置时使用key的自然顺序

private transient Entry<K,V> root = null;

private transient int size = 0;

private transient int modCount = 0;

public TreeMap() {
comparator = null;
}

// 这里可以设置比较器
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}

public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}

public TreeMap(SortedMap<K, ? extends V> m) {
comparator = m.comparator();
try {
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}

// 插入方法,这个是红黑树中非常重要的方法,根据定制的比较器将插入的元素放在合适的位置
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {
compare(key, key); // type (and possibly null) check

root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else {
if (key == null)
throw new NullPointerException();
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null;
}

// 删除KV对
public V remove(Object key) {
Entry<K,V> p = getEntry(key);
if (p == null)
return null;

V oldValue = p.value;
deleteEntry(p);
return oldValue;
}

// 根据key找到对应的Entry对象,熟悉二叉树的人应该很熟悉这里的结构
final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
if (comparator != null)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
return null;
}

// 很多话方法都会调用这个比较方法(这个方法设置为了final,是不允许修改的)
final int compare(Object k1, Object k2) {
return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
: comparator.compare((K)k1, (K)k2);
}
}
  • 原理:TreeMap基于红黑树(Red-Black tree)实现。该映射根据其键的自然顺序进行排序,或者根据创建映射时提供的 Comparator 进行排序,具体取决于使用的构造方法。
  • 特点:
    1. TreeMap 是一个有序的key-value集合,它是通过红黑树实现的;
    2. TreeMap 继承于AbstractMap,所以它是一个Map,即一个key-value集合;
    3. TreeMap 实现了NavigableMap接口,意味着它支持一系列的导航方法。比如返回有序的key集合;
    4. TreeMap 实现了Cloneable接口,意味着它能被克隆;
    5. TreeMap 实现了java.io.Serializable接口,意味着它支持序列化;
    6. TreeMap是非同步的。 它的iterator 方法返回的迭代器是fail-fastl的;
    7. 可以重写comparable
  • 性能:
    1. 因为底层是使用红黑树保存集合中的Entry对象,这也就意味着TreeMap对于添加元素、取出元素的性能要比HashMap低。当TreeMap添加元素时,需要通过循环找到新增Entry的插入位置,因此比较耗性能;当从TreeMap中取出元素时,需要通过循环才能找到合适的Entry,也比较耗性能;
    2. TreeMap的优势在于:TreeMap中的所有Entry都是按key根据指定排序规则(可以根据重写的comparable定制排序规则)操持有序状态。

这里我做了一个测试,使用TreeMapTest(及其自定义排序形式)与HashMap做一下对比(测试代码

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.TreeMap;

/**
* Created by matt on 5/13/16.
*/
public class TreeMapTest {
public static void main(String[] args) {
TreeMap<String, String> treeMap = new TreeMap<>();
HashMap<String, String> hashMap = new HashMap<>();

treeMap.put("a", "wm0");
treeMap.put("b", "wm1");
treeMap.put("c", "wm2");
treeMap.put("d", "wm3");
Iterator tree = treeMap.keySet().iterator();
System.out.println("TreeMap:");
while (tree.hasNext()) {
Object key = tree.next();
System.out.println(key.toString() + " " + treeMap.get(key));
}


TreeMap<String,String> treeMap1 = new TreeMap<String,String>(new Comparator(){
@Override
public int compare(Object o1, Object o2) {
// TODO Auto-generated method stub
String a = (String)o1;
String b = (String)o2;
return -a.compareTo(b);
}});
treeMap1.put("a", "wm0");
treeMap1.put("b", "wm1");
treeMap1.put("c", "wm2");
treeMap1.put("d", "wm3");
Iterator tree1 = treeMap1.keySet().iterator();
System.out.println("\nTreeMap(根据value排序):");
while (tree1.hasNext()) {
Object key = tree1.next();
System.out.println(key.toString() + " " + treeMap1.get(key));
}

hashMap.put("a", "wm0");
hashMap.put("b", "wm1");
hashMap.put("c", "wm2");
hashMap.put("d", "wm3");
Iterator hash = hashMap.keySet().iterator();
System.out.println("\nHashMap:");
while (hash.hasNext()) {
Object key = hash.next();
System.out.println(key.toString() + " " + hashMap.get(key));
}
}
}


/**
* Output:
* TreeMap:
* a wm0
* b wm1
* c wm2
* d wm3
*
* TreeMap(根据value排序):
* d wm3
* c wm2
* b wm1
* a wm0
*
* HashMap:
* d wm3
* b wm1
* c wm2
* a wm0
*/

Set

下面开始介绍Set了,Set是不保存重复元素的集合。当保存对象引用,一般情况下,对象需要重写equals()hashCode()方法,不重写的话,就会使用对应Map(HashMap,TreeMap)的判断方法。

因为Set集合类的底层实现大都与前面的类似,所以下面会介绍稍微简洁一些。

HashSet

先介绍一下HashSet,还是看一下主要的源码,可以参考HashSet,这里摘取几块重要的部分(并非全部代码)

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
public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable{

static final long serialVersionUID = -5024744406713321676L;

private transient HashMap<E,Object> map; // 使用HashMap实现

private static final Object PRESENT = new Object(); // map中默认的value值

// 构造方法都是借助与HashMap实现
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);
}

// 感觉这个应该是老方法,构造对象时是无法使用这个方法的
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

// 添加元素,这个方法本质上还是调用了HashMap的方法
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}

// 删除元素
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}

public boolean contains(Object o) {
return map.containsKey(o);
}
}

从上面的源码中,我们可以看到,HashSet的实现其实非常简单,他只是封装了一个HashMap对象来存储所有的集合元素。所有放入HashSet中的集合元素实际上由HashMap的key来保存,而HashMap的value则存储了一个PRESENT,它是一个静态的Object对象。

  • 原理:HashSet底层使用HashMap来保存所有元素(value出存储了一个静态的Object对象)。
  • 特点:
    1. HashSet实现了Set接口,它不允许集合中有重复的值;
    2. HashSet的随机读取和写入还是很快的,同样也会出现与HashMap一样的问题,即有可能出现数据不均匀的情况;
    3. 重写equals()hashCode()方法,这样才能比较对象的值是否相等,以确保set中没有储存相等的对象;
    4. 当向Set添加元素时,如果与Set中的某一个元素比较时,当equals()比较返回true和hashCode()的返回值相等时,此时,元素就会添加失败(并不会覆盖Set中的元素,因为在HashMap中,遇到这种情况,只是覆盖value,不会覆盖key,而HashSet是基于HashMap实现的,所以元素也并不会被覆盖,只是会添加失败);

下面我们看一个三个测试用例,来说明使用HashSet存储对象引用时,重写equals()hashCode()方法的重要性。

Test1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Person {
private String name;
private int age;
public Person(String name, int age){
this.name=name;
this.age=age;
}
}

public class HashSetTest {
public static void main(String[] args) {
HashSet<Person> set=new HashSet<>();
set.add(new Person("wm",12));
System.out.println(set.contains(new Person("wm",123)));
}
}

/**
* Output: false
*/

Test2:

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
public class Person {
private String name;
private int age;
public Person(String name, int age){
this.name=name;
this.age=age;
}
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o.getClass() == Person.class) {
Person per = (Person) o;
return this.age == per.age && this.name.equals(per.name);
}
return false;
}
}

public class HashSetTest {
public static void main(String[] args) {
HashSet<Person> set=new HashSet<>();
set.add(new Person("wm",12));
System.out.println(set.contains(new Person("wm",123)));
}
}

/**
* 因为两个对象的hash值不同,这样就会当作两个对象来处理。
* Output: false
*/

Test3:

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
public class Person {
private String name;
private int age;

public Person(String name, int age) {
this.name = name;
this.age = age;
}

public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o.getClass() == Person.class) {
Person per = (Person) o;
return this.name.equals(per.name);
}
return false;
}

public int hashCode(){
return name.hashCode();
}
}


public class HashSetTest {
public static void main(String[] args) {
HashSet<Person> set=new HashSet<>();
set.add(new Person("wm",12));
System.out.println(set.contains(new Person("wm",123)));
}
}

/**
* 重写的equals和hashCode方法的返回值必须保持一致,当两个类的hashCode()返回值相同时,
* 它们通过equals()方法的比较也应该相同。
* Output: true
*/

LinkedHashSet

还是先看一下主要的源码,可以参考LinkedHashSet,这里摘取几块重要的部分(并非全部代码)

对于 LinkedHashSet 而言,它继承与 HashSet、又基于 LinkedHashMap 来实现的。

LinkedHashSet 底层使用 LinkedHashMap 来保存所有元素,它继承与 HashSet,其所有的方法操作上又与 HashSet 相同,因此 LinkedHashSet 的实现上非常简单,只提供了四个构造方法,并通过传递一个标识参数,调用父类的构造器,底层构造一个 LinkedHashMap 来实现,在相关操作上与父类 HashSet 的操作相同,直接调用父类 HashSet 的方法即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class LinkedHashSet<E> extends HashSet<E> implements Set<E>, Cloneable, java.io.Serializable {

private static final long serialVersionUID = -2851667679971038690L;

// 实际上是调用了HashSet中的default方法(该方法只能在包内或同一个文件内部调用),实际使用LinkedHashMap实现
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);
}
}
  • 原理:继承于HashSet、又基于LinkedHashMap来实现。
  • 特点:
    1. 是一个Set的实现,所以它其中存的肯定不是键值对,而是值;
    2. 与HashSet的不同之处在于,LinkedHashSet维护着一个运行于所有条目的双向链接列表。 此链接列表定义了迭代顺序,该迭代顺序可为插入顺序或是访问顺序;
    3. 非同步。如果多个线程同时访问链接的哈希Set,而其中至少一个线程修改了该Set,则它必须保持外部同步;
    4. 继承于HashSet、又基于LinkedHashMap(父类HashSet实现时专门为其提供了一个LinkedHashMap的构造方法)来实现的。

TreeSet

TreeSet源码,可以参考TreeSet

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 class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable{

private transient NavigableMap<E,Object> m;

private static final Object PRESENT = new Object();

TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}

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);
}
}

由上面的源码可知,TreeSet底层采用一个NavigableMap来保存TreeSet集合的元素。但实际上,由于NavigableMap只是一个接口,因此底层依然是使用了TreeMap来包含Set集合中的所有元素。TreeSet里绝大多数方法都是直接使用TreeMap的方法来实现的,因此在上面的源码只列出简单的TreeSet的构造方法。

  • 原理:基于TreeMap实现的。
  • 特点:TreeSet中的所有元素总是根据指定排序规则保存有序状态(可以自定义TreeSet的排序规则)。

下面给一个例子(测试代码

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
import java.util.Comparator;
import java.util.Iterator;
import java.util.TreeSet;

/**
* Created by matt on 5/13/16.
*/
public class TreeSetTest {
public static void main(String[] args) {
TreeSet<String> treeSet=new TreeSet<>();
treeSet.add("wm0");
treeSet.add("wm1");
treeSet.add("matt0");
treeSet.add("matt1");
Iterator tree=treeSet.iterator();
System.out.println("HashSet(默认排序规则):");
while (tree.hasNext()){
System.out.println(tree.next());
}

TreeSet<String> treeSet1 = new TreeSet<String>(new Comparator(){
@Override
public int compare(Object o1, Object o2) {
// TODO Auto-generated method stub
String a = (String)o1;
String b = (String)o2;
return -a.compareTo(b);
}});
treeSet1.add("wm0");
treeSet1.add("wm1");
treeSet1.add("matt0");
treeSet1.add("matt1");
System.out.println("\nHashSet(向反的默认排序规则):");
Iterator tree1=treeSet1.iterator();
while (tree1.hasNext()){
System.out.println(tree1.next());
}
}
}
/**
* HashSet(默认排序规则):
* matt0
* matt1
* wm0
* wm1
*
* HashSet(向反的默认排序规则):
* wm1
* wm0
* matt1
* matt0
* /

常见面试题

这里理出一些常见的面试题,大部分题并未给出准确的回答,大家可以根据前面的分析自行总结。

  1. ArrayList VS Vector
  2. ArrayList VS LinkedList
    • ArrayList和LinkedList是两个集合 类,用于存储一系列的对象引用(references)。一般大家都知道ArrayList和LinkedList的大致区别:
    1. ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。
    2. 对于随机访问get和set,ArrayList觉得优于LinkedList,因为LinkedList要进行遍历。
    3. 对于新增和删除操作add和remove,LinkedList比较占优势,因为ArrayList要移动部分数据。
  3. 说你知道的几个Java集合类:list、set、queue、map实现类。
    • Map接口
      映射。主要存储一组组具有映射关系的数据,映射关系主要用key/value的键值对形式表示,一组键值对构成了Map的内部类Entry,所以可以把Map当做由Entry构成的集合。
    • List接口
      表。这个表可以是数组实现的ArrayList,也可以是链表实现的LinkedList。比较古老的实现是Vector,现在不推荐使用,包括它的子类Stack,尽管它是线程安全的。List集合代表一个元素有序、可重复的集合,集合中每个元素都有其对应的顺序索引。List集合允许加入重复元素,因为它可以通过索引来访问指定位置的集合元素。
    • Queue接口
      模拟”队列”这种数据结构
    • Set 接口
      Set是只有Key值,value值为NULL的一个特殊的Map。 只能通过iterator访问元素。
  4. Java中的队列都有哪些,有什么区别。
  5. Java数组和链表两种结构的操作效率,在哪些情况下(从开头开始,从结尾开始,从中间开始),哪些操作(插入,查找,删除)的效率高?
  6. HashMap与HashTable的区别?
    1. 继承的父类不同,HashTable基于Dictionary类,而HashMap是基于AbstractMap,它们都实现了Map接口。Dictionary是任何可将键映射到相应值的类的抽象父类,而AbstractMap是基于Map接口的实现;
    2. key和value是否允许出现null值。HashMap的key和value都允许为null,而Hashtable的key和value都不允许为null。HashMap遇到key为null的时候,调用putForNullKey方法进行处理,而对value没有处理;Hashtable遇到null,直接返回NullPointerException;
    3. 线程安全不同,Hashtable中的几乎所有的public的方法都是synchronized的,而有些方法也是在内部通过synchronized代码块来实现。在多线程并发的环境下,可以直接使用Hashtable,不需要自己为它的方法实现同步,但使用HashMap时就必须要自己增加同步处理;
    4. 是否提供contains方法,HashMap把Hashtable的contains方法去掉了,改成containsValue和containsKey,因为contains方法容易让人引起误解。Hashtable则保留了contains,containsValue和containsKey三个方法,其中contains和containsValue功能相同;
    5. 内部实现使用的数组初始化和扩容方式不同,HashTable中hash数组默认大小是11,增加的方式是 $old*2+1$,HashMap中hash数组的默认大小是16,而且一定是2的指数;
    6. 两个遍历方式的内部实现上不同,Hashtable、HashMap都使用了 Iterator,Hashtable还保留了Enumeration的方式 ;
    7. hash值不同,哈希值的使用不同,HashTable直接使用对象的hashCode,而HashMap重新计算hash值。
  7. HashMap冲突很厉害,最差性能,你会怎么解决?从$O(n)$提升到$\log{n}$。
  8. HashMap和Concurrent HashMap区别, Concurrent HashMap 线程安全吗, Concurrent HashMap如何保证 线程安全?
  9. Hash冲突怎么办?哪些解决散列冲突的方法?
    1. 基于拉链法的散列表
    • 原理:数组+链表(HashMap的实现方式)
    • 特点:
    1. 方法:一,根据散列值查找相应的链表;二,沿着链表查找相应的键;
    2. 性能:对于一张含有M条链表和N个键的散列表中,未命中查找和插入操所需的比较次数都为$~\frac{N}{M}$。
    3. 基于线性探测法的散列表
    • 原理:用大小为M的数组保存N个键值对($M>N$)。利用空位,也称为开放地址散列表。
    • 特点:当发生碰撞时,直接检查散列表的下一个位置(索引值加1),会有三种结果:
    1. 命中,该位置的键和被查找的键相同;
    2. 未命中,键为空;
    3. 继续查找,该位置的键和被查找的键不同。
    • 缺点:进行删除操作时,删除键右边的所有键(连在一起)需要重新插入散列表。
  10. hashCode() 与 equals() 生成算法、方法怎么重写。
  11. 如果不让你用Java Jdk提供的工具,你自己实现一个Map,你怎么做。说了好久,说了HashMap源代码,如果我做,就会借鉴HashMap的原理,说了一通HashMap实现。
  12. 常用的hash算法有哪些?
    • 除法hash:求余;
    • 乘法hash;
  13. 什么是一致性哈希?(参考五分钟理解一致性Hash算法
    为了解决因特网中的热点(Hot spot)问题,初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题。
    判定哈希算法好坏的四个定义:
    1. 平衡性(Balance):平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去,这样可以使得所有的缓冲空间都得到利用;
    2. 单调性(Monotonicity):单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中,又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去,而不会被映射到旧的缓冲集合中的其他缓冲区。;
    3. 分散性(Spread):在分布式环境中,终端有可能看不到所有的缓冲,而是只能看到其中的一部分。好的哈希算法应能够尽量避免不一致的情况发生,也就是尽量降低分散性;
    4. 负载(Load):负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中,那么对于一个特定的缓冲区而言,也可能被不同的用户映射为不同 的内容。与分散性一样,这种情况也是应当避免的,因此好的哈希算法应能够尽量降低缓冲的负荷;
      在一致性哈希算法中,为了尽可能的满足平衡性,其引入了虚拟节点:虚拟节点( virtual node )是实际节点(机器)在 hash 空间的复制品( replica ),一实际个节点(机器)对应了若干个“虚拟节点”,这个对应个数也成为“复制个数”,“虚拟节点”在 hash 空间中以hash值排列.
  14. ReHash
    ReHash的过程其实是空间和时间的双重重大损失,ReHash的过程其实就是一个动态扩容的过程,而哈希表的扩容是个空间和时间消耗都非常惊人的内部操作。
    1. 原来当我们对哈希结构的容器进行扩容时,散列表内部要重新new一个更大的数组,然后把原来数组的内容拷贝到新数组,并进行重新散列;
    2. new出来的这个更大的新数组容量有多大也是一门学问,一般来说,新数组的大小会设置成原数组双倍大小的相近的一个素数

参考: