Android内存优化基础——VSS、RSS、PSS、USS

VSS

Virtual Set Size,虚拟耗用内存。

它是一个进程能访问的所有内存空间地址的大小。这个大小包含了
一些没有驻留在RAM中的内存,就像mallocs已经被分配,但还没有写入。VSS很少用来测量程序的实际使
用内存。

RSS

Resident Set Size,实际使用物理内存。

RSS是一个进程在RAM中实际持有的内存大小。RSS可能会产生误导,因为它包含了所有该进程使用的共享库所占用的内存,一个被加载到内存中的共享库可能有很多进程会使用它。RSS不是单个进程使用内存量的精确表示。

PSS

Proportional Set Size,实际使用的物理内存,

它与RSS不同,它会按比例分配共享库所占用的内存。
例如,如果有三个进程共享一个占30页内存控件的共享库,每个进程在计算PSS的时候,只会计算10页。
PSS是一个非常有用的数值,如果系统中所有的进程的PSS相加,所得和即为系统占用内存的总和。当一个
进程被杀死后,它所占用的共享库内存将会被其他仍然使用该共享库的进程所分担。在这种方式下,PSS
也会带来误导,因为当一个进程被杀后,PSS并不代表系统回收的内存大小。

USS

Unique Set Size,进程独自占用的物理内存。

这部分内存完全是该进程独享的。USS是一个非常有用
的数值,因为它表明了运行一个特定进程所需的真正内存成本。当一个进程被杀死,USS就是所有系统回
收的内存。USS是用来检查进程中是否有内存泄露的最好选择。

数据结构——栈

写在开始

在日常代码中,递归出现的频率都较高,但是递归到了语言处理的时候,其内部实现是什么样的呢?这里介绍的就是和队列一样,出现频率高的一种数据结构——栈。

基本性质

栈和队列相对立,栈里面的元素总是后进先出(LIFO:Last in first out)

栈的基本模型

其最先进的元素位于栈底,最后进的元素位于栈顶。

栈的基本操作

基本参数定义

private Object[] stack;//数据持有数组
private int tail = 0;//用于标记尾部index

1、入栈(压入栈)

@Override
protected E push(E e) {
    if (e == null) {
        return null;
    }
    stack[tail] = e;
    if (++tail == stack.length) {
        doubleCapacity();
    }
    return e;
}

压入的操作比较简单,直接给尾部赋值。

从这儿可以看出数组的尾部即为栈的逻辑栈顶。

2、出栈(弹出栈)

@SuppressWarnings("unchecked")
@Override
protected E pop() {
    if (tail <= 0) {
        return null;
    }
    Object o = stack[--tail];
    stack[tail] = null;
    return (E) o;
}

弹出元素,将尾部指针减一,同时置空之前位置上的元素,促使内存空间在GC的作用下能够更快释放。

3、扩容

private void doubleCapacity() {
    int old = stack.length;
    int newCapacity = old << 1;
    //overflow
    if (newCapacity < 0) {
        throw new IllegalStateException("stack is too big");
    }
    Object[] a = new Object[newCapacity];
    System.arraycopy(stack, 0, a, 0, old);
    stack = a;
}

每次扩容为前一次的两倍,并拷贝数据至扩容之后的数组。

4、移除任意元素

@Override
public boolean remove(E element) {
    for (int i = 0; i < tail; i++) {
        if (stack[i].equals(element)) {
            return delete(i);
        }
    }
    return false;
}

private boolean delete(int i) {
    Object[] stack = this.stack;
    stack[i] = null;
    int size = this.tail;
    int move = size - i - 1;
    if (move > 0) {
        System.arraycopy(stack, i + 1, stack, i, move);
    }
    tail = size - 1;
    return true;
}

每移除一个元素都将会导致其后面的元素一一移动,这带来的额外开销较大,所以和队列一样,不建议频繁的移除任意位置的元素。

递归的实现

递归在虚拟机中通过对栈的调度实现的,在Java当中也就是熟知的栈内存。

这里借用其他文章的一张图,大概标识一下Java运行时的内存分区:

这里写图片描述

在程序运行过程中会开辟一个工作线程,而后当前执行线程中的基本数据类型、方法返回值、局部等信息会存储在虚拟机栈当中。因而执行递归的过程中会不断在虚拟机栈中入栈(压入返回地址),直到抵达最后一层,然后再依次弹出。

所以在执行递归的过程中可能会产生StackOverflowError错误,这就表明,使用递归实现已经将虚拟机给撑爆了(栈已经无法压入新的返回地址)。

这时可以自定义栈存储数据,代替递归。

  • 当前大部分JVM都可以动态扩展,只不过JVM规范也允许固定长度的虚拟机栈;
  • 大部分语言的实现递归方法都是依靠栈,只是栈大小不同。

最后

栈和队列是基本数据结构,也是操作系统或者较多语言常用的数据结构。

数据结构——队列

写在开始

无论是在操作系统还是现实生活中,队列总是一种很有用的数据结构,它是现实中排队模型的结构化。

基本性质

先进先出(FIFO:First in First out)

基本模型

队列元素总是由队尾入队,队首出队。也就保证了先进的先出(不考虑移除元素的情况)

(常见)队列的分类

  1. 顺序队列(ArrayDeque):即上面列举的模型
  2. 循环队列:元素一直在队列中,依靠游标获得元素,游标抵达队尾时再次移向队首。
  3. 优先队列(PriorityQueue):元素在队列内部按照优先级排列,优先级高的先出队。
  4. 阻塞(循环/优先/顺序)队列(BlockingQueue):适用于异步操作的队列模型

下面我们讲解一下使用数组实现顺序队列(除此之外还可以使用链式结构或者栈实现队列),

其中循环队列可以基于顺序队列很容易实现;
优先队列在讲解Java基础Queue的时候已经讲解过,可以使用二叉堆实现;
而阻塞队列因为现在对Java异步不是非常了解,故暂时不做讲解。

队列的基本操作与实现

数据的基本定义

/**
 * Holder all queue data. 
 */
private Object[] queue;
/**
 * The cursor of the head of the queue.
 */
private int head = 0;
/**
 * The cursor of the tail of the queue.
 */
private int tail = 0;

使用head和tail去标记队列的起始位置,可以一定程度上减小每次出队操作需要对数组进行重整的开销。

1、入队(offer)

@Override
public E offer(E e) {
    if (e == null) {
        return null;
    }
    queue[tail] = e;
    if (++tail == queue.length) {
        doubleCapacity();
    }
    return e;
}
入队操作直接将元素放置在队尾,并且将队尾的游标向后移动,如果这时已经到达队尾,那么动态扩容。

2、出队(poll)

@SuppressWarnings("unchecked")
@Override
public E poll() {
    if (tail <= 0) {
        return null;
    }
    Object result = queue[head];
    if (result == null) {
        return null;
    }
    queue[head] = null;
    if (++head == (queue.length >>> 1)) {
        reorganizeQueue();
    }
    return (E) result;
}

private void reorganizeQueue() {
    Object[] q = queue;
    int t = tail;
    int h = head;
    int size = t - h;
    Object[] a = new Object[t];
    System.arraycopy(q, h, a, 0, size);
    queue = a;
    head = 0;
    tail = size;
}

出队的时候直接获取队首的元素,并将队首位置置为null,如果队首的位置已经抵达整个队列容量的一半(此时可能一直在做出队操作),那么重整队列元素,避免下次入队元素的时候进行无效的动态扩容,节约内存空间。

3、扩容

private void doubleCapacity() {
    int old = queue.length;
    int h = head;
    int size = old - h;
    int newCapacity = old << 1;
    //overflow
    if (newCapacity < 0) {
        throw new IllegalStateException("queue is too big");
    }
    Object[] a = new Object[newCapacity];
    System.arraycopy(queue, h, a, 0, size);
    queue = a;
    head = 0;
    tail = size;
}

每次扩容都会对数组进行双倍容量的分配。

4、移除元素

@Override
public boolean remove(E element) {
    for (int i = head; i < tail; i++) {
        Object o = queue[i];
        if (o.equals(element)) {
            return delete(i);
        }
    }
    return false;
}

private boolean delete(int i) {
    if (i == head) {
        poll();
        return true;
    }
    if (i == tail - 1) {
        queue[i] = null;
        tail = i;
        return true;
    }
    //head <= i < tail
    int h = head;
    int t = tail;
    int front = i - h;
    int back = t - i - 1;
    Object[] queue = this.queue;
    queue[i] = null;
    if (front < back) {
        System.arraycopy(queue, h, queue, h + 1, front);
        head = h + 1;
    } else {
        System.arraycopy(queue, i + 1, queue, i, back);
        tail = t - 1;
    }
    return true;
}

每次移除元素通过遍历获得所需要移除的游标i;如果移动的是中间元素,那么势必会在数组中间产生一个空位。所以每次通过remove移除元素都有可能造成对数组的重新分配。因而在使用队列的时候尽量避免频繁移除元素。

Tip:
1、如果使用链表实现队列的话不会存在移除的开销。

2、代码传送门(https://github.com/TangTangG/DataStructure/tree/master/src/queue)

优先队列

基本操作示意

入队

出队

数据结构——(二叉)堆

写在开始

通常在实现优先队列或者解决topN问题的时候,二叉堆这种数据结构都是一个比较好的实现方案。

树/类树

定义

(二叉)堆是一种通常采用数组存储的数据对象。

基本性质

虽然用数组实现,但是

  1. 因为其每个位于i的节点均有两个子节点分别位于2i、2i+1,所以结构上类似于树。
  2. 又因为添加元素的时候总是将树一层填满再填下一层,所以在树的结构上具有完全二叉树的性质,同时也具有类似于AVL树的平衡性。
  3. 又因为我们想要快速找出最小(大)元素,所以,最小(大)的元素应该在根上。也就是,要求任意节点应当小于(大于)其子节点,也就是,每个子树都是最小(大)堆。

1、2反映了堆的结构性;3则反映了其堆序性。

例如:堆中存储的数据如下:(来源于《数据结构与算法分析》)

其对应树是这样的:

堆的基本操作

以下操作均假设有如下结构的最小堆:

insert

将任意元素插入到堆中,我们在堆下一个可用位置创建一个空位(保持堆是完全树的特性)。如果插入元素刚好能够置于空位且不破坏堆序,那么插入完成;否则,我们需要将空位父节点的元素移入空位,这样,空位就朝着根的方向上冒一步。重复该过程,直至找到插入元素合适的位置。

以插入元素14为例,以下是插入的大抵过程:

上述过程,我们称为上滤,每次将待插入元素和其父节点比较,上冒一次(交换空位和父节点),直至找到合适位置。

delete(删除最小/大元素)

Tip:因为例子是最小堆,所以这里讲解移除的是最小元素,最大元素是一样的过程。

移除最小元,即移除根节点。每次移除将最后一个元素(记为Last)也“移除”,并在根节点创建空位。如果Last赋值到根节点刚好满足堆序的性质,那么删除完成;否则,将Last与左右儿子较小,并下潜一层,同时将较小值与空位交换。重复该过程,直至给Last找到合适的位置。

移除根节点13,大抵过程如下图所示:

上述过程,称为下滤,移除根之后创建空位,位置上“移除”掉最后一个元素,每次和左右儿子较小的交换位置,直至找到合适的位置,而后赋值。

小结

  • 无论是上滤还是下滤,首先都保证了对是一颗完全树的特性(通过每次操作最后一个元素)
  • 无论是上滤还是下滤,平均时间复杂度都为O(logN)
  • 上滤是检测是否是最小元的过程,下滤是求解最小元的过程

移除堆中任意位置的元素

讲解堆序的时候提到,堆每个子树也是一个最小(大)堆。所以从逻辑上来说,移除任意位置(记为i)的元素即是移除其某个子树的根节点(最小或者最大元)。所以首先就下滤,如果下滤之后的位置在i的下方,那么删除完成;否则,下滤后的位置就是i,那么就需要策略性将i位置上的元素上滤一次,以保证堆序性。

构建堆

  1. 构建堆可以重复执行(insert)上滤的过程,此时从任意数据源构建堆的最坏时间复杂度也为O(NlogN)。
  2. 构建堆的一般算法如下:
  • 将N个元素元素以任意顺序放入堆(树)中,保持堆的结构特性;
  • 对位于[0,N/2]的元素从N/2开始执行下滤(求得每个子树的最小元),进而保持堆序性。

一颗满二叉树的每层元素是上一层的2倍,所以N/2也就在逻辑上定位到倒数二层。相比于重复N次上滤而言,减少了对最后一层求解最小元的过程。

代码实现

可以参考这里(GitHub_Heap

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扩容的成本很高,如果知道需要存放的数据大小,尽量初始化的时候传入。