Talk about the interview questions of the collection

A collection of interview questions ：

1、 Tell me about the collection you know ：

Sets fall into two categories ：

• Conllection aggregate ( Singleton set )
  • List aggregate ( The elements inside can be repeated )
    • ArrayList aggregate ： The bottom layer is array storage , It is characterized by fast query , Add or delete slowly
    • LinkedList aggregate ： The bottom layer is linked list storage , It is characterized by fast addition and deletion , Slow query
  • Set aggregate ( The elements inside cannot be repeated )
    • HashSet:
    • LinkedHashSet
    • TreeSet
• Map aggregate 　( Double column set )
  • HashMap aggregate
  • LinkedHashMap aggregate
  • TreeMap aggregate
  • HashTable aggregate

2、 Say yes ArrayList The understanding of the

​ ArrayList A set is List An implementation class , Its bottom layer is realized by array , The array is queried by index , The query speed is relatively fast , therefore ,ArrayList Collection queries are also very fast , The time complexity of the query is O(1). Adding and deleting words is very slow , Compared to another set . This collection is thread unsafe . Because in its add() In the method , I will check whether the capacity of the array is enough , Not enough is to create a new array , Then save the contents of the array to the new number , After assigning the referenced array address to the new array , Reach the problem of array expansion , its add() The operation is not atomic

Be careful ： atom （atom） The original intention is “ The smallest particles that cannot be further divided ”,

​ Atomic manipulation （atomic operation） Meaning for ” An operation or series of operations that cannot be interrupted ”

3、 Say yes LinkedList The understanding of the

LinkedList It's also List An implementation class , Its bottom layer is a double linked list structure , There is a next Pointer to the next element , One prev The pointer points to the previous element , Because it is a double linked list structure , So his increase, decrease and deletion are fast , Slow query . It's not thread safe , Its addition operation is not atomic ,

4、 Say yes Vector The understanding of the

Vector It's also List An implementation class of the collection , At the bottom of it is an array , Bottom and ArrayList The collection is almost the same , That is to say ArrayList add （synchironized） After the lock , So it's thread safe , however , Its utilization rate is very low , The main reason is his low efficiency , No, ArrayList high .

5、 say something List and Set The difference between

List and Set The difference between ：List The storage of is in the order of storage , and Set The storage order of is based on the hash value ;

​ List Can store repeated elements , and Set Cannot store duplicate elements

6、 Say yes HashSet The understanding of the

HashSet yes Set An implementation class , The underlying implementation is HashMap Of key, His initial capacity is 16, The load factor is 0.75, If the capacity is expanded, it will be expanded to the original 2 times .HashSet The order in which the elements are stored is not the order in which they are stored , It is stored according to the size of the hash value of the element . It cannot store the same elements , Through it HashCode() Methods and equals() Methods compare whether two elements are the same element .

7、LinkedHashSet The understanding of the

LinkedHashSet It is right for the foundation HashSet Set plus double linked list , Make its access orderly

8、 say something TreeSet The understanding of the

TreeSet Is to use the principle of binary tree add The objects of are sorted in the specified order （ Ascending 、 Descending ）, Each element added will be sorted , Insert the element into the specified position of the binary tree

9、 Chat HashMap The understanding of the （ a key ）

stay JDK1.7 before , At the bottom of it is an array + Linked list implementation of

stay JDK1.8 after , At the bottom of it is an array + Linked list + Red black tree realized , First, use the structure of the array to store , After encountering elements with the same hash value , Determine whether it is the same element , Not after the same element , A linked list will be derived at that position of the array , Store on this chain 8 After elements , When there are elements with the same hash value, the red black tree is used to store the elements ,

It does not guarantee that the access order of elements is consistent

Threads are not safe

10、LinkeHashMap The understanding of the

LinkeHashMap It's solved HashMap The access elements of are not consistent , A linked list has been added to his internal , Ensure consistent access sequence

11、 If you want to guarantee HashMap Thread safety for , What to do ？

Can pass HashTable To ensure its thread safety , The emergence of this class is mainly to solve this problem , The solution is to use synchironized Locking mechanism , So the efficiency is not very high , So it is rarely used , Also do not recommend ,

stay JDK10.0 When , The solution is to use and contract a class inside ,ConcurrentHashMap, This class is java.util.concurrent A class in the package , Is an extension of it , It also solves the problem of thread insecurity

12、Conllection and Conllections Comparison

Conllection Is a collection interface , It is the top-level interface in the collection , Both he and == Provides the public basic operation methods of the collection , Its inherited interfaces are List and Set Two interfaces ,

Conllections Is a collection of tool classes , Provide a series of static methods , Used to sort the elements in the collection 、 Search for 、 And thread safety

13、ArrayList and LinkedList Comparison

ArrayList The underlying data structure of a collection is an array , It supports random access to arrays . Time complexity O(1)

LinkedList The underlying data structure of is a double linked list , Random access is not supported , Use subscripts to access the next element . Time complexity O(n)

14、ArrayList and Vector Comparison

Vector Used synchironzied To ensure that threads are synchronized , Is thread safe , Each expansion is an expansion 1 times

ArrayList Not thread safe , And every time it expands, it just expands 0.5 times

15、HashMap and HashTable Comparison

HashMap Allow empty key value , and HashTable Don't allow ,HashMap It's not thread safe ( Efficient ),HashTable It's thread safe ( The efficiency is not high )