Java collection: source code analysis of ArrayList

Kind little black brother 2021-01-22 16:20:07
java collection source code analysis


As a matter of fact, I have seen many big men have written such articles , And the writing is clear and clear , Then why should I write it again ? In fact, it's also to deepen my impression , Consolidate your foundation

( The main reason is that many articles haven't written out what I want to know !!!​!!!!)


Preface  

Let me talk about how I think I can understand , See through a source code .

When you analyze the source code , First of all, you should be able to use , To understand the function of this tool class , What functions does a tool class contain , The role of these functions is not clear , I think watching the source code is a kind of suffering .( Of course , Except big boys )

​ In self brainwashing ~ I'm a big man ! I'm a big man ! I'm a big man !(he~tui! I don't deserve it. !!!)


Text

This time is based on JDK1.8 Come to the specific analysis ArrayList Source code

ArrayList The concept of :

The dynamic array , It provides dynamic add and drop elements , Realized Collection and List Interface , Set the size of the array flexibly .

Every ArrayList Each instance has a capacity . This capacity refers to the size of the array used to store list elements . It's always at least the size of the list . Go with ArrayList Add elements to it , Its capacity is also high Automatic growth .

1、 Inheritance structure analysis

So let's see ArrayList Class inheritance structure :

Java Support single inheritance , Multiple implementation

AbstractList<E>

Abstract interface class , The goal is to use methods already implemented in abstract classes .

Let's drive AbstractList<E> Source code , You'll see that in fact AbstractList<E> It has been realized List<E> Interface , Why inherit first AbstractList<E>, And let AbstractList To achieve List<E>? Rather than let ArrayList Direct realization List<E>?

Here's an idea , Interfaces are all abstract methods , And abstract classes can have abstract methods , There can also be specific implementation methods , That's what makes use of it , Give Way AbstractList<E> Implement some common methods in the interface , Such as ArrayList Just inherit this AbstractList class , Get some general methods , Then I'm implementing some of my own unique methods , thus , Make the code simpler , The common methods in the lowest class of inheritance structure are extracted , First of all, we realized , Reduce duplicate code . So we usually see an abstract class above a class , It should be this function .

List<E>

Use List Interface specification

RandomAccess

This is a markup interface , By looking at api file , It's used for fast random access , The question of efficiency , After implementing the interface , So use normal for Loop to traverse , Higher performance , for example arrayList. If the interface is not implemented , Use Iterator To iterate , That's better performance , for example linkedList. So this markedness is just to let us know what way we use to get better data performance .

Cloneable

The purpose is to use clone Method . I want to know more about this method , Click here , This article is well written Cloneable~~

Serializable

Implement the serialization interface , Indicates that the class can be serialized , What is serialization ? To put it simply , It can be transferred from class to byte stream , Then it can change from byte to original class .

Why? AbstractList It's done List,ArrayList It's going to happen again ? 

  • Actually ArrayList Do it again List There is no practical significance here , This is actually a mistake , Because when the author wrote this code, he thought it would be useful , But it doesn't really work , But because it doesn't matter , It's been there until now . Those of you who are interested can study it .

2、 Class analysis  

public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
/**
* Default capacity
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* Construct a default empty array with parameters
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* The default empty array is constructed without parameters
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* Array elements ( Array of actual operations , newly added , Delete and other methods are all operations in this array )
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* The size of the actual array
*/
private int size;
/**
* The maximum capacity of an array
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 

Here are a few places to analyze :

(1) Why is the maximum size of an array Integer.MAX_VALUE - 8, instead of Integer.MAX_VALUE

In fact, comments are given in the source code : Some virtual machines keep some header information in the array . Avoid memory overflow !

 /**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

(2) Why defines Two empty arrays

The fundamental reason to define an empty array first is Optimize processing , If there are many of them in an application ArrayList If you don't have an empty instance , There will be lots of empty arrays , No doubt to optimize performance , all ArrayList Empty instances all point to the same empty array . Both are used to reduce the creation of empty arrays , All empty ArrayList All share empty arrays . The difference between the two is mainly used to distinguish , In view of the construction with parameters and without parameters, different expansion logics are used in expansion , Optimize performance .

(3)elementData Why is it defined as transient?

See here for specific reasons : elementData Defined as transent Why

3、 Construction method

Array List There are three construction methods , Let's analyze one by one

1) Nonparametric construction method ArrayList()

 /**
* Initialize the empty array to 10( Initialize the empty array to 10, When to initialize the size to 10, I'll talk about it later )
*/
public ArrayList() {
// take elementData The element array is initialized to an empty array
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

In the nonparametric construction method , Put the elements into an array elementData Initialize to an empty array .( Be careful : This reflects what I said above , Why define two empty arrays )

2) Parametric construction method ArrayList(int)

 /**
* Construct a list with the specified initial capacity
*
* @param initialCapacity: Initializing the value of an array
*/
public ArrayList(int initialCapacity) {
// If the initialization value is greater than 0, Then give elementData A length of initialCapacity Array of
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) { // If the initialization value equals 0, Then initialize to an empty array
this.elementData = EMPTY_ELEMENTDATA;
} else { // otherwise ( Less than 0 The situation of ) Throw an exception
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}

3) Parametric construction method ArrayList(Collection<? extends E> c)

 /**
* Construct a collection of specified elements ( This method is not very common )
* @param c
*/
public ArrayList(Collection<? extends E> c) {
// Convert the set to an array and assign it to elementData
elementData = c.toArray();
// If the size of the set is not 0
if ((size = elementData.length) != 0) {
// If the converted array is not generic (object), You need to use Arrays I want to change my tool to object Array ( It's no longer right here Arrays.copyOf Expand the discussion )
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else { // Otherwise initialize elementData Is an empty array
this.elementData = EMPTY_ELEMENTDATA;
}
}

For the current construction method , Let me give you an example , It's clearer

4、 Common methods source code analysis

boolean add(E e)

A top priority ,ArrayList The core of the mystery !!!!

 /**
* Add an element to the array
* @param e Element object
*/
public boolean add(E e) {
// Determine if the internal capacity is sufficient ,size Is the number of data in the element array , Because to add an element , therefore size+1, First judge size+1 Can this array of numbers hold , It's in this method to determine whether an array .length Is it enough .
ensureCapacityInternal(size + 1);
// Put the element e Assign values to the elementData At the end of
elementData[size++] = e;
return true;
}
// This method can be understood as transit calculation
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// Determine whether the array is an empty array , If it's an empty array ( here minCapacity = 0 + 1 = 1), will minCapacity Initialize to 10, But it just returns the size of the array to be initialized , The array is not really initialized to 10
// private static final int DEFAULT_CAPACITY = 10;
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// Math.max( Parameters 1, Parameters 2) Method means to return the largest number of arguments , If it's empty, the array is , Back at this point is 10
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
// If the initialized collection is not empty , Then returns the size + 1
return minCapacity;
}
// Don't worry I've got a secret. It's automatic ( Mystery detergent ~ People all over the country know ~~)
private void ensureExplicitCapacity(int minCapacity) {
// Structural change records +1 In the parent class AbstractList A is defined in int The properties of type :modCount, Recorded ArrayList The number of structural changes
modCount++;
// Determine if the array is enough , If not enough , It will be automatically expanded
// 1、 When the initialized collection is an empty array , here minCapacity yes 10, and elementData The length of is 0, So we need to expand
// 2、 When the initialized collection is not empty, it is , That is, given the size , Or the element has been initialized , At this time minCapacity = The actual number of arrays +1, At this point, the judgment set is not enough , It also needs to be expanded , Otherwise the element will overflow
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// Automatic expansion
private void grow(int minCapacity) {
// oldCapacity: The actual length of the element array ( That is, the size of the array before expansion )
int oldCapacity = elementData.length;
// oldCapacity Capacity expansion 1.5 A multiplier is assigned to newCapacity( >> For the shift right operator , Equivalent to divided by 2 namely oldCapacity/2 )
int newCapacity = oldCapacity + (oldCapacity >> 1);
// If the initialization is empty , Then expand the array to 10, This is the time to initialize the element array elementData The size is 10
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// If 1.5 The array size of times exceeds the maximum length of the collection , Call hugeCapacity Method , Recalculate , That is, given the maximum set length
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// The size has been determined , Just put the elements copy To elementData Element array ~~
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
// Memory overflow determination
if (minCapacity < 0)
throw new OutOfMemoryError();
// The logic here is : If the size to be expanded is larger than the maximum value of the array , Just go back to Integer,MAX_VALUE(int Maximum ), Otherwise, returns the maximum value of the set (int Maximum -8)
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}

void add(int index, E element)

Add element to specified subscript

 /**
* Add element to specified subscript
*
* @param index Subscript
* @param element Elements
*/
public void add(int index, E element) {
// Parameter checking
rangeCheckForAdd(index);
// This method will not be repeated , Refer to above Add Discussion on the importance of method
ensureCapacityInternal(size + 1);
// Look at the comments for the code block below
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// Overlay the specified element to the specified subscript
elementData[index] = element;
// length size + 1
size++;
}
/**
* Apply to add and addAll The verification method of this paper is as follows
*/
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

System.arraycopy Method resolution

 /**
* System Provides a static method arraycopy(), We can use it to copy between arrays
* Function is :public static native void arraycopy(Object src,int srcPos,Object dest, int destPos,int length);
* @param src the source array. Source array
* @param srcPos starting position in the source array. The starting position of the source array
* @param dest the destination array. Target array
* @param destPos starting position in the destination data. The starting position of the target array
* @param length the number of array elements to be copied. The length of the copy
// for instance
public static void main(String[] args){
int[] arr = {1,2,3,4,5};
int[] copied = new int[10];
System.out.println(Arrays.toString(copied));
System.arraycopy(arr, 0, copied, 1, 5);//5 It's the length of the copy
System.out.println(Arrays.toString(copied));
}
The output is :
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 2, 3, 4, 5, 0, 0, 0, 0] 

boolean remove(Object o)

Delete by element

 public E remove(int index) {
// Parameter checking
rangeCheck(index);
// Structural change records +1
modCount++;
// Get old data , Back to the developer , The goal is to let developers know which data has been deleted
E oldValue = elementData(index);
// Count the number of times the element needs to be moved
int numMoved = size - index - 1;
if (numMoved > 0)
// Same as above
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// Leave the last element empty ( The element moves forward , The last position is empty ), Give Way GC Recycling
elementData[--size] = null;
return oldValue;
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

void clear()

Empty the set

 /**
* Empty the set
*/
public void clear() {
modCount++;
// Leave the array empty , prompt GC Recycling
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}

E get(int index)

Returns the element at the specified location in this list  

 /**
* Check that the given index is in range . without , An appropriate runtime exception is thrown .
* @param index : Subscript
*/
public E get(int index) {
// Verify subscript validity
rangeCheck(index);
// Returns the specified... In the element array index Location data
return elementData(index);
}
private void rangeCheck(int index) {
// If the subscript is larger than the actual array length ( The last data subscript of the element array is size-1)
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

E set(int index, E element) 

 /**
* Overlay the corresponding subscript data
* @param index Subscript
* @param element Element data
*/
public E set(int index, E element) {
// Verification method ( No more explanation , And get In the same way )
rangeCheck(index);
// Get old data , Here, old data is returned , To let developers know which value to replace
E oldValue = elementData(index);
// Override the specified subscript as a new element
elementData[index] = element;
return oldValue;
}


ending

Actually ArrayList There are many, many ways to do it , I'm not going to describe it one by one here , Because you understand the source code in this article , In fact, we need to understand other things , To view the , It's easier and simpler .

That's all for this article , If there's something wrong with it , Your advice are most welcome , I'm a kind little black brother , I hope to make progress with you !!

版权声明
本文为[Kind little black brother]所创,转载请带上原文链接,感谢
https://javamana.com/2021/01/20210122161705630f.html

  1. 【计算机网络 12(1),尚学堂马士兵Java视频教程
  2. 【程序猿历程,史上最全的Java面试题集锦在这里
  3. 【程序猿历程(1),Javaweb视频教程百度云
  4. Notes on MySQL 45 lectures (1-7)
  5. [computer network 12 (1), Shang Xuetang Ma soldier java video tutorial
  6. The most complete collection of Java interview questions in history is here
  7. [process of program ape (1), JavaWeb video tutorial, baidu cloud
  8. Notes on MySQL 45 lectures (1-7)
  9. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  10. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  11. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  12. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  13. 【递归,Java传智播客笔记
  14. [recursion, Java intelligence podcast notes
  15. [adhere to painting for 386 days] the beginning of spring of 24 solar terms
  16. K8S系列第八篇(Service、EndPoints以及高可用kubeadm部署)
  17. K8s Series Part 8 (service, endpoints and high availability kubeadm deployment)
  18. 【重识 HTML (3),350道Java面试真题分享
  19. 【重识 HTML (2),Java并发编程必会的多线程你竟然还不会
  20. 【重识 HTML (1),二本Java小菜鸟4面字节跳动被秒成渣渣
  21. [re recognize HTML (3) and share 350 real Java interview questions
  22. [re recognize HTML (2). Multithreading is a must for Java Concurrent Programming. How dare you not
  23. [re recognize HTML (1), two Java rookies' 4-sided bytes beat and become slag in seconds
  24. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  25. RPC 1: how to develop RPC framework from scratch
  26. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  27. RPC 1: how to develop RPC framework from scratch
  28. 一次性捋清楚吧,对乱糟糟的,Spring事务扩展机制
  29. 一文彻底弄懂如何选择抽象类还是接口,连续四年百度Java岗必问面试题
  30. Redis常用命令
  31. 一双拖鞋引发的血案,狂神说Java系列笔记
  32. 一、mysql基础安装
  33. 一位程序员的独白:尽管我一生坎坷,Java框架面试基础
  34. Clear it all at once. For the messy, spring transaction extension mechanism
  35. A thorough understanding of how to choose abstract classes or interfaces, baidu Java post must ask interview questions for four consecutive years
  36. Redis common commands
  37. A pair of slippers triggered the murder, crazy God said java series notes
  38. 1、 MySQL basic installation
  39. Monologue of a programmer: despite my ups and downs in my life, Java framework is the foundation of interview
  40. 【大厂面试】三面三问Spring循环依赖,请一定要把这篇看完(建议收藏)
  41. 一线互联网企业中,springboot入门项目
  42. 一篇文带你入门SSM框架Spring开发,帮你快速拿Offer
  43. 【面试资料】Java全集、微服务、大数据、数据结构与算法、机器学习知识最全总结,283页pdf
  44. 【leetcode刷题】24.数组中重复的数字——Java版
  45. 【leetcode刷题】23.对称二叉树——Java版
  46. 【leetcode刷题】22.二叉树的中序遍历——Java版
  47. 【leetcode刷题】21.三数之和——Java版
  48. 【leetcode刷题】20.最长回文子串——Java版
  49. 【leetcode刷题】19.回文链表——Java版
  50. 【leetcode刷题】18.反转链表——Java版
  51. 【leetcode刷题】17.相交链表——Java&python版
  52. 【leetcode刷题】16.环形链表——Java版
  53. 【leetcode刷题】15.汉明距离——Java版
  54. 【leetcode刷题】14.找到所有数组中消失的数字——Java版
  55. 【leetcode刷题】13.比特位计数——Java版
  56. oracle控制用户权限命令
  57. 三年Java开发,继阿里,鲁班二期Java架构师
  58. Oracle必须要启动的服务
  59. 万字长文!深入剖析HashMap,Java基础笔试题大全带答案
  60. 一问Kafka就心慌?我却凭着这份,图灵学院vip课程百度云