Chapter 9 holds your object
I. Introduction to the container
1. Classification of containers 1.1. Collection: A set of separate elements, that is, each of which holds only one element. 1) List: Place an element in the order of an element and does not rearrange it. 2) SET: Do not receive a repetition element, which uses a routing mechanism inside itself 1.2. Map: A group of key-value objects, that is, the HEY-VALUE PAIRS. There is no repetitive key in the map, which has its own internal arrangement mechanism. 2. Element type in the container is Object. When an element is obtained from a container, it must be converted into the original type.
Detailed introduction to the container
1. CollectionCollection does not provide a GET () method. If you want to traverse the elements in Collectin, you must use item. 1.1. List1.1.1 List (interface): List Add some functions to Collectin so that it can make an installation and removal actions within the LIST. List will generate Listiterator, which can be interviewed from both directions, or can be used in the LIST. 1.1.2 ArrayList: It can be quickly randomly accessed; however, it is very efficient when the settings of the element occurs in the central position of the List. It is not advisable to use ArrayList to make an insertion and removal operation. 1.1.3 LinkedList: In contrast to ArrayList, suitable for installation and removal, but random access is slow. In addition, STACK, Queue, Deque can be implemented via LinkedList. 1) AddFirst (), getfirst (), getFirst (), getFirst (), received (), RemoveList () function is not defined in any Interface or Base Class, so it can only be used in LinkedList. 1.2. Set1.2.1 set (interface): SET has the same interface as the Collection (Difference: List Add your own function), so set is a collection, but its behavior is different. Each element of the SET must be unique, no repetition with other elements; SET does not allow repeating elements, each element must define Equals () to determine the so-called uniqueness. 1.2.2 Hashset: A sets that looks a lookup time is very important. All elements must define HashCode (). 1.2.3 Treeset: An ordered SET for the underlying structure for TREE. 2. Map2.1. Map: Maintaining the correlation of Key-Value so that you can use Key to find Value. 1) KeySet () function and values () function
Import java.util. *; public class explicitstatic {public static void printkeys (map m) {system.out.print ("size =" m.size ()); system.out.println (", keys:" M.keyset ()); public static void printvalues (map m) {system.out.println ("VALUES:" m.Values ());} public static void test (map m) {for (int i = 1; i <10; i ) m.put ("km" i, "m" i); printKeys (m); PrintValues (M); System.out.Println ("km1 -" m.Get "km1")); set keys = m.keyset (); // (1) Collection value = m.values (); // (2) Keys.Remove ("km2"); // (3) Values. REMOVE ("m1"); // (4) System.out.Println ("km1 -" m.get ("km1")); printKeys (m); PrintValues (m);} public static void main (String [] Args) {system.out.Println ("testing hashmap"); test (new hashmap ());}}
The result is: Testing hashmapsize = 9, keys: [km5, km4, km3, km2, km1, km9, km8, km7, km6] VALUES: [M5, M4, M3, M2, M1, M9, M8, M7, M6] KM1 - M1 // Perform (3) (4) KM1 - Nullsize = 7, Keys: [KM5, KM4, KM3, KM9, KM8, KM7, KM6] // (5) VALUES: [M5, M4, M3, M9, M8, M7, M6] // (6) At (1) (2), the code is obtained by KEYS and VALUES in the map, respectively. From the code before and after execution (3) (4), it is known to modify the value obtained by the keyset () and values () functions. (3) Remove the value of "km2", (4) deleted the value "m1", and they are the same key-value pair, but the result (5) (6) indicates that MAP The deletion is two Key-Pair. As soon as, as long as one of the key or value in the map is deleted, the entire key-value pair will be deleted. 2.2. Hashmap: Can insert an element within a constant time, or find a set of Key-Value Pair. Through its constructor, the user can adjust the performance performance because it allows you to set Capacity and LoadFactor (load factor). 2.3. TreeMap: When you check it, the key or key-value pairs, will appear in the order of order, so that you get the result in ordering form. TreeMap is the only MAP with Submap (), which allows you to return to the part of the TREE. 3. Working principle of HashMap
1. How to implement a Map1.1 and MAP-related knowledge 1.1.1 Map.Entry interface A class that implements the map.Entry interface is an entry in a map (a Key-Value Pair). So a map must have a class that implements the Map.Entry interface, and uses this class to store the key-value pair in Map. 1.1.2 Public Abstract SET ENTRYSET () Function 1) The entryset () function returns a set, and each element in the SET is an object of a map.Entry type. In the entryset () function, you must store all the key-value pair in the map in the Map.Entry package in the SET. 2) After modifying the MAP, the entryset () function will be called. So modifications to MAP also produce modifications to this SET. 3) When operating with this set of Iterator, the ADD and ADDALL operation cannot be performed. 1.2 Implement a simple MAP instance
Import java.util. *; / ** * MPAIR class implements map.Entry * / class mpair imports map.entry, comparable {Object Key, value; // key and value to store Key and Value MPAIR in MAP, respectively (Object K, Object V) {key = k; value = v;} // The method in the map.Entry interface implements the method in the map.Entry interface public object getKey () {Return Key;} public object getValue () {Return Value;} Public Object setValue (object v) {object result = value; value = v; return;} // The following method implements the method in the Comparable interface PUBLIC BOOLEAN Equals (Object O) {Return Key.Equals ((MPAIR) O );} public int compareto (Object RV) {return ((Comparable) Key) .Compareto ((mPair) rv) .key);}} Class SlowMap Extends AbstractMap {Private ArrayList Keys = New ArrayList (), Values = new arraylist (); public object key, object value) {Object results = get (key); if (! keys.contains (key)) {// (1) Keys.add (key); VALUES .add ( Value);} else valuexof (key), value); Return Result;} public object get (Object key) {if (! keys.contains (key)) {return null;} else returnes. Get (Keys.indexof (key));} // Package the key-value pair in MPAIR and store the public set entryset () {set entries = new hashset (); iterator ki = keys.ITerator () , Vi = values.iterator (); while (ki.hasnext ()) entries.add (new mpair (ki.next (), vi.next ())); Return Entries;
}}}} public class explicitstatic {public static void main (String [] args) {SLOWMAP M = New SlowMap (); for (int i = 1; i <10; i ) m.put ("km" i, "M " I); system.out.println (m);}} At (1) at the above code, we have to find out if there is a key value from ArrayList, and this lookup process linearly looks, and Key does not have any order, So speed will be very slow. 2. Several functions associated with HashMap 1) Hashcode () function Object.hashcode () function generates Hash Code for the object. If a class does not implement a HashCode () function, then the memory address of its object will be returned by default. 2) Equals () function Object.equals () compares the memory address of the two objects when comparing two objects. 3. Hashmap works 3.1 Use array to express the information of Key. Each Key's Hashcode () function generates a Hash Code for Key, and Key's Hash Code is an index of Array. If it is assumed that there is an ARRSY called Bucket, a Hash Code 2 is indexed to BUCKET [2], and the value corresponding to the key is also in BUCKET [2]. 3.1 Due to the Value value in Array, the number of the HashMap can be unlimited, so the elements in Array point to a certain key value, but point to the value value of the key with the same Hash Code (also That is to say, a string value value). If the Array is defined as LinkedList [] BUCKET = New LinkedList [10], it is stored in BUCKET [2], all the key of all Hash Code values 2 is 2.
4. To achieve a simple HashMap and its principles
4.1 In the PUT () method: 1) First, the Hash Code to be inserted by Key, and this Hash Code is used as an index to find the element corresponding to the key in the array bucket. 2) Package the key-value pair to be inserted into an object that implements the class of the Map.Entry interface. 3) View the array element (also a LinkedList) found in operation 1 to see if there is the same element as the key- value pair to be inserted, if there is, then update it; if not, Inserted key-value pair array element. 4.2 In a get () method 1) First by Key to find the Hash Code to look for, and this Hash Code finds the element corresponding to the key in the array bucket. 2) Package the Key-Value PAIR of the Key-Value Pair to be found into an object that implements the class of the Map.Entry interface. 3) Viewing the same element as the key-value pair that is inserted in operation 1), if any, return the value corresponding to the key; if not, Returns a NULL. 4.3 an instance
Import java.util. *; / ** * MPAIR class implements map.entry * / class mpair imports map.entry, comparable {Object Key, Value; MPAIR (Object K, Object V) {key = K; Value = V PUBLIC Object getKey () {return key;} public object getValue () {return value;} public object set = value; value = v; returr;} / ** * When a MPAIR object is compared, their key value * / public boolean equals (object o) {return key.equals ((mpair) o) .key);} public int compareto (Object RV) {Return Comparable) Key) .Compareto ((mPair) rv) .key));}}} class simplehashmap extends AbstractMap {private final static int SZ = 997; private linkedlist [] bucket = new linkedList [SZ]; / ** * KEY and VALUE are encapsulated into map.Entry implementation classes into Array * / public object put (Object key, object value) {Object results = null; / / Get KEY-VALUE PAIR's HASH CODE INDEX = Key.hashcode ()% SZ; if (INDEX <0) index = - index; if (bucket [index] == null) Bucket [index] == null) = New LinkedList (); // Find the element LinkedList PAIRS = BUCKET [INDEX] to be inserted by Hash Code; // Package the key-value pair to insert into MPAIR MPAIR PAIR = New MPAIR (key, value); listiterator it = pairs.listiterator (); booleanfact = false; // Check if there is the same key to the same key as the key to insert, if there is, to update while (IT.hasNext () ) {Object iPair = it.next (); IF (iPair.Equals (iPair)) {result = ((mpair) iPair) .getValue ();
IT.SET (Pair); Found = true; Break;}} // If there is no, the new key-value pair is inserted into if (! found) bucket [index] .add (pair); returnrate;} public object; GET (Object Key) {int index = key.hashcode ()% SZ; if (INDEX <0) index = -index; if (bucket [index] == null) Return Null; LinkedList Pairs = bucket [index]; ListIterator IT = pairs.listiterator (); mpair match = new mpair (key, null); while (it.hasnext ()) {Object iPair = it.next (); if (iPair.Equals (match)) Return ((MPAIR) ) ipair) .GetValue ();} return null;} public set entryset () {set entries = new hashset (); for (int i = 0; i 1. The use of the KEY value in HashMap is 1.1. When the Java library function is used as a KEY value of HashMap, it can be used directly. Import java.util. *; coplass counter {INT i = 1; public string toString () {return integer.tostring (i);}} public class explicitstatic}} public class explicitstatic}} public class explicitstatic}} public class explicitstatic}}} HashMap (); for (int i = 0; i <10000; i ) {// Hashmap's key type is Integer Integer R = New Integer ((int) (math.random () * 20)); if (HM .Containskey (R)) ((counters). i ; else hm.put (r, new counter ());} system.out.println (hm);}} 1.2. If you are in HashMap Use the classes you write in your own as Key, you must override HashCode () and Equals (). The following code is made as Key with its own Class, but did not overwrite HashCode () and Equals (). import java.util *;. class Groundhog {int ghNumber; Groundhog (int n) {ghNumber = n;} public String toString () {return "Groundhog @" ghNumber;}} class Prediction {boolean shadow = Math.random ( )> 0.5; public string toString () {if (shadow) Return "Six More Weeks of Winter! / N"; Else Return "Early Spring! / N";}} public class test {public static void main (String [] ARGS) {hashmap hm = new hashMap (); for (int i = 1; i <10; i ) hm.put (New Groundhog (i), new prediction ()); system.out.println ("hm =" HM); System.out.Println ("Looking Up Prediction For Groundhog # 3:"); Groundhog GH = New Groundhog (3); IF (Hm.Containskey (GH)) // (1) System.out .println ((prediction) HM.Get (GH)); Else System.out.println ("Key Not Found:" GH);}} Run results: hm = {Groundhog @ 9 = Early Spring !, a GROUNDHOG @ 8 = Six More Weeks of Winter !,, GROUNDHOG @ 7 = Six More Weeks of Winter !,, Groundhog @ 6 = Early Spring !, !, Groundhog @ 4 = Early Spring !, Groundhog @ 3 = Early Spring !, Groundhog @ 2 = Early Spring !, Groundhog @ 1 = Six more weeks of Winter} Looking up prediction for Groundhog # 3:! Key not found: Groundhog @ 3key did not overwrite HashCode () and equals (), then the memory address of the key will be obtained when getting Hash Code through Key; also A Key address. So (1) The result of the code comparison is false (because the memory addresses of the two objects are certainly different). Obviously, this is not the result we have to get. In order to get the correct result, we only need to implement HashCode () and Equals () in a class as a key. Java.util. *; Class Groundhog2 {INT GHNUMBER; Groundhog2 (INT N) {ghnumber = n;} public string toString () {Return "Groundhog2 @" ghnumber;} / ** * as a Hash code * / public INT hascode () {return ghnumber;} / ** * Compare two Key ghnumber values * / public boolean equals (object o) {Return (o instanceof groundhog2) && (ghnumber == ((Groundhog2) O). Ghnumber);}} class prediction {boolean shadow = math.random ()> 0.5; public string toString () {if (shadow) Return "Six More Weeks of Winter! / N"; Else Return "Early Spring! / N" ;}} Public class test {public static void main (string [] args) {hashmap hm = new hashmap (); For (int i = 1; i <10; i ) hm.put (new growth (i), new prediction ()); system.out.println ("size =" hm.size () ", hm = " Hm); System.out.Println (" Looking Up Prediction for Groundhog # 3: "); Groundhog2 GH = New Groundhog2 (2); if (Hm.Containskey (GH)) System.out.println ((PREDiction) HM.Get (GH)); Else System.out.println ("Key NOT Found:" GH);}}
