suninf 's blog

It’s not what you know, it’s how you think

Java常用容器类

Catalog

Java容器类是java提供的工具包,包含了常用的数据结构:集合、链表、队列、栈、数组、映射等。

Java容器主要可以划分为4个部分:List列表、Set集合、Map映射、工具类(Iterator迭代器、Enumeration枚举类、Arrays和Collections)

Collection接口

Collection是一个接口,包含了集合的基本操作:添加、删除、清空、遍历(读取)、是否为空、获取大小等等。

public interface Collection<E> extends Iterable<E> {
    boolean         add(E object)
    boolean         addAll(Collection<? extends E> collection)
    void            clear()
    boolean         contains(Object object)
    boolean         containsAll(Collection<?> collection)
    boolean         equals(Object object)
    int             hashCode()
    boolean         isEmpty()
    Iterator<E>     iterator()
    boolean         remove(Object object)
    boolean         removeAll(Collection<?> collection)
    boolean         retainAll(Collection<?> collection)
    int             size()
    <T> T[]         toArray(T[] array)
    Object[]        toArray()
}

List列表

public interface List<E> extends Collection<E> {}

List是一个继承于Collection的接口,即List是集合中的一种。

List是有序的队列,List中的每一个元素都有一个索引,第一个元素的索引值是0。

    // List新增的api
    void                add(int location, E object)
    boolean             addAll(int location, Collection<? extends E> collection)
    E                   get(int location)
    int                 indexOf(Object object)
    int                 lastIndexOf(Object object)
    ListIterator<E>     listIterator(int location)
    ListIterator<E>     listIterator()
    E                   remove(int location)
    E                   set(int location, E object)
    List<E>             subList(int start, int end)

ArrayList

public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable

ArrayList是一个动态数组,也是我们最常用的集合。它允许任何符合规则的元素插入甚至包括null。

每一个ArrayList都有一个初始容量:private static final int DEFAULT_CAPACITY = 10;

随着容器中的元素不断增加,容器的大小也会随着增加。在每次向容器中增加元素的同时都会进行容量检查,当快溢出时,就会进行扩容操作。所以如果我们明确所插入元素的多少,最好指定一个初始容量值,避免过多的进行扩容操作而浪费时间、效率。

ArrayList转array

可以使用 toArray 方法

ArrayList<String> friendsnames = new ArrayList<String>();
friendsnames.add("hello");
friendsnames.add("world");

String frnames[] = friendsnames.toArray(new String[friendsnames.size()]);

LinkedList

public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinkedList是一个双向链表,不能随机访问,它所有的操作都是要按照双重链表的需要执行。好处就是可以通过较低的代价在List中进行插入和删除操作。

与ArrayList一样,LinkedList也是非线程安全的。如果多个线程同时访问一个List,则必须自己实现访问同步。

Vector & Stack

public class Vector<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
public class Stack<E> extends Vector<E> {}

Vector是线程安全级别的,但是大多数情况下不使用Vector,因为线程安全需要更大的系统开销。它的操作与ArrayList几乎一样。

Stack继承自Vector,实现一个后进先出的堆栈。

Queue队列

PriorityQueue

优先队列PriorityQueue通过二叉小顶堆实现,可以用一棵完全二叉树表示。

Deque & ArrayDeque

  • Deque是双端队列接口
  • ArrayDeque是一个基于数组的双端队列,和ArrayList类似,它们的底层都采用一个动态的、可重分配的Object[]数组来存储集合元素,当集合元素超出该数组的容量时,系统会在底层重新分配一个Object[]数组来存储集合元素

set集合

public interface Set<E> extends Collection<E> {}

Set是一个继承于Collection的接口,Set是一种不包括重复元素的Collection。与List一样,它同样运行null的存在但是仅有一个。

HashSet

public class HashSet<E> extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable

HashSet堪称查询速度最快的集合,因为其内部是以HashCode来实现的。集合元素可以是null,但只能放入一个null。它内部元素的顺序是由哈希码来决定的,所以它不保证set的迭代顺序。

TreeSet

public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable

TreeSet是二叉树实现的,基于TreeMap,生成一个总是处于排序状态的set,内部以TreeMap来实现,不允许放入null值。它是使用元素的自然顺序对元素进行排序,或者根据创建Set时提供的 Comparator 进行排序,具体取决于使用的构造方法。

LinkedHashSet

public class LinkedHashSet<E> extends HashSet<E>
implements Set<E>, Cloneable, java.io.Serializable

LinkedHashSet集合同样是根据元素的hashCode值来决定元素的存储位置,但是它同时使用链表维护元素的次序。

这样使得元素看起来像是以插入顺序保存的,也就是说,当遍历该集合时候,LinkedHashSet将会以元素的添加顺序访问集合的元素。LinkedHashSet在迭代访问Set中的全部元素时,性能比HashSet好,但是插入时性能稍微逊色于HashSet。

map字典

Map是由一系列键值对组成的集合,提供了key到Value的映射。

HashMap

public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable

以哈希表数据结构实现,查找对象时通过哈希函数计算其位置,它是为快速查询而设计的,其内部定义了一个hash表数组(Entry[] table),元素会通过哈希转换函数将元素的哈希地址转换成数组中存放的索引,如果有冲突,则使用散列链表的形式将所有相同哈希地址的元素串起来。

TreeMap

public class TreeMap<K,V> extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable

有序散列表,实现SortedMap接口,底层通过红黑树实现。

迭代器 Iterator

如List通过迭代器来遍历:

List<String> list = new ArrayList<String>();
// ...

Iterator<String> iter = list.iterator();
while(iter.hasNext())
{
    String item = iter.next();
    //...
}

原生数组

基本使用

DataType[] arrayRefVar;
arrayRefVar = new DataType[arraySize];

DataType[] arrayRefVar2 = {value0, value1, ..., valuek};

数组有length属性,代表数组长度,常用于for循环等场景

Arrays类

java.util.Arrays 类能方便地操作数组,它提供的所有方法都是静态的。

public static int binarySearch(Object[] a, Object key)
public static boolean equals(long[] a, long[] a2)
public static void fill(int[] a, int val)
public static void sort(Object[] a)

参考

Comments