写在前面

数据结构作为编程者最基础的内功，无论何时都是需要巩固的。万丈高楼平地起，了解Java内部的基本结构，能对Java的框架有更深刻的认识。

在Java的数据结构中，最基本的无非就是数组和链表，其他类型无非就是再次基础上扩充其他数据内容。

在本文中，主要对各个Java类的数据存储、默认容量和扩容机制及扩容时的边界问题（如果需要扩容）、线程安全性、查询插入以及删除的时空间性能做对比分析与总结。

 

数据结构概述

向量：实际上就是一个一维的数组，其创建时会被分配到一块连续的内存地址上。内存总是会读取相近的地址，就读取来说向量从内存中读取的时间是快于列表的。向量分无序向量和有序向量。对于有序向量，在查找（有序向量在插入或删除时都需找到插入或删除的下标）时可以通过二分查找，将线性次查找缩短至对数次查找，O(n) ->O(logn)。

队列：一种先进先出（FIFO）的数据结构，是一组按顺序维护的实体集合，一般添加元素到序列的末尾称为入队，而删除序列的第一个元素称为出队。

栈：一种后进先出（LIFO）的数据结构，栈有两种操作，压栈或入栈，添加元素到序列的顶部即栈顶。出栈或退栈，删除最新加入栈中的元素也就是栈顶元素。

列表：一个由多个单节点在逻辑上链接组成的线性序列，是一种采用动态存储的典型结构。由于其不固定的插入或删除操作，其节点的物理地址不一定是相互紧邻的。节点在逻辑上的前一个节点称为前驱，后一个节点成为后继。

散列：对原关键码进行散列函数的运算后，映射到哈希表的某个位置。

常用散列函数：

整除留余：根据散列可能的大致分布，选择一个余数尽可能分布均匀的素数作为除数。

平方取中：对原关键码平方，选取中间部分的若干数字作为散列码。取中间位是为了原关键码的各数位能对最终的散列地址又尽可能接近的影响。

折叠汇总：将关键码分割成等宽的若干段，顺序或者逆序的求其总和。例如：关键码123456789，先将其分为均等长度的位数，对其进行顺序求和123 + 456 + 789  或之字求和 123 + 654 + 789 。或者将该数的二进制位分为均等长度的二进制码，将所有二进制码异或（^ 异或运算，两个位相同为0，否则为1）后得到地址。

树

树的深度：对于任意节点n,n的深度为从根到n的唯一路径长，根的深度为0。

树的高度：对于任意节点n,n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0。

树的遍历：

前三种可以用栈（先进后出）存储需要访问的节点。层次遍历可以用队列存储需要访问的节点。

前序遍历 根->左->右

中序遍历 左->根->右

后续遍历 左->右->根

层次遍历 从根节点开始，进行每一层的遍历，可用队列存储需要遍历的数据（将根节点入队，随后遍历队列，出队时将出队节点的左右子树入队，迭代至队列对空）。

二叉树：度最大为2的树，称为二叉树，二叉树是树的一个特例，但是几乎可以表示其他所有的树。

满二叉树：二叉树中所有叶子的深度完全相等。

完全二叉树：完全二叉树是由满二叉树而引出来的。对于深度为K的，有N个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

真二叉树：每个节点都恰好有0个或2个孩子的树。

霍夫曼树：每个节点要吗没有子节点，要么有两个子节点。

二叉搜索树（BST Binary Search Tree）：

是指一棵空树或者具有下列性质的二叉树：1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；2.若任意节点的右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值；3. 任意节点的左、右子树也分别为二叉查找树；

平衡二叉搜索树（BBST Balanced Binary Search Tree，AVl树是BBST的一种）：非绝对平衡树。所有叶子的深度趋于平衡，更广义的是指在树上所有可能查找的均摊复杂度偏低。

红黑树：BBST的一种，查询与二叉树相同，但是在插入和删除时操作的时间复杂度为O(1)。

B-树：m阶的B树，即m路的平衡搜索树（m>=2），是一种满足大数据的读取的数据结构。每个节点包含多个关键码（用有序数组存储且在整体上满足二叉搜索树的定义），每个节点有多个分支（用数组存储，每个分支与关键码相对应，每个关键码下标n的左右分支为n, n+ 1）。外部节点的深度统一相等（外部节点，即相对内存来说，外部节点的数据存放于磁盘里），所有叶节点的深度统一相等（所有叶节点相同高度）。树高h = 外部节点的深度。

针对访问效率的访问问题，使得内存操作和外存操作的次数大致相当（外存操作即磁盘操作，读取外存的节点数据。和内存操作即在内存中访问有序数组）。B-树的特性，宽度较宽，高度较低，足以满足次操作。

m阶B-树，每个节点的分支a的个数范围为： m/2 <= a <= m ，根节点为 2 <= a <= m。相当于，每个节点的关键码k为： m/2 <= k <= m-1，根节点为 2 <= a <= m-1。

m阶B-树每个节点的分支不超过m个，节点的关键码不超过m-1个。同事树根的最小分支不低于2，其他节点的分支不低于 m/2。m阶B-树又称为(m/2, m)树， 即常见的（2，4）树，（2，3）树，（3，5）树等等。

 

 

Java中所实现的数据结构分析

 

Vector:向量

底层存储：数组。

支持随机访问，随机访问速度快，但是在插入以及删除时需要移动其他元素，插入删除速度较慢。synchronized修饰主要方法，线程安全。

默认容量：10。扩容机制：可在初始化时用户设置每次扩容大小。默认扩容为当前2倍。

查询：遍历查找，没找到返回-1。时间复杂度最好情况为O(1)，总体时间复杂度为线性分布O(n)。

插入：扩容判断后，直接插入到最后一个元素后面。扩容情况下，需要新建一个数组并复制其内容，时间复杂度O(n)，插入时间复杂度为O(1)，如果自定义的capacityIncrement设置太小时，可能每次插入都需要进行一次扩容，导致效率变低。当扩容机制合理时，一般情况插入时间复杂度为O(1)。

    public synchronized boolean add(E e) {modCount++;// 动态扩容ensureCapacityHelper(elementCount + 1);elementData[elementCount++] = e;return true;}private void ensureCapacityHelper(int minCapacity) {// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity);}private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;// 初始化时的扩容量，如果capacityIncrement 为空，则增加当前容量大小的容量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);}

删除：向量的删除有两种，随机删除（根据下标删除）和指定删除。随机删除将直接通过下标定位元素，通过System.arraycopy将待删除元素后面的所有元素向前移动一位，直接覆盖待删除元素，此时时间复杂度最好情况为O(1)，即删除最后一位，一般情况为线性复杂度O(n)，随数组大小增加移动元素的个数也相应增加；指定删除则需要事先遍历，查找到其下标后再删除。查询所需时间O(n), 删除时间O(n)，总体时间复杂度为O(2n)，即O(n)。

    // 随机删除public synchronized E remove(int index) {modCount++;if (index >= elementCount)throw new ArrayIndexOutOfBoundsException(index);E oldValue = elementData(index);int numMoved = elementCount - index - 1;// 移动位数大于0时，将删除元素后的所有元素向前移动。if (numMoved > 0)System.arraycopy(elementData, index+1, elementData, index,numMoved);elementData[--elementCount] = null; // Let gc do its workreturn oldValue;}// 指定删除public synchronized boolean removeElement(Object obj) {modCount++;int i = indexOf(obj);if (i >= 0) {removeElementAt(i);return true;}return false;}public synchronized void removeElementAt(int index) {modCount++;if (index >= elementCount) {throw new ArrayIndexOutOfBoundsException(index + " >= " +elementCount);}else if (index < 0) {throw new ArrayIndexOutOfBoundsException(index);}int j = elementCount - index - 1;if (j > 0) {System.arraycopy(elementData, index + 1, elementData, index, j);}elementCount--;elementData[elementCount] = null; /* to let gc do its work */}

 

Stack: 栈

继承于Vector，后进先出。

容量默认10，线程安全，操作基本上与Vector相同。栈的插入与删除都只允许在栈顶操作，只有栈顶对外的可见。

查询search：从最后一个元素开始遍历，未找到返回-1.

入栈/压栈push：同Vector。

出栈/弹出pop：与Vector相同，但每次都删除最后一个元素。时间复杂度为O(1)

    public synchronized E pop() {E obj;int len = size();obj = peek();removeElementAt(len - 1);// 调用Vector的方法return obj;}

 

Queue: 队列

接口，主要实现类为LinkedList。

ADT：   boolean offer(E value) 入队； E poll() 出队；E peek() 查看队首元素；

 

ArrayList: 数组列表

底层存储：数组。

支持随机访问，随机访问速度快，但是在插入以及删除时需要移动其他元素，插入删除速度较慢。线程不安全。

默认容量：10。扩容机制：不可自定义扩容大小。默认扩容为当前1.5倍。

查询：遍历查找，没找到返回-1。时间复杂度最好情况为O(1)，总体时间复杂度为线性分布O(n)。

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

插入：数组存储的类，插入过程都大致相当。ArrayList与Vector插入的区别就在扩容的大小，ArrayList的扩容是不允许用户自定义的，在不超过最大容量的情况下，每次扩容都是当前容量的1.5倍（x1.5）。

    private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;// 当前容量 + （当前容量x 1/2）// 右移，相当于除2int 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);}

删除：ArrayList的删除与Vector类似，也有随机删除和指定删除。删除方法相同。

    // 随机删除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 workreturn oldValue;}// 指定删除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 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}

 

LinkedList: 双向链表

底层存储：链表。

LinkedList是线程不安全的。

LinkedList支持双向操作，可以对链表的第一个节点和最后一个节点进行插入和删除操作。支持随机查找（伪，需要对链表进行遍历，速度较慢），LinkedList由于使用链表存储，其插入和删除都为常数的时间，速度快。

与ArrayList对比：对于查询，由于内存会一次读取地址毗邻的数据，LinkedList遍历或访问元素的速度会比ArrayList更慢。LinkedList的插入时间不定，所以每次插入一个节点后，其地址有可能是不相邻的。而ArrayList使用数组作为数据存储，在数组创建时它的地址总是临近的；对于插入和删除，LinkedList插入时间复杂度总为常数次即O(1)，指定删除时需要遍历链表O(n)，而ArrayList的插入有时需要扩容，删除总是需要先遍历查找到指定元素后移动元素，就此来说ArrayList的插入删除操作的时间消耗是多于LinkedList的；空间上，LinkedList能够动态扩容，不需要事先指定内存空间，因此能很好地利用空间，不会造成空间上的浪费（ArrayList一开始就会分配好空间，很多空间实际上是很长时间不用的），不过LinkedList需要额外的空间来存储节点之间的逻辑关系。

查询：从队首或队尾遍历整个链表进行查找，没找到返回-1。时间复杂度最好情况为O(1)，总体时间复杂度为线性分布O(n)。

    public int indexOf(Object o) {int index = 0;if (o == null) {for (Node<E> x = first; x != null; x = x.next) {if (x.item == null)return index;index++;}} else {for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item))return index;index++;}}return -1;}

普通插入add：插入链表的末尾，时间复杂度为O(1)。

    public boolean add(E e) {linkLast(e);return true;}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;elsel.next = newNode;size++;modCount++;}

普通删除remove：由于LinkedList支持随机访问，因此也适用于删除操作。时间复杂度O(n)。

    // 随机删除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;}// 解除被删除节点与前驱和后继之间的联系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;}

入队offer：总是插入到链表的尾部，时间复杂度O(1)。调用add()方法。

出队poll：总是删除链表的第一个节点，时间复杂度O(1)。

    public E poll() {final Node<E> f = first;return (f == null) ? null : unlinkFirst(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 GCfirst = next;if (next == null)last = null;elsenext.prev = null;size--;modCount++;return element;}

HashSet: Hashtable: LinkedHashSet: HashMap: