java集合总结

2018-08-03  本文已影响7人  捉虫大师

本文原链接点我查看

前言

在PHP中，集合是很简单的，就一个Array，既可以做数组，又可以做map，对比JAVA常用的List，Map，Set来说只有Set是在PHP中需要封装的,本文就Java中常用的几个集合类来做一个总结。

常用的集合类介绍

List

List的特点是有序，元素可重复

ArrayList

ArrayList的实现其实是对一个数组的封装，实现了一个动态的数组，它的构造器有三种：

ArrayList arrayList = new ArrayList();
ArrayList arrayList1 = new ArrayList(5000);
ArrayList arrayList2 = new ArrayList(linkedList);

如果不指定初始大小，ArrayList默认大小是10，如果添加的元素超过10，则ArrayList会扩容。扩容的源代码如下：

/**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param minCapacity the desired minimum capacity
     */
    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);
    }

可以看出，扩容最少是目前容量的1.5倍，如果我们需要一个5000的ArrayList，初始化的时候不指定大小，使用默认容量10，那么一个一个地往里面添加元素，它将会扩容N次：

10 * 1.5 ^ N = 5000

算出来N至少为16才能完成任务，也就是执行了16次copy动作，这是非常耗时的，所以建议是在知道大小时多申请一些容量，这样就不会频繁的扩容。

从ArrayList的实现也能看出ArrayList适合查询，不适合频繁执行添加删除元素的操作。

Vector

Vector与ArrayList的实现方式基本一致，只是它很多方法用了synchronized来修饰，也就是线程安全的，一个时间只有一个线程可以修改，其他细节与ArrayList类似。

Stack

Stack是基于Vector实现的一个集合，它的特点是先入后出，与Vector一样也是线程安全的。

LinkedList

LinkedList的实现可以看做是一个链表，节点之间是通过指针来连接的，所以LinkedList与ArrayList互补，适合频繁地删除添加元素，而不适合查找。
LinkedList的初始化如下：

LinkedList linkedList = new LinkedList();
LinkedList linkedList1 = new LinkedList(arrayList);

只有两种初始化方式，不需要指定大小。

Map

Map的特点是存储键值对

HashMap

HashMap采用的是将“键”的HashCode对应的存储区域存储上键和值，本质上是一个数组，只不过可以通过“键”计算出应该存在数组的哪个位置，它的key，value可以为null，无序。
看一下它的几个构造方法：

public HashMap(int initialCapacity, float loadFactor);
public HashMap(int initialCapacity);
public HashMap();
public HashMap(Map<? extends K, ? extends V> m);

看出来HashMap是有大小的，也是有一个扩容的过程。网上看到一个概括put的过程直接引用过来：

  1. 对key的hashCode()做hash，然后再计算index;
  2. 如果没碰撞直接放到bucket里；
  3. 如果碰撞了，以链表的形式存在buckets后；
  4. 如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树；
  5. 如果节点已经存在就替换old value(保证key的唯一性)
  6. 如果bucket满了(超过load factor*current capacity)，就要resize。
HashTable

与HashMap类似，但是是线程安全的，键和值都不能是null，他们使用的hashCode也是不一样的，HashTable直接使用HashCode，而HahMap会在HashCode上再做一次Hash，且他们的扩容方式也不尽相同，HashTable中hash数组默认大小是11，增加的方式是old*2+1，HashMap中hash数组的默认大小是16，而且一定是2的指数

LinkedHashMap

LinkedHashMap与HashMap基本相同，只是在定义节点时增加了前后指针，这也就意味着遍历时能保证顺序，其他与HashMap无异。

TreeMap

TreeMap实际上是一个红黑树的实现，与HashMap使用HashCode实现不一样，它的查找效率没有HashMap那么高效，但是也达到了O(logn)，它的元素是有序的且不能为null。

Set

Set的特点是不能存储相同的元素

HashSet

HashSet的实现是对HashMap的封装，只不过是将需要add进set的元素当成是HashMap的key，这样实现了set的不重复。

LinkedHashSet

底层采用了LinkedHashMap来实现，也是在HashSet的基础上增加了有序，读LinkedHashSet源代码没有发现和LinkedHashMap有关？仔细看，所有的LikedHashSet都是调用了HashSet的这个构造方法来初始化的：

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

藏的够深，原来HaSet中有一个专门为LinkedHashMap提供的构造方法。

TreeSet

TreeSet是基于TreeMap实现的，也是一个红黑树，也是有序的且不依赖Hash实现的一种Set,同理也是将要加入到set中的元素当做键插入到TreeMap中去。

总结

上一篇下一篇

猜你喜欢

热点阅读