每日一题面试题

问： "equals"与"=="、"hashCode"的区别，重写"equals"时为什么一定要重写"hashcode"?

答： 1、 "equals":比较两个对象的内容是否相等,但默认情况下(即没有重写equals方法时),作用和"=="相同,判断对象的引用是否相同

2、"==":比较对象的引用是否相等(即判断两个对象是否指向同一个内存地址)、比较基本数据类型的值是否相等

3、"hashcode":获取对象的哈希码(整数值),哈希码是根据对象的内容生成的

前言

1、数组

定义：一组相同数据类型元素的集合。

优点： 1、按照索引查询速度快 2、按照索引遍历数组方便

缺点： 1、数组的大小是固定的 2、数组只能存储相同的数据类型 3、添加、删除比较慢

2、线性表

定义：零个或多个数据元素的有限序列，例如：栈、链表。

3、栈

定义：限定只能在表的一端进行插入和删除的线性表。在表中，允许插入和删除的一端称为"栈顶",另一端称为"栈底"；"出栈"在栈顶中删除元素， "入栈"在 栈顶中插入元素。 特点：先进后出或者后进先出。

4、队列

定义：只允许在一端进行插入操作，在另外一端进行删除操作的线性表 特点：先进先出或后进后出

5、双端队列

定义：它具有栈和队列性质的抽象数据类型，表的两端都可以插入、删除约束，它的底层是使用数组来实现的

双端队列疑问

1、 双端队列是线性安全的吗？ 2、双端队列的插入和删除方法有哪些？为什么说它具有数组和栈的特性？ 3、双端队列是有界面的吗? 4、okhttp中为什么使用双端队列？

正文

数据结构

双端队列源码分析

主要属性

// 存储元素的数组
transient Object[] elements; 
// 队列头位置
transient int head;
// 队列尾位置
transient int tail;
// 最小初始容量
private static final int MIN_INITIAL_CAPACITY = 8;

从属性分析可知，双端队列是使用数组来存储元素的。头尾指针有什么用处呢？请看下面分析。

主要构造方法

// 默认构造方法
public ArrayDeque() {
    elements = new Object[16];
}
// 指定元素个数初始化
public ArrayDeque(int numElements) {
    allocateElements(numElements);
}
// 将集合c中的元素初始化到数组中
public ArrayDeque(Collection<? extends E> c) {
    allocateElements(c.size());
    addAll(c);
}
// 初始化数组
private void allocateElements(int numElements) {
    elements = new Object[calculateSize(numElements)];
}
// 计算容量 |:按位或 创建容量为2倍数的数组
private static int calculateSize(int numElements) {
    //MIN_INITIAL_CAPACITY = 8
    int initialCapacity = MIN_INITIAL_CAPACITY;
    if (numElements >= initialCapacity) {
        initialCapacity = numElements;
        initialCapacity |= (initialCapacity >>>  1);
        initialCapacity |= (initialCapacity >>>  2);
        initialCapacity |= (initialCapacity >>>  4);
        initialCapacity |= (initialCapacity >>>  8);
        initialCapacity |= (initialCapacity >>> 16);
        initialCapacity++;
        if (initialCapacity < 0) initialCapacity >>>= 1;
    }
    return initialCapacity;
}

从构造方法分析得出，默认构造方式创建了固定长度为5的数组elements，有元素时，元素个数小于8时，则创建固定长度为8的数组，若大于8时，则创建大于此数的最小2的倍数固定长度的数组。如元素的个数为8，则数组长度为2 * 2 * 2 * 2=16 (为什么是2的倍数，请看下面的数组插入和删除源码分析)

主要方法

// *** 队列中的方法 ***
// 添加元素到队列头
void addFirst(E e);
// 添加元素到队列尾
void addLast(E e);
// 从队列头移除元素
E removeFirst();
// 从队列尾移除元素
E removeLast();

// *** 栈方法 ***
// 入栈，等于addFirst(e)
void push(E e);
// 出栈，等于removeFirst()
E pop();

// *** Collection中的方法 ***
// 删除指定元素，等于removeFirstOccurrence(o)
boolean remove(Object o);
// 检查是否包含某个元素
boolean contains(Object o);
// 元素个数
public int size();
// 迭代器
Iterator<E> iterator();

doubleCapacity方法(扩容机制)

//扩容机制
private void doubleCapacity() {
    //如果头指针head等于尾指针tail
    assert head == tail;
    int p = head;
    int n = elements.length;
    int r = n - 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);
    Arrays.fill(elements, null);
    //elements数组转化成新的数组
    elements = a;
    head = 0;
    tail = n;
}

从doubleCapacity方法中，可以看到头尾(head、tail)指针的作用是判断存储元素的数据是否需要扩容，若需要扩容则将存储元素的数组长度扩为原来数组长度的一倍。

入队列

-addFirst方法(头部入队列)

public void addFirst(E e) {
    //e为null时抛出异常
    if (e == null) throw new NullPointerException();
    // &运算和%  在2的倍数中(K)，n & (K-1) = n % K
    elements[head = (head - 1) & (elements.length - 1)] = e;
    if (head == tail) doubleCapacity();
}

从addFirst源码中分析得出，元素在队列头部添加是通过计算下标位置进行插入数组中的。因为数组的长度为2的倍数，所以(head = (head - 1) & (elements.length - 1)) == (head = (head - 1) % elements.length)，从数组尾部向头部移动添加数据。为什么使用&运算为不使用%运算？这是因为计算机使用2进制来存储元素的，&运算比%运算的效率快。

-addLast方法(尾部入队列)

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

从数组尾部添加元素和从数组头部添加元素的逻辑差不多，只是添加元素下标的计算是数组的尾部而已， 它是从数组头部向尾部移动添加数据。

出队列

-removeFirst方法(头部出队列)

public E removeFirst() {
    E x = pollFirst();
    if (x == null)
        throw new NoSuchElementException();
    return x;
}

//获取头部的元素
public E pollFirst() {
    final Object[] elements = this.elements;
    final int h = head;
    @SuppressWarnings("unchecked")
    E result = (E) elements[h];
    // Element is null if deque empty
    if (result != null) {
        elements[h] = null; // Must null out slot
        //头部指针修改为旧头部指针+1
        head = (h + 1) & (elements.length - 1);
    }
    //返回头部元素
    return result;
}

通过头部指针获取头部元素，并将数组中该下标的元素置nul，头部指针往后移一位。

-removeLast方法(尾部出队列)

public E removeLast() {
    E x = pollLast();
    if (x == null)
        throw new NoSuchElementException();
    return x;
}
public E pollLast() {
    //获取最后添加元素的下标
    int t = (tail - 1) & (elements.length - 1);
    @SuppressWarnings("unchecked")
    E result = (E) elements[t];
    if (result == null)
        return null;
    elements[t] = null;
    tail = t;
    return result;
}

从尾部移除元素和从头部移除元素的逻辑差不多，只是计算逻辑尾部元素的下标不同而已。

入栈

-push方法

public void push(E e) {
    addFirst(e);
}

从push添加数据源码可以看到，它的实现是直接调用从队头入队(addFirst)方法。

出栈

-pop方法

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

从pop删除数据源码可以看到，它的实现是直接调用从队头出队(removeFirst)方法。

总结

1. 双端队列(arrayDeque)底层是使用数组来实现元素存取的
2. 双端队列(arrayDeque)的出队入队是通过头尾指针循环利用数组实现的
3. 双端队列(arrayDeque)出队入队的下标是通过头尾指针和数组长度进行与(&)运算确定
4. 双端队列(arrayDeque)添加元素时，容量不足会扩容，每次扩容容量为上次容量的一倍
5. 双端队列(arrayDeque)扩容的判断是通过头尾指针是否相同进行判断的
6. 双端队列(arrayDeque)可以直接作为栈使用，入栈和出栈的原理和从头部入、出队列原理相同
7. 双端队列(arrayDeque)不是线程安全的
8. 由于双端队列(arrayDeque)的效率高(增、删的时间复杂度为1)，所以okHttp使用了双端队列