集合中用到的数据结构有以下几种:

  • **数组:**最常用的数据结构之一。数组的特点是长度固定,可以用下标索引,并且所有的元素的类型都是一致的。使用时尽量把数组封装在一个类里,防止数据被错误的操作弄乱。
  • **链表:**是一种由多个节点组成的数据结构,并且每个节点包含有数据以及指向下一个节点的引用,在双向链表里,还会有一个指向前一个节点的引用。例如,可以用单向链表和双向链表来实现堆栈和队列,因为链表的两端都是可以进行插入和删除的动作的。当然,也会有在链表的中间频繁插入和删除节点的场景。
  • **树:**是一种由节点组成的数据结构,每个节点都包含数据元素,并且有一个或多个子节点,每个子节点指向一个父节点可以表示层级关系或者数据元素的顺序关系。如果树的每个子节点最多有两个叶子节点,那么这种树被称为二叉树。二叉树是一种非常常用的树形结构, 因为它的这种结构使得节点的插入和删除都非常高效。树的边表示从一个节点到另外一个节点的快捷路径。
  • **堆栈:**只允许对最后插入的元素进行操作(也就是后进先出,Last In First Out – LIFO)。如果你移除了栈顶的元素,那么你可以操作倒数第二个元素,依次类推。这种后进先出的方式是通过仅有的peek(),push()和pop()这几个方法的强制性限制达到的。这种结构在很多场景下都非常实用,例如解析像(4+2)*3这样的数学表达式,把源码中的方法和异常按照他们出现的顺序放到堆栈中,检查你的代码看看小括号和花括号是不是匹配的,等等。
  • **队列:**和堆栈有些相似,不同之处在于在队列里第一个插入的元素也是第一个被删除的元素(即是先进先出)。这种先进先出的结构是通过只提供peek(),offer()和poll()这几个方法来访问数据进行限制来达到的。例如,排队等待公交车,银行或者超市里的等待列队等等,都是可以用队列来表示。

概览

Java 容器主要包括 Collection 和 Map 两种,Collection存储着对象的集合,而Map存储着键值对(两个对象)的映射表。

Collection

Set

  • TreeSet(有序,唯一):基于红黑树实现,支持有序性操作,例如根据一个范围查找元素的操作。但是查找效率不如 HashSet,HashSet 查找的时间复杂度为 O(1),TreeSet 则为 O(logN)。

  • HashSet(无序,唯一):基于Hashmap实现,支持快速查找,但不支持有序性操作。并且失去了元素的插入顺序信息,也就是说使用 Iterator 遍历 HashSet 得到的结果是不确定的。

  • LinkedHashSet:LinkedHashSet 是 HashSet 的子类,并且其内部是通过 LinkedHashMap 来实现的。具有 HashSet 的查找效率,并且内部使用双向链表维护元素的插入顺序。

List

  • ArrayList:基于动态数组 Object[] 实现,支持随机访问。
  • Vector:和 ArrayList 类似,但它是线程安全的。
  • LinkedList:基于双向链表实现 (JDK1.6 之前为循环链表,JDK1.7 取消了循环),只能顺序访问,但是可以快速地在链表中间插入和删除元素。不仅如此,LinkedList 还可以用作栈、队列和双向队列。

Queue

  • LinkedList:可以用它来实现双向队列。
  • PriorityQueue:基于堆结构实现,可以用它来实现优先队列。

Map

  • **TreeMap:**基于红黑树实现。(自平衡的排序二叉树)
  • **HashMap:**JDK1.8 之前 HashMap 由数组+链表组成的,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的(“拉链法”解决冲突)。JDK1.8 以后在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为 8)(将链表转换成红黑树前会判断,如果当前数组的长度小于 64,那么会选择先进行数组扩容,而不是转换为红黑树)时,将链表转化为红黑树,以减少搜索时间
  • **HashTable:**和 HashMap 类似,但它是线程安全的,这意味着同一时刻多个线程同时写入 HashTable 不会导致数据不一致。它是遗留类,不应该去使用它,而是使用 ConcurrentHashMap 来支持线程安全,ConcurrentHashMap 的效率会更高,因为 ConcurrentHashMap 引入了分段锁。
  • **LinkedHashMap:**LinkedHashMap 继承自 HashMap,所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外,LinkedHashMap 在上面结构的基础上,增加了一条双向链表来维护元素的顺序,顺序为插入顺序或者最近最少使用(LRU)顺序。

迭代器 Iterator

Collection 继承了 Iterable 接口,其中的 iterator() 方法能够产生一个 Iterator 对象,通过这个对象就可以迭代遍历 Collection 中的元素。
从 JDK 1.5 之后可以使用 foreach 方法来遍历实现了 Iterable 接口的聚合对象。

1
2
3
4
5
6
7
public interface Iterator<E> {
//集合中是否还有元素
boolean hasNext();
//获得集合中的下一个元素
E next();
......
}

Iterator 对象称为迭代器(设计模式的一种),迭代器可以对集合进行遍历,但每一个集合内部的数据结构可能是不尽相同的,所以每一个集合存和取都很可能是不一样的,虽然我们可以人为地在每一个类中定义 hasNext()next() 方法,但这样做会让整个集合体系过于臃肿。于是就有了迭代器。

迭代器是将这样的方法抽取出接口,然后在每个类的内部,定义自己迭代方式,这样做就规定了整个集合体系的遍历方式都是 hasNext()next()方法,使用者不用管怎么实现的,会用即可。迭代器的定义为:提供一种方法访问一个容器对象中各个元素,而又不需要暴露该对象的内部细节。

迭代器的作用

Iterator 主要用于遍历集合,他的特点是安全。因为它可以确保,当前遍历的集合元素被更改时,抛出 ConcurrentModificationException 异常。

如何使用

1
2
3
4
5
6
7
8
9
Map<Integer, String> map = new HashMap();
map.put(1, "Java");
map.put(2, "C++");
map.put(3, "PHP");
Iterator<Map.Entry<Integer, String>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry<Integer, String> entry = iterator.next();
System.out.println(entry.getKey() + entry.getValue());
}

List

ArrayList

查看专题文章

ArrayList扩容

查看专题文章

Vector

查看专题文章

LinkedList

查看专题文章

Arraylist 和 Vector 的区别?

  1. ArrayList 是 List 的主要实现类,底层使用 Object[ ]存储,适用于频繁的查找工作,线程不安全 ;
  2. Vector 是 List 的古老实现类,底层使用 Object[ ]存储,线程安全的。

Arraylist 与 LinkedList 区别?

  1. 是否保证线程安全: ArrayListLinkedList 都是不同步的,也就是不保证线程安全;
  2. 底层数据结构: Arraylist 底层使用的是 Object 数组LinkedList 底层使用的是 双向链表 数据结构(JDK1.6 之前为循环链表,JDK1.7 取消了循环。注意双向链表和双向循环链表的区别,下面有介绍到!)
  3. 插入和删除是否受元素位置的影响:ArrayList 采用数组存储,所以插入和删除元素的时间复杂度受元素位置的影响。 比如:执行add(E e)方法的时候, ArrayList 会默认在将指定的元素追加到此列表的末尾,这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话(add(int index, E element))时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。 ② LinkedList 采用链表存储,所以对于add(E e)方法的插入,删除元素时间复杂度不受元素位置的影响,近似 O(1),如果是要在指定位置i插入和删除元素的话((add(int index, E element)) 时间复杂度近似为o(n))因为需要先移动到指定位置再插入。
  4. 是否支持快速随机访问: LinkedList 不支持高效的随机元素访问,而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
  5. 内存空间占用: ArrayList 的空 间浪费主要体现在在 list 列表的结尾会预留一定的容量空间,而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间(因为要存放直接后继和直接前驱以及数据)。

Map

Map与List、Set接口不同,它是由一系列键值对组成的集合,提供了key到Value的映射。同时它也没有继承Collection。在Map中它保证了key与value之间的一一对应关系。也就是说一个key对应一个value,所以它不能存在相同的key值,当然value值可以相同。key可以为空,但是只允许出现一个null。它的主要实现类有HashMap、HashTable、LinkedHashMap、TreeMap。

HashMap

HashMap 是 Map 的一个实现类,它代表的是一种键值对的数据存储形式。
大多数情况下可以直接定位到它的值,因而具有很快的访问速度,但遍历顺序却是不确定的。
HashMap最多只允许一条记录的键为null,允许多条记录的值为null。遇到key为null的时候,调用putForNullKey方法进行处理,而对value没有处理。不保证有序(比如插入的顺序)、也不保证序不随时间变化。
jdk 8 之前,其内部是由数组+链表来实现的,而 jdk 8 对于链表长度超过 8 的链表将转储为红黑树。
HashMap非线程安全,即任一时刻可以有多个线程同时写HashMap,可能会导致数据的不一致。如果需要满足线程安全,可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力,或者使用ConcurrentHashMap。
hash数组的默认大小是16,而且大小一定是2的指数

查看专题文章

HashTable

Hashtable和HashMap一样也是散列表,存储元素也是键值对,底层实现是一个Entry数组+链表。Hashtable继承于Dictionary类(Dictionary类声明了操作键值对的接口方法),实现Map接口(定义键值对接口)。HashTable是线程安全的,它的大部分类都被synchronized关键字修饰。key和value都不可为null。
hash数组默认大小是11,扩充方式是old*2+1

LinkedHashMap

LinkedHashMap继承自HashMap实现了Map接口。基本实现同HashMap一样(底层基于数组+链表+红黑树实现),不同之处在于LinkedHashMap保证了迭代的有序性。其内部维护了一个双向链表,解决了 HashMap不能随时保持遍历顺序和插入顺序一致的问题。除此之外,LinkedHashMap对访问顺序也提供了相关支持。在一些场景下,该特性很有用,比如缓存。
在实现上,LinkedHashMap很多方法直接继承自HashMap,仅为维护双向链表覆写了部分方法。
默认情况下,LinkedHashMap的迭代顺序是按照插入节点的顺序。也可以通过改变accessOrder参数的值,使得其遍历顺序按照访问顺序输出。

查看专题文章

TreeMap

TreeMap集合是基于红黑树(Red-Black tree)的 NavigableMap实现。该集合最重要的特点就是可排序,该映射根据其键的自然顺序进行排序,或者根据创建映射时提供的 Comparator 进行排序,具体取决于使用的构造方法。

Set

Set接口继承了Collection接口。Set集合中不能包含重复的元素,每个元素必须是唯一的。你只需将元素加入set中,重复的元素会自动移除。有三种常见的Set实现——HashSet, TreeSet和LinkedHashSet。如果你需要一个访问快速的Set,你应该使用HashSet;当你需要一个排序的Set,你应该使用TreeSet;当你需要记录下插入时的顺序时,你应该使用LinedHashSet。

HashSet

HashSet是是基于 HashMap 实现的,底层采用 HashMap 来保存元素,所以它不保证set 的迭代顺序;特别是它不保证该顺序恒久不变。add()、remove()以及contains()等方法都是复杂度为O(1)的方法。由于HashMap中key不可重复,所以HashSet元素不可重复。可以存储null元素,是线程不安全的。

TreeSet

TreeSet是一个有序集,基于TreeMap实现,是线程不安全的。
TreeSet底层采用TreeMap存储,构造器启动时新建TreeMap。TreeSet存储元素实际为TreeMap存储的键值对为<key,PRESENT>的key;,PRESENT为固定对象:private static final Object PRESENT = new Object().
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
自然排序:

public TreeSet() {
// 新建TreeMap,自然排序
this(new TreeMap<E,Object>());
}

Comparator排序:

public TreeSet(Comparator<? super E> comparator) {
// 新建TreeMap,传入自定义比较器comparator
this(new TreeMap<>(comparator));
}

TreeSet支持正向/反向迭代器遍历和foreach遍历

// 顺序TreeSet:迭代器实现
Iterator iter = set.iterator();
while (iter.hasNext()) {
System.out.println(iter.next());
}

// 顺序遍历TreeSet:foreach实现
for (Integer i : set) {
System.out.println(i);
}

// 逆序遍历TreeSet:反向迭代器实现
Iterator iter1 = set.descendingIterator();
while (iter1.hasNext()) {
System.out.println(iter1.next());
}

LinkedHashSet

LinkedHashSet介于HashSet和TreeSet之间。哈希表和链接列表实现。基本方法的复杂度为O(1)。
LinkedHashSet 是 Set 的一个具体实现,其维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序,该迭代顺序可为插入顺序或是访问顺序。
LinkedHashSet 继承于 HashSet,并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的LinkedHashMap 其内部是基于 Hashmap 实现的一样。
如果我们需要迭代的顺序为插入顺序或者访问顺序,那么 LinkedHashSet 是需要你首先考虑的。
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
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
package java.util;

public class LinkedHashSet<E>

extends HashSet<E>

implements Set<E>, Cloneable, java.io.Serializable {

private static final long serialVersionUID = -2851667679971038690L;

/**
* 构造一个带有指定初始容量和加载因子的空链表哈希set。
*
* 底层会调用父类的构造方法,构造一个有指定初始容量和加载因子的LinkedHashMap实例。
* @param initialCapacity 初始容量。
* @param loadFactor 加载因子。
*/

public LinkedHashSet(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor, true);
}

/**
* 构造一个指定初始容量和默认加载因子0.75的新链表哈希set。
*
* 底层会调用父类的构造方法,构造一个指定初始容量和默认加载因子0.75的LinkedHashMap实例。
* @param initialCapacity 初始容量。
*/
public LinkedHashSet(int initialCapacity) {
super(initialCapacity, .75f, true);
}

/**
* 构造一个默认初始容量16和加载因子0.75的新链表哈希set。
*
* 底层会调用父类的构造方法,构造一个默认初始容量16和加载因子0.75的LinkedHashMap实例。
*/
public LinkedHashSet() {
super(16, .75f, true);
}

/**
* 构造一个与指定collection中的元素相同的新链表哈希set。
*
* 底层会调用父类的构造方法,构造一个足以包含指定collection
* 中所有元素的初始容量和加载因子为0.75的LinkedHashMap实例。
* @param c 其中的元素将存放在此set中的collection。
*/
public LinkedHashSet(Collection<? extends E> c) {
super(Math.max(2*c.size(), 11), .75f, true);
addAll(c);
}

@Override
public Spliterator<E> spliterator() {
return Spliterators.spliterator(this, Spliterator.DISTINCT | Spliterator.ORDERED);
}
}

通过观察HashMap的源码我们可以发现:
Hash Map的前三个构造函数,即访问权限为public类型的构造函数均是以HashMap作为实现。而以LinkedHashMap作为实现的构造函数的访问权限是默认访问权限,即包内访问权限。

即:在java编程中,通过new创建的HashSet对象均是以HashMap作为实现基础。只有在jdk中java.util包内的源代码才可能创建以LinkedHashMap作为实现的HashSet(LinkedHashSet就是通过封装一个以LinkedHashMap为实现的HashSet来实现的)。
只有包含三个参数的构造函数才是采用的LinkedHashMap作为实现。

无序性和不可重复性的含义是什么

1、什么是无序性?无序性不等于随机性 ,无序性是指存储的数据在底层数组中并非按照数组索引的顺序添加 ,而是根据数据的哈希值决定的。
2、什么是不可重复性?不可重复性是指添加的元素按照 equals()判断时 ,返回 false,需要同时重写 equals()方法和 HashCode()方法。

比较 HashSet、LinkedHashSet 和 TreeSet 三者的异同

HashSet 是 Set 接口的主要实现类 ,HashSet 的底层是 HashMap,线程不安全的,可以存储 null 值;
LinkedHashSet 是 HashSet 的子类,能够按照添加的顺序遍历;
TreeSet 底层使用红黑树,能够按照添加元素的顺序进行遍历,排序的方式有自然排序和定制排序。

Set中的元素不能重复,如何实现?

在Java的Set体系中,根据实现方式不同主要分为两大类。HashSet和TreeSet。

TreeSet 是二叉树实现的,Treeset中的数据是自动排好序的,不允许放入null值 2、HashSet 是哈希表实现的,HashSet中的数据是无序的,可以放入null,但只能放入一个null,两者中的值都不能重复,就如数据库中唯一约束

在HashSet中,基本的操作都是有HashMap底层实现的,因为HashSet底层是用HashMap存储数据的。当向HashSet中添加元素的时候,首先计算元素的hashcode值,然后通过扰动计算和按位与的方式计算出这个元素的存储位置,如果这个位置位空,就将元素添加进去;如果不为空,则用equals方法比较元素是否相等,相等就不添加,否则找一个空位添加。

TreeSet的底层是TreeMap的keySet(),而TreeMap是基于红黑树实现的,红黑树是一种平衡二叉查找树,它能保证任何一个节点的左右子树的高度差不会超过较矮的那棵的一倍。

TreeMap是按key排序的,元素在插入TreeSet时compareTo()方法要被调用,所以TreeSet中的元素要实现Comparable接口。TreeSet作为一种Set,它不允许出现重复元素。TreeSet是用compareTo()来判断重复元素的。

Set大多都用的Map接口的实现类来实现的(HashSet基于HashMap实现,TreeSet基于TreeMap实现,LinkedHashSet基于LinkedHashMap实现)在HashMap中通过如下实现来保证key值唯一

1
2
3
4
5
6
7
8
9
10
11
12
13
 // 1. 如果key 相等  
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;

// 2. 修改对应的value
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}

添加元素的时候,如果key(也对应的Set集合的元素)相等,那么则修改value值。而在Set集合中,value值仅仅是一个Object对象罢了(该对象对Set本身而言是无用的)。
也就是说:Set集合如果添加的元素相同时,是根本没有插入的(仅修改了一个无用的value值)。从源码(HashMap)中也看出来,==和equals()方法都有使用!

comparable 和 Comparator 的区别

  • comparable 接口实际上是出自java.lang包 它有一个 compareTo(Object obj)方法用来排序
  • comparator接口实际上是出自 java.util 包它有一个compare(Object obj1, Object obj2)方法用来排序

一般我们需要对一个集合使用自定义排序时,我们就要重写compareTo()方法或compare()方法,当我们需要对某一个集合实现两种排序方式,比如一个 song 对象中的歌名和歌手名分别采用一种排序方法的话,我们可以重写compareTo()方法和使用自制的Comparator方法或者以两个 Comparator 来实现歌名排序和歌星名排序,第二种代表我们只能使用两个参数版的 Collections.sort().

Comparator 定制排序

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
        ArrayList<Integer> arrayList = new ArrayList<Integer>();
arrayList.add(-1);
arrayList.add(3);
arrayList.add(3);
arrayList.add(-5);
arrayList.add(7);
arrayList.add(4);
arrayList.add(-9);
arrayList.add(-7);
System.out.println("原始数组:");
System.out.println(arrayList);
// void reverse(List list):反转
Collections.reverse(arrayList);
System.out.println("Collections.reverse(arrayList):");
System.out.println(arrayList);

// void sort(List list),按自然排序的升序排序
Collections.sort(arrayList);
System.out.println("Collections.sort(arrayList):");
System.out.println(arrayList);
// 定制排序的用法
Collections.sort(arrayList, new Comparator<Integer>() {

@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
});
System.out.println("定制排序后:");
System.out.println(arrayList);

OutPut :

原始数组:
[-1, 3, 3, -5, 7, 4, -9, -7]
Collections.reverse(arrayList):
[-7, -9, 4, 7, -5, 3, 3, -1]
Collections.sort(arrayList):
[-9, -7, -5, -1, 3, 3, 4, 7]
定制排序后:
[7, 4, 3, 3, -1, -5, -7, -9]

重写 compareTo()方法实现按年龄排序

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
// person对象没有实现Comparable接口,所以必须实现,这样才不会出错,才可以使treemap中的数据按顺序排列
// 前面一个例子的String类已经默认实现了Comparable接口,详细可以查看String类的API文档,另外其他
// 像Integer类等都已经实现了Comparable接口,所以不需要另外实现了
public class Person implements Comparable<Person> {
private String name;
private int age;

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

public String getName() {
return name;
}

public void setName(String name) {
this.name = name;
}

public int getAge() {
return age;
}

public void setAge(int age) {
this.age = age;
}

/**
* T重写compareTo方法实现按年龄来排序
*/
@Override
public int compareTo(Person o) {
if (this.age > o.getAge()) {
return 1;
}
if (this.age < o.getAge()) {
return -1;
}
return 0;
}
}

public static void main(String[] args) {
TreeMap<Person, String> pdata = new TreeMap<Person, String>();
pdata.put(new Person("张三", 30), "zhangsan");
pdata.put(new Person("李四", 20), "lisi");
pdata.put(new Person("王五", 10), "wangwu");
pdata.put(new Person("小红", 5), "xiaohong");
// 得到key的值的同时得到key所对应的值
Set<Person> keys = pdata.keySet();
for (Person key : keys) {
System.out.println(key.getAge() + "-" + key.getName());

}
}

OutPut :

5-小红
10-王五
20-李四
30-张三

其他

说说List、Set、Map的区别

List 存储元素有序,可重复。
Set 存储元素无序,不可重复。
Map 使用键值对(kye-value)存储,类似于数学上的函数 y=f(x),“x”代表 key,"y"代表 value,Key 是无序的、不可重复的,value 是无序的、可重复的,每个键最多映射到一个值。

如何选用集合?

主要根据集合的特点来选用,比如我们需要根据键值获取到元素值时就选用 Map 接口下的集合,需要排序时选择 TreeMap,不需要排序时就选择 HashMap,需要保证线程安全就选用 ConcurrentHashMap

当我们只需要存放元素值时,就选择实现Collection 接口的集合,需要保证元素唯一时选择实现 Set 接口的集合比如 TreeSetHashSet,不需要就选择实现 List 接口的比如 ArrayListLinkedList,然后再根据实现这些接口的集合的特点来选用。

为什么要使用集合?

当我们需要保存一组类型相同的数据的时候,我们应该是用一个容器来保存,这个容器就是数组,但是,使用数组存储对象具有一定的弊端, 因为我们在实际开发中,存储的数据的类型是多种多样的,于是,就出现了“集合”,集合同样也是用来存储多个数据的。

数组的缺点是一旦声明之后,长度就不可变了;同时,声明数组时的数据类型也决定了该数组存储的数据的类型;而且,数组存储的数据是有序的、可重复的,特点单一。 但是集合提高了数据存储的灵活性,Java 集合不仅可以用来存储不同类型不同数量的对象,还可以保存具有映射关系的数据

有哪些集合是线程不安全的?怎么解决呢?

我们常用的 Arraylist ,LinkedList,Hashmap,HashSet,TreeSet,TreeMapPriorityQueue 都不是线程安全的。解决办法很简单,可以使用线程安全的集合来代替。
如果你要使用线程安全的集合的话, java.util.concurrent 包中提供了很多并发容器供你使用:

  1. ConcurrentHashMap: 可以看作是线程安全的 HashMap
  2. CopyOnWriteArrayList:可以看作是线程安全的 ArrayList,在读多写少的场合性能非常好,远远好于 Vector.
  3. ConcurrentLinkedQueue:高效的并发队列,使用链表实现。可以看做一个线程安全的 LinkedList,这是一个非阻塞队列。
  4. BlockingQueue: 这是一个接口,JDK 内部通过链表、数组等方式实现了这个接口。表示阻塞队列,非常适合用于作为数据共享的通道。
  5. ConcurrentSkipListMap :跳表的实现。这是一个Map,使用跳表的数据结构进行快速查找。

fail-fast

fail-fast 机制是java集合(Collection)中的一种错误机制。当多个线程对同一个集合的内容进行操作时,就可能会产生fail-fast事件。例如:当某一个线程A通过iterator去遍历某集合的过程中,若该集合的内容被其他线程所改变了;那么线程A访问集合时,就会抛出ConcurrentModificationException异常,产生fail-fast事件。
快速失败(fail—fast)
在用迭代器遍历一个集合对象时,如果遍历过程中对集合对象的内容进行了修改(增加、删除、修改),则会抛出Concurrent Modification Exception。
**原理:**迭代器在遍历时直接访问集合中的内容,并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化,就会改变modCount的值。每当迭代器使用hashNext()/next()遍历下一个元素之前,都会检测modCount变量是否为expectedmodCount值,是的话就返回遍历;否则抛出异常,终止遍历。
注意:这里异常的抛出条件是检测到 modCount!=expectedmodCount 这个条件。如果集合发生变化时修改modCount值刚好又设置为了expectedmodCount值,则异常不会抛出。因此,不能依赖于这个异常是否抛出而进行并发操作的编程,这个异常只建议用于检测并发修改的bug。
场景:java.util包下的集合类都是快速失败的,不能在多线程下发生并发修改(迭代过程中被修改)。
安全失败(fail—safe)
采用安全失败机制的集合容器,在遍历时不是直接在集合内容上访问的,而是先复制原有集合内容,在拷贝的集合上进行遍历。
**原理:**由于迭代时是对原集合的拷贝进行遍历,所以在遍历过程中对原集合所作的修改并不能被迭代器检测到,所以不会触发Concurrent Modification Exception。
缺点:基于拷贝内容的优点是避免了Concurrent Modification Exception,但同样地,迭代器并不能访问到修改后的内容,即:迭代器遍历的是开始遍历那一刻拿到的集合拷贝,在遍历期间原集合发生的修改迭代器是不知道的。
场景:java.util.concurrent包下的容器都是安全失败,可以在多线程下并发使用,并发修改。

Vector和ArrayList

**相同点:**这两个类都实现了List接口,他们都是有序的集合(储存有序),底层都用数组实现。可以通过索引来获取某个元素。允许元素重复和出现null值。ArrayList和Vector的迭代器实现都是fail-fast的。
**不同点:**vector是线程同步的,所以它也是线程安全的,而arraylist是线程异步的,是不安全的。如果不考虑到线程的安全因素,一般用arraylist效率比较高。
扩容时,arraylist扩容1.5倍,vector扩容2倍(或者扩容指定的大小)
ArrayList 和Vector是采用数组方式存储数据,此数组元素数大于实际存储的数据以便增加和插入元素,都允许直接序号索引元素,但是插入数据要设计到数组元素移动等内存操作,所以索引数据快插入数据慢,Vector由于使用了synchronized方法(线程安全)所以性能上比ArrayList要差,LinkedList使用双向链表实现存储,按序号索引数据需要进行向前或向后遍历,但是插入数据时只需要记录本项的前后项即可,所以插入数度较快!

Aarraylist和Linkedlist

ArrayList是基于数组实现的,LinkedList基于双向链表实现的。
ArrayList它支持以下标位置进行索引出对应的元素(随机访问),而LinkedList则需要遍历整个链表来获取对应的元素。因此一般来说ArrayList的访问速度是要比LinkedList要快的
ArrayList由于是数组,对于删除和修改而言消耗是比较大(复制和移动数组实现),LinkedList是双向链表删除和修改只需要修改对应的指针即可,消耗是很小的。因此一般来说LinkedList的增删速度是要比ArrayList要快的
LinkedList比ArrayList消耗更多的内存,因为LinkedList中的每个节点存储了前后节点的引用。
对于增加/删除元素操作
如果增删都是在末尾来操作(每次调用的都是remove()和add()),此时ArrayList就不需要移动和复制数组来进行操作了。如果数据量有百万级的时,速度是会比LinkedList要快的。
如果删除操作的位置是在中间。由于LinkedList的消耗主要是在遍历上,ArrayList的消耗主要是在移动和复制上(底层调用的是arraycopy()方法,是native方法)。LinkedList的遍历速度是要慢于ArrayList的复制移动速度的如果数据量有百万级的时,还是ArrayList要快。

哪些集合类提供对元素的随机访问?

ArrayList、HashMap、TreeMap和HashTable类提供对元素的随机访问。

Enumeration和Iterator接口的区别

Enumeration的速度是Iterator的两倍,也使用更少的内存。Enumeration是非常基础的,也满足了基础的需要。但是,与Enumeration相比,Iterator更加安全,因为当一个集合正在被遍历的时候,它会阻止其它线程去修改集合。
Iterator的方法名比Enumeration更科学Iterator有fail-fast机制,比Enumeration更安全Iterator能够删除元素,Enumeration并不能删除元素

Iterater和ListIterator之间有什么区别?

我们可以使用Iterator来遍历Set和List集合,而ListIterator只能遍历List。Iterator只可以向前遍历,而LIstIterator可以双向遍历。ListIterator从Iterator接口继承,然后添加了一些额外的功能,比如添加一个元素、替换一个元素、获取前面或后面元素的索引位置。

Java中HashMap的key值要是为类对象则该类需要满足什么条件?

需要同时重写该类的hashCode()方法和它的equals()方法。
从源码可以得知,在插入元素的时候是先算出该对象的hashCode。如果hashcode相等话的。那么表明该对象是存储在同一个位置上的。如果调用equals()方法,两个key相同,则替换元素如果调用equals()方法,两个key不相同,则说明该hashCode仅仅是碰巧相同,此时是散列冲突,将新增的元素放在桶子上
重写了equals()方法,就要重写hashCode()的方法。因为equals()认定了这两个对象相同,而同一个对象调用hashCode()方法时,是应该返回相同的值的!

HashSet与HashMap

HashSet 实现了 Set 接口,它不允许集合中有重复的值,当我们提到 HashSet 时,第一件事情就是在将对象存储在 HashSet 之前,要先确保对象重写 equals()和 hashCode()方法,这样才能比较对象的值是否相等,以确保set中没有储存相等的对象。如果我们没有重写这两个方法,将会使用这个方法的默认实现。
public boolean add(Object o)方法用来在 Set 中添加元素,当元素值重复时则会立即返回 false,如果成功添加的话会返回 true。
HashMap 实现了 Map 接口,Map 接口对键值对进行映射。Map 中不允许重复的键。Map 接口有两个基本的实现,HashMap 和 TreeMap。TreeMap 保存了对象的排列次序,而 HashMap 则不能。HashMap 允许键和值为 null。HashMap 是非 synchronized 的,但 collection 框架提供方法能保证 HashMap synchronized,这样多个线程同时访问 HashMap 时,能保证只有一个线程更改 Map。
public Object put(Object Key,Object value)方法用来将元素添加到 map 中。

HashMap HashSet
HashMap实现了Map接口 HashSet实现了Set接口
HashMap储存键值对 HashSet仅仅存储对象
使用put()方法将元素放入map中 使用add()方法将元素放入set中
HashMap中使用键对象来计算hashcode值 HashSet使用成员对象来计算hashcode值,对于两个对象来说hashcode可能相同,所以equals()方法用来判断对象的相等性,如果两个对象不同的话,那么返回false

hashtable与hashmap

**相同点:**储存结构和实现基本相同,都是是实现的Map接口
**不同点:**HashTable是同步的,HashMap是非同步的,需要同步的时候可以ConcurrentHashMap方法
HashMap允许为null,HashTable不允许为null
继承不同,HashMap继承的是AbstractMap,HashTable继承的是Dictionary
HashMap提供对key的Set进行遍历,因此它是fail-fast的,但HashTable提供对key的Enumeration进行遍历,它不支持fail-fast。
HashTable是一个遗留类,如果需要保证线程安全推荐使用CocurrentHashMap

HashMap与TreeMap

HashMap通过hashcode对其内容进行快速查找,而TreeMap中所有的元素都保持着某种固定的顺序,如果你需要得到一个有序的结果你就应该使用TreeMap(HashMap中元素的排列顺序是不固定的)。HashMap中元素的排列顺序是不固定的)。
在Map 中插入、删除和定位元素,HashMap 是最好的选择。但如果您要按自然顺序或自定义顺序遍历键,那么TreeMap会更好。使用HashMap要求添加的键类明确定义了hashCode()和 equals()的实现。 这个TreeMap没有调优选项,因为该树总处于平衡状态。

集合框架中的泛型有什么优点?

Java1.5引入了泛型,所有的集合接口和实现都大量地使用它。泛型允许我们为集合提供一个可以容纳的对象类型,因此,如果你添加其它类型的任何元素,它会在编译时报错。这避免了在运行时出现ClassCastException,因为你将会在编译时得到报错信息。泛型也使得代码整洁,我们不需要使用显式转换和instanceOf操作符。它也给运行时带来好处,因为不会产生类型检查的字节码指令。

comparable 和 comparator的不同之处?

comparable接口实际上是出自java.lang包它有一个 compareTo(Object obj)方法来将objects排序comparator接口实际上是出自 java.util 包它有一个compare(Object obj1, Object obj2)方法来将objects排序

如何保证一个集合线程安全?

Vector, Hashtable, Properties 和 Stack 都是同步的类,所以它们都线程安全的,可以被使用在多线程环境中使用Collections.synchronizedList(list)) 方法,可以保证list类是线程安全的使用java.util.Collections.synchronizedSet()方法可以保证set类是线程安全的。

TreeMap和TreeSet在排序时如何比较元素?Collections工具类中的sort()方法如何比较元素?

TreeSet要求存放的对象所属的类必须实现Comparable接口,该接口提供了比较元素的compareTo()方法,当插入元素时会回调该方法比较元素的大小。
TreeMap要求存放的键值对映射的键必须实现Comparable接口从而根据键对元素进行排序。
Collections工具类的sort方法有两种重载的形式,第一种要求传入的待排序容器中存放的对象比较实现Comparable接口以实现元素的比较;第二种不强制性的要求容器中的元素必须可比较,但是要求传入第二个参数,参数是Comparator接口的子类型(需要重写compare方法实现元素的比较),相当于一个临时定义的排序规则,其实就是通过接口注入比较元素大小的算法,也是对回调模式的应用(Java中对函数式编程的支持)。

什么是Java优先级队列?

Java PriorityQueue是一个数据结构,它是Java集合框架的一部分。 它是一个队列的实现,其中元素的顺序将根据每个元素的优先级来决定。 实例化PriorityQueue时,可以在构造函数中提供比较器。 该比较器将决定PriorityQueue集合实例中元素的排序顺序。

Java hashCode()和equals()方法。

equals()方法用于确定两个Java对象的相等性。 当我们有一个自定义类时,我们需要重写equals()方法并提供一个实现,以便它可以用来找到它的两个实例之间的相等性。 通过Java规范,equals()和hashCode()之间有一个契约。 它说,“如果两个对象相等,即obj1.equals(obj2)为true,那么obj1.hashCode()和obj2.hashCode()必须返回相同的整数”
无论何时我们选择重写equals(),我们都必须重写hashCode()方法。 hashCode()用于计算位置存储区和key。

Enumeration和Iterator区别

函数接口不同

  • Enumeration只有2个函数接口。通过Enumeration,我们只能读取集合的数据,而不能对数据进行修改。
  • Iterator只有3个函数接口。Iterator除了能读取集合的数据之外,也能数据进行删除操作。

Iterator支持fail-fast机制,而Enumeration不支持。

  • Enumeration 是JDK 1.0添加的接口。使用到它的函数包括Vector、Hashtable等类,这些类都是JDK 1.0中加入的,Enumeration存在的目的就是为它们提供遍历接口。Enumeration本身并没有支持同步,而在Vector、Hashtable实现Enumeration时,添加了同步。
  • 而Iterator 是JDK 1.2才添加的接口,它也是为了HashMap、ArrayList等集合提供遍历接口。Iterator是支持fail-fast机制的:当多个线程对同一个集合的内容进行操作时,就可能会产生fail-fast事件。

注意:Enumeration迭代器只能遍历Vector、Hashtable这种古老的集合,因此通常不要使用它,除非在某些极端情况下,不得不使用Enumeration,否则都应该选择Iterator迭代器。

HashMap 和 ConcurrentHashMap 的区别?

ConcurrentHashMap和HashMap的实现方式不一样,虽然都是使用桶数组实现的,但是还是有区别,ConcurrentHashMap对桶数组进行了分段,而HashMap并没有。

ConcurrentHashMap在每一个分段上都用锁进行了保护。HashMap没有锁机制。所以,前者线程安全的,后者不是线程安全的。

HashMap中hash方法的原理

https://hollischuang.github.io/toBeTopJavaer/#/basics/java-basic/hash-in-hashmap

为什么HashMap的默认容量设置成16

https://hollischuang.github.io/toBeTopJavaer/#/basics/java-basic/hashmap-default-capacity

为什么HashMap的默认负载因子设置成0.75

https://hollischuang.github.io/toBeTopJavaer/#/basics/java-basic/hashmap-default-loadfactor

Java 8中stream相关用法

https://hollischuang.github.io/toBeTopJavaer/#/basics/java-basic/stream

Apache集合处理工具类的使用

https://hollischuang.github.io/toBeTopJavaer/#/basics/java-basic/apache-collections

评论




Copyright 2019-2020 YANLIANG'S BLOG 载入天数...载入时分秒...