Detailed explanation of Set, List and Map in Java for multi-use and multi-learning

For a long time, the data list that has been used more frequently in the code is mainly List, and they are all ArrayList. I feel that this thing is enough. ArrayList is a packaging tool class used to implement dynamic arrays. This way you can pull in and out and iterate through when writing code, which is quite convenient.

I don’t know since when tool classes such as HashMap and HashSet often appeared in the code. It should be said that there are more HashMap, and it is a classic interview question, so I will look at it more often. When you first start using it, you can simply understand it as a key-value correspondence table. It is more convenient to use keys to find data. After further understanding, I found that there is still a little mystery in

, especially after the new version of JDK changes HashMap to a tree, the code is a little complicated.

Set was rarely used at first, but I accidentally discovered a TreeSet in a code, and found that this class can be used smoothly. It felt quite interesting, and then I slowly discovered that it is also a good tool.

After writing a lot of code, I feel the importance of the basics, so I will write a short article here to briefly organize some knowledge about collections.

Okay, let’s briefly organize it:

•List: It is a list, supports the functions of arrays and linked lists, and is generally linear
•Map: It is a mapping table, What is stored is the corresponding relationship between keys and values
•Set: It means set, mainly used for deduplicating data and sorting

Let’s take a look at List first

List is a window used to store linear data, such as ArrayList for arrays and LinkedList for linked lists.

ArrayList

This is an array list, but it provides the function of automatic expansion and implements the List interface. External operations are accessed through the methods declared by the interface, which is safe and convenient.

The key to ArrayList is automatic expansion. When the object is initialized, the initial capacity can be set, or the default capacity can be used. If the array size is not particularly clear, you do not need to specify the initial size. If it is clear, you can specify a size to reduce the lag caused by dynamic expansion. Speaking of which, let’s talk about how expansion is achieved. Look at the following code:

private void grow(int minCapacity) {
 
    // overflow-conscious code
 
    int oldCapacity = elementData.length;
 
    int newCapacity = oldCapacity + (oldCapacity >> 1);
 
    if (newCapacity - minCapacity < 0)
 
      newCapacity = minCapacity;
 
    if (newCapacity - MAX_ARRAY_SIZE > 0)
 
      newCapacity = hugeCapacity(minCapacity);
 
    // minCapacity is usually close to size, so this is a win:
 
    elementData = Arrays.copyOf(elementData, newCapacity);
 
  }

grow is a method that is triggered when ArrayList adds elements or some easy checks. Main process:

1. Get the length of the array and shift it right, which is equivalent to oldCapacity/2, get the new length

2. If this length is less than the minimum capacity, then Just use the minimum easy

3. If it is greater than the maximum easy, take a maximum value. Here, a hugeCapacity method will be called, mainly to compare minCapacity with MAX_ARRAY_SIZE. If minCapacity is greater than MAX_ARRAY_SIZE, take Integer.MAX_VALUE, otherwise Just take MAX_ARRAY_SIZE. What’s interesting is that MAX_ARRAY_SIZE takes Integer.MAX_VALUE - 8; I don’t know what the meaning of this is.

4. The last step is to call a copy method to copy the existing number to a new array. .

Because of this copy process, if the array is relatively large, then of course there will be lags if the expansion is always triggered. So if the maximum value is known from the beginning and can easily grow to this value, then specifying the size at the beginning of the initialization will have some effect.

LinkedList

This is a tool class for linked lists. The advantage of linked lists is that they are faster to add, delete, etc., but search will be slower.

As for the code, there seems to be nothing special. It is just a series of pointers linked together. Of course, Java uses objects instead to create a Node object. The Node itself points to the previous Node and the next Node. This is The structure of the linked list:

private static class Node<E> {
 
   E item;
 
   Node<E> next;
 
   Node<E> prev;
 
 
 
   Node(Node<E> prev, E element, Node<E> next) {
 
     this.item = element;
 
     this.next = next;
 
     this.prev = prev;
 
   }
 
 }

Then use two Nodes to point to the head and tail. The following code:

/**
 
   * Pointer to first node.
 
   * Invariant: (first == null && last == null) ||
 
   *      (first.prev == null && first.item != null)
 
   */
 
  transient Node<E> first;
 
  
 
  /**
 
   * Pointer to last node.
 
   * Invariant: (first == null && last == null) ||
 
   *      (last.next == null && last.item != null)
 
   */
 
  transient Node<E> last;

Look at an add operation:

/**
 
   * Links e as last element.
 
   */
 
  void linkLast(E e) {
 
    final Node<E> l = last;
 
    final Node<E> newNode = new Node<>(l, e, null);
 
    last = newNode;
 
    if (l == null)
 
      first = newNode;
 
    else
 
      l.next = newNode;
 
    size++;
 
    modCount++;
 
  }

The past is:

1. Obtain the last Node and put it in l

2. Create a new Node and fetch the data into this Node. The creation process will point the prev of the new Node to l. , so the chain is connected

3, and then point last to this new Node

4, and then determine whether l is null. If it is null, it means it is an empty linked list, and the new node is the first one. element, so first must also point to newNode

5. If it is not empty, point next of l to newNode

6. The cumulative counter

deletion operation is also this kind of Node. The front and back Node points to the move operation.

Let’s take a look at Map

Map is an application that creates a mapping table between keys and values. The main implementation classes are: HashMap, HashTable, TreeMap

HashMap and HashTable

The one that uses hash algorithm for key-value mapping is HashMap. HashTable is a thread-safe class with synchronization. The main difference between them is this. The principle is also similar, both are implemented through the combination of bucket + chain. Buckets are used to store Keys, and due to Hash collisions, values ​​need to be stored in a linked list.

•The significance of buckets lies in high efficiency, and can be located in one step through Hash calculation
•The significance of linked lists lies in accessing duplicate hashed data

The specific principle has been previously written in an article "Study Notes" ：Hashtable and HashMap》

It’s just that the HashMap of JDK1.8 has changed the storage structure and adopts a red-black tree structure. This may solve the problem of linked list search efficiency, right? There is no detailed study.

TreeMap

看过TreeMap的代码后发现还是使用的树结构，红黑树。由于红黑树是有序的，所以自然带排序功能。当然也可通过comparator来指定比较方法来实现特定的排序。

因为采用了树结构存储那么添加和删除数据时会麻烦一些，看一下put的代码：

public V put(K key, V value) {
 
    Entry<K,V> t = root;
 
    if (t == null) {
 
      compare(key, key); // type (and possibly null) check
 
  
 
      root = new Entry<>(key, value, null);
 
      size = 1;
 
      modCount++;
 
      return null;
 
    }
 
    int cmp;
 
    Entry<K,V> parent;
 
    // split comparator and comparable paths
 
    Comparator<? super K> cpr = comparator;
 
    if (cpr != null) {
 
      do {
 
        parent = t;
 
        cmp = cpr.compare(key, t.key);
 
        if (cmp < 0)
 
          t = t.left;
 
        else if (cmp > 0)
 
          t = t.right;
 
        else
 
          return t.setValue(value);
 
      } while (t != null);
 
    }
 
    else {
 
      if (key == null)
 
        throw new NullPointerException();
 
      @SuppressWarnings("unchecked")
 
        Comparable<? super K> k = (Comparable<? super K>) key;
 
      do {
 
        parent = t;
 
        cmp = k.compareTo(t.key);
 
        if (cmp < 0)
 
          t = t.left;
 
        else if (cmp > 0)
 
          t = t.right;
 
        else
 
          return t.setValue(value);
 
      } while (t != null);
 
    }
 
    Entry<K,V> e = new Entry<>(key, value, parent);
 
    if (cmp < 0)
 
      parent.left = e;
 
    else
 
      parent.right = e;
 
    fixAfterInsertion(e);
 
    size++;
 
    modCount++;
 
    return null;
 
  }

1、先是检查根节点是否存在，不存在说明是第一条数据，直接作为树的根

2、判断是否存在比较器，如果存在则使用比较器进行查找数据的存放位置，如果比较器返回结果小于0取左，大于0取右，否则直接替换当前节点的值

3、如果不存在比较器则key直接与节点的key比较，比较和前面方法一样

4、接下来就是在找到的parent上创建一个子节点，并放入左或者右子节点中

5、fixAfterInsertion是对节点进行着色

6、累加器处理

在remove操作时也会有点麻烦，除了删除数据外，还要重新平衡一下红黑树。

另外，TreeMap实现了NavigableMap接口，所以也提供了对数据集合的一些返回操作。

最后看看Set

Set主要是两类应用：HashSet和TreeSet。

HashSet

字面意思很明确，使用了Hash的集合。这种集合的特点就是使用Hash算法存数据，所以数据不重复，存取都相对较快。怎么做到的呢？

public boolean add(E e) {
 
    return map.put(e, PRESENT)==null;
 
  }

原来是存在一个map对象中，再看map是个啥？

private transient HashMap<E,Object> map;

是个HashMap，了解HashMap的就明白，这样的数据是不会重复的。因为存入时是鼗对象本身作为Key来存的，所以在HashMap中只会存在一份。

了解了这点其他的东西就非常明白了。

TreeSet

这个集合是用于对集合进行排序的，也就是除了带有排重的能力外，还可以自带排序功能。只不过看了TreeSet的代码发现，其就是在TreeMap的基础实现的。更准确的说应该是NavigableMap的派生类。默认不指定map情况下TreeSet是以TreeMap为基础的。

public TreeSet() {
 
    this(new TreeMap<E,Object>());
 
  }

所以，这里可能更关注的是TreeSet是如何排重呢？看一下add的方法吧：

public boolean add(E e) {
 
    return m.put(e, PRESENT)==null;
 
  }

和HashSet有点类似，都是基于Map的特性来实现排重。确实简单而且有效。

以上就是小编为大家带来的多用多学之Java中的Set,List,Map详解全部内容了，希望大家多多支持PHP中文网~

更多多用多学之Java中的Set,List,Map详解相关文章请关注PHP中文网！