- 浏览: 2148955 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (682)
- 软件思想 (7)
- Lucene(修真篇) (17)
- Lucene(仙界篇) (20)
- Lucene(神界篇) (11)
- Solr (48)
- Hadoop (77)
- Spark (38)
- Hbase (26)
- Hive (19)
- Pig (25)
- ELK (64)
- Zookeeper (12)
- JAVA (119)
- Linux (59)
- 多线程 (8)
- Nutch (5)
- JAVA EE (21)
- Oracle (7)
- Python (32)
- Xml (5)
- Gson (1)
- Cygwin (1)
- JavaScript (4)
- MySQL (9)
- Lucene/Solr(转) (5)
- 缓存 (2)
- Github/Git (1)
- 开源爬虫 (1)
- Hadoop运维 (7)
- shell命令 (9)
- 生活感悟 (42)
- shell编程 (23)
- Scala (11)
- MongoDB (3)
- docker (2)
- Nodejs (3)
- Neo4j (5)
- storm (3)
- opencv (1)
最新评论
-
qindongliang1922:
粟谷_sugu 写道不太理解“分词字段存储docvalue是没 ...
浅谈Lucene中的DocValues -
粟谷_sugu:
不太理解“分词字段存储docvalue是没有意义的”,这句话, ...
浅谈Lucene中的DocValues -
yin_bp:
高性能elasticsearch ORM开发库使用文档http ...
为什么说Elasticsearch搜索是近实时的? -
hackWang:
请问博主,有用solr做电商的搜索项目?
Solr中Group和Facet的用法 -
章司nana:
遇到的问题同楼上 为什么会返回null
Lucene4.3开发之第八步之渡劫初期(八)
ArrayList也是在Java开发中使用频率非常高的一个类,内部是基于数组的动态管理的方式来实现的。数组在内存里面是一块连续的存储空间,其优势是基于下标的随机访问和遍历是非常高效的。
JDK8源码中的ArrayList类结构定义如下:
```` class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable ````
(1)继承了AbstractList实现了List接口是一个数组队列拥有了List基本的的增删改查功能
(2)实现了RandomAccess接口拥有随机读写的功能
(3)实现了Cloneable接口可以被克隆
(4)实现了Serializable了接口并重写了序列化和反序列化方法,使得ArrayList可以拥有更好的序列化的性能。
ArrayList中的成员变量和几个构造方法如下:
````java //定义的序列化id,主要是为了标识不同版本的兼容性 private static final long serialVersionUID = 8683452581122892189L; //默认的数组存储容量 private static final int DEFAULT_CAPACITY = 10; //当指定数组的容量为0的时候使用这个变量赋值 private static final Object[] EMPTY_ELEMENTDATA = {}; //默认的实例化的时候使用此变量赋值 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //真正存放数据的对象数组,并不被序列化 transient Object[] elementData; //数组中的真实元素个数它小于或等于elementData.length private int size; //数组中最大存放元素的个数 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; //构造函数一,如果指定容量就分配指定容量的大小 //没有指定就使用EMPTY_ELEMENTDATA赋值 public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } } //构造函数二,使用默认的DEFAULTCAPACITY_EMPTY_ELEMENTDATA赋值 public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } //构造一个传入的集合,作为数组的数据 public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); 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 { // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; } } ````
在了解了它的成员变量和构造函数之后,我们再来看下几个常用的方法:
(一)添加
添加有两个方法,第一个add(E e)方法的调用链涉及5个方法,分别如下:
```` //1 public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } //2 private void ensureCapacityInternal(int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } //3 private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); } //4 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); } //5 private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } ````这里一步步分析,在调用了add(E e)的方法第一步,我们看到了它调用了ensureCapacityInternal(size + 1)方法,在这个方法里面首先判断了数组是不是一个长度为0的空数组,如果是的话就给它容量赋值为默认的容量大小也就是10,然后调用了ensureExplicitCapacity方法,这个方法里面记录了modCount+1之后,并判断了当前的容量是否小于数组当前的长度,如果大于当前数组的长度就开始进行扩容操作调用方法 grow(minCapacity),扩容的长度是增加了原来数组数组的一半大小,然后并判断了是否达到了数组扩容的上限并赋值,接着把旧数组的数据拷贝到扩容后的新数组里面再次赋值给旧数组,最后把新添加的元素赋值给了扩容后的size+1的位置里面。
接着看第2个add方法:
```` public void add(int index, E element) { rangeCheckForAdd(index);//是否越界 ensureCapacityInternal(size + 1); // Increments modCount!! System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; } ````
这里面用到了 System.arraycopy方法,参数含义如下:
(原数组,原数组的开始位置,目标数组,目标数组的的开始位置,拷贝的个数)
(注:如果想了解关于Java里面数组拷贝的几种方式,请参考我的上一篇文章。)
这里面主要是给指定位置添加一个元素,ArrayList首先检查是否索引越界,如果没有越界,就检查是否需要扩容,然后将index位置之后的所有数据,整体拷贝到index+1开始的位置,然后就可以把新加入的数据放到index这个位置,而index前面的数据不需要移动,在这里我们可以看到给指定位置插入数据ArrayList是一项大动作比较耗性能。
(二)移除
(1)根据下标移除
````java public E remove(int index) { //检查是否越界 rangeCheck(index); //记录修改次数 modCount++; //获取移除位置上的值 E oldValue = elementData(index); //获取要移动元素的个数 int numMoved = size - index - 1; if (numMoved > 0) //拷贝移动的所有数据到index位置上 System.arraycopy(elementData, index+1, elementData, index, numMoved); //把size-1的位置的元素赋值null,方便gc elementData[--size] = null; // clear to let GC do its work //最终返回旧的数据 return oldValue; } ````
(2)根据元素移除
```` public boolean remove(Object o) { //等于null值的移除 if (o == null) { //遍历数组 for (int index = 0; index < size; index++) //找到集合里面第一个等于null的元素 if (elementData[index] == null) { //然后移除 fastRemove(index); return true; } } else { //非null情况下,遍历每一个元素通过equals比较 for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { //然后移除 fastRemove(index); return true; } } return false; } //该方法与通过下标移除的原理一样,整体左移 private void fastRemove(int index) { modCount++; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work } ````
remove方法与add(int index, E element)正好是一个相反的操作过程,移除一个元素,会影响到一批数据的位置移动,所以也是比较耗性能的。
(三)查询
```` public E get(int index) { //检查是否越界 rangeCheck(index); //返回指定位置上的元素 return elementData(index); } ````
(四)修改
```` public E set(int index, E element) { //检查是否越界 rangeCheck(index); //获取旧的元素值 E oldValue = elementData(index); //新元素赋值 elementData[index] = element; //返回旧的元素值 return oldValue; } ````
(五)清空方法
```` public void clear() { modCount++; // clear to let GC do its work for (int i = 0; i < size; i++) elementData[i] = null; size = 0; } ````
clear方法是把每个元素的值赋值为null,便于gc回收
(六)瘦身方法
```` public void trimToSize() { modCount++; if (size < elementData.length) { elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); } } ````该方法主要将数组空间缩减,去掉数组里面的null值。
Arrays.copyOf方法参数含义:(原数组,拷贝的个数)
(七)是否包含
````java public boolean contains(Object o) { return indexOf(o) >= 0; } public int indexOf(Object o) { if (o == null) { for (int i = 0; i < size; i++) if (elementData[i]==null) return i; } else { for (int i = 0; i < size; i++) if (o.equals(elementData[i])) return i; } return -1; } ````这里面主要是分两种情况null值的遍历和非null的遍历遍历,如果查询到就返回下标位置,否则就返回-1,然后与0相比,大于0就存在,小于0就是不存在。
总结:
本文介绍了JDK8中的ArrayList的工作原理和常用方法分析,此外ArrayList非线程安全,所以需要多线程的场景下,请使用jdk自带并发List结构或者Guava,Apache Common等工具包提供的List集合。基于数组实现的List在随机访问和遍历的效率比较高,但在插入指定和删除指定元素的时候效率比较低,而这正好和链表相反,链表的的查询和随机遍历效率较低,但插入和删除指定位置元素的效率比较高,这也是为什么HashMap中同时使用两种数据结构来优势互补的原因。
有什么问题可以扫码关注微信公众号:我是攻城师(woshigcs),在后台留言咨询。 技术债不能欠,健康债更不能欠, 求道之路,与君同行。
发表评论
-
记一次log4j不打印日志的踩坑记
2019-09-22 01:58 1466### 起因 前几天一个跑有java应用的生产集群(200多 ... -
在Java里面如何解决进退两难的jar包冲突问题?
2019-07-23 19:10 1146如上图所示: es api组件依赖guava18.0 ... -
如何轻松理解二叉树的深度遍历策略
2019-07-03 23:33 1027我们知道普通的线性数据结构如链表,数组等,遍历方式单一 ... -
为什么单线程Redis性能也很出色
2019-01-21 18:02 2136高性能的服务器,不一 ... -
如何将编程语言里面的字符串转成数字?
2019-01-11 23:23 1999将字符串转成数字在很 ... -
为什么Java里面String类是不可变的
2019-01-06 18:36 1593在Java里面String类型是不可变对象,这一点毫无疑问,那 ... -
关于Java里面volatile关键字的重排序
2019-01-04 18:49 990Java里面volatile关键字主 ... -
多个线程如何轮流打印ABC特定的次数?
2018-12-11 20:42 5934之前的一篇文章,我给 ... -
聊聊Java里面的引用传递
2018-11-16 21:21 941长久以来,在Java语言里面一直有一个争论,就是Java语言到 ... -
理解计数排序算法的原理和实现
2018-10-11 10:03 2050计数排序(Counting sort) ... -
理解Java7和8里面HashMap+ConcurrentHashMap的扩容策略
2018-09-06 11:31 3344### 前言 理解HashMap和Con ... -
关于Java里面多线程同步的一些知识
2018-07-18 09:45 1067# 关于Java里面多线程同步的一些知识 对于任何Java开 ... -
Java单例模式之双检锁深入思考
2018-07-08 12:25 3247# Java单例模式之双检锁 ... -
关于Java里面多线程同步的一些知识
2018-07-08 12:23 1087# 关于Java里面多线程同步的一些知识 对于任何Java开 ... -
重新认识同步与异步,阻塞和非阻塞的概念
2018-07-06 14:30 1430# 重新认识同步与异步 ... -
线程的基本知识总结
2018-06-27 16:27 1023### (一)创建线程的方式 (1)实现Runnable接口 ... -
Java里面volatile关键字修饰引用变量的陷阱
2018-06-25 11:42 1331# Java里面volatile关键字修饰引用变量的陷阱 如 ... -
关于Java里面的字符串拼接,你了解多少?
2018-06-25 11:28 1319# 关于Java里面的字符串 ... -
深入理解Java内存模型的语义
2018-06-25 11:39 693### 前言 Java内存模型( ... -
如何证明Java多线程中的成员变量数据是互不可见的
2018-06-21 10:09 1457前面的几篇文章主要介绍了Java的内存模型,进程和线程的定义, ...
相关推荐
这是我从JDK中拿出的Arraylist,Vector,LinkedList源码,自己看源码的时候弄出来的,并写了一点自己的分析,仅供源码分析者使用
基于jdk1.8 的ArrayList的源码分析 前言:一说到ArrayList的大家可能立马想到的就是:有序、可重复、查找快但是增删慢、线程不安全。但是具体的原因都不是很清楚,本文就会根据这些问题和大家一起去学习。主要会从...
ArrayList的源码,写了一些自己的分析,包括jdk1.8的新特性
·基于JDK 11,将Java8、Java9、Java10、Java11新特性一网打尽 ·课程中,Eclipse和IDEA这两种企业一线开发环境都使用到了 3.技术讲解更深入、更全面: ·课程共30天,715个知识视频小节,涉及主流Java使用的...
·基于JDK 11,将Java8、Java9、Java10、Java11新特性一网打尽 ·课程中,Eclipse和IDEA这两种企业一线开发环境都使用到了 3.技术讲解更深入、更全面: ·课程共30天,715个知识视频小节,涉及主流Java使用的...
1、首先看ArrayList默认构造方法创建 /** * Shared empty array instance used for default sized empty instances. We * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when * first ...
数组的缺点是每个元素之间不能有间隔,当数组大小不满足时需要增加存储能力,就要讲已经有数组的数据复制到新的存储空间中。当从ArrayList的中间位置插入或者删除元素时,需要对数组进行复制、移动、代价比较高。...
JDK1.8源码分析 相关的原始码分析结果会以注解的形式体现到原始码中 已完成部分: ReentrantLock CountDownLatch Semaphore HashMap TreeMap LinkedHashMap ConcurrentHashMap 执行器 ...
java8 源码 List相关实现类的源码解析(JDK1.8) 2018.9.22- List的架构图 ArrayList 继承关系: ArrayList -> AbstractList 实现 List接口 ArrayList 是一个数组队列,相当于 动态数组。与Java中的数组相比,它的...
知识追寻者目前的系列都是基于jdk1.8进行学习分析;本篇源码分析会进行每步分析,当所有方法分析完最后还会做个大总结;如果不爱看源码分析步骤,只要面试最终结论的读者可以看看文末的总结就行了; 知识追寻者...
文章目录Collection源码剖析(一)简介(二)源码分析 Collection源码剖析 (一)简介 Collection接口是集合层次结构中的根接口。 (1)下面是常用集合类关系图 Collection |___List 有序,可重复 |___...
ArrayList源码分析(基于JDK8) 因为Vector和ArrayList除了数组扩容有点差别,还有加锁使Vector迈进了线程安全的行列外,底层实现大约是没有太大区别的!基本一致!线程安全问题更是另当别论了!继续往下看就OK! ...
缓慢更新一些个人学习java相关源码过程中的笔记,在这里你将不可避免地看到以下情况: 个别不懂/没想好的地方留空待补全 限于个人水平出现的解读错误 编辑错误 排版不统一 如发现有错,欢迎指正! 如果对你有用,...
分析源码发现,在add方法中的elementData[size++] = e;存在线程不安全的风险。 elementData与size都是全局变量,但没有进行sychronization同步处理,elementData是共享的线程不安全的mutable可变数据。 public class...
Source code analysis for Java or JDK 记录一些重要的JDK/Java相关的源码分析。 Java 集合框架 ArrayList LinkedList HashMap 参考文章:
初始化仓库,其实这份源码之前有阅读过一点,有一些注释现在正是开始同步写博客分析 Java8 源码 博客地址: ArrayList ctor-3 get set add-2 remove-2 clear addAll write/readObject fast-fail subList iterator ...
HashMap(JDK1.8)源码+底层数据结构分析 ConcurrentHashMap 源码+底层数据结构分析 IO IO 基础知识总结 IO 设计模式总结 IO 模型详解 并发 知识点/面试题总结 : (必看 ) Java 并发常见知识点&面试题总结(上) Java ...
HashMap(JDK1.8)源码+底层数据结构分析 ConcurrentHashMap 源码+底层数据结构分析 IO IO 基础知识总结 IO 设计模式总结 IO 模型详解 并发 知识点/面试题总结 : (必看 ) Java 并发常见知识点&面试题总结(上) Java ...