Java 集合
2017-02-04 本文已影响41人
酱油和醋
1 java集合的接口框架
集合的接口框架
集合1.png
Java集合分为Collections和Map两大种。
2 Collection集合
定义了Collection集合分支的基础方法，有查询方法，修改集合方法，批量操作方法和比较与hash方法，这些都是集合的基础方法。
package java.util;
import java.util.function.Predicate;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;
public interface Collection<E> extends Iterable<E> {
// Query Operations
int size();
boolean isEmpty();
boolean contains(Object o);
Iterator<E> iterator();
Object[] toArray();
<T> T[] toArray(T[] a);
// Modification Operations
boolean add(E e);
boolean remove(Object o);
// Bulk Operations
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c);
boolean removeAll(Collection<?> c);
default boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
boolean removed = false;
final Iterator<E> each = iterator();
while (each.hasNext()) {
if (filter.test(each.next())) {
each.remove();
removed = true;
}
}
return removed;
}
boolean retainAll(Collection<?> c);
void clear();
// Comparison and hashing
boolean equals(Object o);
int hashCode();
default Spliterator<E> spliterator() {
return Spliterators.spliterator(this, 0);
}
default Stream<E> stream() {
return StreamSupport.stream(spliterator(), false);
}
default Stream<E> parallelStream() {
return StreamSupport.stream(spliterator(), true);
}
}
Collection分为这几类
1.List: 有序集合，值允许有重复
2.Set:无需集合，值不允许有重复
3.Queue:保持先进先出顺序
2.1 List集合: ArrayList&LinkedList
ArrayList的基础数据结构是数组，数组因为可以通过下标访问成为一个随机访问第n个数效率很高的数据结构，随机访问查询的时间复杂度是O(1)，查询某个定值的时间复杂度是O(n)，删除/增加新的元素到某个位置时，需要一个一个的移动数组中的元素直至适合的位置，所以时间复杂度是O(n)
LinkedList的基础数据结构是链表，在java中链表的每一个节点具有指向前结点的prev引用和指向后结点next引用，即双向链表。正是因为这样的设计，在链表中插入元素时，只需要改变插入位置前后结点的结点指向和添加新元素的结点指向即可，时间复杂度是O(1)，在访问元素的时候，无论是随机方位第几位的元素还是查询某个定值时，链表的时间复杂度均为O(n)
所以，根据实际场景，如果查询操作比较多的话，建议采用ArrayList等数组实现的List，效率会高。
在java中，LinkedList也提供根据index获得元素的方法
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
每次查找一个元素都要从列表的头部重新开始搜索，LinkedList对象不做任何缓存位置信息的操作，所以循环遍历获取LinkedList对象的数据值，效率不高。
for (int i = 0; i < linkedList.size(); i++){
do something with linkedList.get(i);
}
2.2 Set集合: HashSet&TreeSet
HashSet：不会对放入集中的数据进行排序，基于Hash存储与查找数据。在java中，散列表用链表数组实现，每个列表被称为桶，想要查找表中的对象，需要先计算他的hashCode，然后与桶的总数取余，所得到的结果就是保存这个元素的桶的索引。一般装填因子是0.75，保持一个好的装填因子与桶的数目，可以减少hash冲突，使每次查找尽量一次定位找到，采用has方式查找元素的时间复杂度是O(1)
TreeSet：对放入集中的数据进行排序，他是一个有序的集合，可以以任意顺序将元素插入到集合中，在对集合进行遍历时，每个值将自动地按照排序后的顺序呈现，他采用的数据结构是红黑树。每次将一个元素添加到树中，都被放置在正确的排序位置上，因此，迭代器总是以排好序的顺序访问每个元素。
将一个元素添加到树中要比添加到散列表中慢，但是与将元素添加到数组或者链表的正确位置上还是快很多的。如果树中包含n个元素，查找新元素的正确位置平均需要log2 n次比较。
如果所要收集的数据，不需要排序的话，那么并不需要付出排序的开销即可以考虑HashSet
TreeSet如何知道希望元素怎么排列呢？
2.3 对象的比较: Comparable&Comparator
Comparable：是排序接口，若一个类实现了Comparatable接口，就意味着“该类支持排序”，既然实现Comparable接口的类支持排序，假设现在存在“实现Comparable接口的对象的List数组”，则该List列表或者数组可以通过Collection.sort(或Arrays.sort)进行排序。实现Comparable接口的类的对象可以用作有序映射(e.g.TreeMap)中的“键值”或“有序集合(e.g.TreeSet)中的元素”，而不需要指定比较器。
package java.lang;
import java.util.*;
public interface Comparable<T> {
public int compareTo(T o);
}
Comparator：比较器接口，如果需要控制某个类的次序，而该类本身不支持排序（没有实现Comparable接口），那么我们可以建立一个“该类的比较器”来进行排序，这个“比较器”只需要实现Comparator接口即可，我们可以通过“实现Comparator类来建立一个比较器”，然后通过该比较器对类进行排序。
package java.util;
public interface Comparator<T> {
int compare(T o1, T o2);
boolean equals(Object obj);
}
Comparable相当于“内部比较器”，而Comparator相当于“外部比较器”。
Comparable&Comparator使用：
public class Item implements Comparable<Item> {
private String description;
private int partNumber;
public Item(String description, int partNumber) {
this.description = description;
this.partNumber = partNumber;
}
public String getDescription() {
return description;
}
public void setDescription(String description) {
this.description = description;
}
public int getPartNumber() {
return partNumber;
}
public void setPartNumber(int partNumber) {
this.partNumber = partNumber;
}
@Override
public String toString() {
return "Item{" +
"description='" + description + '\'' +
", partNumber=" + partNumber +
'}';
}
@Override
public boolean equals(Object otherObject) {
if (this == otherObject){
return true;
}
if (otherObject == null){
return false;
}
if (getClass() != otherObject.getClass()){
return false;
}
Item other = (Item)otherObject;
return Objects.equals(description, other.description) && partNumber == other.partNumber;
}
@Override
public int hashCode() {
return Objects.hash(description, partNumber);
}
@Override
public int compareTo(Item other) {
return Integer.compare(partNumber, other.partNumber);
}
}
public class ComparatorTest {
@Test
public void treeSetTest(){
SortedSet<Item> parts = new TreeSet<Item>();
parts.add(new Item("Toaster", 1234));
parts.add(new Item("Widget", 4562));
parts.add(new Item("Modem", 9912));
SortedSet<Item> sortByDescription = new TreeSet<Item>(new Comparator<Item>() {
public int compare(Item a, Item b) {
String descA = a.getDescription();
String descB = b.getDescription();
return descA.compareTo(descB);
}
});
sortByDescription.addAll(parts);
System.out.println(sortByDescription);
}
}
2.4 Queue: PriorityQueue
优先级队列，元素可以按照任意的顺序插入，但总是按照排序的顺序进行检索，内部实现的数据结构是堆。堆是一个可以自我调整的二叉树，对树执行添加和删除的时候，可以让最小的元素移动到根，而不用花费时间对元素进行排序。使用的典型实例是任务调度场景。
3 Map集合
键值对，键必须是唯一的，不能对同一个键存放两个值，Map的基础方法
public interface Map<K,V> {
// Query Operations
int size();
boolean isEmpty();
boolean containsKey(Object key);
boolean containsValue(Object value);
V get(Object key);
// Modification Operations
V put(K key, V value);
V remove(Object key);
// Bulk Operations
void putAll(Map<? extends K, ? extends V> m);
void clear();
// Views
Set<K> keySet();
Collection<V> values();
Set<Map.Entry<K, V>> entrySet();
interface Entry<K,V> {
K getKey();
V getValue();
V setValue(V value);
boolean equals(Object o);
int hashCode();
public static <K extends Comparable<? super K>, V> Comparator<Map.Entry<K,V>> comparingByKey() {
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> c1.getKey().compareTo(c2.getKey());
}
public static <K, V extends Comparable<? super V>> Comparator<Map.Entry<K,V>> comparingByValue() {
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> c1.getValue().compareTo(c2.getValue());
}
public static <K, V> Comparator<Map.Entry<K, V>> comparingByKey(Comparator<? super K> cmp) {
Objects.requireNonNull(cmp);
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> cmp.compare(c1.getKey(), c2.getKey());
}
public static <K, V> Comparator<Map.Entry<K, V>> comparingByValue(Comparator<? super V> cmp) {
Objects.requireNonNull(cmp);
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> cmp.compare(c1.getValue(), c2.getValue());
}
}
// Comparison and hashing
boolean equals(Object o);
int hashCode();
// Defaultable methods
default V getOrDefault(Object key, V defaultValue) {
V v;
return (((v = get(key)) != null) || containsKey(key))
? v
: defaultValue;
}
default void forEach(BiConsumer<? super K, ? super V> action) {
Objects.requireNonNull(action);
for (Map.Entry<K, V> entry : entrySet()) {
K k;
V v;
try {
k = entry.getKey();
v = entry.getValue();
} catch(IllegalStateException ise) {
// this usually means the entry is no longer in the map.
throw new ConcurrentModificationException(ise);
}
action.accept(k, v);
}
}
default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
Objects.requireNonNull(function);
for (Map.Entry<K, V> entry : entrySet()) {
K k;
V v;
try {
k = entry.getKey();
v = entry.getValue();
} catch(IllegalStateException ise) {
// this usually means the entry is no longer in the map.
throw new ConcurrentModificationException(ise);
}
// ise thrown from function is not a cme.
v = function.apply(k, v);
try {
entry.setValue(v);
} catch(IllegalStateException ise) {
// this usually means the entry is no longer in the map.
throw new ConcurrentModificationException(ise);
}
}
}
default V putIfAbsent(K key, V value) {
V v = get(key);
if (v == null) {
v = put(key, value);
}
return v;
}
default boolean remove(Object key, Object value) {
Object curValue = get(key);
if (!Objects.equals(curValue, value) ||
(curValue == null && !containsKey(key))) {
return false;
}
remove(key);
return true;
}
default boolean replace(K key, V oldValue, V newValue) {
Object curValue = get(key);
if (!Objects.equals(curValue, oldValue) ||
(curValue == null && !containsKey(key))) {
return false;
}
put(key, newValue);
return true;
}
default V replace(K key, V value) {
V curValue;
if (((curValue = get(key)) != null) || containsKey(key)) {
curValue = put(key, value);
}
return curValue;
}
default V computeIfAbsent(K key,
Function<? super K, ? extends V> mappingFunction) {
Objects.requireNonNull(mappingFunction);
V v;
if ((v = get(key)) == null) {
V newValue;
if ((newValue = mappingFunction.apply(key)) != null) {
put(key, newValue);
return newValue;
}
}
return v;
}
default V computeIfPresent(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
Objects.requireNonNull(remappingFunction);
V oldValue;
if ((oldValue = get(key)) != null) {
V newValue = remappingFunction.apply(key, oldValue);
if (newValue != null) {
put(key, newValue);
return newValue;
} else {
remove(key);
return null;
}
} else {
return null;
}
}
default V compute(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
Objects.requireNonNull(remappingFunction);
V oldValue = get(key);
V newValue = remappingFunction.apply(key, oldValue);
if (newValue == null) {
// delete mapping
if (oldValue != null || containsKey(key)) {
// something to remove
remove(key);
return null;
} else {
// nothing to do. Leave things as they were.
return null;
}
} else {
// add or replace old mapping
put(key, newValue);
return newValue;
}
}
default V merge(K key, V value,
BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
Objects.requireNonNull(remappingFunction);
Objects.requireNonNull(value);
V oldValue = get(key);
V newValue = (oldValue == null) ? value :
remappingFunction.apply(oldValue, value);
if(newValue == null) {
remove(key);
} else {
put(key, newValue);
}
return newValue;
}
}
a.Map的三个视图方法
Set<K> keySet();
Collection<V> values();
Set<Map.Entry<K, V>> entrySet();
分别是获得键集、值集合键值对集
