Java 集合总结
Java集合类提供了一组接口用于存储/操作一系列的元素。
继承结构
集合类继承结构
Collection
Collection是List以及Set的基类，代表了一组集合，定义了add remove等集合必须实现的接口。
| 方法 | 作用 |
|---|---|
| Iterator<E> iterator() | 返回一个Iterator用于遍历集合 |
| boolean add(E e) | 添加一个元素用于，如果Collection发生了变化，返回true |
| boolean remove(Object o) | 删除一个元素，如果Collection发生变化，返回true |
| int size() | 返回集合中元素的个数 |
| boolean isEmpty() | 如果集合为空则返回true |
List
概述
List接口继承自 Collection，在Collection的基础上增加了随机访问的功能。其增加的方法如下：
| 方法 | 作用 |
|---|---|
| E get(int index) | 返回index位置的元素 |
| E remove(int index) | 删除index位置的元素 |
| void add(int index, E element) | 将元素插入指定位置 |
| boolean addAll(int index, Collection<? extends E> c) | 将集合c插入某个位置 |
ArrayList
ArrayList内部是以数组实现的有如下特点：
- 使用 new ArrayList() 实例化时初始化的是一个空的数组
- 当数组空间不够的时候增加当前数组大小一般的空间，并发生数据拷贝
- 随机读(get(index index))等接口取效率较高
- 指定位置增加，删除等方法都需要移动（拷贝）数组中的数据，效率较低
- 非线程安全
LinkedList
LinkedList实际上是双向链表，其链表节点的定义如下代码：
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
其特点如下:
- 随机访问需要遍历链表，效率较ArrayList低
- 在指定位置删除/增加元素无需移动元素，效率较ArrayList高
Vector
Vector内部依然是以数组实现，其中的方法都增加了synchronized关键字，可以堪称线程安全版的ArrayList。
Set
Set可以看成不允许重复的对象集合。和List对比Set主要缺少了随机访问的一系接口，包括 get(int index), set(int index), sublist(int from,int to)等。
HashSet
HashSet 是一个常见的Set实现，HashSet内部通过一个HashMap来实现，并将对象作为HashMap的Key存储，从而达到没有重复元素的目的。
Map
Map提供了一种映键值对的机制，在map中，一个key只能返回一个Value，并且Key不允许有重复。
HashMap
- HashMap 是以键值对链表数组来存储元素的，其中键值对的基本数据结构如下：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
其中key 和 value代表键，HashMap通过链表来解决冲突，当链表长度较大时则会将链表转换成树以换取更高的效率。
- HashMap中的Hash函数如下:
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
tab[(n - 1) & hash]
通过链表来解决冲突，当链表长度较大（超过64）时则会将链表转换成树以换取更高的效率。
- HashMap默认的Table大小为16，如果添加键值对后size超过一定的大小，则需要重新生成键值对的数组，并重建Hash表。
HashTable
HashTable 可以等价于HashMap，区别有如下几点：
- HashTable是线程安全的，HashMap不是
- HashTable不能接收null作为key，HashMap可以。
常见工具类
Arrays 包含了一系列操作数组的静态方法，包括 sort, fill,binarySearch等。
Collections 包含了一系列操作Collecntion类的静态方法，包括sort,fill,bianrySearch等
常见问题
如何遍历Collection
- 使用Iterator
ArrayList<String> list = new ArrayList<String>();
list.add("A");
list.add("B");
list.add("C");
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
System.out.print(iterator.next());
}
- foreach循环
ArrayList<String> list = new ArrayList<String>();
list.add("A");
list.add("B");
list.add("C");
for (String str : list) {
System.out.print(str);
}
- 转换为数组
ArrayList<String> list = new ArrayList<String>();
list.add("A");
list.add("B");
list.add("C");
String[] strArray = new String[list.size()];
strArray = list.toArray(strArray);
for (int i = 0; i < strArray.length; i++) {
System.out.print(strArray[i]);
}
如何遍历Map
- 通过Key
Map<String, Integer> nameAgeMap = new HashMap<String, Integer>();
nameAgeMap.put("Tom", 1);
nameAgeMap.put("Jerry", 2);
nameAgeMap.put("Alen", 3);
Set<String> keySet = nameAgeMap.keySet();
for (String key : keySet) {
System.out.print("(" + key + ", " + nameAgeMap.get(key) + ")\r\n");
}
- 通过Entry
Map<String, Integer> nameAgeMap = new HashMap<String, Integer>();
nameAgeMap.put("Tom", 1);
nameAgeMap.put("Jerry", 2);
nameAgeMap.put("Alen", 3);
Set<Entry<String, Integer>> entrySet = nameAgeMap.entrySet();
for (Entry<String, Integer> entry : entrySet) {
System.out.print("(" + entry.getKey() + ", " + entry.getValue() + ")\r\n");
}
- 只遍历Value
Map<String, Integer> nameAgeMap = new HashMap<String, Integer>();
nameAgeMap.put("Tom", 1);
nameAgeMap.put("Jerry", 2);
nameAgeMap.put("Alen", 3);
Collection<Integer> values = nameAgeMap.values();
for (int value : values) {
System.out.print("(value is " + value + ")\r\n");
}
LinkedList 和 ArrayList有什么不同
- ArrayList 内部以数组实现，LinkedList是双向链表
- ArrayList 随机访问效率较高
- LinkedList 在插入删除时效率较高
HashSet 和 HashMap有什么不同
- HashSet 是Set 代表个补充复的对象的集合
- HashMao 是Mao，代表了一个键值对的集合
- HashSet 内部是通过HashTable实现的
HashMap 和 Hashtable有什么不同
- Hashtable 线程安全，但是不能接受null作为key
- HashMap 不是线程安全的，可以接受null作为Key
Iterator 和 Enumeration有什么不同
Iterator 和 Enumeration都是Java中的接口，两者的区别如下:
| Iterator | Enumeration | |
|---|---|---|
| 是否还有更多元素 | hasNext | hasMoreElements |
| 返回下一个元素 | next | nextElement |
| 删除上一个获得的元素 | remove | 无 |
Comparable 和 Comparator的区别
Comparable 接口中只定义如下,实现了Comparable的类可以和该类的其他对象进行比较
public interface Comparable<T> {
public int compareTo(T o);
}
Comparator 接口定义如下，实现了Comparator的类可以用于对比一个类的两个实例。
public interface Comparator<T> {
int compare(T o1, T o2);
}
通常有两种情况需要使用到Comparator：
- 比较未实现Comparable类的实例
- 实现了Comparable的类的实现方式和不满足需求
集合排序
以Person类为例，Person类实现了Comprable接口：
static class Person implements Comparable<Person> {
String mName;
int mAge;;
public Person(String name, int age) {
mName = name;
mAge = age;
}
public int compareTo(Person otherPerson) {
return mAge - otherPerson.mAge;
}
@Override
public String toString() {
return "[ " + mName + "," + mAge + " ]";
}
}
- 默认排序
由于Person实现了Comparable接口，可以直接使用Collections.sort方法排序，代码如下:
List<Person> personList = new ArrayList<Person>();
personList.add(new Person("Allen", 30));
personList.add(new Person("Bill", 28));
personList.add(new Person("Carl", 25));
Collections.sort(personList);
for (Person person : personList) {
System.out.print(person + "\r\n");
}
输出如下:
[ Carl,25 ]
[ Bill,28 ]
[ Allen,30 ]
- 通过Comparator 自定义排序方式,代码如下:
List<Person> personList = new ArrayList<Person>();
personList.add(new Person("Allen", 30));
personList.add(new Person("Bill", 28));
personList.add(new Person("Carl", 25));
personList.sort(new Comparator<Person>() {
public int compare(Person arg0, Person arg1) {
return arg0.mName.compareTo(arg1.mName);
}
});
for (Person person : personList) {
System.out.print(person + "\r\n");
}
[ Allen,30 ]
[ Bill,28 ]
[ Carl,25 ]
