I. Working principle and realization of HashMap
1. How to implement a map
1.1 knowledge related to MAP
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
Implements map.entry, comparable {
Object Key, Value; // Key and Value are used to store Key and Value in MAP, respectively.
MPAIR (Object K, Object V) {
Key = k;
Value = v;
}
// The following method 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 Result;
}
// The method is implemented in the Comparable interface.
Public Boolean Equals (Object O) {
Return Key.Equals ((mPair) o) .key);
}
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 Put (Object Key, Object Value) {
Object result = get (key);
IF (! keys.contains (key)) {// (1)
Keys.Add (key);
VALUES.Add (Value);
}
Else
Values.set (Keys.indexof (key), value
Return Result;
}
Public Object Get (Object Key) {
IF (! keys.contains (key)) {
Return NULL;
}
Else
Return Values.get (Keys.Indexof (key));
}
// Package the key-value pair in MPAIR and store the SET
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) of 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 the speed will be very slow.
1.3 How to operate the MAP with iter
Other containers can generate objects of objects through the Iterator () function, but MAP cannot be generated. If you want to operate with the object with an iterator, you must pass the entryset () function. The iterator generated by the entryset () function cannot perform ADD and ADDALL operations.
PUBLIC CLASS ExplicitStatic {
Public static void main (String [] args) {
Hashmap m = new hashmap ();
For (int i = 1; i <10; i )
M.PUT ("km" i, "m" i);
System.out.println ("User for loop:");
For (INT i = 1; i <= m.size (); i )
System.out.println ("km" i "=" m.get ("km" i));
System.out.println ("User Iterator Loop:");
Iterator it = m.enTryset (). Iterator ();
While (it.hasnext ()) {
Map.Entry Entry = (map.entry) it.next ();
System.out.println (entry.getKey () "=" entry.getValue ());
}
}
}
2. Several functions related to havehmap
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 KEY information. 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]. 4. To achieve a simple HashMap and its principles
4.1 In the PUT () method:
1) First, by Key to insert the Hash Code to insert, and this Hash Code is used as an index to find the elements 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 same element as the key-value pair that is inserted in operation 1), if there is, if there is, if there is no, Inserted key-value pair array element.
4.2 in the get () method
1) First, by Key to find the Hash Code to find the key-value pair, 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 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
Implements 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 SetValue (Object V) {
Object result = value;
Value = v;
Return Result;
}
/ **
* When comparing two MPAIR objects, compare their Key values
* /
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];
/ **
* Insert KEY and VALUE to implement the class into the realization of Map.Entry, inserted into array * /
Public Object Put (Object Key, Object Value) {
Object result = null;
/ / Get the key-value pair to insert by Key to insert the Hash Code
Int index = key.hashcode ()% sz;
IF (INDEX <0) index = - index;
IF (bucket [index] == NULL)
Bucket [index] = new linkedlist ();
// Find the element in the array corresponding to the key to inserted by Hash Code
LinkedList Pairs = BUCKET [INDEX];
/ / Package the key-value pair to be inserted into MPAIR
MPAIR PAIR = New MPAIR (Key, Value);
Listiterator it = pairs.listiterator ();
Boolean Found = False;
/ / Check if there is the same key to the same key as the key to insert, if there is, it will be updated.
While (it.hasnext ()) {
Object iPair = it.next ();
IPAIR.EQUALS (IPAIR) {
Result = ((MPAIR) ipair) .getValue ();
IT.set (pair);
Found = True;
Break;
}
}
// If there is no, insert the new key-value pair
IF (! Found)
BUCKET [INDEX] .ADD (Pair);
Return Result;
}
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 ();
IPAIR.EQUALS (Match))
Return ((MPAIR) ipair .getValue ();
}
Return NULL;
}
Public set entryset () {
Set entries = new hashset ();
For (int i = 0; i IF (Bucket [i] == null) Continue; Iterator it = bucket [i] .Itemrator (); While (it.hasnext ()) Entries.add (it.next ()); } Return entries; } } PUBLIC CLASS ExplicitStatic { Public static void main (String [] args) { Simplehashmap m = new simplehashmap (); For (int i = 1; i <10; i ) M.PUT ("km" i, "m" i); System.out.println (m); } }
