数据结构与集合源码-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构与集合源码。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

数据结构概述

概述：

数据结构的研究对象（三个）：

逻辑结构：

物理结构（存储结构）

运算（相关算法操作）

常见存储结构：

树的理解

经典二叉树

BST（二叉排序树）

平衡二叉树（AVL）

红黑树（RBT）（复杂，不多讲，了解）

List源码解析

ArraysList在JDK7和JDK8中的代码分析

特点：

源码解析

小结：

Vector源码解析（简单介绍）

特点：

源码1.8

LinkedList源码解析

特点：

JDK8

LinkedList内部声明

启示：

Map源码解析

HashMap(非常重要)

底层使用：

HashMap中元素的特点

源码解析：

实例化：

put方法：

entry的定义：

JDK7（1.7.0_07）

添加/修改操作

扩容

JDK8

jdk7与jdk8的不同之处

LinkedHashMap\HashSet\LinkedHashSet

LinkedHashMap

HashSet和LinkedHashSet

数据结构概述

概述：

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

数据结构的研究对象（三个）：

逻辑结构：

集合结构：同属于一个集合

树形结构：一对多

线性结构：一对一

图形结构：多对多

物理结构（存储结构）

顺序结构

链式结构

索引结构（数据库）

散列结构（HashMap/HashSet）

开发中我们更容易这样理解存储结构：

线性表（一对一）链表、栈、队列等

树（一对多）B+树，二叉树

图（多对多）

哈希表（HashMap/HashSet）

运算（相关算法操作）

分配资源、建立结构、释放资源

插入和删除

获取和遍历

修改和排序

常见存储结构：

数组
- 对于基本数据类型：一个槽（slot）等于四个字节，是int，byte，short，float，char的基本单位。long、double是两个槽
- 对于引用数据类型：里面存的是一个地址，用一个槽
链表
- 链表的基本单位是：节点(Node)

单向链表

//格式
    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;

双向链表

//格式
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.next=next;
this.data=data;
}
}
//创建对象
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;

二叉树


//格式1
class TreeNode{
TreeNode left;
object data;
TreeNode right;
public TreeNode(Object data){
this.data=data;
}
public TreeNode(TreeNode left , Object data, TreeNode right){
this.left=left;
this.right=right;
this.data=data;
}
}
//格式2
class TreeNode{
TreeNode parent;
TreeNode left;
object data;
TreeNode right;
public TreeNode(Object data){
this.data=data;
}
public TreeNode(TreeNode left , Object data, TreeNode right){
this.left=left;
this.right=right;
this.data=data;
}
public TreeNode( TreeNode parent , TreeNode left , Object data, TreeNode right){
this.left=left;
this.parent = parent;
this.right=right;
this.data=data;
}
}

//创建对象1
TreeNode node1 = new TreeNode(null,"AA",null);
TreeNode leftNode = new TreeNode(null,"BB",null);
TreeNode rightNode = new TreeNode(null,"CC",null);
node1.left = leftNode;
node1.right = rightNode;
//创建对象2
TreeNode node1 = new TreeNode(null , null,"AA",null);
TreeNode leftNode = new TreeNode(node1,null,"BB",null);
TreeNode rightNode = new TreeNode(node1,null,"CC",null);
node1.left = leftNode;
node1.right = rightNode;

栈（stack、先进后出、first in last out、FILO、LIFO）

比如：穿衣，弹夹射击

属于抽象数据类型（ADT）

可以使用数组或者链表构建、

//格式（用数组实现栈）
class Stack{
Object [ ] values;
int size;//记录存储元素的个数
public Stack (int length){
values = new Object [length];
}
//只提供入栈和出栈(只能对现有元素的最后操作)
public void push(Object ele){
if(size >= values.length){
throw new RuntimeException("栈空间已满，入栈失败！");
}
values[size] = ele;
size++;
}
public Object pop( ){
if(size <= 0){
throw new RuntimeException("栈空间已空，出栈失败！");
}
Object obj = values[size-1];
values[size-1]=null;
size - -;
return obj;
}
}

队列（queue、先进先出、first in first out、FIFO）

比如：排队

属于抽象数据类型（ADT）

可以使用数组或者链表构建

//格式（用数组实现队列）
class Queue{
Object [ ] values;
int size;//记录存储元素的个数
public Queue (int length){
values = new Object [length];
}
//添加
public void add(Object ele){
if(size >= values.length){
throw new RuntimeException("队列已满，添加失败！");
}
values[size] = ele;
size++;
}
public Object get( ){
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;
}
}

真实的存储结构：就是链表和数组，其他的全可以有他们构建

树的理解

结点：树中的数据元素都称为节点
根节点：最上面的结点称之为根
父节点：结点的上层节点
子节点：节点的下层节点
节点的度数：每个结点所拥有的字数的个数
树叶：度数为0的结点，也叫终端节点
树的深度：树中节点的最大层数
节点的层数：根为1，每下一层加一
同代：同一棵树中具有相同层数的结点

经典二叉树

数据结构与集合源码,数据结构,java,jvm

BST（二叉排序树）

数据结构与集合源码,数据结构,java,jvm

平衡二叉树（AVL）

数据结构与集合源码,数据结构,java,jvm

红黑树（RBT）（复杂，不多讲，了解）

数据结构与集合源码,数据结构,java,jvm

List源码解析

ArraysList在JDK7和JDK8中的代码分析

特点：

1.实现了List接口，存储有序、可以重复的数据；

2.底层使用的Object[]数组存储；

3.线程不安全的

源码解析

JDK（1.7.0_07）

源码

1.如下代码会被执行，底层会初始化数组，数组长度为0

1.Object[] elementData = new Object[10];

2.Arrayslist<String> list = new ArrayList<>();

3.list.add("AA");//elementData[0] = "AA";

4.list.add.........(一直加到第11个元素的时候)

5.//底层的elementData数组已满，则需要扩容。默认扩容为原来长度的1.5倍。并将原有的数组中的元素复制到新的数组

5.底层的elementData数组已满后，则需要扩容。默认扩容为原来长度的1.5倍。并将原有的数组中的元素复制到新的数组

JDK(1.8.0_271）

源码（区别为红色部分）1.如下代码将被执行：

1.Object[] elementData = new Object[]{};

2.Arrayslist<String> list = new ArrayList<>();

3.list.add("AA");//首次添加元素时，会初始化数组elementData = new elementData[10];elementData[0] = ="AA";

4.list.add.........(一直加到第11个元素的时候)

5.底层的elementData数组已满、则需要扩容，默认扩容为原来长度的1.5倍。并将原有的数组元素复制到新的数组中

小结：

JDK7版本中，ArrayList类似于饿汉式；JDK8中ArrayList类似于懒汉式

Vector源码解析（简单介绍）

特点：

1.实现了List接口，存储有序的可以重复的数据

2.底层使用Object[]数组存储

3.线程安全的

源码1.8

Vector vector = new Vector();//底层初始化数组，长度为10的Object数组

vector.add("AA");//elementData[0] = "AA";........

当添加到第11个元素的时候，底层的elementData数组已满，需要扩容，默认扩容为原来的2倍。并将原有数组中的元素复制到新的数组中

LinkedList源码解析

特点：

实现了List接口，存储有序的、可以重复的数据；底层使用双向链表；线程不安全的

JDK8

源码

LinkedList<String> list = new LinkedList<>();\\底层啥也没做就是给你声明了一下

list.add("AA");\\将数据"AA"封装到Node对象1中，list对象的属性first、last都指向此对象

list.add("BB");\\讲数据"BB"封装到Node对象2中，对象1和1对象2构成一个双向链表，同时last指向此Node对象2 .......

因为LinkedList使用的是双向链表，不需要考虑扩容问题

LinkedList内部声明

public static class Node<E>{E item;Node<E> next;Node<E> prev;}

启示：

1.Vector基本不用

2.ArrayList底层使用的是Object[]数组结构，查找和添加（尾插法）效率高，时间复杂度为O(1);删除和插入操作效率低，时间复杂度为O(n);

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

4.在选择了Arraylist的前提下，new ArrayList()；底层创建长度为10的数组。new ArrayList(int capacity)：底层创建指定capacity长度的数组。如果开发中大体确定数组的长度，推荐使用new ArrayList(int capacity);

Map源码解析

HashMap(非常重要)

底层使用：

数组+单向链表+红黑树存储（jdk8）

HashMap中元素的特点

HashMap中的所有的key是不可重复的，无序的。所有的key构成一个set集合。——>key所在的类要重写hashCode（）和equals（）两个方法
HashMap中所有的value彼此之间是可重复的，无序的。所有的value构成一个Collection集合——>所在的类要重写equals（）方法
HashMap中的一个key-value，就构成了一个Entry。
HashMap中所有的Entry彼此之间是不可重复的，无序的。所有的Entry就构成了一个set集合。

源码解析：

实例化：

数据结构与集合源码,数据结构,java,jvm

put方法：

数据结构与集合源码,数据结构,java,jvm

entry的定义：

数据结构与集合源码,数据结构,java,jvm

JDK7（1.7.0_07）

//创建对象的过程中，底层会初始化数组Entry [ ] table = new Entry [16];
HashMap< String , Integer > map = new HashMap< >( );
……
map.put("AA",78);//"AA"和78封装到一个Eentry对象中，考虑将此对象添加到table数组中
……

添加/修改操作

将(key1,value1)添加到当前的map中。
首先，需要调用key1所在类的hashCode( )方法，计算key1对应的哈希值1，此哈希值1经过某种算法( hash( ) )之后，得到哈希值2
哈希值2再经过某种算法(IndexFor( ) )之后，就确定了(key1,value1)在数组table中的索引位置i；
- 如果此索引位置i的数组上没有元素，则(key1,value1)添加成功。情况1
- 如果此索引位置i的数组上有元素(key2,value2),则继续比较key1和key2的哈希值2 ----->哈希冲突
  - 如果key1的哈希值2与key2的哈希值2不相同，则(key1,value1)添加成功。情况2
  - 如果key1的哈希值2与key2的哈希值2相同，则需要继续比较key1和key2的equals( )。要调用key1的所在类的equals( ),将key2作为参数传递进去
    - 调用equals( ),返回false：则(key1,value1)添加成功。情况3
    - 调用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 ])
- 当元素的个数达到临界值（--->数组的长度 * 加载因子）时就考虑扩容。默认的临界值=16*0.75-->12
- 默认扩容为原来的2倍.

JDK8

//属性/字段
    static final int DEFAULT_CAPACITY = 1<<4;默认初始容量
    static final int MAXIMUM_CAPACITY = 1<<30;最大容量
    static final float  DEFAULT_LOAD_FACTOR = 0.75f ;默认加载因子
    static final float  TREEIFY_THRESHOLD = 8 ;默认树化阈值8
    static final float  UNIREEIFY _THRESHOLD = 6 ;默认反树化阈值6
    static final int MIN_TREEIFY_CAPACITY = 64;最小树化容量
    transient Node<K,V>[ ] table;//数组
    transient int size;//对象的个数
    int threshold;//阈值，当size达到时，考虑扩容
    final float loadFactor;//加载因子

jdk7与jdk8的不同之处

1.在jak8中我们创建了HashMap实例以后，底层并没有初始化table数组。当首次添加(key,value)时，进行判断，如果发现table尚未初始化，则对数组进行初始化
2.在jdk8中，HashMap底层定义了Node内部类，替换jdk7中的Entry内部类。意味着我们创建的数组是Node类型的数组（只是名字变了）
3.在jdk8中，如果当前的(key，value)经过一系列判断之后，可以添加到当前的数组角标i中，如果此时i位置上有元素，jdk7中是头插法，jdk8中是尾插法.
jdk8：数组+单向链表+红黑树存储
- 什么时候使用单向链表变为红黑树：如果数组索引i位置上的元素的个数达到8个，并且数组的长度达到64，我们就将此索引i位置上的多个元素改为使用红黑树的结构进行存储（为什么修改呢？红黑树进行put/get/remove操作的时间复杂度为O(logn),比单向链表的时间复杂的O(n)的好，性能高）
- 什么时候使用红黑树变为单向链表：当使用红黑树的索引i位置上的元素的个数低于6的时候，就会将红黑树结构退化为单向链表。节省空间(TreeNode>链表)
jdk7中：数组+单向链表；