preface

For the record, this article uses JDK1.8

Having spent a week going through the core of the Java container, the feeling collection has nothing to fear!! (hahaha….) Now to sum up ~~

Review table of Contents:

• The Collection overview
• List collection is as simple as that.
• Map sets, hash tables, and red-black trees
• HashMap is as simple as this
• LinkedHashMap is as simple as this
• TreeMap is that simple
• ConcurrentHashMap is analyzed based on JDK1.8 source code
• Set sets are that simple!

Java containers fall into two broad categories:

• Collection
  • List
    • ArrayList
    • LinkedList
    • Vector(understood, obsolete)
  • Set
    • HashSet
      • LinkedHashSet
    • TreeSet
• Map
  • HashMap
    • LinkedHashMap
  • TreeMap
  • ConcurrentHashMap
  • Hashtable(understand,, obsolete)

The ones highlighted are the ones we use the most.

Actually, I don’t know how to sum it up, because I’ve summed it up in every article I’ve written before. It’s a bit daunting to list them all again now, so I decided to answer some Java container interview questions!

Of course, my answer may not be the right one. If there are mistakes, please include them in the comments section

ArrayList and Vector

Thing in common:

• Both of these classes implement the List interface, which is an ordered collection (storage order) with an array at the bottom. We can retrieve an element by position index, allowing elements to be duplicated and null.

The difference between:

• Synchronicity:
  • ArrayList is asynchronous
  • Vector is synchronous
  • Even when synchronization was needed, we could use the Collections utility class to build a synchronized ArrayList instead of a Vector
• Capacity expansion:
  • Vector is doubled, ArrayList is 0.5 times

The difference between HashMap and Hashtable

Thing in common:

• Storage structure and implementation are basically the same, are implemented Map interface ~

The difference between:

• Synchronicity:
  • HashMap is asynchronous
  • Hashtable is synchronous
  • Need to be synchronized, we tend not to use, and use ConcurrentHashMapConcurrentHashMap JDK1.8 based on source analysis
• Whether null is allowed:
  • HashMap can be null
  • Hashtable cannot be null
• The contains method
  • This knowledge point is in the cattle guest net brush to, did not think this kind of problem will have (I do not like)….
  • Hashtable contains methods
  • HashMap contains containsValue and containsKey
• Different inheritance:
  • HashMap<K,V> extends AbstractMap<K,V>
  • public class Hashtable<K,V> extends Dictionary<K,V>

The difference between a List and a Map

Thing in common:

• Both are common Java containers, both are interfaces (ps: writing feels like not writing…..)

Difference:

• Different storage structures:
  • A List is a collection that stores single columns
  • A Map stores a collection of key-value pairs
• Whether the element is repeatable:
  • List allows elements to be repeated
  • Map does not allow duplicate keys
• Whether to order:
  • List collections are ordered (store ordered)
  • Map collection is unordered (storage is unordered)

4. Elements in a Set cannot be repeated. Equals == or equals()?

We know that most sets actually use the PUT method of Map sets to add elements.

In the case of a HashSet, elements in a HashSet cannot be repeated, as shown in the source code (HashMap) :

	
	// 1. If the key is equal
    if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
        e = p;
	// 2. Modify the corresponding value
	   if(e ! =null) { // existing mapping for key
            V oldValue = e.value;
            if(! onlyIfAbsent || oldValue ==null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
       }
Copy the code

When adding an element, if the key(which also corresponds to the Set element) is equal, then change the value. In a Set, the value is just an Object (which is useless to the Set itself).

In other words, if a Set is added to the same element, it is not inserted at all. == and equals() are both used!

A Collection is a Collection

1. A Collection is the parent interface of a Collection, which is inherited by the Set and List interfaces
2. Collections is a utility class for Collections that provides a set of static methods for searching, finding, synchronizing, and so on

ArrayList,LinkedList storage performance and features

The underlying layer of an ArrayList is an array, and the underlying layer of a LinkedList is a bidirectional list.

• ArrayList allows you to index the corresponding element by corner position (random access), whereas LinkedList requires traversing the entire list to get the corresponding element. So arrayLists are generally faster than LinkedLists
• ArrayList is an array, which is expensive to delete and modify (copy and move the array implementation). LinkedList is a bidirectional LinkedList, which only needs to modify the corresponding pointer and consumes very little. As a result, linkedLists are generally added and deleted faster than arrayLists

6.1 extensions:

Arraylists are not necessarily slower to add or delete than linkedLists.

• If additions and deletions are done at the end (remove() and add() are called each time), the ArrayList does not need to move and copy the array to operate. If the data volume is in the millions, it is faster than LinkedList. (I’ve tested it)
• ifDelete operationThe location of theIn the middle. Since the consumption of LinkedList is mainly traversal, the consumption of ArrayList is mainly movement and copy(the underlying call is arrayCopy (), which is a native method).
  • LinkedList traversal is slower than ArrayList copy movement
  • If the data is in the millions, ArrayList is still faster. (I’ve tested it)

The differences between Enumeration and Iterator interfaces

Iterator replaces Enumeration. Enumeration is an old Iterator.

Iterator is safer than Enumeration because it prevents other threads from modifying the collection while it is being traversed.

• When we are doing exercises, iteration will not often wrong, throw ConcurrentModificationException, said when we were in the traversal in modifying elements.
• This is actually the fail – fast mechanism to specific posts for reference: blog.csdn.net/panweiwei19…

There are three differences:

• Iterator has a more scientific method name than Enumeration
• Iterator has fail-fast, which is more secure than Enumeration
• Iterator can delete elements. Enumeration cannot

8. ListIterator

• ListIterator inherits the Iterator interface, which is used to iterate over elements of a List collection.
• ListIterator allows you to traverse both ways, add elements, set elements

Take a look at the source method to know:

What is the concurrent collection class?

Java1.5 concurrency (java.util.concurrent) contains thread-safe collection classes that allow collections to be modified during iteration.

• Utils package under the collection of the iterator is designed to fail – fast, will throw ConcurrentModificationException. Java.util.concurrent does not, thanks for the comment section
• Some classes are:
  • CopyOnWriteArrayList
  • ConcurrentHashMap
  • CopyOnWriteArraySet

If the key of a Java HashMap is a class object, what conditions should the class meet?

You need to override both the class’s hashCode() method and its equals() method.

• As you can see from the source code, the object’s hashCode is computed before inserting an element. If hashCode is equal. That means the object is stored in the same location.
• If the equals() method is called and both keys are the same, the element is replaced
• If you call equals() and the two keys are different, then the hashCode just happens to be the same, which is a hash collision, putting the new element on the bucket

In general, we assume that two objects are equal as long as their member variables are equal! Object compares the addresses of two objects, which doesn’t make much sense to us. That’s why we overrode equals()

If you override equals(), you override hashCode(). Because equals() determines that the two objects are the same, and the same object should return the same value when calling hashCode()!

What are the best practices related to Java collections frameworks

1. Determine the type of collection as needed. For single-column collections, we consider using the subinterfaces ArrayList and Set under Collection. If it is a mapping, we consider using Map~
2. Having determined our set type, let’s move onDetermines which subclass of the collection type to useI think it can be divided into several steps:
   • Whether to synchronize
     • Find a thread-safe collection class to use
   • Whether order is required during iteration (order of insertion)
     • Look for Linked two-way list structures
   • Whether sorting is required (natural or manual)
     • Tree red black Tree type (JDK1.8)
3. Estimating how much data is stored in a collection, whether it’s a List or a Map, is performance costly when it grows dynamically. Giving a reasonable capacity at the time of initial collection will reduce the consumption of dynamic growth ~
4. Use generics to avoid classcastExceptions at runtime
5. Instead of writing your own implementation, use the Collections utility class whenever possible, or get read-only, synchronous, or empty Collections. It will provide code reuse, it will have better stability and maintainability

Add 10,000 pieces of data to ArrayList

The default initial capacity of an ArrayList is 10, which needs to be continuously expanded to insert large amounts of data, which can be very performance critical. So now that we know 100,000 pieces of data, we can set the size of the ArrayList directly at initialization!

This can improve efficiency

Xiii. Conclusion

Answer some of the interview questions above. I didn’t find the answers to many of the questions I thought were important (maybe MY search skills were too poor?). .

I took this article as the summary of the collection, but I didn’t think there was anything to write, so I answered some interview questions. After looking for the questions, I found it was not systematic enough. And this summary I do not want to copy the previous chapter summary here. So I decided to draw a brain map to end this article!

April 15, 2018 19:31:33 finished ！！！！！

Students who need more brain maps can follow the public account: Java3y, reply to “brain maps” ~

Open source project (6 K STAR) :Github.com/ZhongFuChen…

If you want to follow my updated articles and shared dry goods in real time, you can search Java3y on wechat.

The content of the PDF document is typed by hand. If you don’t understand anything, you can ask me directly (the official account has my contact information).