ArrayList

本贴最后更新于 2313 天前,其中的信息可能已经物是人非

java.util.ArrayList

允许为空;
允许重复数据;
有序;
非线程安全。

public class ArrayList<E> extends AbstractList<E> implememts List<E>, RondomAccess, Cloneable, java.io.Serializable {
  private static final int DEFAULT_CAPACITY = 10;
  
  // ArrayList在序列化的时候会调用writeObject,直接将size和element写入ObjectOutputStream;反序列化时调用readObject,从ObjectInputStream获取size和element,再恢复到elementData。
  // 为什么不直接用elementData来序列化,而采用上诉的方式来实现序列化呢?原因在于elementData是一个缓存数组,它通常会预留一些容量,等容量不足时再扩充容量,那么有些空间可能就没有实际存储元素,采用上诉的方式来实现序列化时,就可以保证只序列化实际存储的那些元素,而不是整个数组,从而节省空间和时间。
  transient Object[] elementData; // 非私有简化嵌套类访问
  
  private int size; // 逻辑长度
  
  public  ArrayList() { 
	elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; // 为什么这里选择空数组而不是初始化为容量为10的数组呢?其实是用了懒加载,第一次添加元素时会自动扩容为容量10
  }
  
  // 先把集合转化为数组,然后判断数组类型是否是Object[].class(如果不是的话,不属于此类及其子类但属于Object类或其子类的实例就添加不进去了),不是的话通过Arrays.copyOf()复制(copyOf底层靠System.copyArray()方法)
  public ArrayList(Collection<? extens E> c) {
	elementData = c.toArray(); // 用Arrays.copyOf()实现
	if ((size = elementData.length) != 0) { 
	  // c.toArray might (incorrectly) not return Object[] (see 6260652) 
	  if (elementData.getClass() != Object[].class) 
		elementData = Arrays.copyOf(elementData, size, Object[].class);
	} else { 
	  array.  this.elementData = EMPTY_ELEMENTDATA; 
	}
  }
  
  public Object[] toArray() {
	return Arrays.copyOf(elementData, size);
  }
  
  /*
  * 先判断是否是第一次添加元素,是的话懒加载默认容量10,添加元素
  * 否则断数组长度是否大于逻辑长度,是的话直接添加元素,不是的话进行数组扩容;
  * 将数组长度扩大为1.5倍,然后进一步判断;
  * 如果数组长度依然比请求的最小长度小,将数组直接扩容到请求的长度(这种情况发生在:一次性插入多个值,也就是调用addAll()方法)
  * 如果数组长度大于2\^31-9且小于等于2\^31-1(因为有一个符号位),返回2\^31-1。(2^31-1是因为size是int类型)
  */
  public boolean add(E e) {
	ensureCapacityInternal(size + 1);
	elementData[size++] = e;
	return true;
  }
  
  private  void  ensureCapacityInternal(int minCapacity) {
	// 第一次添加元素懒加载默认容量10
	if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
	  minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); 
	} 
  
	ensureExplicitCapacity(minCapacity); 
  }
  
  private  void  ensureExplicitCapacity(int minCapacity) { 
	modCount++; // 记录修改次数,modCount在AbstractList类中声明protected transient int modCount = 0;
  
  // 数组越界,需要进行容量扩展  
  if (minCapacity - elementData.length > 0) 
  grow(minCapacity); 
  } 
  
  /**
  * 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
  * -8 是为了减少出错的几率
  */
  private  static  final  int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 
  
  private  void  grow(int minCapacity) {  
	int oldCapacity = elementData.length; 
	int newCapacity = oldCapacity + (oldCapacity >> 1);  // 相当于oldCapacity + (oldCapacity / 2)
	
	if (newCapacity - minCapacity < 0) 
	  newCapacity = minCapacity; 
	  
	if (newCapacity - MAX_ARRAY_SIZE > 0)
	  newCapacity = hugeCapacity(minCapacity); 
	  
	elementData = Arrays.copyOf(elementData, newCapacity);
  } 
  
  private  static  int  hugeCapacity(int minCapacity) { 
	if (minCapacity < 0) // overflow,因为0111 .... 1111 + x 只要 x 大于 1 就进位,符号位变为 1 ,为负数
	  throw  new OutOfMemoryError(); 
	  
	return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; 
  }
  
  public  void add(int  index, E element)
  
  public  boolean  addAll(Collection c)
  
  public E get(int  index)
  
  public  int  indexOf(Object o)
  
  public  int  lastIndexOf(Object o)
  
  public E remove(int  index)
  
  // 根据删除的对象是否为null进行区分,因为是null就不能调用equals方法了
  public  boolean remove(Object o)
  
  private  void fastRemove(int  index)
  
  // 要求集合c不能为null
  public  boolean  removeAll(Collection c)
  
  public  void  clear()

  public Iterator<E> iterator() {
	  return new Itr();
  }
  
  private class Itr implements Iterator<E> {
	  int cursor;       // index of next element to return
	  int lastRet = -1; // index of last element returned; -1 if no such
	  int expectedModCount = modCount;

	  public boolean hasNext() {
		  return cursor != size;
	  }

	  @SuppressWarnings("unchecked")
	  public E next() {
		  checkForComodification();
		  int i = cursor;
		  if (i >= size)
			  throw new NoSuchElementException();
		  Object[] elementData = ArrayList.this.elementData;
		  if (i >= elementData.length)
			  throw new ConcurrentModificationException();
		  cursor = i + 1;
		  return (E) elementData[lastRet = i];
	  }
	  
	 //检查modCount是否改变了,如果改变了,直接抛出异常  
	 final  void checkForComodification() { 
	   if (modCount != expectedModCount) 
		 throw  new ConcurrentModificationException(); 
	 }
  }
  
  // 双向移动
  public ListIterator listIterator(int  index)
  
  private  class ListItr extends Itr implements ListIterator<E>

Verctor:
1、线程安全;
2、Vector 可以指定增长因子,如果该增长因子指定了,那么扩容的时候会每次新的数组大小会在原数组的大小基础上加上增长因子;如果不指定增长因子,那么就给原数组大小*2。

int newCapacity = oldCapacity + ((capacityIncrement >  0  ) ? capacityIncrement : oldCapacity);

数组和 List 相互转化:
List strList = Arrays.asList(arr);
String[] arr = strList.toArray();

类.class
对象.getClass()

参考:
ArrayList 源码
http://blog.csdn.net/qq_19431333/article/details/54405686
http://blog.csdn.net/shijinupc/article/details/7827507

  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3165 引用 • 8206 回帖

相关帖子

回帖

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...

推荐标签 标签

  • Swift

    Swift 是苹果于 2014 年 WWDC(苹果开发者大会)发布的开发语言,可与 Objective-C 共同运行于 Mac OS 和 iOS 平台,用于搭建基于苹果平台的应用程序。

    34 引用 • 37 回帖 • 496 关注
  • 招聘

    哪里都缺人,哪里都不缺人。

    189 引用 • 1056 回帖
  • Caddy

    Caddy 是一款默认自动启用 HTTPS 的 HTTP/2 Web 服务器。

    10 引用 • 54 回帖 • 125 关注
  • ReactiveX

    ReactiveX 是一个专注于异步编程与控制可观察数据(或者事件)流的 API。它组合了观察者模式,迭代器模式和函数式编程的优秀思想。

    1 引用 • 2 回帖 • 124 关注
  • Bootstrap

    Bootstrap 是 Twitter 推出的一个用于前端开发的开源工具包。它由 Twitter 的设计师 Mark Otto 和 Jacob Thornton 合作开发,是一个 CSS / HTML 框架。

    18 引用 • 33 回帖 • 683 关注
  • Mobi.css

    Mobi.css is a lightweight, flexible CSS framework that focus on mobile.

    1 引用 • 6 回帖 • 689 关注
  • frp

    frp 是一个可用于内网穿透的高性能的反向代理应用,支持 TCP、UDP、 HTTP 和 HTTPS 协议。

    15 引用 • 7 回帖
  • 笔记

    好记性不如烂笔头。

    303 引用 • 777 回帖
  • BookxNote

    BookxNote 是一款全新的电子书学习工具,助力您的学习与思考,让您的大脑更高效的记忆。

    笔记整理交给我,一心只读圣贤书。

    1 引用 • 1 关注
  • Vue.js

    Vue.js(读音 /vju ː/,类似于 view)是一个构建数据驱动的 Web 界面库。Vue.js 的目标是通过尽可能简单的 API 实现响应的数据绑定和组合的视图组件。

    261 引用 • 662 回帖 • 1 关注
  • wolai

    我来 wolai:不仅仅是未来的云端笔记!

    1 引用 • 11 回帖
  • Ruby

    Ruby 是一种开源的面向对象程序设计的服务器端脚本语言,在 20 世纪 90 年代中期由日本的松本行弘(まつもとゆきひろ/Yukihiro Matsumoto)设计并开发。在 Ruby 社区,松本也被称为马茨(Matz)。

    7 引用 • 31 回帖 • 166 关注
  • 数据库

    据说 99% 的性能瓶颈都在数据库。

    330 引用 • 614 回帖
  • C++

    C++ 是在 C 语言的基础上开发的一种通用编程语言,应用广泛。C++ 支持多种编程范式,面向对象编程、泛型编程和过程化编程。

    106 引用 • 152 回帖 • 2 关注
  • Facebook

    Facebook 是一个联系朋友的社交工具。大家可以通过它和朋友、同事、同学以及周围的人保持互动交流,分享无限上传的图片,发布链接和视频,更可以增进对朋友的了解。

    4 引用 • 15 回帖 • 449 关注
  • OAuth

    OAuth 协议为用户资源的授权提供了一个安全的、开放而又简易的标准。与以往的授权方式不同之处是 oAuth 的授权不会使第三方触及到用户的帐号信息(如用户名与密码),即第三方无需使用用户的用户名与密码就可以申请获得该用户资源的授权,因此 oAuth 是安全的。oAuth 是 Open Authorization 的简写。

    36 引用 • 103 回帖 • 3 关注
  • SQLite

    SQLite 是一个进程内的库,实现了自给自足的、无服务器的、零配置的、事务性的 SQL 数据库引擎。SQLite 是全世界使用最为广泛的数据库引擎。

    4 引用 • 7 回帖 • 1 关注
  • 安全

    安全永远都不是一个小问题。

    189 引用 • 813 回帖 • 2 关注
  • Python

    Python 是一种面向对象、直译式电脑编程语言,具有近二十年的发展历史,成熟且稳定。它包含了一组完善而且容易理解的标准库,能够轻松完成很多常见的任务。它的语法简捷和清晰,尽量使用无异义的英语单词,与其它大多数程序设计语言使用大括号不一样,它使用缩进来定义语句块。

    534 引用 • 671 回帖
  • uTools

    uTools 是一个极简、插件化、跨平台的现代桌面软件。通过自由选配丰富的插件,打造你得心应手的工具集合。

    5 引用 • 13 回帖
  • SMTP

    SMTP(Simple Mail Transfer Protocol)即简单邮件传输协议,它是一组用于由源地址到目的地址传送邮件的规则,由它来控制信件的中转方式。SMTP 协议属于 TCP/IP 协议簇,它帮助每台计算机在发送或中转信件时找到下一个目的地。

    4 引用 • 18 回帖 • 581 关注
  • Telegram

    Telegram 是一个非盈利性、基于云端的即时消息服务。它提供了支持各大操作系统平台的开源的客户端,也提供了很多强大的 APIs 给开发者创建自己的客户端和机器人。

    5 引用 • 35 回帖 • 1 关注
  • 倾城之链
    23 引用 • 66 回帖 • 93 关注
  • Electron

    Electron 基于 Chromium 和 Node.js,让你可以使用 HTML、CSS 和 JavaScript 构建应用。它是一个由 GitHub 及众多贡献者组成的活跃社区共同维护的开源项目,兼容 Mac、Windows 和 Linux,它构建的应用可在这三个操作系统上面运行。

    15 引用 • 136 回帖
  • jQuery

    jQuery 是一套跨浏览器的 JavaScript 库,强化 HTML 与 JavaScript 之间的操作。由 John Resig 在 2006 年 1 月的 BarCamp NYC 上释出第一个版本。全球约有 28% 的网站使用 jQuery,是非常受欢迎的 JavaScript 库。

    63 引用 • 134 回帖 • 744 关注
  • RIP

    愿逝者安息!

    8 引用 • 92 回帖 • 285 关注
  • 国际化

    i18n(其来源是英文单词 internationalization 的首末字符 i 和 n,18 为中间的字符数)是“国际化”的简称。对程序来说,国际化是指在不修改代码的情况下,能根据不同语言及地区显示相应的界面。

    7 引用 • 26 回帖 • 1 关注