Java base collection Map

The Map:

For general applications, programs should consider using Hashmaps because hashmaps are designed for quick queries (the underlying HashMap also uses arrays to store key-value pairs). But if your program needs an always-ordered Map, consider using TreeMap.

LinkedHashMap is a bit slower than HashMap because it needs to maintain a linked list to maintain the order in which key-values are added to the Map. IdentityHashMap doesn’t perform particularly well because it uses a similar implementation to HashMap, except that it uses the == method instead of equals() to determine element equality. EnumMap performs best, but it can only use enumeration values of the same enumeration class as keys.

Collections

public class SynchronizedTest{

public static void main(String[] args){

    // The following program creates four synchronized collection objects

    Collection c=Collections.synchronizedCollection(new ArrayList());

    List list=Collections.synchronizedList(new ArrayList());

    Set s=Collections.synchronizedSet(new HashSet());

    Map m=Collections.synchronizedMap(newHashMap()); }}Copy the code

Implement a Map that is declarative, inefficient, and inflexible with a fixed size:

//: containers/AssociativeArray.java
// Associates keys with values.
import static net.mindview.util.Print.*;

public class AssociativeArray<K.V> {
  private Object[][] pairs;
  private int index;
  public AssociativeArray(int length) {
    pairs = new Object[length][2];
  }
  public void put(K key, V value) {
    if(index >= pairs.length)
      throw new ArrayIndexOutOfBoundsException();
    pairs[index++] = new Object[]{ key, value };
  }
  @SuppressWarnings("unchecked")
  public V get(K key) {
    for(int i = 0; i < index; i++)
      if(key.equals(pairs[i][0]))
        return (V)pairs[i][1];
    return null; // Did not find key
  }
  public String toString(a) {
    StringBuilder result = new StringBuilder();
    for(int i = 0; i < index; i++) {
      result.append(pairs[i][0].toString());
      result.append(":");
      result.append(pairs[i][1].toString());
      if(i < index - 1)
        result.append("\n");
    }
    return result.toString();
  }
  public static void main(String[] args) {
    AssociativeArray<String,String> map =
      new AssociativeArray<String,String>(6);
    map.put("sky"."blue");
    map.put("grass"."green");
    map.put("ocean"."dancing");
    map.put("tree"."tall");
    map.put("earth"."brown");
    map.put("sun"."warm");
    try {
      map.put("extra"."object"); // Past the end
    } catch(ArrayIndexOutOfBoundsException e) {
      print("Too many objects!");
    }
    print(map);
    print(map.get("ocean")); }}/* Output:
Too many objects!
sky : blue
grass : green
ocean : dancing
tree : tall
earth : brown
sun : warm
dancing
*// / : ~

Copy the code

Comparison between maps

Mapimplementation	describe
HashMap*	Implementation based on hash table. Use this class insteadHashtable). Provides constant time performance for inserting and positioning key-value pairs. Performance can be tuned using constructors that allow you to set the capacity and loading factor of a hash table.
LinkedHashMap	withHashMapSimilar, but when traversing, key-value pairs can be obtained in insertion order or least recently used (LRU) order. Only thanHashMapSlightly slower, with the exception of iteration, which is faster due to the use of linked lists to maintain internal order.
TreeMap	Implementation based on red black tree. When viewing keys or key-value pairs, they are in sort order (byComparable 或 ComparatorSure).TreeMapThe emphasis is on getting results in sorted order.TreeMapIs the only usesubMap()methodsMap, it returns a portion of the red-black tree.
WeakHashMap	A kind ofWeak bondWeak keysMapIn order to solve certain types of problems, it allows releaseMapThe object referenced. If theMapIf there is no foreign reference to a particular key, that key can be garbage collected.
ConcurrentHashMap	Thread-safe without using synchronous lockingMap. This is discussed in the chapter on Concurrency.
IdentityHashMap	use= =Rather thanequals()To compare keys. Only for solving special problems, not for general use.

//: containers/Maps.java
// Things you can do with Maps.
import java.util.concurrent.*;
import java.util.*;
import net.mindview.util.*;
import static net.mindview.util.Print.*;

public class Maps {
  public static void printKeys(Map<Integer,String> map) {
    printnb("Size = " + map.size() + ",");
    printnb("Keys: ");
    print(map.keySet()); // Produce a Set of the keys
  }
  public static void test(Map<Integer,String> map) {
    print(map.getClass().getSimpleName());
    map.putAll(new CountingMapData(25));
    // Map has 'Set' behavior for keys:
    map.putAll(new CountingMapData(25));
    printKeys(map);
    // Producing a Collection of the values:
    printnb("Values: ");
    print(map.values());
    print(map);
    print("map.containsKey(11): " + map.containsKey(11));
    print("map.get(11): " + map.get(11));
    print("map.containsValue(\"F0\"): "
      + map.containsValue("F0"));
    Integer key = map.keySet().iterator().next();
    print("First key in map: " + key);
    map.remove(key);
    printKeys(map);
    map.clear();
    print("map.isEmpty(): " + map.isEmpty());
    map.putAll(new CountingMapData(25));
    // Operations on the Set change the Map:
    map.keySet().removeAll(map.keySet());
    print("map.isEmpty(): " + map.isEmpty());
  }
  public static void main(String[] args) {
    test(new HashMap<Integer,String>());
    test(new TreeMap<Integer,String>());
    test(new LinkedHashMap<Integer,String>());
    test(new IdentityHashMap<Integer,String>());
    test(new ConcurrentHashMap<Integer,String>());
    test(newWeakHashMap<Integer,String>()); }}/* Output: HashMap Size = 25, Keys: [15, 8, 23, 16, 7, 22, 9, 21, 6, 1, 14, 24, 4, 19, 11, 18, 3, 12, 17, 2, 13, 20, 10, 5, 0] Values: [P0, I0, X0, Q0, H0, W0, J0, V0, G0, B0, O0, Y0, E0, T0, L0, S0, D0, M0, R0, C0, N0, U0, K0, F0, A0] {15=P0, 8=I0, 23=X0, 16=Q0, 7=H0, 22=W0, 9=J0, 21=V0, 6=G0, 1=B0, 14=O0, 24=Y0, 4=E0, 19=T0, 11=L0, 18=S0, 3=D0, 12=M0, 17=R0, 2=C0, 13=N0, 20=U0, 10=K0, 5=F0, 0=A0} map.containsKey(11): true map.get(11): L0 map.containsValue("F0"): true First key in map: 15 Size = 24, Keys: [8, 23, 16, 7, 22, 9, 21, 6, 1, 14, 24, 4, 19, 11, 18, 3, 12, 17, 2, 13, 20, 10, 5, 0] map.isEmpty(): true map.isEmpty(): true ... * // / : ~

Copy the code

HashMap:

In JDK 1.7 it was arrays + linked lists,

In JDk1.8 it is an array + a linked list + a red-black tree. If the number of linked elements in the bucket is greater than or equal to 8, the linked list is converted to a tree structure. If the number of linked elements in the bucket is less than or equal to 6, the tree structure is restored to a linked list. When the number of linked lists is around 8, tree to tree will be generated, linked list to tree, inefficient. The default hasMap load factor is 0.75, 2^n for more uniform hashing.

See more: mp.csdn.net/console/edi…

SortedMap

With SortedMap (implemented by TreeMap or ConcurrentSkipListMap), the keys are guaranteed in sort order, which allows these methods to be used in the SortedMap interface to provide additional functionality:

• Comparator comparator(): build for thisMapThe comparator of,nullRepresents natural sort.
• T firstKey()Returns the first key.
• T lastKey(): Returns the last key.
• SortedMap subMap (fromKey, toKey): to generate theMapView, where the key is fromfromKey(including), totoKey(Not included).
• SortedMap headMap(toKey): Use less thantoKeyThe key generates thisMapIn the view.
• SortedMap tailMap(fromKey): Uses greater than or equal tofromKeyThe key generates thisMapIn the view.

Here is an example similar to sortedSetDemo.java that shows this additional behavior of TreeMap:

// collectiontopics/SortedMapDemo.java
// What you can do with a TreeMap
import java.util.*;
import onjava.*;

public class SortedMapDemo {
  public static void main(String[] args) {
    TreeMap<Integer,String> sortedMap =
      new TreeMap<>(new CountMap(10));
    System.out.println(sortedMap);
    Integer low = sortedMap.firstKey();
    Integer high = sortedMap.lastKey();
    System.out.println(low);
    System.out.println(high);
    Iterator<Integer> it =
      sortedMap.keySet().iterator();
    for(int i = 0; i <= 6; i++) {
      if(i == 3) low = it.next();
      if(i == 6) high = it.next();
      elseit.next(); } System.out.println(low); System.out.println(high); System.out.println(sortedMap.subMap(low, high)); System.out.println(sortedMap.headMap(high)); System.out.println(sortedMap.tailMap(low)); }}/* Output:
{0=A0, 1=B0, 2=C0, 3=D0, 4=E0, 5=F0, 6=G0, 7=H0, 8=I0,
9=J0}
0
9
3
7
{3=D0, 4=E0, 5=F0, 6=G0}
{0=A0, 1=B0, 2=C0, 3=D0, 4=E0, 5=F0, 6=G0}
{3=D0, 4=E0, 5=F0, 6=G0, 7=H0, 8=I0, 9=J0}
*/Copy ErrorOK!Copy the code

Here, the key-value pair is sorted by the order in which the key is sorted. Because there is a sense of order in TreeMap, the concept of “place” makes sense, so you can have the first and last element or subgraph.

LinkedHashMap

LinkedHashMap hashes for speed, but also generates key-value pairs in insertion order during traversal (System.out.println() can iterate over it, so you can see the result of the traversal). In addition, you can configure the LinkedHashMap in the constructor to use the access-based least-recently-used (LRU) algorithm, so that elements that are not accessed (and therefore candidates for deletion) appear first in the list. This makes it easy to create a program that can be cleaned up periodically to save space. Here is a simple example showing both capabilities:

// collectiontopics/LinkedHashMapDemo.java
// What you can do with a LinkedHashMap
import java.util.*;
import onjava.*;

public class LinkedHashMapDemo {
  public static void main(String[] args) {
    LinkedHashMap<Integer,String> linkedMap =
      new LinkedHashMap<>(new CountMap(9));
    System.out.println(linkedMap);
    // Least-recently-used order:
    linkedMap =
      new LinkedHashMap<>(16.0.75 f.true);
    linkedMap.putAll(new CountMap(9));
    System.out.println(linkedMap);
    for(int i = 0; i < 6; i++)
      linkedMap.get(i);
    System.out.println(linkedMap);
    linkedMap.get(0); System.out.println(linkedMap); }}/* Output:
{0=A0, 1=B0, 2=C0, 3=D0, 4=E0, 5=F0, 6=G0, 7=H0, 8=I0}
{0=A0, 1=B0, 2=C0, 3=D0, 4=E0, 5=F0, 6=G0, 7=H0, 8=I0}
{6=G0, 7=H0, 8=I0, 0=A0, 1=B0, 2=C0, 3=D0, 4=E0, 5=F0}
{6=G0, 7=H0, 8=I0, 1=B0, 2=C0, 3=D0, 4=E0, 5=F0, 0=A0}
*/!
Copy the code

These key-value pairs are indeed traversed in insertion order, even for the LRU version. However, after the first six items are accessed (only) in the LRU version, the last three items are moved to the top of the list. Then, when “0” is accessed again, it moves down the list.

Create a Collection or Map that cannot be modified

Often, it is convenient to create read-only versions of collections or maps. The Collections class returns a read-only version of the collection by passing the original collection to a method. There are many variations of this class for Collection (if you can’t treat Collection as a more specific type), List, Set, and Map. This example shows how to properly build a collection of read-only versions for each type:

// collectiontopics/ReadOnly.java
// Using the Collections.unmodifiable methods
import java.util.*;
import onjava.*;

public class ReadOnly {
  static Collection<String> data = new ArrayList<>(Countries.names(6));
  public static void main(String[] args) {
    Collection<String> c = Collections.unmodifiableCollection(new ArrayList<>(data));
    System.out.println(c); // Reading is OK
    //- c.add("one"); // Can't change it

    List<String> a = Collections.unmodifiableList(new ArrayList<>(data));
    ListIterator<String> lit = a.listIterator();
    System.out.println(lit.next()); // Reading is OK
    //- lit.add("one"); // Can't change it

    Set<String> s = Collections.unmodifiableSet(new HashSet<>(data));
    System.out.println(s); // Reading is OK
    //- s.add("one"); // Can't change it

    // For a SortedSet:
    Set<String> ss = Collections.unmodifiableSortedSet(new TreeSet<>(data));

    Map<String,String> m =Collections.unmodifiableMap(new 					                                        HashMap<(Countries.capitals(6)));
    System.out.println(m); // Reading is OK
    //- m.put("Ralph", "Howdy!" );

    // For a SortedMap:
    Map<String,String> sm =
      Collections.unmodifiableSortedMap(
        new TreeMap<>(Countries.capitals(6))); }}/* Output:
[ALGERIA, ANGOLA, BENIN, BOTSWANA, BURKINA FASO,
BURUNDI]
ALGERIA
[BENIN, BOTSWANA, ANGOLA, BURKINA FASO, ALGERIA,
BURUNDI]
{BENIN=Porto-Novo, BOTSWANA=Gaberone, ANGOLA=Luanda,
BURKINA FASO=Ouagadougou, ALGERIA=Algiers,
BURUNDI=Bujumbura}
*/!
Copy the code

For specific types call “unmodifiable” method will not lead to a compile-time checks, but in the event of conversion, to modify the content of specific set any method call will produce UnsupportedOperationException anomalies.

In each case, the collection must be populated with meaningful data before it can be made read-only. After populating, the best way is to replace the existing reference with the reference generated by the “unmodifiable” method call. This way, once you make the content unmodifiable, you don’t run the risk of accidentally changing the content. On the other hand, this tool allows you to keep a modifiable collection as a private collection in a class and return a read-only reference to the collection from a method call. So, you can modify it inside the class, but other people can only read it.

Synchronize a Collection or a Map

The synchronized keyword is an important part of the topic of multithreading, and more complex content is covered in concurrency. Just notice here that the Collections class contains a way to automatically synchronize the entire collection. The syntax is similar to the ‘unmodifiable’ method:

// collectiontopics/Synchronization.java
// Using the Collections.synchronized methods
import java.util.*;

public class Synchronization {
  public static void main(String[] args) {
    Collection<String> c =
      Collections.synchronizedCollection(
        new ArrayList<>());
    List<String> list = Collections
      .synchronizedList(new ArrayList<>());
    Set<String> s = Collections
      .synchronizedSet(new HashSet<>());
    Set<String> ss = Collections
      .synchronizedSortedSet(new TreeSet<>());
    Map<String,String> m = Collections
      .synchronizedMap(new HashMap<>());
    Map<String,String> sm = Collections
      .synchronizedSortedMap(newTreeMap<>()); }}Copy the code

It is best to pass the new collection immediately through the appropriate “synchronized” method, as shown above. This way, the out-of-sync version is not accidentally exposed.

Fail Fast

Java collections also have mechanisms to prevent multiple processes from modifying the contents of the collection. This problem occurs if you are currently iterating through the collection and some other process steps in and inserts, deletes, or changes objects in the collection. Maybe the element has been traversed in the collection, maybe it hasn’t been traversed yet, maybe the collection will shrink after calling size()… There are many disaster scenarios. The Java Collections library uses a fail-fast mechanism that can detect any changes to a collection other than those caused by the current process. If it detects someone else is modify the collection, it will immediately generate ConcurrentModificationException anomalies. That’s what “fail-fast” means — it doesn’t try to detect problems later (and fail fast) using more sophisticated algorithms.

We can easily see the fail-fast mechanism in the operation by creating iterators and adding elements to the collection to which the iterator points, as follows:

// collectiontopics/FailFast.java
// Demonstrates the "fail-fast" behavior
import java.util.*;

public class FailFast {
  public static void main(String[] args) {
    Collection<String> c = new ArrayList<>();
    Iterator<String> it = c.iterator();
    c.add("An object");
    try {
      String s = it.next();
    } catch(ConcurrentModificationException e) { System.out.println(e); }}}/* Output:
java.util.ConcurrentModificationException
*/
Copy the code

The exception comes from trying to add an element to the collection after obtaining an iterator from the collection. The possibility that two parts of the program might modify the same collection creates an indeterminate state, so an exception notifies you to change the code. In this case, all elements should be added to the collection before the iterator is fetched.

ConcurrentHashMap, CopyOnWriteArrayList and CopyOnWriteArraySet use specific techniques to avoid ConcurrentModificationException anomalies.

To summarize, we can simply say HashMap:

• Underneath, a HashMap treats key-value pairs as a whole, which is an Entry object.

• At the bottom of HashMap, an Entry[] array is used to store all key-value pairs. When an Entry object needs to be stored, its storage location will be determined according to the Hash algorithm. When an Entry needs to be retrieved, the system finds its storage location based on the Hash algorithm and directly retrieves the Entry. Therefore, the reason why HashMap can quickly save and retrieve the entries it contains is exactly similar to real life: different things need to be placed in different locations so that they can be found quickly when needed.

• When creating a HashMap, there is a default load factor, which defaults to 0.75. This is a tradeoff between time and space costs: increasing the load factor reduces the memory footprint of the Hash table (that is, the Entry array), but increases the time overhead of querying data, which is the most frequent operation (both the Get () and PUT () methods of a HashMap use queries). Reducing the load factor improves the performance of data queries, but increases the memory used by Hash tables

• When using HashMap, adjust the load factor value as needed. If the program is concerned about space overhead, memory is tight, you can increase the load factor appropriately; If the program is more concerned about the time cost, memory is relatively rich, you can reduce the load factor appropriately. Typically, programmers do not need to change the value of the load factor.

• If you know from the beginning that a HashMap will hold multiple key-value pairs, you can create a HashMap with a large initial capacity. If the number of entries in the HashMap never exceeds the capacity * load factor, A HashMap does not need to call the resize() method to reallocate the table array, thus ensuring better performance. Of course, setting the initial capacity too high to begin with can be a waste of space (the system needs to create an Entry array of capacity), so you need to be careful about setting the initial capacity when creating a HashMap

The Map to Set

The relationship between sets and maps is very close:

The mapping between a Set and a Map is as follows.

S Set < – > Map

S enumsets < – > EnumMap

S SortedSet < – > SortedMap

S TreeSet < – > TreeMap

S NavigableSet < – > NavigableMap

S HashSet < – > HashMap

S LinkedHashSet < – > LinkedHashMap

Although the elements in a Map are key-value pairs and the elements in a Set are individual objects, if we think of a value in a key-value pair as an appendage to the key: wherever the key is, the value follows. This allows you to treat a Map the same way you treat a Set. In fact, Map provides an Entry inner class to encapsulate key-value pairs, and only the key encapsulated in the Entry is considered when calculating the Entry store. From the Java source, Java implements a Map, and then implements a Set by wrapping a Map with all values null.

If you put all the values in a Map together, they look a lot like a List: elements can be repeated, and each element can be looked up by index, except that instead of using integer values, the index in the Map has another object as its index. If you need to fetch an element from a List collection, you need to provide a numeric index of that element; If you need to pull an element from a Map, you need to provide the key index for that element. For this reason, maps are sometimes called dictionaries, or associative arrays

Traverse the map using the keyset() method:

public class LinkedHashMapTest {

    public static void main(String[] args) {

        LinkedHashMap scores = new LinkedHashMap();

        scores.put("Chinese".80);
        scores.put("English".82);
        scores.put("Mathematics".76);
		// Iterate over scores with key-value pairs
        for (Object key : scores.keySet()) {
            System.out.println(key + "-- -- -- -- -- - >"+ scores.get(key)); }}}Copy the code

Performance of HashSet and HashMap:

For HashSet and its subclasses, they use hash algorithm to determine the storage location of elements in the set and control the size of the set through hash algorithm. For HashMap, Hashtable, and its subclasses, they use hash algorithms to determine the storage of keys in the Map and increase the size of the key set through hash algorithms.

The location where elements can be stored in a hash table is called a bucket. Typically, one element is stored in a single bucket, which provides the best performance: The hash algorithm calculates the location of the bucket based on the hashCode value, and then extracts elements from the bucket. But the hash table is in open state: in the case of a hash collision, a single bucket stores multiple elements, which are stored in a linked list and must be searched in order. Figure 8.8 shows a diagram of the hash table storing elements and “hash conflicts” occur

Since a HashSet, a HashMap, and a Hashtable both use hash algorithms to determine the storage of their elements (a HashMap only considers keys), the hash table of a HashSet, a HashMap, and a HashMap contains the following attributes:

• Capacity: number of hash buckets
• Initial capacity: The number of buckets at which the hash table is created. Both HashMap and HashSet allow you to specify initial capacity in the constructor
• Size: indicates the number of records in the current hash table.
• Load Factor: The load factor is equal to size/ Capacity. A load factor of 0 represents an empty hash table, 0.5 represents a half-full hash table, and so on. A lightly loaded hash table has the characteristics of low conflict, good for insertion and query (but slower to iterate over elements using Iterator)

There is also a load limit in the hash table, which is a value ranging from 0 to 1. The load limit determines the maximum amount of the hash table can be filled. When the hash table’s load factor reaches a specified “load limit,” the hash table automatically doubles the capacity (number of buckets) and redistributes the original objects into new buckets. This is called rehashing. The constructors of HashSet and HashMap and Hashtable allow you to specify a load limit. The default “load limit” for HashSet and HashMap and Hashtable is 0.75, indicating that rehashing can occur when three-quarters of the hash table is already full.

The default value of load limit (0.75) is a compromise on the cost of time and space: a high load limit reduces the memory footprint of the hash table, but increases the time spent querying data, which is the most frequent operation (both get() and PUT () methods of a HashMap use queries); A low “load limit” improves the performance of the query data, but increases the memory overhead of the hash table. The programmer can adjust the “load limit” values of the HashSet and HashMap based on the actual situation.

If you know from the beginning that a HashSet and a HashMap and a Hashtable will hold many records, you can create a HashSet with a large initialization capacity. If the initialization capacity is always greater than the maximum number of records contained in a HashSet and a HashMap and a Hashtable divided by the load limit, Rehashing would not occur. You can increase records more efficiently when creating hashsets and hashmaps and hashtables with a large enough initial capacity, but setting the initial capacity too high can be a waste of space, so it is generally not desirable to set the initial capacity too high

Hashsets and maps have a good idea: