1、ArrayList
ArrayList是List接口最常见的实现,其实现是基于数组的方式实现,无容量的限制,ArrayList是非线程安全的。
如下代码为ArrayList的构造函数,当没有确定的容量大小时,默认长度为10:
private transient Object[] elementData; public ArrayList(int initialCapacity) { super(); if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); this.elementData = new Object[initialCapacity]; } public ArrayList() { this(10); }
插入对象方法add(E e)把对象插入到数据尾部和add(int index, E element)把对象插入到指定位置index上:
public boolean add(E e) { ensureCapacity(size + 1); // Increments modCount!! elementData[size++] = e; return true; } public void add(int index, E element) { if (index > size || index < 0) throw new IndexOutOfBoundsException( "Index: "+index+", Size: "+size); ensureCapacity(size+1); // Increments modCount!! System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; }
插入对象都要做的就是先给对象扩容ensureCapacity(size+1):
public void ensureCapacity(int minCapacity) { modCount++; int oldCapacity = elementData.length; if (minCapacity > oldCapacity) { Object oldData[] = elementData; int newCapacity = (oldCapacity * 3)/2 + 1; if (newCapacity < minCapacity) newCapacity = minCapacity; // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } }
扩容后的空间有原来空间1.5倍+1。
删除对象remove(int index)和remove(Object o):
public boolean remove(Object o) { if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; } public E remove(int index) { RangeCheck(index); modCount++; E oldValue = (E) elementData[index]; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // Let gc do its work return oldValue; } 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; // Let gc do its work }
remove(Object o)采用的是遍历数组中的元素方式,指到等于传入的对象来删除,null与非null对象判断是否相等的方式是不一样的,然后都调用 fastRemove(int index)方法来删除;remove(int index)的删除跟remove(Object o)中的fastRemove(int index)删除方法一样,只是多了一个RangeCheck(index)数组范围检测和提供返回值。
ArrayList在插入元素的时候可能要先扩容,在删除元素的时候并不会减小数组的容量,如果希望相应的减小数组容量,可以调用trimToSize()方法:
public void trimToSize() { modCount++; int oldCapacity = elementData.length; if (size < oldCapacity) { elementData = Arrays.copyOf(elementData, size); } }
2、LinkedList
LinkedList也是 List接口常见的一种实现,也是非线程安全的,它是基于双向链表机制,所谓双向链表就是集合中的每个元素都知道其它前一个元素及后一个元素的位置。在 LinkedList中以一个内部的Entry类来代表集合中的元素,元素中的值赋给element属性,Entry中的next属性指向元素中的后一个 元素,previous指向无线的前一个属性。
private transient Entry<E> header = new Entry<E>(null, null, null); public LinkedList() { header.next = header.previous = header; } public LinkedList(Collection<? extends E> c) { this(); addAll(c); }
在创建LinkedList对象时先创建一个element属性、next属性、previous属性都为null的Entry对象并赋值给全局对象header。
LinkedList 的添加元素和删除元素也就是双向链表的操作,不像ArrayList那样考虑扩容、遍历和数据的复制问题,但它在插入元素时要创建一个新的Entry对 象。在删除元素时也要遍历链表,但是只需要只接删除链表上的元素即可而不像ArrayList那样实现数据复制。在查找元素时也必须要遍历链表。
3、Vector
Vector是从JDK1.2开始实现的,Vector和ArrayList一样,也是基于Object方式来实现的,但它是线程安全的。它的线程安全是基于synchronized关键字来实现的,也就是在所有操作方法前面加上synchronized关键字:
public synchronized int size() { return elementCount; } public synchronized void addElement(E obj) { modCount++; ensureCapacityHelper(elementCount + 1); elementData[elementCount++] = obj; } ......
和ArrayList不同的是Vector的扩容方式,通过传入capacityIncrement来控制容量 的扩充,如果capacityIncrement大于0,则将Object数组的大小扩大为现有的size加上capacityIncrement,如果 capacityIncrement等于或小于0,则将数组的大小扩大为现有size的两倍,这种扩容方式比ArrayList更为可控。
public Vector(int initialCapacity) { this(initialCapacity, 0); } public Vector(int initialCapacity, int capacityIncrement) { super(); if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); this.elementData = new Object[initialCapacity]; this.capacityIncrement = capacityIncrement; } private void ensureCapacityHelper(int minCapacity) { int oldCapacity = elementData.length; if (minCapacity > oldCapacity) { Object[] oldData = elementData; int newCapacity = (capacityIncrement > 0) ? (oldCapacity + capacityIncrement) : (oldCapacity * 2); if (newCapacity < minCapacity) { newCapacity = minCapacity; } elementData = Arrays.copyOf(elementData, newCapacity); } }
4、Stack
Stack继承于Vector,在Vector的基于上实现了栈的后进先出(LIFO)算法,提供了push、pop、peek等方法,Stack也是线程安全的。
5、HashSet
HashSet是Set接口的常见实现,Set和List最明显的区别是Set不充许有重复的元素,而List则充许。Set的内部实现是基于HashMap来实现的,Set中的元素就是HashMap中的Key,其容易是不限制的,HashSet是非线程安全的。
public HashSet() { map = new HashMap<E,Object>(); } public boolean add(E e) { return map.put(e, PRESENT)==null; }
6、TreeSet
TreeSet也是Set接口的一种实现,也是非线程安全的,和HashSet主要区别是TreeSet对排序的支持,TreeSet基于TreeMap实现:
private transient NavigableMap<E,Object> m; TreeSet(NavigableMap<E,Object> m) { this.m = m; } public TreeSet() { this(new TreeMap<E,Object>()); }
相关推荐
其中Collection接口是Java集合框架的基础接口之一,定义了一些基本的集合操作,包括添加元素、删除元素、遍历集合等。在这里,我将为您详细介绍Java集合框架中的Collection接口。 Collection接口是Java集合框架中的...
xmind格式的Java集合框架学习导图,包括Collection接口/Map接口以及具体实现类。 同样包含大厂面试题,也在导图中有所体现。 能学到什么: 更加成体系的知识框架,更加全面的、系统的知识。 思维导图: 思维导图具有...
Java集合框架概述 Java集合框架是一个抽象数据类型的框架,它提供了一组接口和类,可用于处理各种类型的数据结构,如列表、队列、集、映射等。 Java集合框架的主要特点是: 1、可扩展性:Java集合框架提供了一组可...
所有抽象出来的数据结构和操作(算法)统称为Java集合框架(Java Collection Framework)。 Java程序员在具体应用时,不必考虑数据结构和算法实现细节,只需要用这些类创建出来一些对象,然后直接应用就可以了。这样...
Java集合框架中的Set接口是一种不允许包含重复元素的集合。Set接口继承自Collection接口,因此它具有Collection接口定义的所有方法。同时,Set接口还具有自己的特殊方法,例如:添加元素、删除元素、判断元素是否...
Java集合框架中的List接口是一种有序的集合,它可以存储重复的元素。它是Collection接口的子接口,提供了一系列可以对列表进行操作的方法,如添加、插入、删除、获取元素等。List接口还可以通过索引访问元素,类似于...
主要为大家详细介绍了Java集合框架之Collection接口,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
Java集合框架常见面试题 剖析⾯试最常⻅问题之 Java 集合框架 包含以下几个模块: 1、集合概述 2、Collection子接口之List 3、Collection子接口之Set 4、Map接口 5、Collection工具类 6、其他重要问题
Java集合框架汇总 1.集合框架结构图 1 2.两种特殊的Java容器类List和Set分析 2 3. Collection 接口: 2 4.Iterator 接口: 3 5.List接口: 3 5.1 LinkedList类: 5 5.2 ArrayList类: 5 6.Set接口: 5 7.Map...
本文档先从整体介绍了Java集合框架包含的接口和类,然后总结了集合框架中的一些...Java的集合类主要由两个接口派生而出:Collection和Map,Collection和Map是Java集合框架的根接口,这两个接口又包含了一些接口或实现类
超全Java集合框架讲解 - 超全Java集合框架讲解 - 集合框架总览 - Iterator Iterable ListIterator - Map 和 Collection 接口 - Map 集合体系详解 - HashMap - LinkedHashMap - TreeMap - WeakHashMap - ...
掌握Java集合框架中的三大类集合的特征和适用场合 掌握ArrayList类的使用 掌握HashMap类的使用 了解HashSet类的使用 掌握Collections类的使用 了解集合框架中的其它集合类 集合框架(Collection Framework) java.util...
Java 集合框架的基础接口有哪些? 4. 为何 Collection 不从 Cloneable 和 Serializable 接口继承? 5. 为何 Map 接口不继承 Collection 接口? 6. Iterator 是什么? 7. Enumeration 和 Iterator 接口的区别? ...
但是,在“集合框架”中,接口 Map 和 Collection 在层次结构没有任何亲缘关系,它们是截然不同的。这种差别的原因与 Set 和 Map 在 Java 库中使用的方法有关。Map 的典型应用是访问按关键字存储的值。它支持一系列...
Koloboke是一个精心设计的java集合框架,相比JDK的设计更加专业和高效。支持JDK6 ,采用Apache 2许可证。Koloboke兼容所有的原始的集合扩展基本的接口(Collection, Set, Map)。示例代码:@KolobokeMap @...
Java集合框架 集合:集合就是一个容器,可以存储很多东西,可以添加,可以删除,可以修改。 Collection接口 Collection接口式Java集合的根接口,是所有集合的父接口。该接口里面提供了很多操作集合的抽象方法。 ...
Java平台提供了一个全新的集合框架,框架的核心为Collection、List(列表)、Set(集合)和Map(映射)。集合类的框架为集合的实现者提供了大量的接口和抽象类,并对其中的某些机制给予了描述,例如,Iterator(迭代...
Collection集合框架的体系 Collection常用功能 1.public boolean add(E e):把给定的对象添加到集合中 2.public void clear():清空集合中的所用元素,但是集合仍然在。 3.public boolean remove(E e):把指定的对象从...
java数据结构,泛型与集合框架,有各种集合运算的算法,Collection接口介绍,数组方法介绍等
JAVA集合框架主要由两个接口派生而出,分别是Collection接口进入Map接口,这是集合框架的两个根接口,其中Collection接口的实现类直接保存对象,而Map接口的实现类是用键值对(key-value)的形式保存数据的,可以根据...