Java中常用的容器类笔记

Android 开发笔记 onGithub

文章内容

• 1.容器总体结构
• 2.Map
  • 2.1 HashMap
  • 2.2 Hashtable
  • 2.3 LinkedHashMap
  • 2.4 TreeMap
• 3.Collection
  • 3.1 List
    • ArrayList
    • LinkedList
    • Vector
  • 3.2 Set
    • HashSet
    • TreeSet
    • LinkedHashSet
  • 3.3 Queue与Deque
    • ArrayDeque
    • PriorityQueue
• 4.同步集合
  • 4.1 CopyOnWriteArrayList
  • 4.2 CopyOnWriteArrayset
  • 4.3 ArrayBlockkingQueue
  • 4.4 LinkedBlockingQueue
• 5.散列码产生规则

容器总体结构

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

public interface Map<K, V> {
	...
	
	Collection<V> values();	
	...
}

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

public abstract class AbstractCollection<E> implements Collection<E> {}

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {}

复制代码

2.Map

2.1 HashMap

2.1.1 HashMap的存储结构

2.1.2 两个重要的参数 Capacity 和 Load Factor

简单的说，Capacity就是buckets的数目，容量都是2的幂。Load factor就是buckets填满程度的最大比例。如果对迭代性能要求很高的话不要把capacity设置过大，也不要把load factor设置过小。当bucket填充的数目（即hashmap中元素的个数）大于capacity*load factor时就需要调整buckets的数目为当前的2倍。

2.1.3 put方法的实现

put函数大致的思路为：

• 对key的hashCode()做hash(调用了hash方法)，然后再计算index;
• 如果没碰撞直接放到bucket里；
• 如果碰撞了，以链表的形式存在buckets后；
• 如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树(Java 8中做的优化,但是在Android API25 中还没有看到这样的优化)；
• 如果节点已经存在就替换old value(保证key的唯一性)
• 如果bucket满了(超过load factor*current capacity)，就要resize。

2.1.4 get方法的实现

在理解了put之后，get就很简单了。大致思路如下：

• bucket里的第一个节点，直接命中；
• 如果有冲突，则通过key.equals(k)去查找对应的entry
  • 若为树，则在树中通过key.equals(k)查找，O(logn)；
  • 若为链表，则在链表中通过key.equals(k)查找，O(n)。

2.1.5 hash方法的实现

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

复制代码

2.1.6 resize

当put时，如果发现目前的bucket占用程度已经超过了Load Factor所希望的比例，那么就会发生resize。在resize的过程，简单的说就是把bucket扩充为2倍，之后重新计算index，把节点再放到新的bucket中。

2.1.7 红黑树和链表的实现

我们在树中确实存储了比链表更多的数据。

根据继承原则，内部表中可以包含Node（链表）或者TreeNode（红黑树）。Oracle决定根据下面的规则来使用这两种数据结构：

• 对于内部表中的指定索引（桶），如果node的数目多于8个（TREEIFY_THRESHOLD = 8），那么链表就会被转换成红黑树。

• 对于内部表中的指定索引（桶），如果node的数目小于6个（UNTREEIFY_THRESHOLD = 6），那么红黑树就会被转换成链表。

参考:

• Java HashMap工作原理及实现(主要参考这一篇，写的很清晰)
• 深入分析hashmap
• Java HashMap工作原理

2.2 Hashtable

Hashtable和HashMap区别

• 第一，继承不同。 public class Hashtable extends Dictionary implements Map

  public class HashMap extends AbstractMap implements Map  

• 第二，Hashtable中的方法是同步的(通过synchronized实现)，而HashMap中的方法在缺省情况下是非同步的。在多线程并发的环境下，可以直接使用Hashtable，但是要使用HashMap的话就要自己增加同步处理了。

• 第三，Hashtable中，key和value都不允许出现null值。在HashMap中，null可以作为键，这样的键只有一个；可以有一个或多个键所对应的值为null。

  当get()方法返回null值时，既可以表示HashMap中没有该键，也可以表示该键所对应的值为null。因此，**在HashMap中不能由get()方法来判断HashMap中是否存在某个键，**而应该用containsKey()方法来判断。

• 第四，两个遍历方式的内部实现上不同。Hashtable，HashMap都使用了Iterator。而由于历史原因，Hashtable还使用了Enumeration的方式。并且HashMap的迭代器是fail-fast机制，Hashtable的Enumeration迭代器不是fail-fast的

• 第五，哈希值的使用不同，Hashtable直接使用对象的hashCode。而HashMap重新计算hash值。

• 第六，Hashtable和HashMap它们两个内部实现方式的数组的初始大小和扩容的方式。Hashtable中hash数组默认大小是11，增加的方式是 old*2+1。HashMap中hash数组的默认大小是16，而且一定是2的指数。

参考

• Hashtable 的实现原理
• HashMap和Hashtable的区别

2.3 LinkedHashMap

Entry增加了两个变量，after和befor用来维护双向链表

LruCache使用LinkedHashMap作为缓存

对节点进行访问后会调用afterNodeAccess方法，更新列表，将最近访问的元素放在最后，afterNodeAccess 会调用afterNodeInsertion方法，在afterNodeInsertion方法中会调用removeNode方法，而在LruCache中对重写removeNode方法，当size超过LruCache的容量的时候就会删除。(不同的JDK和Android API中实现的方式有所不同)

参考

• Java LinkedHashMap工作原理及实现
• LinkedHashMap 与 LRUcache
• 图解集合6：LinkedHashMap

2.4 TreeMap

之前已经学习过HashMap和LinkedHashMap了，HashMap不保证数据有序，LinkedHashMap保证数据可以保持插入顺序，而如果我们希望Map可以保持key的大小顺序的时候，我们就需要利用TreeMap了。

另外需要参考红黑树的笔记

参考文章

• Java TreeMap工作原理及实现
• 通过分析 JDK 源代码研究 TreeMap 红黑树算法实现

2.5 WeakHashMap

WeakHashMap是一种改进的HashMap，它对key实行“弱引用”.

private static class Entry<K, V> extends WeakReference<Object> implements java.util.Map.Entry<K, V>
复制代码

• Java 中的 WeakHashMap
• Java中的四大引用

3.Collection

不要将Collection误认为Collections

• 1.java.util.Collection 是一个集合接口。它提供了对集合对象进行基本操作的通用接口方法。Collection接口在Java 类库中有很多具体的实现。Collection接口的意义是为各种具体的集合提供了最大化的统一操作方式。
• 2.java.util.Collections 是一个包装类。它包含有各种有关集合操作的静态多态方法。此类不能实例化，就像一个工具类，服务于Java的Collection框架。

3.1 List

3.1.1 ArrayList

（是否有序，有序的意思是读取数据的顺序和存放数据的顺序是否一致）

ArrayList比较适合顺序添加.随机访问的场景。

增加元素进行扩容

内部维护了一个int类型的size和Object[]数组，默认大小是10，如果add之后大小不够的话会调用ensureCapacityInternal方法进行动态扩容，扩容后的大小是原大小的1.5倍，并调用Arrays.copyOf进行一次数组的复制。(查阅源码发现默认情况下ArrayList的最大长度是Integer.MAX_VALUE - 8，当超过这个数值时会扩展到Integer.MAX_VALUE，如果超过这个限制会抛OOM)

删除元素

不论按下标删除还是按元素删除，总的来说做了两件事

• 1.把指定元素后面位置的所有元素，利用System.arraycopy方法整体向前移动一个位置

• 2.最后一个位置的元素指定为null，这样让gc可以去回收它

优点

• 1.ArrayList底层以数组实现，是一种随机访问模式，再加上它实现了RandomAccess接口，因此查找也就是get的时候非常快

• 2.ArrayList在顺序添加一个元素的时候非常方便，只是往数组里面添加了一个元素而已

缺点

• 1.删除元素的时候，涉及到一次元素复制，如果要复制的元素很多，那么就会比较耗费性能

• 2.插入元素的时候，涉及到一次元素复制，如果要复制的元素很多，那么就会比较耗费性能

• 图解集合1：ArrayList

• Java ArrayList工作原理及实现

3.1.2 LinkedList

使用双向链表实现，set和get方法时间复杂度是O(n/2),同时实现了Deque接口，可以将LinkedList作为双端队列使用

private static class Entry<E> {
    E element;
    Entry<E> next;
    Entry<E> previous;
    ...
}
复制代码

set和get的时间复杂度为什么是O(n/2)?

public E get(int index) {
    return entry(index).element;
}

private Entry<E> entry(int index) {
     if (index < 0 || index >= size)
         throw new IndexOutOfBoundsException("Index: "+index+
                                             ", Size: "+size);
     Entry<E> e = header;
     if (index < (size >> 1)) {
         for (int i = 0; i <= index; i++)
             e = e.next;
     } else {
         for (int i = size; i > index; i--)
             e = e.previous;
     }
     return e;
}
复制代码

与ArrayList的对比

• 1、顺序插入速度ArrayList会比较快

• 2、因为LinkedList里面不仅维护了待插入的元素，还维护了Entry的前置Entry和后继Entry，如果一个LinkedList中的Entry非常多，那么LinkedList将比ArrayList更耗费一些内存

• 3、使用各自遍历效率最高的方式，ArrayList的遍历效率会比LinkedList的遍历效率高一些。因为使用普通for比for each快一些。

• 4、有些说法认为LinkedList做插入和删除更快，这种说法其实是不准确的：

  -（1）LinkedList做插入、删除的时候，慢在寻址，快在只需要改变前后Entry的引用地址 -（2）ArrayList做插入、删除的时候，慢在数组元素的批量copy，快在寻址

• 图解集合2：LinkedList

• Java LinkedList工作原理及实现

• LinkedList的实现原理浅析

3.1.3 Vector

类似ArrayList，内部实现的原理形同，也是通过Object[]数组实现的。但是是线程安全的,但是为了同步，尽量少使用vector，因为vector的方法都是通过synchronized实现的，代价很大

• Vector 是线程安全的吗？

3.2 Set

不包含重复元素的Collection，最多有一个null元素

3.2.1 HashSet

HashSet是基于HashMap来实现的，操作很简单，更像是对HashMap做了一次“封装”，而且只使用了HashMap的key来实现各种特性。内部有多个不同的构造方法，对应初始化HashMap的操作也不同。

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    static final long serialVersionUID = -5024744406713321676L;

    private transient HashMap<E,Object> map;
    
    public HashSet() {
        map = new HashMap<>();
    }
    
    public HashSet(Collection<? extends E> c) {
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }
    
    public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor);
    }
    

    public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity);
    }
}    
复制代码

实际上HashSet存储的对象是HashMap的key，只不过HashMap的value是一个Object对象。

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}
public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}
public boolean contains(Object o) {
    return map.containsKey(o);
}
public int size() {
    return map.size();
}
复制代码

如果想获得线程安全的HashSet可以使用如下方法：

Collections.synchronizedSet(new HashSet<String>());

• Java HashSet工作原理及实现

3.2.2 TreeSet

TreeSet是基于TreeMap实现的，也非常简单，同样的只是用key及其操作，然后把value置为dummy的object。

利用TreeMap的特性，实现了set的有序性(通过红黑树实现，这里的有序性指的是排序后的顺序，对于某些类型的元素，需要传递自定义的Comparable)。

TreeSet添加null时，如果再添加不是null的元素，就会报NullPointerException异常

• Java TreeSet工作原理及实现

3.2.3 LinkedHashSet

继承自HashSet，内部使用LinkedHashMap维持双向的链表。

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

复制代码

• Java LinkedHashSet工作原理及实现

3.3 Queue与Deque

3.3.1 ArrayDeque

基于数组实现，实现了一个逻辑上的循环数组。

ArrayDeque的高效来源于head和tail这两个变量，它们使得物理上简单的从头到尾的数组变为了一个逻辑上循环的数组，避免了在头尾操作时的移动。我们来解释下循环数组的概念。

对于一般数组，比如arr，第一个元素为arr[0]，最后一个为arr[arr.length-1]。但对于ArrayDeque中的数组，它是一个逻辑上的循环数组，所谓循环是指元素到数组尾之后可以接着从数组头开始，数组的长度.第一个和最后一个元素都与head和tail这两个变量有关，具体来说：

• 如果head和tail相同，则数组为空，长度为0。
• 如果tail大于head，则第一个元素为elements[head]，最后一个为elements[tail-1]，长度为tail-head，元素索引从head到tail-1。
• 如果tail小于head，且为0，则第一个元素为elements[head]，最后一个为elements[elements.length-1]，元素索引从head到elements.length-1。
• 如果tail小于head，且大于0，则会形成循环，第一个元素为elements[head]，最后一个是elements[tail-1]，元素索引从head到elements.length-1，然后再从0到tail-1。

参考：

• Java编程的逻辑 (48) - 剖析ArrayDeque
• Java ArrayDeque源码剖析

3.3.2 PriorityQueue

• Java编程的逻辑 (46) - 剖析PriorityQueue

4.同步集合

4.1 CopyOnWriteArrayList

参考笔记:线程关键字、锁、同步集合.md

4.2 CopyOnWriteArrayset

参考笔记:线程关键字、锁、同步集合.md

4.3 ArrayBlockkingQueue

参考笔记:线程关键字、锁、同步集合.md

4.4 LinkedBlockingQueue

参考笔记:线程关键字、锁、同步集合.md

5.散列码产生规则