Collections
- ArrayList——An indexed sequence that allows shrinks and grows dynamically.
- LinkedList——An ordered sequence that allows efficient insertion and removal at any location. The add() method adds the object at the end of the list.
- ArrayDeque——A double-ended queue that is implemented as a circular array.
- HashSet——An unordered collection that rejects duplication.
- TreeSet——A sorted set that values are automatically presented in sorted order.
- EnumSet——A set of enumerated values.
- LinkedHashSet——A set that remembers the order in which elements were inserted.
- PriorityQueue——A collection that allows efficient removal of the smallest element.
- HashMap——A data structure that stores key/ value associations.
- TreeMap——A map in which keys are stored.
- EnumMap——A map in which the keys are belonged to an enumerated type.
- LinkedHashMap——A map that remembers the order in which entries were added.
- WeakHashMap——A map with values that can be reclaimed by the garbage collector if they are not used elsewhere.
- IdentityHashMap——A map with keys that are compared with ==, not equals.
1. Use concrete class only when you construct collection object. Use the interface type to hold that reference.
2. add() method returns true (false) -> changes the collection (unchanged, respectively).
3. Inspect elements
1) Request an iterator
2) Keep calling the next() method while hasNext() returns true.
iterator.forEachRemaining(element -> do sth. with element);
4. The remove method of the Iterator interface removes the element that was returned by the last call to next. More importantly, it’s illegal to call remove if it wasn’t preceded by a call to next.
5. Two fundamental interfaces for collections: Collection and Map.
6. You can read values from a map with the get method.
7. A list is an ordered collection. Elements are added into a particular position in the container. It is best traversed with an iterator rather than random access.
8. To test whether a collection supports random access:
if (c instanceof RandomAccess){
// ...
}
9. The add() method of a set should reject duplicates. The equals() method of a set should be defined so that if two sets are identical if they have the same elements, but not necessarily in the same order. The hashCode() method of a set should be defined so that if two sets with the same elements yield the same hash code.
10. For searching and—— traversal in sorted sets and maps——NavigableSet and NavigableMap.
11. Using iterators to add elements makes sense only for collections that have a natural ordering.
12. The add() method adds the new element before the iterator position.
13. Use contains method to check whether an element is present in a linked list.
14. Never use
for(int I = 0; i < list.size(); i++){
// do sth.
}
to step through a linked list. (Each time from the beginning of the list -> Inefficient)
15. Use an array or ArrayList (not a linked list) if you want random access.
16. In Java, hash tables are implemented as arrays of linked lists. Each list is called a bucket.
17. To find the place of an object in the table, computes its hash code and reduce it modulo the number of buckets. (index = hashCode % num)
18. Hash collision——Hit a bucket that is already filled.
19. If you know how many elements approximately, you should set the bucket count to somewhere between 75% and 150% of the expected element count.
20. The buckets change from linked list to balanced binary trees when they get full.
21. The load factor (default: 0.75) determines when a hash table is rehashed.
22. A set is a collection without duplicates.
23. You would only use a hashSet if you don’t care about the ordering of the elements in the collection.
24. Adding an element to a tree is slower than adding to a hash table. (Still faster than array or linked list for checking for duplicates.)
25. In order to use a tree set, you must be able to compare the elements. The elements must implement the Comparable interface, or you must supply a Comparator when constructing the set.
26. The sort order for a tree must be a total ordering. Some data is much more difficult to come up with a sort order than a hash function.
27. A double-ended queue, or deque, lets you add or remove elements at the head and tail (in the middle not supported).
28. A priority queue retrieves elements in sorted order after they were inserted in arbitrary order. That is, whenever you call the remove method, you get the smallest element currently in the priority queue.
29. The priority queue does not sort all its elements.
30. A heap is a self-organizing binary tree in which add and remove operations cause the smallest element to gravitate to the root.
31. A priority queue can either hold elements of a class that implements the Comparable interface or a Comparator object you supply in the constructor.
32. A hash map hashes the keys, and a tree map uses an ordering on the keys to organize them in a search tree. The hash or comparison function is applied only to the keys. The values associated with the keys are not hashed or compared.
33. Whenever you add an object to a map, you must supply a key as well. Keys must be unique.
34. To retrieve an object, you must use (and remember) the key.
35. Use the getOrDefault method if keys may not be present in the map.
36. Iterating over the keys and values of a map -> forEach method.
example.forEach((k, v) ->
System.out.println(“key = ” + k + “value = ” + v));
37. Special case—first-occurrence data update in a map, use merge method (See API).
38. Three views—the set of keys, the collection of values, and the set of key/value pairs.
39. The keySet is not a hash set or tree set, but an object of some other class that implements the Set interface (which extends Collection interface). Therefore, you can use a keySet as you would use any collection.
40. Visiting all map entries:
example.forEach((k, v) -> {Do sth. with k, v});
41. Enumerating all keys of a map:
Set<String> keys = map.keySet();
for(String key : keys){
// do sth. with keys;
}
42. You cannot add an element to the key set view. It makes no sense to add a key without a value.
43. Remove unused values from long-lived maps——Use WeakHashMap.
44. The LinkedHashMap and LinkedHashSet classes remember in which order you inserted items. As entries inserted into table, they are joined in a doubly linked list. A liked hash map can use access order to iterate through the map entries. Every time you call get or put, the affected entry is removed from its current position and placed at the end of the linked list of entries.
45. Access order is useful for implementing a “least recently used” discipline for a cache.
46. Use a static factory method to construct the EnumSet. Use the methods of Set interface to modify an EnumSet.
47. All enumerated types extend the generic Enum class.
48. The IdentityHashMap class is useful for implementing object traversal algorithms.
49. The static asList method returns a List wrapper around a plain Java array.
50. The Collections class contains a number of utility methods with parameters or return values that are collections.
example.forEach((k, v) ->
System.out.println(“key = ” + k + “value = ” + v));