Java集合(10)——Stack和Queue

写在开始

队列和栈,在数据请求等场景应用比较广的数据结构,本章将介绍Java是如何实现Stack和Queue的。

Java集合的结构图

Stack(LIFO)

定义:

public
class Stack<E> extends Vector<E>

Stack继承至Vector,即Stack间接实现了List的相关内容(协议),介绍Vector的时候提到,Vector相当于是ArrayList的线程安全实现,所以我们可以推断出Stack有以下基本性质:

  • 基本容量为10,每次扩容都是翻倍
  • 基本存储形式为数组
  • 线程安全

栈的基本操作

入栈
public E push(E item) {
    addElement(item);

    return item;
}

最后调用的是Vector实现方法addElement。

出栈
public synchronized E pop() {
    E       obj;
    int     len = size();

    obj = peek();
    removeElementAt(len - 1);

    return obj;
}

先调用查询函数获得元素用于返回,然后从栈里移除。

查询
public synchronized E peek() {
    int     len = size();

    if (len == 0)
        throw new EmptyStackException();
    return elementAt(len - 1);
}

如果栈为空,直接会抛出异常。

Queue

定义:

public interface Queue<E> extends Collection<E>

声明:

Queue接口通常期望它的实现者遵循队列的顺序(FIFO),但是实现者实际上也可以通过该接口实现栈(LIFO)这种“队列”。


定义可以看出,Queue直接扩展Collection接口。我们主要关注其约定的队列需要实现的基本协议:

入队
//添加成功返回true,如果队列中没有位置可用,直接抛出IllegalStateException异常
boolean add(E e);
//添加成功返回true,当使用限制(长度)队列的时候,这个函数比add更为推荐;不会抛出上述异常
boolean offer(E e);
出队
//返回并移除队列的第一个(头)元素;如果队列为空,抛出NoSuchElementException异常
E remove();
//返回并移除队列的第一个(头)元素;不会抛出异常
E poll();
查询
//返回队列的第一个(头)元素;如果队列为空,抛出NoSuchElementException异常
E element();
//返回第一个(头)元素;不会抛出异常
E peek();
小结
  • 定义的方法都含有抛出指定异常和不抛出的两种命名实现,为什么要提供两种呢?

参考链接在实现队列的过程中,当明确队列不会为空的时候,不应该再去捕获异常,做一些没有用的异常处理工作,这些工作也会让代码显得很臃肿

PriorityQueue

定义:

public class PriorityQueue<E> extends AbstractQueue<E>

源码对该类的说明:

An unbounded priority {@linkplain Queue queue} based on a priority heap.
The elements of the priority queue are ordered according to their
{@linkplain Comparable natural ordering}, or by a {@link Comparator}
provided at queue construction time, depending on which constructor is
used.  A priority queue does not permit {@code null} elements.
A priority queue relying on natural ordering also does not permit
insertion of non-comparable objects (doing so may result in
{@code ClassCastException}).

大抵意思如下:

这是一个不限制存储数量的优先队列,其优先级依靠传入的Comparator或者存储的数据(实现Comparable接口)所决定,所以:PriorityQueue不允许存放null或者没有实现Comparable接口的对象(在没有传入Comparator的情况下)。

实现优先队列的方式

优先队列,顾名思义,一种一直维护某种顺序的队列。

如果要有序,那么只有两种情况

  1. 无序的插入——在获取(优先)元素的时候按照规则(后)排序一次
  2. 插入元素的时候就有序——在有序队列中找需要插入元素的位置

第一种方式的(获取)时间复杂度根据每次的排序算法而定,但是它的查询(指定元素)的时间复杂度为O(N);

第二种方式在创建数据初期就维护其顺序

  • 维护插入有序的数组——插入的最糟糕每次都是O(N)的时间复杂度,对于根据一个有序队列创建优先队列效率显然底了很多。
  • 二叉查找树——优先队列,那么获取的永远是最大(小)元素,这就会造成二叉查找树总会有一边子树深度无限加深;如果是AVL,上述问题都可以解决,但是实际上我们并不需要每个元素都是严格有序,同时AVL树为了维护期平衡会进行额外的旋转工作,从而带来不必要的开销。
  • 二叉堆——具有平衡的性质,能够获取最大(小)元素,但是并不是严格有序。

从上面看来,二叉堆避免了数组和二叉查找树(在实现优先队列方面)的不足,是实现优先队列的较佳方案。

基本存储

PriorityQueue采用堆实现优先队列,所以其基本存储形式和堆一致,都为数组

/**
 * Priority queue represented as a balanced binary heap: the two
 * children of queue[n] are queue[2*n+1] and queue[2*(n+1)].  The
 * priority queue is ordered by comparator, or by the elements'
 * natural ordering, if comparator is null: For each node n in the
 * heap and each descendant d of n, n <= d.  The element with the
 * lowest value is in queue[0], assuming the queue is nonempty.
 */
transient Object[] queue;

和堆不一样的是,位于n的节点,其左儿子位于2*n+1,右儿子位于2*(n+1)

默认数组大小为11

private static final int DEFAULT_INITIAL_CAPACITY = 11;
动态扩容

数组存储(不定)集合数据,那么必定涉及动态扩容。

按照套路,查看在插入数据的时候调用的扩容函数:

private void grow(int minCapacity) {
    int oldCapacity = queue.length;
    // Double size if small; else grow by 50%
    int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                     (oldCapacity + 2) :
                                     (oldCapacity >> 1));
    // overflow-conscious code
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    queue = Arrays.copyOf(queue, newCapacity);
}

从上面代码可以分析出,扩容策略:

  1. 如果数组容量小于64,那么就翻倍;
  2. 如果数组容量大于64,那么就只扩容原容量的50%;

基本操作

堆基本操作(上滤和下滤)的实现

关于堆上滤和下滤的讲解可以看这里:http://www.areahash.com/?p=318

堆上滤

private void siftUp(int k, E x) {
    if (comparator != null)
        siftUpUsingComparator(k, x);
    else
        siftUpComparable(k, x);
}

@SuppressWarnings("unchecked")
private void siftUpComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>) x;
    while (k > 0) {
        //获取当前节点的父节点
        int parent = (k - 1) >>> 1;
        Object e = queue[parent];
        //比对
        if (key.compareTo((E) e) >= 0)
            break;
        //交换空位和父节点
        queue[k] = e;
        k = parent;
    }
    //找到位置,赋值
    queue[k] = key;
}

@SuppressWarnings("unchecked")
private void siftUpUsingComparator(int k, E x) {
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = queue[parent];
        if (comparator.compare(x, (E) e) >= 0)
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = x;
}

堆下滤

private void siftDown(int k, E x) {
    if (comparator != null)
        siftDownUsingComparator(k, x);
    else
        siftDownComparable(k, x);
}

@SuppressWarnings("unchecked")
private void siftDownComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>)x;
    int half = size >>> 1;        // loop while a non-leaf
    //不会对最后一层进行下滤
    while (k < half) {
        //获取左节点的索引
        int child = (k << 1) + 1; // assume left child is least
        //获得左节点的对象
        Object c = queue[child];
        //获得右节点的索引
        int right = child + 1;
        //如果左节点不是最后一个节点,且左节点比右节点大
        if (right < size &&
            ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
            //获得右节点对象
            c = queue[child = right];
        //以上过程获取到了左右节点较小的一个
        //比对
        if (key.compareTo((E) c) <= 0)
            break;
        //交换空位和较小节点
        queue[k] = c;
        k = child;
    }
    //找到位置
    queue[k] = key;
}

@SuppressWarnings("unchecked")
private void siftDownUsingComparator(int k, E x) {
    int half = size >>> 1;
    while (k < half) {
        int child = (k << 1) + 1;
        Object c = queue[child];
        int right = child + 1;
        if (right < size &&
            comparator.compare((E) c, (E) queue[right]) > 0)
            c = queue[child = right];
        if (comparator.compare(x, (E) c) <= 0)
            break;
        queue[k] = c;
        k = child;
    }
    queue[k] = x;
}

从集合构建优先队列(堆)

private void heapify() {
    for (int i = (size >>> 1) - 1; i >= 0; i--)
        siftDown(i, (E) queue[i]);
}
优先队列的基本操作

插入

public boolean add(E e) {
    return offer(e);
}

public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length)
        grow(i + 1);
    size = i + 1;
    if (i == 0)
        queue[0] = e;
    else
        siftUp(i, e);
    return true;
}
  • 添加元素的add方法最后调用的也是offer方法;
  • offer方法会对插入元素做校验而后对队列的size做操作,最后执行上滤操作。

获取最小元(删除)

public boolean remove(Object o) {
    int i = indexOf(o);
    if (i == -1)
        return false;
    else {
        removeAt(i);
        return true;
    }
}

首先遍历获得当前对象的index,然后调用removeAt方法执行删除。

//移除最小元
public E poll() {
    if (size == 0)
        return null;
    int s = --size;
    modCount++;
    E result = (E) queue[0];
    E x = (E) queue[s];
    //移除顶部元素,执行下滤
    queue[s] = null;
    if (s != 0)
        siftDown(0, x);
    return result;
}

//根据索引移除队列中的元素
@SuppressWarnings("unchecked")
private E removeAt(int i) {
    // assert i >= 0 && i < size;
    modCount++;
    int s = --size;
    if (s == i) // removed last element
        queue[i] = null;
    else {
        E moved = (E) queue[s];
        queue[s] = null;
        //当前位置执行下滤
        siftDown(i, moved);
        //如果需要移动元素的位置就是移除的位置
        if (queue[i] == moved) {
            //执行上滤,保证堆序
            siftUp(i, moved);
            if (queue[i] != moved)
                return moved;
        }
    }
    return null;
}

从代码可以看出,都是执行的对堆的操作。

查找

public E peek() {
    return (size == 0) ? null : (E) queue[0];
}

private int indexOf(Object o) {
    if (o != null) {
        for (int i = 0; i < size; i++)
            if (o.equals(queue[i]))
                return i;
    }
    return -1;
}

peek返回根节点——最小元。

小结

  • PriorityQueue内部实现为二叉堆
  • 插入、删除最坏时间复杂度为O(logN)

Deque(After JDK1.6)

JDK的介绍:

A linear collection that supports element insertion and removal at
both ends.  The name <i>deque</i> is short for "double ended queue"
and is usually pronounced "deck"

Deque实际上是”double ended queue”的简写,从名字可以看出,其实现的是一个支持在两(头、尾)端插入或移除的线性集合

定义:

public interface Deque<E> extends Queue<E>

继承自Queue,并对操作方法进行了扩充。

因为Queue只支持一端操作,所以Deque对其中的操作方法进行了细分:

Comparison of Queue and Deque methods
Queue Method Equivalent  Deque  Method
{@link java.util.Queue#add add(e)} {@link #addLast addLast(e)}
{@link java.util.Queue#offer offer(e)} {@link #offerLast offerLast(e)}
{@link java.util.Queue#remove remove()} {@link #removeFirst removeFirst()}
{@link java.util.Queue#poll poll()} {@link #pollFirst pollFirst()}
{@link java.util.Queue#element element()} {@link #getFirst getFirst()}
{@link java.util.Queue#peek peek()} {@link #peek peekFirst()}

注:在介绍List下的实现类的时候,LinkedList也实现了该接口;

ArrayDeque

JDK对类的介绍:

Resizable-array implementation of the {@link Deque} interface.  Array
deques have no capacity restrictions; they grow as necessary to support
usage.  They are not thread-safe; in the absence of external
synchronization, they do not support concurrent access by multiple threads.
Null elements are prohibited.  This class is likely to be faster than
{@link Stack} when used as a stack, and faster than {@link LinkedList}
when used as a queue
  • 该类是一个基于数组实现的动态扩容Deque
  • 不支持线程安全;
  • 当作为栈使用的时候,速度会比Stack快;
  • 当作为队列使用的时候,速度会比LinkedList快。
  • 不支持Null的元素

定义:

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>

基本数据结构

/**
 * The array in which the elements of the deque are stored.
 * The capacity of the deque is the length of this array, which is
 * always a power of two. The array is never allowed to become
 * full, except transiently within an addX method where it is
 * resized (see doubleCapacity) immediately upon becoming full,
 * thus avoiding head and tail wrapping around to equal each
 * other.  We also guarantee that all array cells not holding
 * deque elements are always null.
 */
transient Object[] elements;

通过类的名字ArrayDeque以及上面的代码可以看到,内部实现的数据结果是数组,并且具有如下性质:

  • 默认初始化大小为16
  • 数组的大小维护在2的幂这个维度
  • 最小初始化数组的大小为8
  • 数组永远不为填满,即将满的时候就会调用doubleCapacity进行扩容。

数组维护为2的幂,根据之前介绍HashMap的时候可以知道:

可以快速获取元素在数组中的索引(基于位的与运算)。

这一点将在下面介绍基本操作的时候有体现。

基本操作

因为和ArrayList或者Vector一样,内部都是采用数组作为基本数据结构,所以这里就简单分析添加的一个例子:

——添加一个头部元素

public void addFirst(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e;
    if (head == tail)
        doubleCapacity();
}

Step 1:

校验是否为NULL

Step 2:

计算“逻辑头”的位置: (head – 1) & (elements.length – 1)

case 1(第一次插入头部元素): head = 0;

那么计算之后逻辑头的位置为(elements.length – 1)

case 2(第二次插入头部元素): head = elements.length – 1;

计算之后逻辑头的位置为(elements.length – 2)

Step 3:

head和tail相遇,调用doubleCapacity扩容。

  1. 通过每次将头部插入数组的尾部,避免了每次在数组头部插入元素移动后面所有元素的开销;
  2. 将头部插入尾部,那么在真正想尾部添加元素的时候就需要跳过头部,代码如下:
public void addLast(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[tail] = e;
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)
        doubleCapacity();
}

如果tail(尾部) + 1即将和head相遇——扩容条件,那么就扩容,这样就不会影响到头部元素的存储。同时,也表明,数组不会装满,一直在动态扩容。

注:默认使用add添加元素的话,就是一直向后添加的。

public boolean add(E e) {
    addLast(e);
    return true;
}

动态扩容

上面介绍基本操作的时候提到扩容条件如下:

  1. 从头部添加元素的情况下,当head和tail相遇
  2. 从尾部添加元素的情况下,当head和tail即将相遇

因为容量大小始终维护为2的幂,所以扩容比较简单,直接翻倍。

扩容函数:

private void doubleCapacity() {
    assert head == tail;
    int p = head;
    int n = elements.length;
    int r = n - p; // number of elements to the right of p
    int newCapacity = n << 1;
    if (newCapacity < 0)
        throw new IllegalStateException("Sorry, deque too big");
    Object[] a = new Object[newCapacity];
    System.arraycopy(elements, p, a, 0, r);
    System.arraycopy(elements, 0, a, r, p);
    elements = a;
    head = 0;
    tail = n;
}

主要操作:扩容、重新赋值head和tail

为什么会比Stack和LinkedList快?

——个人理解

比Stack快的原因:

Stack是线程安全的,在不需要线程安全的环境会增加维护锁的开销;

比LinkedList快的原因:

LinkedList是基于链表实现的,所以除了移除元素的时候开销比ArrayDeque小,其他都会麻烦一些。

BlockingQueue

Java集合(9)——List

写在开始

List作为通用集合,在代码中出现的频率也比较高,本章我们会介绍ArrayList、LinkedList、Vector。

Java集合的结构图

List

定义:

public interface List<E> extends Collection<E>

List扩展了Collection接口,加入了实现列表集合的一些必要条件。

作为列表,需要具有任意访问表中某个位置的元素的能力,所以新增了如下方法:

E get(int index); 获取元素
E set(int index, E element) 设置某个位置的元素
void add(int index, E element) 在某个位置添加元素
E remove(int index) 移除某个位置的元素
int indexOf(Object o) 返回某个元素的索引(允许重复,所以返回第一次遇到的位置)
int lastIndexOf(Object o) 返回某个元素最后遇到的位置

当然还有我们熟悉的遍历方法:

ListIterator<E> listIterator() 从 Map 中删除所有映射
ListIterator<E> listIterator(int index) 从 Map 中删除键和关联的值

最后,返回子列表的方法:

List<E> subList(int fromIndex, int toIndex)

从上面方法我们可以看出:

  • 列表的索引顺序依靠int型的index维护;
  • 列表允许存放重复元素。

AbstractList

定义:

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

作为List的抽象类,其中没有定义比较特别的扩充方法。

ArrayList

定义:

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess

数组类型的列表。从定义可以看出,ArrayList实现了RandomAccess接口,那么就表明,该集合支持快速的随机访问。

注:RandomAccess接口本身没有定义任何方法,只是作为一个支持随机访问的标识存在,像Serializable一样。

基本存储

从定义以及名字我们可以得知,其基本存储的形式是数组

transient Object[] elementData;

那么数组的默认大小(集合容量)是多少呢?

private static final int DEFAULT_CAPACITY = 10;

前面我们学习Map的时候知道,使用数组实现存储的集合,大多都会涉及数组大小的动态扩容。那么在ArrayList中,扩容是怎样操作的呢?

动态扩容

按照套路,在添加的时间检查数组是否够用,不够用就扩容:

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

扩容函数:

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    //如果当前数组长度比最小容量小,那么就需要扩容
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

/**
 * The maximum size of array to allocate.
 * Some VMs reserve some header words in an array.
 * Attempts to allocate larger arrays may result in
 * OutOfMemoryError: Requested array size exceeds VM limit
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;//最大容量

/**
 * 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;
    //每次扩容原大小的50%
    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);
}

通过上面源码可以看出,和Map不一样,ArrayList扩容是等到装满了才扩容,所以也就不存在负载因子一类的概念。

而且每次扩容的大小是原容量的50%

基本操作

添加

支持两种添加方法,是否指定索引

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

public void add(int index, E element) {
    //指定索引的话会先进行范围检查,不满足直接抛出异常
    rangeCheckForAdd(index);
    //调用只是为了增加保证数据一致的modCount
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

删除

public E remove(int index) {
    //范围检查
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);
    //拷贝数据——更改新数据的索引
    //如果数据量大,这里就很耗时
    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

    return oldValue;
}
//根据传入的对象移除元素,最后调用跳过范围检查的fastRemove
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;
}
/*
 * Private remove method that skips bounds checking and does not
 * return the value removed.
 */
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
}

查询

E elementData(int index) {
    return (E) elementData[index];
}

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;
}

至此ArrayList的基本知识介绍完毕,没有什么值得特别注意的。

不过在这里想提一下之前集合中一直没有讲的一个变量modCount。

数据同步的维护

数据同步这里是我自己取的名字,主要是想有别于线程同步,理解为数据源同步。

modCount全名应该叫Modify Count,操作次数的累加。

操作数据成功一次,该变量累加一次。

这样的好处是什么呢?

防止在使用迭代器遍历的同时去改变数据源,导致一些不可描述的错误。

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

在迭代开始,modCount会被记录下来,每次调用next都会检查。

其实在迭代的时候也达到了线程同步的效果(不允许异步线程操作该集合)。

LinkedList

定义:

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>

LinkedList继承AbstractSequentialList并实现了Deque接口。也就是说这是一个双端且有序(添加顺序)的列表。

注:Deque接口定义了一种支持双端操作(两端均可添加和移除)的线性集合。

基本存储

在LinkedList内部定义了一个这样的Node:

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

其中包含了指向前后的对象引用next和prev,也就是说,内部存储的基本结构是双向链表。

数据存储定义的代码:

transient Node<E> first;

transient Node<E> last;
基本操作

添加

public boolean add(E e) {
    linkLast(e);
    return true;
}

指定索引的添加:

public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

对双向链表的操作代码:

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

/**
 * Inserts element e before non-null Node succ.
 */
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

注:添加是默认向后添加。

删除

移除是默认先移除第一个元素。

public E remove() {
    return removeFirst();
}

移除指定位置的元素

public E remove(int index) {
    checkElementIndex(index);//范围检查,是否超过存储的数据大小
    return unlink(node(index));
}

移除指定的元素

public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

对链表的操作代码:

/**
 * Unlinks non-null first node f.
 */
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

/**
 * Unlinks non-null last node l.
 */
private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    final E element = l.item;
    final Node<E> prev = l.prev;
    l.item = null;
    l.prev = null; // help GC
    last = prev;
    if (prev == null)
        first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
}

/**
 * Unlinks non-null node x.
 */
E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

查询

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

获取链表头尾的代码:

public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}

遍历链表,获取指定位置元素:

Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

更新

public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

和ArrayLsit相比,LinkedList插入或者删除的时间成本低一些,但是查询和更新高一些。

频繁的插入删除数据可以使用LinkedList换取较好的时间。

Vector

定义

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess

Vector的基本存储形式和ArrayList一致,都是通过数组实现存储,大多基本实现都相同(基本容量也是10),这里介绍它们的两个不同点:

1、Vector使用synchronized关键字实现了线程安全

2、Vector每次扩容不是扩容50%,而是依靠变量 int capacityIncrement,扩容函数如下:

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

可以看到,如果capacityIncrement 没有初始化或者初始化大小为0,那么每次扩容默认翻倍;否则就只扩容定义的大小。

总结

  • ArrayList和Vector都是使用数组存储、LinkedList使用双向链表存储。
  • Vector线程安全,ArrayList和LinkedList线程不安全
  • Vector和ArrayList都支持随机访问,LinkedList不支持
  • LinkedList插入和删除的速度比ArrayList和Vector快
  • ArrayList和Vector的查询和更新速度比LinkedList快
  • ArrayList和Vector的默认大小都是10
  • ArrayList每次扩容50%,Vector扩容大小默认为翻倍(capacityIncrement 没有初始化的情况)

Java集合(8)——Map之TreeMap、EnumMap

写在开始

作为Map家族中没有用哈希映射实现键值对存储的集合类,其内部实现有些什么不同呢?

Java集合的结构图

TreeMap

定义:

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>

和TreeSet一样,TreeMap继承至NavigableMap。其上溯的父类有:

也就是说,TreeMap实现了一种有序的(SortedMap)键值对存储集合,并且对外提供快速获取符合条件的键值对(NavigableMap)

下面介绍其存储的最小单元——红黑树;


基本数据存储形式

关于红黑树

采用红黑树存储,所以它有如下基本特性:

  • 增加、删除、查询的最大时间复杂度都为logN。
  • 没有动态扩容的开销;但是(为了保持树的平衡)多了翻转红黑树的开销。

如何实现有序

默认的TreeMap是以(对象的)自然顺序排列,也可以通过Comparator指定排序的方式。

final int compare(Object k1, Object k2) {
    return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
        : comparator.compare((K)k1, (K)k2);
}

上述代码是源码中比较常用的一个排序方法。

可以看出排序要求传入的key实现了Comparable,或者实例化的时候传入自定义的Comparator用于比较对象。

即,顺序本质上依赖于作为key的对象的定义。

基本操作

——添加

  • 如果集合为空,初始化;
  • 检测是否存在相同的key,如果存在,替换原值
  • 生成新的键值对,然后重新着色并维护红黑树基本性质。
public V put(K key, V value) {
    Entry<K,V> t = root;
    if (t == null) {
        compare(key, key); // type (and possibly null) check

        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }
    int cmp;
    Entry<K,V> parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    else {
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}

——删除

先获取需要删除的节点,然后删除

public V remove(Object key) {
    Entry<K,V> p = getEntry(key);
    if (p == null)
        return null;

    V oldValue = p.value;
    deleteEntry(p);
    return oldValue;
}

移除节点,并翻转,维持红黑树基本性质。

private void deleteEntry(Entry<K,V> p) {
    modCount++;
    size--;

    // If strictly internal, copy successor's element to p and then make p
    // point to successor.
    if (p.left != null && p.right != null) {
        Entry<K,V> s = successor(p);
        p.key = s.key;
        p.value = s.value;
        p = s;
    } // p has 2 children

    // Start fixup at replacement node, if it exists.
    Entry<K,V> replacement = (p.left != null ? p.left : p.right);

    if (replacement != null) {
        // Link replacement to parent
        replacement.parent = p.parent;
        if (p.parent == null)
            root = replacement;
        else if (p == p.parent.left)
            p.parent.left  = replacement;
        else
            p.parent.right = replacement;

        // Null out links so they are OK to use by fixAfterDeletion.
        p.left = p.right = p.parent = null;

        // Fix replacement
        if (p.color == BLACK)
            fixAfterDeletion(replacement);
    } else if (p.parent == null) { // return if we are the only node.
        root = null;
    } else { //  No children. Use self as phantom replacement and unlink.
        if (p.color == BLACK)
            fixAfterDeletion(p);

        if (p.parent != null) {
            if (p == p.parent.left)
                p.parent.left = null;
            else if (p == p.parent.right)
                p.parent.right = null;
            p.parent = null;
        }
    }
}

——查询

直接调用getEntry获取到相关的entry,如果存在就返回值,否则,返回空。

public V get(Object key) {
    Entry<K,V> p = getEntry(key);
    return (p==null ? null : p.value);
}

遍历获取entry

final Entry<K,V> getEntry(Object key) {
    // Offload comparator-based version for sake of performance
    if (comparator != null)
        return getEntryUsingComparator(key);
    if (key == null)
        throw new NullPointerException();
    @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = k.compareTo(p.key);
        if (cmp < 0)
            p = p.left;
        else if (cmp > 0)
            p = p.right;
        else
            return p;
    }
    return null;
}

——获得最近元素的方法(NavigableMap接口定义)

获取大于等于当前key的最近entry(其他函数基本类似,就不贴出来了)

final Entry<K,V> getCeilingEntry(K key) {
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = compare(key, p.key);
        if (cmp < 0) {
            if (p.left != null)
                p = p.left;
            else
                return p;
        } else if (cmp > 0) {
            if (p.right != null) {
                p = p.right;
            } else {
                Entry<K,V> parent = p.parent;
                Entry<K,V> ch = p;
                while (parent != null && ch == parent.right) {
                    ch = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        } else
            return p;
    }
    return null;
}

Tip:分析源码的基本操作可以发现:基本操作使用到的都是中序遍历

小结

TreeMap提供了一个key有序的集合;

内部实现为红黑树,所以最大时间复杂度为O(logN);

因为多余了存储其他节点的指针,所以占用内存会大一些。


EnumMap

定义:

public class EnumMap<K extends Enum<K>, V> extends AbstractMap<K, V>

在介绍Set的时候,有EnumSet为枚举类型提供快捷存储,在Map中也一样。EnumSet内部实现为位向量,那么EnumMap呢?

基本的数据存储形式

查看源码可以发现,内部存储为数组。

private transient Object[] vals;

既然数组为基本存储形式,那么它的索引是怎么实现的呢?是否会涉及到自动扩容呢?

数组大小的确定
public EnumMap(Class<K> keyType) {
    this.keyType = keyType;
    keyUniverse = getKeyUniverse(keyType);
    vals = new Object[keyUniverse.length];
}

从构造函数中可以看出,数组大小默认为枚举域的大小。因为键为某种类型的枚举,所以其能够存储的键值对是恒定的。

注:枚举域的大小是通过以下这个函数获取的:

private static <K extends Enum<K>> K[] getKeyUniverse(Class<K> keyType) {
    return SharedSecrets.getJavaLangAccess()
                                    .getEnumConstantsShared(keyType);
}

其中使用到SharedSecretsJavaLangAccess,通过这两个类来获取Java栈帧中存储的类信息,从而获取到在栈中的枚举。

如何建立索引?
public V put(K key, V value) {
    typeCheck(key);

    int index = key.ordinal();
    Object oldValue = vals[index];
    vals[index] = maskNull(value);
    if (oldValue == null)
        size++;
    return unmaskNull(oldValue);
}

值在数组中的索引即是key在枚举中的索引。

基本操作

——添加

public V put(K key, V value) {
    typeCheck(key);

    int index = key.ordinal();
    Object oldValue = vals[index];
    vals[index] = maskNull(value);
    if (oldValue == null)
        size++;
    return unmaskNull(oldValue);
}

——删除

public V remove(Object key) {
    if (!isValidKey(key))
        return null;
    int index = ((Enum<?>)key).ordinal();
    Object oldValue = vals[index];
    vals[index] = null;
    if (oldValue != null)
        size--;
    return unmaskNull(oldValue);
}

——获取

public V get(Object key) {
    return (isValidKey(key) ?
            unmaskNull(vals[((Enum<?>)key).ordinal()]) : null);
}

注:在操作之前,都会对key进行校验,减少成本。

小结

如果使用的键是枚举类型,那就用EnumMap。不涉及动态扩容、键值对存储等的开销,无论从速度还是内存方面,都是更好的替代者。

Java集合(7)——Map之HashTable

写在开始

作为和HashMap一样使用哈希映射实现的存储键值对的集合,它和HashMap有些什么区别呢?

Java集合的结构图

定义:

public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>

Hashtable继承至Dictionary并实现了Map接口,Map接口在之前有介绍过。现在我们先看看Dictionary。

Dictionary

定义:

public abstract
class Dictionary<K,V>

在JDK1.0的时候,设计中是没有Map接口的(那会也没有HashMap——since JDK 1.2)。那么在当时需要存储键值对,映射到现实当中的抽象就是字典集了,惟一的key对应惟一的Val。所以我们可以看到Dictionary是一个抽象类,描述了一种存储键值对的个体。

Tip:1、在JDK 1.2之后新增了Map接口,用以替代Dictionary,因为协议(规范)比抽象类更具有扩展性。

2、Dictionary不允许存放重复、为NULL的键,也不允许存放为NULL的值。

3、Dictionary本质上也就是按图索骥——Map接口,所以说,接口是比抽象类更深层次的抽象。

基本方法:

//返回集合的大小
abstract public int size();
//字典是否为空
abstract public boolean isEmpty();
//返回键的集合
abstract public Enumeration<K> keys();
//返回值的集合
abstract public Enumeration<V> elements();
//根据键索引值
abstract public V get(Object key);
//添加元素
abstract public V put(K key, V value);
//移除元素
abstract public V remove(Object key);

基本属性

  1. 因为继承至Dictionary,所以HashTable不允许存放重复、为NULL的键,也不允许存放为NULL的值
  2. 和其他集合一样,HashTable的容器容量(capacity)也是由阀值(threshold)和负载因子(loadFactor)所决定的,其中threshold = (int)(capacity * loadFactor) 。
  3. 默认的负载因子是0.75,默认的初始化大小是11。
  4. 计算索引的方法:

index = (hash & 0x7FFFFFFF) % tab.length

《Hash映射》中提到过基本计算索引的方式为:

索引(index) = (元素的hashCode的绝对值)对 数组length 求余

这里hash & 0x7FFFFFFF即通过位运算快速获取绝对值的方式。0x7FFFFFFF是int能够存储的最大值,其二进制表示为0111 1111 1111 1111 1111 1111 1111 1111,第一位标识符号位,其余全部为1,与运算,快速将任意int值的符号位转换为0,从而获得绝对值。

基本操作

添加

public synchronized V put(K key, V value) {
    // Make sure the value is not null
    if (value == null) {
        throw new NullPointerException();
    }

    // Makes sure the key is not already in the hashtable.
    //如果key为null,获取hashcode直接异常
    //如果key(对应的索引)不为空,且key是同一个,直接修改原值
    //如果key只是计算出来索引一致,那么还是添加元素,外挂为链表
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    for(; entry != null ; entry = entry.next) {
        if ((entry.hash == hash) && entry.key.equals(key)) {
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }
    //添加元素
    addEntry(hash, key, value, index);
    return null;
}

真正添加元素的逻辑:

private void addEntry(int hash, K key, V value, int index) {
    modCount++;

    Entry<?,?> tab[] = table;
    //如果当前数据大小达到阀值,扩容并重新计算索引值
    if (count >= threshold) {
        // Rehash the table if the threshold is exceeded
        rehash();

        tab = table;
        hash = key.hashCode();
        index = (hash & 0x7FFFFFFF) % tab.length;
    }

    // Creates the new entry.
    @SuppressWarnings("unchecked")
    Entry<K,V> e = (Entry<K,V>) tab[index];
    tab[index] = new Entry<>(hash, key, value, e);
    count++;
}

注:默认存储的最小单元是——单链表节点;

删除

public synchronized V remove(Object key) {
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> e = (Entry<K,V>)tab[index];
    //获得索引,如果满足条件,维护单链表并移除相关节点
    for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            modCount++;
            if (prev != null) {
                prev.next = e.next;
            } else {
                tab[index] = e.next;
            }
            count--;
            V oldValue = e.value;
            e.value = null;
            return oldValue;
        }
    }
    return null;
}

获取

public synchronized V get(Object key) {
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            return (V)e.value;
        }
    }
    return null;
}

扩容

protected void rehash() {
    int oldCapacity = table.length;
    Entry<?,?>[] oldMap = table;
    //生成新的容量并检测是否可能超过最大限制
    //这里可以看出Tbale的容量一直是奇数
    // overflow-conscious code
    int newCapacity = (oldCapacity << 1) + 1;
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        if (oldCapacity == MAX_ARRAY_SIZE)
            // Keep running with MAX_ARRAY_SIZE buckets
            return;
        newCapacity = MAX_ARRAY_SIZE;
    }
    Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];

    modCount++;
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    table = newMap;
    //拷贝数据,直接给每个元素寻找新的位置
    for (int i = oldCapacity ; i-- > 0 ;) {
        for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
            Entry<K,V> e = old;
            old = old.next;

            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            e.next = (Entry<K,V>)newMap[index];
            newMap[index] = e;
        }
    }
}

区别

和HashMap的区别
  • HashMap的默认容量是2的幂,而HashTable是11

因为在HashMap中使用2的幂的目的是通过位运算快速获得索引,但是带来不好的效果是需要对输入的hashcode扰动(避免散列不完全)。而HashTable当中是直接对数组求余,任意数对奇数求余的散列程度比偶数好(这一点也不大懂,质数应该最理想,但是当自定义初始化容量时不能保证,所以保证为奇数)。

参考链接:知乎(https://www.zhihu.com/question/29587252;https://www.zhihu.com/question/39448597)

  • HashTable线程安全,HashMap线程不安全

查看源码的时候可以发现对于关键操作数据的方法(如put、get等),都是使用关键字synchronized加入同步锁。而HashMap则没有。

  • HashTable不允许Key或者Val为NULL,HashMap允许
  • HashTable在出现碰撞的时候,只能外挂单链表。HashMap还外挂红黑树。
  • HashTbale可以理解为简化(阉割)但安全版的HashMap。
和ConcurrentHashMap的区别

在Map的实现类中,HashTable和ConcurrentHashMap都线程安全,他们的区别是,ConcurrentHashMap具有所有HashMap的高效的特性,且在加入同步锁的时候只对相关代码块做了修饰而不是HashTable的整个方法同步锁,效率更高。

Java集合(6)——Hash映射相关

写在开始

在HashMap中,我们了解到哈希映射基本定义,这里会详细介绍如下:基本原理、Hash碰撞以及其一般解决办法。

注:代码都是基于JDK 1.8的HashMap分析。

定义

Hash映射是一种能够元素(对象)映射数组的机制。通过该机制,我们可以快速通过每个元素都存在的差异化特性获取元素的在数组中的索引。

基本原理

首先来一波需求分析,我们要将元素映射到数组:

1、数组依靠一个唯一的编号用来索引元素,所以简化问题,将元素映射到一个编号(索引)

2、数组大小是确定的,数学上学过,两个数求余,那么有个对数组长度的(非0)余数一定是小于数组长度的,也就可以用来当索引值。再次简化问题,将元素的某个特性转换为一串数字

3、元素我们认为有差异化,那么我们定义一个属性——元素的特征值,它能够唯一标识一个元素(理论上)。在Java中,所有东西都是对象,基本的特征值体现为对象的hashcode(散列值)

根据上面的分析,在Java中该机制可以表达如下(伪代码):

索引(index) = (元素的hashCode的绝对值)对 数组length 求余

元素 = 数组[index] 


以JDK 1.8中的HashMap为例介绍Java中的实现(之后的代码也都是):

1、获取特征值(hash),这里对元素的散列值做了扰动,具体下面的哈希碰撞介绍。

static final int hash(Object key) {
    int h;
    //key.hashCode()获取对象的散列值
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

2、获得索引(HashMap中putVal函数获取索引的操作

i = (n - 1) & hash

可以发现将hash和 (size – 1)做与操作,之后就可以得到index。

在HashMap中提到,数组的大小(size)永远是2的整次幂,那么size – 1的二进制也就永远是这种格式0111…1111,刚好是size的低位掩码。然后再做一次与操作,直接将散列值的高位归零,获得的低位作为数组的索引(index)。

——从集合的角度分析,就是快速获取散列值和数组最大索引(size – 1)在二进制位上的交集。


Tip调用hashCode之后的获取的散列值可能有以下两种来源:

  • 覆写超类的方法,返回根据自定义规则计算出的散列值;
  • 没有覆写的,返回根据底层默认实现的hash算法计算出的散列值(该值是在对象上的地址做了一系列偏移并和掩码混淆之后的结果,并不是存储的地址,看了JDK1.7底层部分源码得出的结果,如果有误还请指正)。

所以对HashMap添加元素的基本过程可以表示为下图:

哈希工作原理

图 3

图片来源于:http://www.oracle.com/technetwork/cn/articles/maps1-100947-zhs.html

哈希碰撞

定义:两个本来不同的对象计算出的散列值(hashcode)相同。

1、对象的散列值是一个int类型的数字。在Java中32位的int存储范围大约40亿,虽然范围很大,但是在大量的数据下,碰撞也会时而发生(总觉得和高数的正态分布有关)。

2、自定义hashcode函数的实现,其计算规则制定得不大好,这也就更容易造成碰撞。

存储结构中解决碰撞的方案

如果在大街上撞衫了,处理方案有可能如下:

1、衣服不要了(丢弃)

2、再找个地方买个新衣服(换)

3、在自己的衣服上加点装饰,让它看起来不一样(更换形式)

4、下次买贵点的,避免撞衫(减小概率)

在HashMap这种存储数据的场景中,方案一不大可行,其他的处理方案(思想)基本一致。

基本的存储形式:

“换”位置的思想

  • 开放地址法

对参与寻找计算的hash增加或者减少一个偏移量。

公式:index = (hash(key)+di) MOD length 其中 i=1,2,…,k(k<=length-1);di为产生冲突的时候的增量序列

  1. di值可能为1,2,3,…m-1,称线性探测再散列
  2. di取值为1,-1,2,-2,4,-4,9,-9,16,-16,…k*k,-k*k(k<=m/2),称二次探测再散列
  3. di取值为伪随机数列。称伪随机探测再散列
  • 再哈希法

即对原对象(按照不同规则)重新hash,直到获得无冲突的位置为止。

更换存储单元的形式

链地址法

即在HashMap一文当中提到的外挂数据结构——将存储单元由单一的键值对修改为 键值对+链表或者红黑树。

减小冲突概率

对原始hash进行扰动(扰动函数,个人觉得称为混合函数更合适)

在HashMap中求散列值的函数如下:

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

可以看到对获取的hash做了这样的操作 hash ^ (hash >>> 16)

前面我们提到hash实际上是一个int类型的数字。

假设已获得的哈希值为:1010 1100 0011 0110 |  0110 1001 1011 0101

数组长度为16             :0000 0000 0000 0000 |  0000 0000 0001 0000

则数组长度 – 1           :0000 0000 0000 0000 |  0000 0000 0000 1111

先看不做扰动的:

0      1010 1100 0011 0110 |  0110 1001 1011 0101

   0000 0000 0000 0000 |  0000 0000 0000 1111

   0000 0000 0000 0000 |  0000 0000 0000 0101 = 5(十进制)

这个时候,发现高位并没有参与到计算索引的过程中呢?

结果就是在这样的大小下,所有散列值二进制最后4位是0101的都会被放到数组[5]这个位置,无论高位的后四位是什么样的,这样一来,碰撞的元素就多了。现在出现重复的概率由低位(后4位)决定也就是1/16 = 0.0625,每100个出现6个。


如果做扰动呢?

0     1010 1100 0011 0110 |  0110 1001 1011 0101

>>>0000 0000 0000 0000 |  1010 1100 0011 0110(右移16位之后的结果)

    1010 1100 0011 0110 |  0110 1001 1011 0101

   0000 0000 0000 0000 |  1100 0101 1000 0011

   0000 0000 0000 0000 |  0000 0000 0000 1111

   0000 0000 0000 0000 |  0000 0000 0000 0011 = 3(十进制)

可以看到在扰动之前可能会放在位置5上的元素现在被分配到了位置3上面。

hash右移16位,也就意味着,去掉了低位,只留下了高位(前16位)。异或只保存不同的,也就是异或之后将原散列值的高位和低位相同去掉(分别保留了高位和低位的特征位),通过这样的扰动,使低位出现的重复概率减小。

扰动之后重复的概率为:1/(16*16) = 0.00390625,大概每1000个出现4个。

从上面概率可以看出扰动的效果还是很明显的,在容量越大的时候重复的概率也就越小(参与计算索引的特征位越多)。

最后,附上Bloch大大说的(来源 https://stackoverflow.com/questions/9413966/why-initialcapacity-of-hashtable-is-11-while-the-default-initial-capacity-in-has):

Joshua Bloch: The downside of using a power-of-two is that the resulting hash table is very sensitive to the quality of the hash function (hashCode). It is imperative that any change in the input must affect the low order bits of the hash value. (Ideally, it should affect all bits of the hash value with equal likelihood.) Because we have no assurance that this is true, we put in a secondary (or “defensive”) hash function when we switched to the power-of-two hash table. This hash function is applied to the results of hashCode before masking off the low order bits. Its job is to scatter the information over all the bits, and in particular, into the low order bits. Of course it has to run very fast, or you lose the benefit of switching to the power-of-two-sized table. The original secondary hash function in 1.4 turned out to be insufficient. We knew that this was a theoretical possibility, but we thought that it didn’t affect any practical data sets. We were wrong. The replacement secondary hash function (which I developed with the aid of a computer) has strong statistical properties that pretty much guarantee good bucket distribution.

大意就是说在HashMap为了使用位运算快速获得在数组中的位置,所以采用了大小必须是2的幂。

在理想状态下,输入的hashcode发生一个位的改变,应该都产生不同的效果,即,得到的索引是hashcode所以二进制位参与计算后的结果。但是,使用2的幂的时候,会造成大部分的位置可能都不会用到(扰动前的效果)。所以设计了一个散列函数将信息分散到所有位(特别是低位),而这个散列函数也必须运行的很快,要不采用2的幂作为容量的好处就没有了。在1.4的时候的二级散列做的不是很好,在1.8中(借助计算机以及概率统计)保证良好的存储分布,避免有大量的位置被浪费。

Java集合(5)——Map之HashMap

写在开始

本文主要介绍HashMap基本原理,以及可能遇到的一些问题(均基于JDK 1.8)。

Java集合的结构图

定义:

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

从定义可以看到,其通过Hash映射间接的实现了Map的功能。

1、什么是Hash映射?

一句话:一种将元素映射到数组的机制。

由上面可以得出,通过Hash存储的基本形式为数组。而访问数组又是依靠一个唯一确定的index(索引),所以在该机制中必然有一种唯一确定索引的机制。

如何确定唯一的索引?

在Java万物之父Object有一个方法hashCode(),每个子类都会通过该方法返回一个整数值(该对象的散列值),那么无论存储的是什么对象,我们都可以这样做:将返回的整数值转换为正值,而后对数组大小求余。

代码表示: int hashvalue = Maths.abs(key.hashCode()) % table.length;(基本的求索引的形式)

在JDK1.8中获得索引分为以下几步:

——获得HashCode(这里并不是纯粹的对象的散列值,而是做了扰动,具体在《Hash映射》的文章中会详细讲解)

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

——获取索引(其中n为存储用的数组大小,通过位运算符&获得两个数字的交集,从而快速求余)

(n - 1) & hash

如果需要详细了解《Hash映射》点这里

2、在数组中基本存储的形式是什么?

在介绍Map的时候,我们提到定义在Map中的嵌套接口Entry是存储Map中元素的基本形式,而HashMap采用数组存储,简易版如图:

HashMap中有定义了两个实现Entry的内部类:

——为什么要实现两个呢?

上面Hash映射提到,会根据对象的散列值(hashcode)计算出在数组中的索引。那么如果两个不同的对象,但是计算出的索引一样呢?

(虽然32位的int能表示的范围大约有40亿,但是不可避免出现碰撞的现象,这种情况在使用自定义对象作为key的时候尤为明显)

这种情况我们称之为哈希冲突(或哈希碰撞),在这种情况下,我们也必须保证Map存储的正常。因而有一些通用的方案。

在HashMap中采用的是链地址法来解决(更多解决方案请看《Hash映射》)。

链地址法:将之前单一存储数据(key和Val)的Entry增加能够获取下一(或上一)元素的指针。也就将当前地址存储的数据形式演变为——链表或者其他数据结构(将当前地址链接到一个数据结构上)。如图所示:

HashMap中支持链接到链表和红黑树。

  • 当链接的数据不超过8个的时候,使用链表(如果此时数据结果是红黑树,那么在存储数据不超过6个的时候会转为链表);
  • 当链接的数据超过8个的时候,使用红黑树(如果此时数据结果是链表,会转为红黑树);
  • 红黑树(节点)所占用的内存大概是链表(节点)的两倍,所以只有在满足条件(数据超过8个)的时候才会使用;
  • 一但转换为红黑树,只有在重新扩容(resize)的时候会检测是否需要转换为链表。
  • 外挂数据较多的时候,链表的查询效率O(N),而红黑树的效率为O(LogN),时间效率更高。

代码定义:

static final int TREEIFY_THRESHOLD = 8;

static final int UNTREEIFY_THRESHOLD = 6;

static final int MIN_TREEIFY_CAPACITY = 64;(树的最小容量被定义为64)

——Node<K,V>(链表)

定义:(还有其他构造方法,这里没有全部列出)

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    //...
}

调整为红黑树的地方:

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //1、如果这个Map为空,首先初始化数组
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //2、(n - 1) & hash 获得在数组中的索引,如果当前位置为空,直接放置数据
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        //3、不为空,表明存在哈希冲突
        Node<K,V> e; K k;
        //3.1 以下都是查找是否存在该元素的逻辑
        //3.1.1 外挂的数据结构第一个和要插入的数据key一致
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //3.1.2 如果是红黑树,使用树的插入方法
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            //3.1.3 外挂的数据结构是链表
            for (int binCount = 0; ; ++binCount) {
                // 查询到最后一个都没有匹配,直接在最后加入
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    //检测是否需要转换为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                //在外挂链表中查到相同Key的节点
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //3.2 节点已经存在,更改节点的值就好
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    //4、扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

注:1、上述方法也描述了HashMap的添加过程,下文就不再赘述。

2、重置外挂数据结构的最佳时机就是下次插入数据的时候

在JDK1.8中Map新增了较多添加数据的方式(具体过程都差不多,需了解可自己查看源码):

  • compute——插入计算之后的值
  • computeIfAbsent——如果不存在键,就插入计算后的值
  • merge——由调用者决定插入哪一个值

——TreeNode<K,V>(红黑树)

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }

   //...
}

由红黑树转为链表的方法:

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit)

注:这里只说方法名,因为这个下面即将介绍的扩容相关。一起介绍

3、用数组存储,数组的大小是如何确定的?

Map作为一个容器,原则上是允许无限制放入数据。但是,在创建的时候,我们不能说一下就分配一个超大的数据空间,保证元素够放(即使我可能只需要放几个数据),因为这样会浪费太多的磁盘空间。那怎么允许无限制放入元素,还能够不那么浪费磁盘空间呢?

答案就是对数组动态扩容。扩容的标准:负载因子(loadFactor)

负载因子:容器内所有元素(size)超过负载因子(loadFactor) * 容器容量(capacity),就认为容器已经装不下了,需要扩容。

注:在HashMap中默认负载因子为0.75,这个魔数是经过概率(泊松分布)计算得出的。

元素大小阀值(threshold):扩容的时候用于比较的参数,初始化值为(capacity * loadFactor)


下面我们对可能出现的几种情况分组:

case1:初始化Map时,没有说明大小:

//只会初始化好loadFactor
HashMap<String, String> hashMap = new HashMap<>();

case2:初始化的时候传入了大小:

//这种情况会初始化好loadFactor和threshold,其中loadFactor = DEFAULT_LOAD_FACTOR = 0.75
HashMap<String, String> hashMap = new HashMap<>(12);

case3:初始化的时候指定大小以及负载因子:

//这种情况会会初始化好loadFactor和threshold
HashMap<String, String> hashMap = new HashMap<>(12,0.82f);

case4:初始化的时候传入Map(拷贝):

//这种情况会会初始化好loadFactor和threshold
Map<String,String> map = new HashMap<>();
HashMap<String, String> hashMap = new HashMap<>(map);

整个数组的初始化和扩容都在这里完成(代码略长):

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    //***************计算新的容量、阀值
    if (oldCap > 0) {
        //在使用过程中扩容
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //newCap = oldCap << 1 数组进行两倍扩容
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold阀值也两倍
    }
    //Case 2、3、4
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {//Case1               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    //***************计算完成
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    //***************开始拷贝数据,并维护新数组的索引顺序
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)//Node只存了一个值,直接计算在新表中的索引值
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    //Node是红黑树,拆分里面的节点,看现在能不能放入到新的数组中
                    //(能够放入意味着会对后面添加的元素的索引计算产生影响)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    //Node是链表,拆分链表中的节点,看现在能不能放入到新的数组中
                    //将链表分为两个区域
                    //1、之前旧数组绝对能够存放的数据(元素Hash值绝对小于数组容量)——低位元素
                    //这一类位置元素,在新数组中的位置一定不会变动
                    Node<K,V> loHead = null, loTail = null;
                    //2、可能在新数组中能够存放的数据(在新数组中位置可能会变动)——高位元素
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        //e.hash & oldCap 快速判断元素的Hash值是否绝对小于之前数组的容量
                        if ((e.hash & oldCap) == 0) {
                            //第一次查找到,生成低位的链表
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;//链表的尾巴指向下一个
                            loTail = e;
                        }
                        else {
                            //同上
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;//原位置放置低链表
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        //因为数组是两倍扩容,所以直接加上旧数组大小,就是新的索引
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

值得注意以下几点:

1、默认负载因子为0.75;默认容器大小为16。

2、在使用者传入了初始化大小的时候,也会强制将大小修正为2的倍数(最近的)。因为使用2的倍数作为数组大小,再使用二进制的位运算计算位置或者判断数组边界都比常规的运算符快(例如:计算索引(capacity – 1) & hash 等)。数组大小永远为2的倍数

3、上面提到在TreeNode中的split函数会执行链表转换到红黑树的操作,下面我们来看看这个函数:

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    TreeNode<K,V> b = this;
    // Relink into lo and hi lists, preserving order
    TreeNode<K,V> loHead = null, loTail = null;
    TreeNode<K,V> hiHead = null, hiTail = null;
    int lc = 0, hc = 0;
    //拆分树的逻辑,和上面拆分链表逻辑基本一致
    //只是在拆分的时候,先没有形成树,是后面进行再次生成的
    for (TreeNode<K,V> e = b, next; e != null; e = next) {
        next = (TreeNode<K,V>)e.next;
        e.next = null;
        if ((e.hash & bit) == 0) {
            if ((e.prev = loTail) == null)
                loHead = e;
            else
                loTail.next = e;
            loTail = e;
            ++lc;
        }
        else {
            if ((e.prev = hiTail) == null)
                hiHead = e;
            else
                hiTail.next = e;
            hiTail = e;
            ++hc;
        }
    }

    if (loHead != null) {
        //新树的深度小于UNTREEIFY_THRESHOLD = 6 转为链表
        if (lc <= UNTREEIFY_THRESHOLD)
            tab[index] = loHead.untreeify(map);
        else {
            tab[index] = loHead;
            //如果有高位树,说明可能从中间抽取了元素,需要重新生成树
            if (hiHead != null) // (else is already treeified)
                loHead.treeify(tab);
        }
    }
    if (hiHead != null) {
        if (hc <= UNTREEIFY_THRESHOLD)
            tab[index + bit] = hiHead.untreeify(map);
        else {
            tab[index + bit] = hiHead;
            if (loHead != null)
                hiHead.treeify(tab);
        }
    }
}

4、JDK 1.7中的扩容函数(1.7中的HashMap只外挂了链表作为解决冲突的数据结构):

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable);
    table = newTable;
    threshold = (int)(newCapacity * loadFactor);
}
//对所有的元素都计算一次在新数组中的位置
void transfer(Entry[] newTable) {
    Entry[] src = table;
    int newCapacity = newTable.length;
    for (int j = 0; j < src.length; j++) {
        Entry<K, V> e = src[j];
        if (e != null) {
            src[j] = null;
            do {
                Entry<K, V> next = e.next;
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            } while (e != null);
        }
    }
}

static int indexFor(int h, int length) {
    return h & (length-1);
}

可以看出在JDK 1.8中对HashMap做了查询等一系列优化,效率比1.7高。


4、HashMap的基本函数

 

添加(其调用的putVal上文已经分析过,不再赘述):

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

获取:

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        //首先检查保存在当前位置的Node
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        //如果没有,再看是否存在外挂数据结构
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

删除(相当于先调用get,然后移除节点):

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        //********************开始找元素
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        //********************找到元素然后移除
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

5、多线程使用HashMap应该注意什么?

在查看源码过程中,我们可以看到对于很多核心操作并没有线程同步。

举例put的时候,场景:如果两个线程同时添加元素且这时Map需要扩容(resize)

  • 在JDK1.7的时候,会因为提前改变了元素的指向,而另一个线程不知,还是继续resize,并重组链表,从而形成环型链表,造成死循环。
  • 在JDK1.8中,不会造成死循环,因为在拷贝数据的过程中,新建两个链表分别添加数据,而不是1.7中的直接操作链表;但是有风险造成数据丢失(同时给一个node添加节点,数据丢失)。

所以多线程的时候,除非自己处理了线程安全,不然还是建议使用ConcurrentHashMap保证线程同步。

6、和LinkedHashMap的区别是什么?

LinkedHashMap定义:

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>

LinkedHashMap继承至HashMap,比较重要的就是重写了HashMap的Entry类。在之前单向链表的键值对对象中加入了对前后对象的引用句柄。即,默认外挂的单向链表变为双向链表。最后达到的效果是撒呢?

通过双向链表,迭代的时候,能够获知添加到Map的顺序(保存了添加的顺序),而HashMap没有维护添加时的顺序的。

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

最后

  • HashMap是使用基于哈希映射实现快速存储数据(键值对)的容器,是空间换时间的范本。
  • HashMap线程不安全,在多线程下,应当使用ConcurrentHashMap或者HashTable保证线程安全。
  • HashMap处理碰撞的方式是外挂链表或红黑树。
  • HashMap的容量大小永远是2的倍数。
  • HashMap扩容的成本很高,如果知道需要存放的数据大小,尽量初始化的时候传入。

Java集合(4)——Map

写在开始

每当想要使用键值对存储数据的时候,总能想到Map,现在我们就来看下它的实现原理。本章会讲解HashMap、TreeMap、EnumMap、HashTable。

Java集合的结构图

Map

首先上结构图:

从上面的图可以看出,所有的Map都直接或者间接实现了Map接口,同时也定义了基本的抽象实现AbstractMap。

官方对Map的描述如下:

一个能够将键映射到值的对象。不允许存在两个相同的键,并且一个键理论上只能对应一个值。

注意以下两点:

  • Map在JDK1.2的时候才加入,在此之前,只有基本的抽象类Dictionary。1.2之后,推荐实现Map接口替代Dictionary(类型的协议比类型的抽象更为重要)。
  • 通过Map,我们能够获取到至少3种集合:包含所有键的集合、包含所有值的集合、包含所有键值对的集合。

定义了如下方法:

int size() 获取集合中元素的大小
boolean isEmpty() 检测集合中是否有元素,返回布尔值
boolean containsKey(Object key) 判断给定值是否在集合中作为键存在
boolean containsValue(Object value) 判断给定值是否在集合中作为值存在
V get(Object key) 获取键对应的值
V put(K key, V value) 插入新的键值对
V remove(Object key) 根据键移除键值对
void putAll(Map<? extends K, ? extends V> m) 拷贝给定Map的值到该Map
void clear() 清掉所有的键值对
Set<K> keySet() 获取所有键的集合
Collection<V> values() 获取所有值的集合
Set<Map.Entry<K, V>> entrySet() 获取所有键值对的集合

在JDK1.8之后新增了较多的默认方法:

default V getOrDefault(Object key, V defaultValue) 获取指定键的值的时候可指定默认值
default void forEach(BiConsumer<? super K, ? super V> action) 遍历所有的键值对
default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) 替换所有键值对的值
default V putIfAbsent(K key, V value) 只有在键值对不存在的时候才添加
default boolean remove(Object key, Object value) 如果存在给定的键值对,才执行移除
default boolean replace(K key, V oldValue, V newValue) 如果存在给定的键值对,才执行替换
default V replace(K key, V value) 如果存在给定的键,就执行替换操作
default V computeIfAbsent(K key,Function<? super K, ? extends V> mappingFunction) 如果不存在指定键,那么就插入接口计算后的值
default V computeIfPresent(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction)
如果存在指定键,并且通过接口计算后的值不为null,就执行插入操作;为null,就移除该键
default V compute(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction)
如果存在指定键,并且通过接口计算后的值不为null,就执行插入操作;为null存在指定键,就移除,否则不做操作
default V merge(K key, V value,
BiFunction<? super V, ? super V, ? extends V> remappingFunction)
由调用者决定采用哪个值插入

注:1.8中新增的默认方法大多是对我们通常写的代码的封装,比如说如下代码:

Map<String,String> map = new HashMap<>();
if (map.get("a") == null){
    map.put("a","test");
}

如果Map中不存在,才执行添加操作。在JDK1.8封装为方法putIfAbsent(),实现就是这样的:

Map<String,String> map = new HashMap<>();
map.putIfAbsent("a", "test");

小结,Map定义了一种一一映射的数据存储方式,其中通过put添加、remove移除。(再次申明:Map和Collection没有必然联系,它们都是Java集合框架中的顶级类)。

上面提到,Map是存储的是一一对应的键值对。这个键值对,在Map中是怎么样存在的呢?


Entry

存储键值对的实体。(定义在Map中的内部接口)

定义:

interface Entry<K,V>

可以发现定义的泛型<K,V>和Map的泛型是一致的,但是值得注意的是,在接口定义这一层,他们是属于各自的泛型申明,没有任何关系。

定义了如下方法:

K getKey() 获取键值对的键
V getValue() 获取键值对的值
V setValue(V value) 设置键值对的值
JDK1.8之后提供以下static方法

都是快速获得比较器的方法)

comparingByKey() 返回以键作为比较的比较器(调用键的compareTo)
comparingByValue() 返回以值作为比较的比较器(调用值的compareTo)
comparingByKey(Comparator<? super K> cmp) 返回以键作为比较的比较器(使用传入的比较器比较)
comparingByValue(Comparator<? super V> cmp) 返回以值作为比较的比较器(使用传入的比较器比较)

小结,Entry定义了在Map中存储的最小单元数据的形式。


AbstractMap

先来看定义:

public abstract class AbstractMap<K,V> implements Map<K,V>

该抽象类实现了Map接口,按照AbstractCollection(传送门)的思路,应该也会提供一些默认的实现。

仔细看了一下源码,大部分默认实现思想和AbstractCollection基本类似,这里就只分析一下比较重要或者有差别的了。

1、和AbstractCollection一样,没有提供默认添加单个元素的具体实现(都是简单的抛出了一个异常)

public V put(K key, V value) {
    throw new UnsupportedOperationException();
}

2、在介绍Map的时候提到,Map能够提供3中基本的集合,在代码中提供了这两种基本集合的定义:

transient Set<K>        keySet;
transient Collection<V> values;

注:transient意味着该变量反序列化

public Set<K> keySet() {
    Set<K> ks = keySet;
    if (ks == null) {
        ks = new AbstractSet<K>() {
            //...
        };
        keySet = ks;
    }
    return ks;
}

public Collection<V> values() {
    Collection<V> vals = values;
    if (vals == null) {
        vals = new AbstractCollection<V>() {
            //...
        };
        values = vals;
    }
    return vals;
}

而对于键值对的集合,则没有默认实现(每个子类实现键值对的真实存储方式可能都是有区别的)

public abstract Set<Entry<K,V>> entrySet();

3、提供了两张实现键值对存储的范例:

基本的键值对存储,每个键值对生成之后,可以重设值(val)

public static class SimpleEntry<K,V>
    implements Entry<K,V>

基本的键值对存储,每个键值对生成之后,不可以重设值(val)

public static class SimpleImmutableEntry<K,V>
    implements Entry<K,V>

具体就不分析了,就是实现了所有Entry定义的方法。

HashMap

HashTable

TreeMap

EnumMap


总结

HashMap使用哈希映射提供了快速存储键值对的方式,但线程不安全;

数据结构:数组

默认容量:16(容量要求为2的幂)

默认负载因子:0.75

扰动函数:hash ^ (hash >>> 16)

散列函数:hash & (length – 1)

外挂数据结构:链表或红黑树

最坏时间复杂度:O(N)——发生很多碰撞

最优时间复杂度:O(1)——分散均匀,没有碰撞

线程安全的实现(ConcurrentHashMap)

保存元素加入顺序的实现(LinkedHashMap)


HashTable使用哈希映射提供了不存放Null且线程安全的集合;

数据结构:数组

默认容量:11(最好为质数,这样可以均匀散列)

默认负载因子:0.75

散列函数: (hash & 0x7FFFFFFF) % tab.length

外挂数据结构:链表

最坏时间复杂度:O(N)——发生很多碰撞

最优时间复杂度:O(1)——分散均匀,没有碰撞

tip:线程安全且速度要求高,建议使用ConcurrentHashMap


TreeMap使用红黑树提供了元素有序(排序)的集合;

数据结构:红黑树

最坏时间复杂度:O(lgN)


EnumMap使用枚举的特性提供存储键为枚举的集合;

数据结构:数组

默认容量:枚举的域大小

时间复杂度:O(1)

Java集合(3)——Set

写在开始

作为我们常使用的集合之一,本章会讲解常用的HashSet、TreeSet、EnumSet,以及它们的父类、接口。

Java集合的结构图

Set

一种存放不重复元素的集合。

其结构图如下:

注:关于AbstractCollection(传送门

public interface Set<E> extends Collection<E>

代码层次可以发现,Set继承自集合Collection (传送门)。

查看方法可以发现,Set接口并没有新增任何方法,也就是 它只定义了一个不可以添加重复元素的集合类别

AbstractSet

定义了实现Set的基本框架,同时提供一些基本的代码实现。(没有新增方法)

定义如下:

public abstract class AbstractSet<E> extends AbstractCollection<E> implements Set<E>

提供了默认实现的方法如下:

1、Set的equals方法

public boolean equals(Object o) {
    if (o == this)
        return true;

    if (!(o instanceof Set))
        return false;
    Collection<?> c = (Collection<?>) o;
    if (c.size() != size())
        return false;
    try {
        return containsAll(c);
    } catch (ClassCastException unused)   {
        return false;
    } catch (NullPointerException unused) {
        return false;
    }
}

2、移除给定集合所有元素的方法

public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    boolean modified = false;

    if (size() > c.size()) {
        for (Iterator<?> i = c.iterator(); i.hasNext(); )
            modified |= remove(i.next());
    } else {
        for (Iterator<?> i = iterator(); i.hasNext(); ) {
            if (c.contains(i.next())) {
                i.remove();
                modified = true;
            }
        }
    }
    return modified;
}

3、哈希值的计算函数

public int hashCode() {
    int h = 0;
    Iterator<E> i = iterator();
    while (i.hasNext()) {
        E obj = i.next();
        if (obj != null)
            h += obj.hashCode();
    }
    return h;
}

HashSet

使用Hash映射存储(不重复)元素的集合

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>

这里有个小问题,为什么AbstractSet已经实现了Set,而HashSet还要实现Set接口?

其实这个为了代码可读性,查看源码的时候不需要多次跳转就知道其最上层的抽象类型;

很便捷的体现出,这个类就是一个Set;

多继承一次也并没有什么损失。

具体参考这里:https://stackoverflow.com/questions/4387419/why-does-arraylist-have-implements-list


查看源码,发现——内部存储是使用HashMap来存储的

private transient HashMap<E,Object> map;//反序列化

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();//占位用到的空对象

public HashSet() {
    map = new HashMap<>();
}

其中利用HashMap中key的唯一性,保证了Set里面不会有重复的元素(如果遇到两个hashcode一致的对象,但是实际上不一致的对象。这时代码没有做处理。所以在使用HashSet的时候,如果E为自定义对象,一定要处理好其hash函数)。

值得注意的是,通过以下构造,我们也能够快速构造一个有序的HashSet.

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

其中的具体实现就不分析了,因为都是调用的Map的实现。

TreeSet

使用红黑树存储(不重复)元素的集合

从Set的结构图我们可以知道,TreeSet可以向上追溯到NavigableSet和SortedSet。

为什么TreeSet要特殊一些,额外实现了这两个接口?

首先,为什么要定义这两个接口?

1、SortedSet

定义了一个不包含重复元素,且有序的集合。

新增如下函数:

Comparator<? super E> comparator() 返回一个对Set元素排序的比较器
SortedSet<E> subSet(E fromElement, E toElement) 返回一个子Set,范围是[fromElement,toElement)
SortedSet<E> headSet(E toElement) 返回一个子Set,范围是[head,toElement)
SortedSet<E> tailSet(E fromElement) 返回一个子Set,范围是[fromElement,end)
E first() 返回第一个元素
E last() 返回最后一个元素

  • Set中的顺序默认按照元素的自然顺序排列,这时获取比较器会返回null
  • 在获取子Set的时候,返回的都是半开区间。如果想要获取闭区间并且存储的类型运行计算给定值的后继值,那么只需要获取lowEndpoint 到 successor(highEndpoint) 的子区间。举个栗子(假设 s 是一个字符串有序 set):

SortedSet<String> sub = s.subSet(low, high+”\0″);——获取到一个闭区间

SortedSet<String> sub = s.subSet(low+”\0″, high);——获取到一个开区间


2、NavigableSet

在SortedSet的基础上,新增了在目标最近寻找符合条件的元素的方法。

新增如下函数:

E lower(E e) 获取小于给定元素的最大元素
E floor(E e) 获取小于等于给定元素的最大元素
E ceiling(E e) 获取大于等于给定元素的最小元素
E higher(E e) 获取大于给定元素的最小元素
E pollFirst() 返回第一个元素并移除
E pollLast() 返回最后一个元素并移除
NavigableSet<E> descendingSet() 以降序返回Set
Iterator<E> descendingIterator() 以降序返回Set 的迭代器。
NavigableSet<E> subSet(E fromElement, boolean

fromInclusive,E toElement, boolean toInclusive)

获取子Set时,严格指明是否开闭区间
NavigableSet<E> headSet(E toElement, boolean inclusive) 获取小于toElement的Set,严格指明是否开闭区间
NavigableSet<E> tailSet(E fromElement, boolean inclusive) 获取大于fromElement的Set,严格指明是否开闭区间

3、为什么要定义它们

SortedSet定义了一个有序的集合;而NavigableSet扩展了方法,并定义了一种可以快速查找的集合,这也正是TreeSet所期望的。

其次,TreeSet的实现是怎样的?

定义:

public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>

和HashSet一样,内部采用了Map作为内部存储工具。

private transient NavigableMap<E,Object> m;

private static final Object PRESENT = new Object();

public TreeSet() {
    this(new TreeMap<E,Object>());
}

其他的实现也均是通过TreeMap实现的,文末有Map的传送门,这里就不具体分析了。

EnumSet

定义:

public abstract class EnumSet<E extends Enum<E>> extends AbstractSet<E>

JDK的部分介绍文本:

* A specialized {@link Set} implementation for use with enum types.  All of
* the elements in an enum set must come from a single enum type that is
* specified, explicitly or implicitly, when the set is created.  Enum sets
* are represented internally as bit vectors.  This representation is
* extremely compact and efficient. The space and time performance of this
* class should be good enough to allow its use as a high-quality, typesafe
* alternative to traditional <tt>int</tt>-based "bit flags."  Even bulk
* operations (such as <tt>containsAll</tt> and <tt>retainAll</tt>) should
* run very quickly if their argument is also an enum set.

大抵就是说这是:

专为存储(不重复)枚举类型设计的集合,通过使用Enum的某些特性使得该集合的时间效率和空间使用率都比普通的集合要高。

  • 在其内部存储的时候,该集合体现为一个位向量(即:用一个位表示一个元素的状态;用一组位表示一个集合,每个位对应一个元 素,而状态只可能有两种);
  • 该类可以良好的替代位域(《Effective Java》第32条也有提到);
  • 在进行批量操作的时候,如果参数也是EnumSet的话就会很快完成(因为内部都是位运算)。

注:EnumSet从定义可以看出是抽象类,也就是不可直接实例化,但是在其内部,提供了静态的实例化方法,分别返回RegularEnumSet和JumboEnumSet两个实现,后面会讲这两个的区别。

public static <E extends Enum<E>> EnumSet<E> noneOf(Class<E> elementType) {
    Enum<?>[] universe = getUniverse(elementType);
    if (universe == null)
        throw new ClassCastException(elementType + " not an enum");

    if (universe.length <= 64)
        return new RegularEnumSet<>(elementType, universe);
    else
        return new JumboEnumSet<>(elementType, universe);
}

基本属性:

final Class<E> elementType;//存储的枚举类型(用于校验)
final Enum<?>[] universe;//记录存储的枚举所有的变量

主要讲解如下两点:

1、存储为位向量

  • 位向量

用一个位表示一个元素的状态;用一组位表示一个集合,每个位对应一个元 素,而状态只可能有两种

假设我们有如下对人状态的标记:

enum PersonState {EATING, WORKING,SLEEPING}

对于任意的状态,人只能选择是或者不是该状态,这也就对应到计算机的0和1。我们可以假设1就是用户拥有该状态,0就是没有。

那么,如果人同时有多种状态,我们怎么区分呢?

建立一个位数组。而对于enum类型,变量在初始化的时候就会有一个index(且一但初始化就不变),可以通过enum.ordinal()获取到这个索引,并做为在位数组中的索引,也就能够唯一定位一种状态的位置了。

这里方便理解,建立一个长度位3的位数组,用来标识我们上面的某个人所具有的状态:

阿Q现在的状态是边吃饭边工作

在Java中一个byte有8位,一个int有32位,一个long有64位,每个基本数据类型都可以看做 位的一维数组。所以我们能使用基本数据类型表示一个集合,同时,增加或者减少数据,直接使用位运算就可以快速实现。

注:RegularEnumSet中使用的是long作为位数组;JumboEnumSet使用的是 long的数组 作为位数组。

  • RegularEnumSet——enum变量个数小于等于64

存储:

private long elements = 0L;

添加

public boolean add(E e) {
    typeCheck(e);

    long oldElements = elements;
    elements |= (1L << ((Enum<?>)e).ordinal());
    return elements != oldElements;
}

1L << ((Enum<?>)e).ordinal():对1向左移动索引那么多位,也就是将位数组中索引对应的位置置为1(举个例子:假设ordinal() =  3,而1的二进制为1,那么左移三位,就得到1000)。

然后通过或操作,将数组中的目标(索引所在的)位更改为1(继续上面例子:假设现在用于存储的long二进制是100100000,求或(并集)之后的结果为100101000,成功将标志位更改)。

移除

public boolean remove(Object e) {
    if (e == null)
        return false;
    Class<?> eClass = e.getClass();
    if (eClass != elementType && eClass.getSuperclass() != elementType)
        return false;

    long oldElements = elements;
    elements &= ~(1L << ((Enum<?>)e).ordinal());
    return elements != oldElements;
}

移除的时候还是先获取到索引位是多少,而后置非,再和原存储的long做与操作,将目标位更改为0;

还是上面的例子,移除索引为3的状态:

首先获取到在位数组中的表示1000,而后非——0111,100101000 & 0111最后得到100100000,移除标记位。

  • JumboEnumSet——enum变量个数大小超过64

存储

private long elements[];

添加

public boolean add(E e) {
    typeCheck(e);

    int eOrdinal = e.ordinal();
    int eWordNum = eOrdinal >>> 6;

    long oldElements = elements[eWordNum];
    elements[eWordNum] |= (1L << eOrdinal);
    boolean result = (elements[eWordNum] != oldElements);
    if (result)
        size++;
    return result;
}

因为采用的是long型的数组存储,所以在定位到是多少位之前,增加了一步——查找在long型数组中的位置;

int eWordNum = eOrdinal >>> 6;

也就是将enum的索引(index)无符号右移6位(也就是说除以2的6次方,即index/64),这样就得到在long型数组中的位置了。

注:将long理解为位的二维数组就好理解了。

移除

public boolean remove(Object e) {
    if (e == null)
        return false;
    Class<?> eClass = e.getClass();
    if (eClass != elementType && eClass.getSuperclass() != elementType)
        return false;
    int eOrdinal = ((Enum<?>)e).ordinal();
    int eWordNum = eOrdinal >>> 6;

    long oldElements = elements[eWordNum];
    elements[eWordNum] &= ~(1L << eOrdinal);
    boolean result = (elements[eWordNum] != oldElements);
    if (result)
        size--;
    return result;
}

2、为什么可以良好代替位域

首先,什么是位域?

private static final int EATING = 1 << 0;
private static final int WORKING = 1 << 1;
private static final int SLEEPING = 1 << 2;

public void addState(int flag){
    //...
}

在表示某些状态的时候,我们经常会想到以上代码。可以比较方便的通过或(|)运算添加标记位到某个集合中——这个就是位域(信息在存储时,并不需要占用一个完整的字节, 而只需占几个或一个二进制位),即,利用一个或者几个二进制位表示信息。

在上面代码中,很简单的实现添加:

addState(EATING | WORKING);

但是,当我们想要打印一下状态,查看已有状态的时候就比较麻烦了(打印出的就只是一个数字,即使转换为二进制也不是很直观)。

同时,我们想看一下一共有多少种状态,也比较麻烦,没有比较简单的遍历方式获取所有状态。

其次,如果使用EnumSet实现呢?

enum PersonState {EATING, WORKING,SLEEPING}

public void addState(Set set){
    //...
}

因为EnumSet都是使用位运算(和手动实现位域一样),但是避免了手动实现容易出现错误的问题。同时,内部使用long来存储,所以在性能上面也能够和手动实现相媲美。

addState(EnumSet.of(PersonState.EATING,PersonState.WORKING));

添加状态的代码也很直观,打印所有的状态或者其他操作也都比较便捷。

最后

  • Set可以说是数学中集合的一种代码抽象;
  • 大多的Set通过Map实现;
  • Set存放不重复的元素(如果存放值为null的对象也是,不允许重复),然而在限定null只能存一个是比较麻烦的(相对直接不允许存储null而言),所以建议Set在实现的时候不允许存储null。

附上Map的传送门

Java集合(2)——AbstractCollection

写在开始

从结构图中可以发现,几乎所以的集合(List、Set、Queue)实现的时候都直接或者间接继承了AbstractCollection。下面我们来看看它的战略意义。

Java集合的结构图

AbstractCollection

在集合框架中的位置:

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

从代码看,抽象类实现了接口Collection。这就意味着,它能够为子类提供部分方法的具体实现(代码复用),同时也不会影响到Collection定义的规范(抽象类可以不实现接口的函数)。

其中定义了如下两个抽象方法,所有非抽象子类都必须实现:

public abstract Iterator<E> iterator();

public abstract int size();

包含获取迭代器以及集合大小的方法,以下的默认实现都会用到这两个方法。

提供了如下默认实现:

1、判断集合是否为空

public boolean isEmpty() {
    return size() == 0;
}

2、是否包含某个元素(使用equals比对)

public boolean contains(Object o) {
    Iterator<E> it = iterator();
    if (o==null) {
        while (it.hasNext())
            if (it.next()==null)
                return true;
    } else {
        while (it.hasNext())
            if (o.equals(it.next()))
                return true;
    }
    return false;
}

3、集合转为数组的方法(数组中元素顺序和存储顺序一致)

public Object[] toArray() {
    // Estimate size of array; be prepared to see more or fewer elements
    Object[] r = new Object[size()];
    Iterator<E> it = iterator();
    for (int i = 0; i < r.length; i++) {
        if (! it.hasNext()) // fewer elements than expected
            return Arrays.copyOf(r, i);
        r[i] = it.next();
    }
    return it.hasNext() ? finishToArray(r, it) : r;
}

这个方法和以下代码等效

List<E> list = new ArrayList<E>(size());
for (E e : this)
    list.add(e);
return list.toArray();

同时,如果在遍历完了之后,发现还有元素没有加入到数组中(比如说在遍历的时候在集合中加入了元素),会调用以下方法进行扩容并生成新数组的操作。

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private static <T> T[] finishToArray(T[] r, Iterator<?> it) {
    int i = r.length;
    while (it.hasNext()) {
        int cap = r.length;
        if (i == cap) {
            int newCap = cap + (cap >> 1) + 1;
            // overflow-conscious code
            if (newCap - MAX_ARRAY_SIZE > 0)
                newCap = hugeCapacity(cap + 1);
            r = Arrays.copyOf(r, newCap);
        }
        r[i++] = (T)it.next();
    }
    // trim if overallocated
    return (i == r.length) ? r : Arrays.copyOf(r, i);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError
            ("Required array size too large");
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

其中可以看到,对数组最大的大小是Integer.MAX_VALUE,如果溢出的话,会直接抛出OutOfMemoryError异常。

4、添加单个元素的方法(没有默认实现,粗暴的抛个异常出来)

public boolean add(E e) {
    throw new UnsupportedOperationException();
}

因为默认是抛出异常,所以支持加入单个元素到集合是需要子类自己实现的。

5、移除某个指定元素

public boolean remove(Object o) {
    Iterator<E> it = iterator();
    if (o==null) {
        while (it.hasNext()) {
            if (it.next()==null) {
                it.remove();
                return true;
            }
        }
    } else {
        while (it.hasNext()) {
            if (o.equals(it.next())) {
                it.remove();
                return true;
            }
        }
    }
    return false;
}

6、集合元素是否包含指定集合(也就是,指定集合元素是否都在集合中)

public boolean containsAll(Collection<?> c) {
    for (Object e : c)
        if (!contains(e))
            return false;
    return true;
}

7、拷贝源集合的数据到该集合

public boolean addAll(Collection<? extends E> c) {
    boolean modified = false;
    for (E e : c)
        if (add(e))
            modified = true;
    return modified;
}

注意:这里最终也是调用添加单个元素,所以,如果不是实现一个空集合,都还是要实现add()去添加元素。

8、根据指定集合,对当前集合求余(移除两个集合的共有元素)

public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    boolean modified = false;
    Iterator<?> it = iterator();
    while (it.hasNext()) {
        if (c.contains(it.next())) {
            it.remove();
            modified = true;
        }
    }
    return modified;
}

9、求源集合和当前集合的并集(共同有的元素)

public boolean retainAll(Collection<?> c) {
    Objects.requireNonNull(c);
    boolean modified = false;
    Iterator<E> it = iterator();
    while (it.hasNext()) {
        if (!c.contains(it.next())) {
            it.remove();
            modified = true;
        }
    }
    return modified;
}

10、清除所有元素

public void clear() {
    Iterator<E> it = iterator();
    while (it.hasNext()) {
        it.next();
        it.remove();
    }
}

最后

看了这么多默认实现,发现他们有很多相似的代码:

Iterator<E> it = iterator();
while (it.hasNext()) {
    //...
}

可见,对于遍历集合的方式依然推荐使用迭代器;

同时,为什么没有抽出一个方法来做这样相同的事情呢?

在JDK1.8的 Iterator 提供了如下方法:

default void forEachRemaining(Consumer<? super E> action) {
    Objects.requireNonNull(action);
    while (hasNext())
        action.accept(next());
}

是的,它就是来做这个事情的(对集合当中的每个元素都执行接口action指定的操作),只是到得有点晚。

Java集合(1)——基础接口Collection、Map、Iterator

写在开始

无论是写业务代码。还是自己的奇思妙想,用Java集合相关的东西都比较多,一直没有认真分析其源码。本文主要讲解集合的上层基础接口Collection、Map、Iterator。通过这些接口,我们定义了实现集合的基本协议(规范)。

Java集合的结构图

Collection

Collection(集合)是List、Queue、Set的上层(也就是ArrayList、LinkedList、Vector、EnumSet、HashSet、TreeSet都是它派生出来的),其中定义了作为一个数据集的必须实现的功能。

首先,什么是集合?

包含一类数据的容器,并支持对数据的基本操作(增、删、查)。

其次,集合要求一些什么东西?

集合的子类要求实现以下基本方法:

int size() 返回集合拥有的数据大小
boolean isEmpty() 判断集合是否为空
boolean contains(Object o) 检测是否包含某个数据
Iterator<E> iterator() 返回一个标准的遍历器
Object[] toArray() 将数据集转换为同类型的数组
<T> T[] toArray(T[] a) 将数据集复制到指定的数组当中
boolean add(E e) 添加一个数据
boolean remove(Object o) 移除一个数据
boolean containsAll(Collection<?> c) 判断集合是否包含某个子集
boolean addAll(Collection<? extends E> c) 将某个集合的数据全部添加到数据集中
boolean removeAll(Collection<?> c) 移除数据集和给定集合的交集元素
boolean retainAll(Collection<?> c) 获取数据集和指定集合的交集
void clear() 移除所有元素
JDK1.8以后提供以下方法


default Spliterator<E> spliterator() 返回一个可以分割的元素遍历器(并行遍历)
default Stream<E> stream() 返回一个流
default Stream<E> parallelStream() 通过并行快速返回一个流
default boolean removeIf(Predicate<? super E> filter) 移除符合filter指定条件的元素

最后,为什么不是先抽象再接口,而是先接口再抽象?(个人见解)

接口定义了集合的规范形式;(行业规范,想要当集合,就得符合这个标准)

架构的体现,通过这样的架构,从ArrayList到HashSet能够较快的学习(结构一样,学习成本降低);

Map

Map提供了一种将值(数据)映射到键(某个对象)上的数据集存储方式。

注:虽然Map和Collection都是在java.util包下,但是他们并没有什么关系(可能它们都是数据集吧)。

通过键的索引(哈希映射),我们可以很快的获取到数据集上的某个元素。

1、Map提供的操作数据的几个方法

clear() 从 Map 中删除所有映射
remove(Object key) 从 Map 中删除键和关联的值
put(Object key, Object value) 将指定值与指定键相关联
clear() 从 Map 中删除所有映射
putAll(Map t) 将指定 Map 中的所有映射复制到此 map

putAll方法的存在实际上可以比自己多次put数据快一些,因为在内部实现中,putAll通常会初始化Map大小,避免了动态扩容的开销。

2、遍历元素的方法

entrySet() 返回 Map 中所包含映射的 Set 视图。Set 中的每个元素都是一个 Map.Entry 对象,可以使用 getKey() 和 getValue() 方法(还有一个 setValue() 方法)访问后者的键元素和值元素
keySet() 返回 Map 中所包含键的 Set 视图。删除 Set 中的元素还将删除 Map 中相应的映射(键和值)
values() 返回 map 中所包含值的 Collection 视图。删除 Collection 中的元素还将删除 Map 中相应的映射(键和值)

在小节末引用的文章中对使用entrySet和toArray对元素进行遍历做了比较,这里直接上结论:

如果只是为了单纯的遍历,使用entrySet然后使用Iterator遍历会快一些;如果需要获取到所有元素集(这个元素集在后面有用),这时使用toArray会快一些。
3、获取Map中元素的方法

get(Object key) 返回与指定键关联的值
containsKey(Object key) 如果 Map 包含指定键的映射,则返回 true
containsValue(Object value) 如果此 Map 将一个或多个键映射到指定值,则返回 true
isEmpty() 如果 Map 不包含键-值映射,则返回 true
size() 返回 Map 中的键-值映射的数目

通常情况下,containValue会比containKey慢(因为在内部如果是按照数组存储,那么到达key的位置通常具有快速映射的方式)。

大部分知识点来自这里:http://www.oracle.com/technetwork/cn/articles/maps1-100947-zhs.html

Iterator

针对集合的遍历器。

包含一下方法:

boolean hasNext() 迭代器是否还有其他元素
E next() 返回迭代器中的下一个元素
default void remove() 从集合中移除迭代器返回的最后一个元素
default void forEachRemaining() 为每个元素执行指定的操作