Collection Interface

• the Java collection library separates interfaces and implementations
  

Concrete Implementations

LinkedList

Add

Get and Set

Offer, Peek, Poll

Pop, Push

Remove

Utilities

void clear(): Removes all of the elements from this list.
1

Object clone(): Returns a shallow copy of this LinkedList.
1

boolean	contains(Object o): Returns true if this list contains the specified element.
1

int indexOf(Object o): Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element.
1

int	size(): Returns the number of elements in this list.
1

Object[]	toArray(): Returns an array containing all of the elements in this list in proper sequence (from first to last element).
1

ArrayList

Add

delete

set, get, replace

E get(int index): Returns the element at the specified position in this list.
1

E set(int index, E element): Replaces the element at the specified position in this list with the specified element.
1

void replaceAll(UnaryOperator<E> operator): Replaces each element of this list with the result of applying the operator to that element.##  Sets
1

Utilities

void clear(): Removes all of the elements from this list.
1

Object clone(): Returns a shallow copy of this ArrayList instance.
1

boolean	contains(Object o): Returns true if this list contains the specified element.
1

void forEach(Consumer<? super E> action): Performs the given action for each element of the Iterable until all elements have been processed or the action throws an exception.
1

int	indexOf(Object o): Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element.
1

Object[] toArray(): Returns an array containing all of the elements in this list in proper sequence (from first to last element).
1

“only arrayList”

boolean	isEmpty(): Returns true if this list contains no elements.
1

int	size(): Returns the number of elements in this list.
1

void sort(Comparator<? super E> c): Sorts this list according to the order induced by the specified Comparator.
1

void trimToSize(): Trims the capacity of this ArrayList instance to be the list's current size.
1

void ensureCapacity(int minCapacity): Increases the capacity of this ArrayList instance, if necessary, to ensure that it can hold at least the number of elements specified by the minimum capacity argument.
1

ArrayList 和 LinkedList的区别

insert and delete

• ArrayList: O(n), 因为要将目标位置之后的元素向前移位(delete)或者向后移位(insert),
  如果超出capacity则需要扩容会增加时间复杂度
• LinkedList: O(n), 需要遍历linkedlist找到node, 然后进行操作: O(1)

set and get

• ArrayList: O(1), 通过下标直接操作
• LinkedList: O(n) 需要遍历linkedlist找到node, 然后进行操作

“space”

• ArrayList: 只需数组的空间
• LinkedList: 有overhead, 比如next,pre指针

Summary

• 很多场景下ArrayList更受欢迎

Queues and Deques

• Queue: 在尾部加入元素, 从头部删除元素
• Deque (double-ended queue): 可以从头部或者尾部加入删除元素
• 可以用LinkedList替代(LinkedList提供了Queue和Deque功能)
  
  
  

Priority Queues

package priorityQueue;
import java.util.*;
import java.time.*;
/**
 * This program demonstrates the use of a priority queue.
 * @version 1.02 2015-06-20
 * @author Cay Horstmann
 */
public class PriorityQueueTest
{
	public static void main(String[] args) {
		PriorityQueue<LocalDate> pq = new PriorityQueue<>();
		pq.add(LocalDate.of(1906, 12, 9)); // G. Hopper
		pq.add(LocalDate.of(1815, 12, 10)); // A. Lovelace
		pq.add(LocalDate.of(1903, 12, 3)); // J. von Neumann
		pq.add(LocalDate.of(1910, 6, 22)); // K. Zuse
		System.out.println("Iterating over elements...");
		for (LocalDate date : pq)
   			System.out.println(date);
   		System.out.println("Removing elements...");
   		while (!pq.isEmpty())
    		System.out.println(pq.remove());
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

HashSets

• 无序的set
• 使用HashTable实现 bucket hashing (Array + LinkedList)
• 默认bucket大小是 2^16, load factor是0.75

public class SetTest
{
	public static void main(String[] args) {
		Set<String> words = new HashSet<>(); // HashSet implements Set
		long totalTime = 0;

		try (Scanner in = new Scanner(System.in)) {
			while (in.hasNext()) {
 				String word = in.next();
 				long callTime = System.currentTimeMillis();
 				words.add(word);
 				callTime = System.currentTimeMillis() - callTime;
 				totalTime += callTime;
 			}
 		}
 
 		Iterator<String> iter = words.iterator();
 		for (int i = 1; i <= 20 && iter.hasNext(); i++)
 			System.out.println(iter.next());
 			System.out.println(". . .");
 			System.out.println(words.size() + " distinct words. " + totalTime + " milliseconds.");
 		}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

LinkedHashSet

是HashSet的一个子类, 元素按照加入顺序排序

TreeSets

• 有序的Set
• 使用红黑树实现
• TreeSet的插入复杂度要比HashSet快, 但是检查重复要比HashSet快(LogN)
• 因为是有序的所以必须重新compareTo 否则会报错, String等非自定义类型已经重写了compareTo方法
• 如果数据不要求排序最好使用HashSet

public class TreeSetTest {
	public static void main(String[] args) {
		SortedSet<Item> parts = new TreeSet<>();
		parts.add(new Item("Toaster", 1234));
		parts.add(new Item("Widget", 4562));
		parts.add(new Item("Modem", 9912));
		System.out.println(parts);
		NavigableSet<Item> sortByDescription = new TreeSet<>(
		Comparator.comparing(Item::getDescription)); 
		sortByDescription.addAll(parts);
		System.out.println(sortByDescription);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

EnumSet

• element是enum类型
• Since an enumerated type has a finite number of instances, the EnumSet is internally implemented simply as a sequence of bits.
• A bit is turned on if the corresponding value is present in the set.

enum Weekday { MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY, SUNDAY };
EnumSet<Weekday> always = EnumSet.allOf(Weekday.class);
EnumSet<Weekday> never = EnumSet.noneOf(Weekday.class);
EnumSet<Weekday> workday = EnumSet.range(Weekday.MONDAY, Weekday.FRIDAY);
EnumSet<Weekday> mwf = EnumSet.of(Weekday.MONDAY, Weekday.WEDNESDAY, Weekday.FRIDAY);
1
2
3
4
5

Map

• Map没有继承Collection接口
• AbstractMap和AbstractCollection是平级关系
  

Map的基本操作

package map;
import java.util.*;
/**
 * This program demonstrates the use of a map with key type String and value type Employee.
 * @version 1.12 2015-06-21
 * @author Cay Horstmann
 */
public class MapTest {
	public static void main(String[] args) {
		Map<String, Employee> staff = new HashMap<>();
		staff.put("144-25-5464", new Employee("Amy Lee"));
		staff.put("567-24-2546", new Employee("Harry Hacker"));
		staff.put("157-62-7935", new Employee("Gary Cooper"));
		staff.put("456-62-5527", new Employee("Francesca Cruz"));
		// print all entries
		System.out.println(staff);
		// remove an entry
		staff.remove("567-24-2546");
		// replace an entry
		staff.put("456-62-5527", new Employee("Francesca Miller"));
		// look up a value
		System.out.println(staff.get("157-62-7935"));
		// iterate through all entries
		staff.forEach((k, v) -> 
		System.out.println("key=" + k + ", value=" + v));
	}
}
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

如何查看Map

the set of keys: 将所有的key作为一个set返回

Set<K> keySet()
1

Set<String> keys = map.keySet();
for (String key : keys) {
	do something with key
}
1
2
3
4

the collection of values (which is not a set): 将所有的value作为一个collection返回

Collection<V> values()
1

 Map<String,String> map=new HashMap<>();
        map.put("abc","123");
        map.put("efg","456");
        // 使用增强型for遍历循环Map集合
        Collection<String> values = map.values();
        for (String value : values) {
            System.out.println(value);
        }
1
2
3
4
5
6
7
8

the set of key/value pairs: 得到每一对key value pair

Set<Map.Entry<K, V>> entrySet()
1

for (Map.Entry<String, Employee> entry : staff.entrySet()) {
	String k = entry.getKey();
	Employee v = entry.getValue();
	do something with k, v
}
1
2
3
4
5

Type of HashMap

HashMap

• Hash table based implementation of the Map interface
• the default load factor (.75)
• 有一个子类为LinkedHashMap, 元素按照加入顺序排序

TreeMap

• A Red-Black tree based NavigableMap implementation.
• 需要根据compareTo排序

EumerateHashMap

• A specialized Map implementation for use with enum type keys.
• All of the keys in an enum map must come from a single enum type that is specified

WeakHashMap

• Hash table based implementation of the Map interface, with weak keys.
• An entry in a WeakHashMap will automatically be removed when its key is no longer in ordinary use

Collection和Array互相转换

Collection To Array

Object[] values = staff.toArray();
1

• 但是values的类型是Object并且不能转换类型 String[] values = (String[]) staff.toArray(); // Error!
• 可以用如下写法: String[] values = staff.toArray(new String[staff.size()]);

Array To Collection

Arrays.asList()
1

String[] values = . . .;
HashSet<String> staff = new HashSet<>(Arrays.asList(values)); //所有的collection都可以通过另外一个collection初始化

1
2
3