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内部是以数组实现的有如下特点：

1. 使用 new ArrayList() 实例化时初始化的是一个空的数组
2. 当数组空间不够的时候增加当前数组大小一般的空间，并发生数据拷贝
3. 随机读(get(index index))等接口取效率较高
4. 指定位置增加，删除等方法都需要移动（拷贝）数组中的数据，效率较低
5. 非线程安全

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

其特点如下:

1. 随机访问需要遍历链表，效率较ArrayList低
2. 在指定位置删除/增加元素无需移动元素，效率较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，区别有如下几点：

1. HashTable是线程安全的，HashMap不是
2. HashTable不能接收null作为key，HashMap可以。

常见工具类

• Arrays 包含了一系列操作数组的静态方法，包括 sort, fill,binarySearch等。

• Collections 包含了一系列操作Collecntion类的静态方法，包括sort,fill,bianrySearch等

常见问题

如何遍历Collection

1. 使用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());
}

2. foreach循环

ArrayList<String> list = new ArrayList<String>();
list.add("A");
list.add("B");
list.add("C");
for (String str : list) {
    System.out.print(str);
}

3. 转换为数组

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

1. 通过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");
}

2. 通过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");
}

3. 只遍历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：

1. 比较未实现Comparable类的实例
2. 实现了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 + " ]";
    }
}

1. 默认排序
   由于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 ]

2. 通过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 ]