Bài giảng Java 2 - Trần Duy Thanh - Collections

Objects with identical contents may yield different hash codes. You should always define the hashCode method for objects that you insert into a collection. This method should return an integer (which can be negative). 6 Identifying object (1) The equals method Furthermore, you also need to make sure that the equals method is well defined. The Object class defines equals, but that method only tests whether or not two objects are identical. If you don't redefine equals, then every new object that you insert into the table will be considered a different object. 7 Concrete collections 8 Concrete Collections - List Classes and Interfaces (1)	 The LinkedList object A LinkedList is an ordered collection in which the position of the objects matters. 9 Concrete Collections - List Classes and Interfaces (2)	 The LinkedList object - methods 10 Concrete Collections - List Classes and Interfaces (3)	 The ArrayList object An implementation of the List interface Variable-length array of object references. Best suited for random access without inserting or removing elements from any place other than the end. 11 Concrete Collections - List Classes and Interfaces (4)	 The Vector object Similar to an ArrayList The methods of Vector are synchronized and are thread-safe. 12 Hash table conceptual (1) A hash table is a data structure that stores information by mapping the key of each data element into an array position or index. A hash table is an array of linked lists. Each list is called a bucket 13 Hash table conceptual (2) To add an object to hash table, first we compute its hash code and then, modulo it with the total number of buckets => so we has the bucket number that the object will place in hash table. Put the object in to the identified bucket (add it in to linked list) To find the place of an object in the table, compute its hash code and reduce it modulo the total number of buckets. The resulting number is the index of the bucket that holds the element. For example, if an object has hash code 345 and there are 101 buckets, then the object is placed in bucket 42. 14 Hash table conceptual (3) Perhaps you are lucky and there is no other element in that bucket. Of course, it is inevitable that you hit a bucket that is already filled. This is called a hash collision. Then, you need to compare the new object with all objects in that bucket to see if it is already present. You can specify the initial bucket count. You should set the initial bucket count to about 150 percent of the expected element count.(known how many elements). If you do not always know how many elements you need to store, or your initial guess may be too low. If the hash table gets too full, it needs to be rehashed. 15 Concrete Collections - Set Classes and Interfaces (1)	introduction Set is an unordered and non-duplicate list of object references. 16 Concrete Collections - Set Classes and Interfaces (2)	 The HashSet class HashSet class implements a set based on a hash table. The default constructor HashSet constructs a hash table with 101 buckets and a load factor of 0.75. HashSet() HashSet(int initialCapacity) HashSet(int initialCapacity, float loadFactor) You would only use a hash set if you don't care about the ordering of the elements in the collection. 17 Concrete Collections - Set Classes and Interfaces (3)	 LinkedHashSet class LinkedHashSet keeps track of the order in which the elements are added to the set. The iterator of a LinkedHashSet visits the elements in insertion order. That gives you an ordered collection with fast element lookup. 18 Concrete Collections - Set Classes and Interfaces (4)	Example of "HashSet" and "LinkedHashSet" class 19 Concrete Collections - Set Classes and Interfaces (5)	The TreeSet class The TreeSet class is similar to the hash set, with one added improvement. A tree set is a sorted collection. Every time an element is added to a tree, it is placed into its proper sorting position. Therefore, the iterator always visits the elements in sorted order. Adding an element to a tree is slower than adding it to a hash table, but it is still much faster than adding it into the right place in an array or linked list. If the tree contains n elements, then an average of log2n comparisons are required to find the correct position for the new element. Notes: When add an object to TreeSet, this object must be implements Comparable interface. 20 Concrete Collections - Map Interfaces (1)	 A Map object stores data in the form of relationships between keys and values. Each key map to at least a single value. Value can be retrieved from the Map object by key information. Keys should be unique but values can be duplicated. Two general-purpose Map implementation: HashMap TreeMap 21 Concrete Collections - Map Interfaces (1)	methods Some methods: V get(K key) V put(K key, V value) void putAll(Map entries) boolean containsKey(Object key) boolean containsValue(Object value) Set> entrySet() Set keySet() Collection values() … 22 Concrete Collections - Map Interfaces (1)	The put methods Whenever you add an object to a map using put method, you must supply an unique key. If the key is already present, the new object replaces the old one previously associated with the key. The put() method returns the old value of the key, or null if the key was not previously present. V put(K key, V value) 23 Concrete Collections - Map Interfaces (1)	Viewing methods There are three views of objects stored in HashMap: The set of keys. The collection of values (which is not a set) The set of key/value pairs. The methods: Set keySet() Collection values() Set> entrySet() return these three views. 24 Concrete Collections - Map Interfaces (2)	Specialized Map Classes WeakHashMap This data structure cooperates with the garbage collector to remove key/value pairs when the only reference to the key is the one from the hash table entry. LinkedHashMap LinkedHashMap remembers in which order you inserted key/value pairs into the map. IdentityHashMap The hash values for the keys should not be computed by the hashCode method but by the System.identityHashCode method. That's the method that Object.hashCode uses to compute a hash code from the object's memory address. Also, for comparison of objects, the IdentityHashMap uses ==, not equals. 25 Concrete Collections - Map Interfaces (3)	Example of "HashMap" Class 26 Concrete Collections - Map Interfaces (2)	Example of "TreeMap" Class 27 Concrete Collections - Queue Interfaces (1)	 In Queue, the elements are normally ordered in First In First Out (FIFO) order. A queue can be arranged in other orders too. 28 Concrete Collections - Queue Interfaces (2)	 The PriorityQueue class Priority Queues is a collection that allows efficient removal of the smallest element. A priority queue retrieves elements in sorted order after they were inserted in arbitrary order. However, the priority queue does not sort all its elements. Priority queue can either hold elements of a class that implements the Comparable interface or a Comparator object you supply in the constructor. A typical use for a priority queue is job scheduling: Each job has a priority. Jobs are added in random order. Whenever a new job can be started, the highest-priority job is removed from the queue. 	Note: priority 1 to be the "highest" priority 29 Example of of "PriorityQueue" Class Output 30 Collection Algorithms	Sorting and Shuffling The sort method in the Collections class sorts a collection that implements the List interface. Ex: Collections.sort(staff); Collections.sort(staff,Collections.reverseOrder()); The Collections class has an algorithm shuffle that does the opposite of sorting it randomly permutes the order of the elements in a list. Ex:	ArrayList cards = . . .; 	Collections.shuffle(cards); 31 Collection Algorithms	Binary Search Note that the collection must already be sorted or the algorithm will return the wrong answer. Example:i = Collections.binarySearch(c, element);i = Collections.binarySearch(c, element, comparator); i>=0: the index of the matching object. i> T 	min(Collection elements) static > T 	max(Collection elements) static min(Collection elements, Comparator c) static max(Collection elements, Comparator c) static void copy(List to, List from) … 33 Legacy collection	The Hashtable Class The classic Hashtable class serves the same purpose as the HashMap and has essentially the same interface. All Hashtable methods are synchronized. If you do not require synchronization or compatibility with legacy code, you should use the HashMap instead. 34 Legacy collection	The Enumerations Class The legacy collections use the Enumeration interface for traversing sequences of elements. An object that implements the Enumeration interface generates a series of elements, one at a time. Successive calls to the nextElement method return successive elements of the series. 35 Legacy collection	The Properties Class(1) A property set is a map structure of a very special type. It has three particular characteristics: The keys and values are strings. The table can be saved to a file and loaded from a file. A secondary table for defaults is used. The Java platform class that implements a property set is called Properties. 36 Legacy collection	The Properties Class(2) Property maps are useful in specifying configuration options for programs. For example: 37 Legacy collection	The Properties Class(3) Property maps are useful in specifying configuration options for programs. For example: Use the store method to save this list of properties to a file. Here, we just save the property map in the file settings.properties. FileOutputStream out = new 	FileOutputStream(“settings.properties"); settings.store(out, “my settings"); To load the properties from a file, use: FileInputStream in = new 	FileInputStream("settings.properties"); settings.load(in); 38 Summary Collections Framework Concrete collections Collection algorithm Legacy collection END 39