数据结构与集合源码

一、数据结构剖析

数据结构就是一种程序设计优化的方法论，研究数据的逻辑结构和物理结构以及它们之间的相互关系，并对这种结构定义相应的运算，目的是加快程序的执行速度并减少内存占用的空间;

1.数据结构的研究对象:

(1)数据间的逻辑关系:

a.集合关系:数据结构中的元素之间除了“同属一个集合"的相互关系外，别无其他关系。集合元素之间没有逻辑关系;

b.线性关系:数据结构中的元素存在一对一的相互关系;

c.树形结构:数据结构中的元素存在一对多的相互关系;

d.图形结构:数据结构中的元素存在多对多的相互关系;

(2)数据的物理结构:

数据的物理结构包括数据元素的表示和关系的表示

a.结构一:顺序结构

顺序结构就是使用一组连续的存储单元依次存储逻辑上相邻的各个元素;

优点是只需要申请存放数据本身的内存空间即可，支持下标访问也可以实现随机访问;

缺点是必须静态分配连续空间，内存空间的利用率比较低。插入或删除可能需要移动大量元素，效率比较低;

b.结构二:链式结构

不使用连续的存储空间存放结构的元素，而是为每一个元素构造一个节点。节点中除了存放数据本身以外还需要存放指向下一个节点的指针;

优点是不采用连续的存储空间导致内存空间利用率比较高，克服顺序存储结构中预知元素个数的缺点。插入或删除元素时不需要移动大量的元素;

缺点是需要额外的空间来表达数据之间的逻辑关系，不支持下标访问和随机访问。

c.结构三:索引结构

除建立存储节点信息外还建立附加的索引表来记录每个元素节点的地址。索引表由若干索引项组成。索引项的一般形式是:(关键字，地址);

优点是用节点的索引号来确定结点存储地址，检索速度快;

缺点是增加了附加的索引表，会占用较多的存储空间。在增加和删除数据时要修改索引表，因而会花费较多的时间;

c.结构四:散列结构

根据元素的关键字直接计算出该元素的存储地址，又称为Hash存储;

优点是检索、增加和删除结点的操作都很快;

缺点是不支持排序，一般比用线性表存储需要更多的空间，并且记录的关键字不能重复;

(3)运算结构

a.分配资源、建立结构、释放资源;

b.插入和删除;

c.获取和遍历;

d.修改和排序

二、常见的存储结构:链表

链表中的基本单位是节点Node

1.单向链表:

class Node{
    Object data;
    Node next;
    public Node(Object data){
     this.data = data;
    }
}
Node node1 = new Node("AA");
Node node2 = new Node("BB");
node1.next = node2;

2.双向链表

class Node{
    Node prev;
    Object data;
    Node next;
    public Node(Object data){
     this.data = data;
    }
    public Node(Node prev,Object data,Node next){
     this.prev = prev;
     this.data = data;
     this.next = next;
    }
}
Node node1 = new Node(null,"AA",null);
Node node2 = new Node(node1,"BB",null);
Node node3 = new Node(node2,"CC",null);
node1.next = node2;
node2.next = node3;

三、常见的存储结构:栈stack

栈(stack)又称为堆栈或堆叠，是限制仅在表的一端进行插入和删除运算的线性表。栈按照先进后出(FILO,first in last out)的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶。每次删除(退栈)的总是删除当前栈中最后插入(进栈)的元素，而最先插入的是被放在栈的底部，要到最后才能删除。属于抽象数据类型(ADT),可以使用数组或链表构建

class Stack{
    Object[] values;
    int size;//记录存储的元素个数
    public Stack(int length){
        values = new Object[length];
    }
    public void push(Object element){
        if(size>=values.length){
            throw new RuntimeException("栈空间已满");
        }
        values[size++] = element;
    }
    public Object pop(){
        if(size<=0){
            throw new RuntimeException("栈空间为空");
        }
        Object obj = values[size-1];
        values[size - 1] = null;
        size--;
        return obj;
    }
}

四、常见的存储结构:队列queue(先进先出，FIFO)

队列(Queue)是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。队列是逻辑结构，其物理结构可以是数组，也可以是链表。队列的修改是依先进先出(FIFO)的原则进行的。新来的成员总是加入队尾(即不允许”加塞”)，每次离开的成员总是队列头上的(不允许中途离队)，即当前“最老的“成员离队。队列同样属于抽象数据类型(ADT),可以使用数组或链表来构建

class Queue{
    Object[] values;
    int size;//记录存储的元素个数
    public Queue(int length){
        values = new Object[length];
    }
    public void push(Object element){
        if(size>=values.length){
            throw new RuntimeException("队列空间已满");
        }
        values[size++] = element;
    }
    public Object pop(){
        if(size<=0){
            throw new RuntimeException("队列空间为空");
        }
        Object obj = values[0];
        for(int i =0;i<size-1;i++){
            values[i] = values[i+1];
        }
        values[size-1]=null;
        size--;
        return obj;
    }
}

五、常见的存储结构:树和二叉树

1.名词解释:

(1)结点:树中的数据元素都称之为结点

(2)根节点:最上面的结点称之为根，一颗树只有一个根且由根发展而来，从另外一个角度来说每个结点都可以认为是其子树的根

(3)父节点:结点的上层结点

(4)子节点:节点的下层结点

(5)兄弟节点:具有相同父节点的结点称为兄弟节点;

(6)结点的度数:每个结点所拥有的子树的个数称之为结点的度；

(7)树叶:度数为0的结点,也叫作终端结点；

(8)非终端节点(分支节点):树叶以外的节点或度数不为0的节点;

(9)树的深度(或高度):树中结点的最大层次数；

(10)结点的层数:从根节点到树中某结点所经路径上的分支数称为该结点的层数，根节点的层数规定为1，其余结点的层数等于其父亲结点的层数+1;

(11)同代:在同一棵树中具有相同层数的节点;

2.二叉树的基本概念:

二叉树(Binary tree)是树形结构的一个重要类型。二叉树特点是每个结点最多只能有两棵子树，且有左右之分。许多实际问题抽象出来的数据结构往往是二叉树形式，二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。

3.二叉树的遍历:

(1)前序遍历:中左右(根左右)

即先访问很结点，再前序遍历左子树，最后再前序遍历右子树。前序遍历运算访问二叉树各结点是以根、左、右的顺序进行访问的。

(2)中序遍历:左中右(左根右)

即先中前序遍历左子树，然后再访问根结点，最后再中序遍历右子树。中序遍历运算访问二叉树各结点是以左、根、右的顺序进行访问的。

(3)后序遍历:左右中(左右根)

即先后序遍历左子树，然后再后序遍历右子树，最后访问根结点。后序遍历运算访问二叉树各结点是以左、右、根的顺序进行访问的

4.常见的二叉树:

(1)满二叉树:除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。第n层的结点数是2的n-1次方，总的结点个数是2的n次方-1

(2)完全二叉树:叶结点只能出现在最底层的两层，且最底层叶结点均处于次底层叶结点的左侧

(3)二叉排序/查找/搜索树，即为BST(binary search/sort tree)。满足如下性质:

a.若它的左子树不为空，则左子树上所有结点的值均小于它的根节点的值；

b.若它的右子树不为空，则右子树上所有结点的值均大于它的根节点的值；

c.它的左、右子树也分别为二叉排序/查找/搜索树;

d.对二叉查找树进行中序遍历可以得到有序集合。便于检索

(4)平衡二叉树:(Self-balancing binary search tree，AVL)首先是二叉排序树，此外具有以下性质:

a.它是一棵空树或它的左右两个子树的高度差的绝对值不超过1;

b.左右两个子树也都是一棵平衡二叉树；

c.不要求非叶节点都有两个子结点;

d.平衡二叉树的目的是为了减少二又查找树的层次，提高查找速度。

(5)红黑树:即Red-Black Tree,红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)

红黑树的特性如下:

a.每个节点是红色或者黑色；

b.根节点是黑色；

c.每个叶子节点(NIL)是黑色。(注意:这里叶子节点是指为空(NIL或NULL)的叶子节点)

d.每个红色节点的两个子节点都是黑色的。(从每个叶子到根的所有路径上不能有两个连续的红色节点);

e.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点(确保没有一条路径会比其他路径长出2倍)

六、ArrayList源码解析:

1.JDK7版本:

如下代码的执行，底层会初始化数组，数组的长度为10:Object elementData = new Object[10];
ArrayList<String> list = new ArrayList<>();
list.add("AA");
list.add("AA");
...
当添加第11个元素时底层的数组已满需要扩容;默认扩容为原先长度的1.5倍,并将原有数组中的元素复制到该数组中

2.JDK8版本:

如下代码的执行,底层会初始化数组:Object elementData = new Object[]{};
ArrayList<String> list = new ArrayList<>();
list.add("AA");
首次添加元素时会初始化数组
elementData = new Object[10];
list.add("AA");
...
当添加第11个元素时底层的数组已满需要扩容;默认扩容为原先长度的1.5倍,并将原有数组中的元素复制到该数组中

七、Vector源码解析，以JDK1.8为例:

如下代码的执行，底层会初始化数组，数组的长度为10:Object elementData = new Object[10];
Vector v = new Vector();
v.add("AA");
v.add("AA");
...
当添加第11个元素时底层的数组已满需要扩容;默认扩容为原先长度的2倍,并将原有数组中的元素复制到该数组中

八、LinkedList源码解析，以JDK8为例: 

LinkedList<String> list = new LinkedList<>();
list.add("AA");
将数据"AA"封装到一个Node对象1中，list对象的属性first和last属性都指向该Node对象
list.add("BB");
将数据"BB"封装到一个Node对象2中，对象1和对象2构成一个双向链表，同时last指向此Node对象2
...
LinkedList中随着元素的插入不存在扩容的现象

ArrayList底层使用数组结构，查找和添加效率高，时间复杂度为O(1),删除和插入操作效率低，时间复杂度为O(n);

LinkedList底层使用双向链表结构，删除和插入操作效率高，时间复杂度为O(1),查找和添加操作效率高，时间复杂度为O(n);

在选择了ArrayList的前提下，如果使用new ArrayList()则底层创建长度为10的数组，如果使用new ArrayList(int capacity)则底层创建长度为capacity的数组，如果开发中大体确认数组的长度建议使用给定长度的构造器，可以避免扩容。

九、HashMap源码剖析:

1.以JDK7中创建对象和添加数据过程为例:

创建对象的过程中底层会初始化数组Entry[] table = new Entry[16];
HashMap<String,Integer> map = new HashMap<>();
"AA"和78封装到一个Entry对象中，考虑将此对象添加到table数组中
map.put("AA",78);
添加/修改的过程:
将(key1,value1)添加到当前的map中:
1.调用key1所在类的hashCode()方法，计算key1对应的哈希值1;
2.此哈希值1经过某种算法(hash(哈希值1))之后得到哈希值2;
3.哈希值2经过某种算法(indexFor())之后确定(key1,value1)在数组table中的索引位置1;
    3.1如果此索引位置的数组上没有元素,则(key1,value1)添加成功;[情况1]
    3.2如果此索引位置的数组上有元素(key2,value2),则需要比较key1和key2的哈希值2;
        4.1如果key1的哈希值2与key2的哈希值2不相同,则(key1,value1)添加成功[情况2]
        4.2如果key1的哈希值2与key2的哈希值2相同,则需要比较key1和key2的equals()方法
            5.1调用equals()方法返回false:则(key1,value1)添加成功;[情况3]
            5.2调用equals()方法返回true:则key1和key2是相同的，默认情况下value1替换原有的value2;
出现情况1将(key1,value1)存放到数组的索引i的位置;
出现情况2或情况3将(key1,value1)元素与现有的(key2,value2)构成单向链表结构,(key1,value1)指向(key2,value2);
随着不断地添加元素，在满足如下的条件情况下会考虑扩容:
(size >= threshold) && (null != table[i])
当元素的个数达到临界值(数组的长度 * 加载因子)时就考虑扩容;默认扩容为原来的2倍

2.JDK8与JDK7的不同之处

(1)jdk8中当创建HashMap实例以后底层并没有初始化table数组，当首次添加(key,value)时进行判断，如果发现table尚未初始化，则对数组进行初始化;

(2)在JDK8中HashMap底层定义了Node的内部类，用于替换jdk7中的Entry内部类，意味着创建的是Node数组

(3)JDK8中如果当前的(key,value)经过一系列判断之后可以添加到当前数组的角标i中，如果此时角标i的位置上有元素，则采用尾插法将旧的元素指向新的(key,value)元素

(4)JDK8中采用数组+单向链表+红黑树的数据结构。如果数组索引i位置处的元素个数达到8并且数组的长度达到64时，就将此索引i位置上的多个元素改为使用红黑树的结构进行存储;当使用红黑树的索引i位置处的元素的个数低于6时就会将红黑树结构退化成单向链表

3.JDK8中HashMap的属性

static final int DEFAULT_INITIAL_CAPACITY=1<<4;//默认的初始容量16
static final int MAXIMUM_CAPACITY=1<<30;//最大容量1<<30
static final fLOat DEFAULT_LOAD_FACTOR =0.75f; //默认加裁因子
static finaL int TREEIFY_THRESHOLD=8;//默认树化阈值8,当链表的长度达到这个值后要考虑树化
static final int UNTREEIFY_THRESHOLD=6;//默认反树化阈值6,当树结点的个数达到此阈值后要考虑变为链表;
static final int MIN_TREEIFY_CAPACITY =64;//最小树化容量64
//当单个的链表的结点个数达到8并且table的长度达到64才会树化。
//当单个的链表的结点个数达到8但是table的长度未达到64会先扩容
transient Node<K,V>[]table;//数组
transient int size;//记录有效映射关系的对数,也是Entry对象的个数
int threshold;//阈值,当size达到阈值时考虑扩容;
final float loadFactor;//加载因子,影响扩容的顿率

十、LinkedHashMap、HashSet和LinkedHashSet源码剖析: 

1.LinkedHashMap

HashMap<String,Integer> map = new LinkedHashMap<>();
map.put("AA",123);
LinkedHashMap重写了HashMap的如下方法:
Node<K,V> newNode(int hash,K key,V value, Node<K,V> e){
    LinkedHashMap.Entry<K,V> p= new LinkedHashap.Entry<K,V>(hash, key, value,e);
    linkNodeLast(p):
    return p;
}
LinkedHashMap内部定义了一个Entry:
static class Entry<K,V> extends HashHap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash,K key,V value, Node<K,V> next){
    super(hash,key,value,next);
    }
}

2.HashSet:HashSet底层使用的是HashMap