Java中的数据结构与集合源码

目录

一、数据结构

1.1 数据结构概念

1.2 研究对象

1.3 常见存储结构

1.3.1 数组

1.3.2 链表

1.单向链表

2.双向链表

1.3.3 二叉树

1.3.4 栈（FILO，先进后出）

1.3.5 队列（FIFO，先进先出）

二、集合源码

2.1 List

2.1.1 ArrayList

2.1.2 Vector

2.1.3 Linkedlist

2.1.4 小结

2.2 Map

2.2.1 HashMap

2.2.2 LinkedHashMap

2.3 Set

2.4 练习

---

一、数据结构

1.1 数据结构概念

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

1.2 研究对象

研究对象1:数据之间的逻辑关系

• 集合结构
• 线性结构:一对一关系
• 树形结构:一对多关系
• 图形结构:多对多关系

研究对象2:数据的存储结构(或物理结构)

• 顺序结构
• 链式结构
• 索引结构
• 散列结构

研究对象3:相关的算法操作

• 分配资源，建立结构，释放资源
• 插入和删除
• 获取和遍历
• 修改和排序

在开发中，习惯上如下的方式理解存储结构:

• 线性表(一对一关系):一维数组、单向链表、双向链表、栈、队列
• 树(一对多关系):各种树。比如:二叉树、B+树
• 图(多对多关系)
• 哈希表:比如:HashMap、HashSet

1.3 常见存储结构

1.3.1 数组

• 数组是一个容器，用于存储一组相同类型的数据。数组在创建时需要指定大小，并且大小在数组创建后不能更改。

大体格式：

// 声明数组
int[] numbers; // 推荐的方式
int numbers[]; // 另一种方式// 初始化数组
numbers = new int[5]; // 创建一个长度为5的整数数组// 也可以在声明时直接初始化
int[] numbers = new int[]{1, 2, 3, 4, 5}; // 显式初始化
int[] numbers = {1, 2, 3, 4, 5}; // 简化的初始化

优点

• 访问速度快：由于数组的元素是连续存储的，因此可以通过索引快速访问元素。
• 内存利用效率高：数组在内存中是连续存储的，减少了内存碎片。

缺点

• 固定大小：数组的大小在创建后不可更改，可能导致空间浪费或不足。
• 插入和删除操作复杂：在数组中插入或删除元素需要移动元素，效率较低。

1.3.2 链表

链表中的基本单位;Node

1.单向链表

结构

• 数据域：存储节点的数据。
• 指针域：指向下一个节点的引用。

特点

• 单向性：每个节点只能向后访问，不能向前访问。
• 动态大小：链表的大小可以动态调整，适合需要频繁插入和删除的场景。
• 不连续存储：链表的节点在内存中不必连续存储。

图示：

大体格式：

//创建对象
public class Test1{ @Test public void test(){ Node node1 = new Node("Aa"); Node node2 = new Node("Bb"); node1.next = node2; }
}
//节点类
class Node{Object date; //数据域Node next;//指针域public void setDate(Object date) {this.date = date;}
}

应用场景

• 当需要频繁插入和删除元素时。
• 对于元素数量不确定的场景，链表比数组更合适。

2.双向链表

结构

• 数据域：存储节点的数据。
• 前驱指针：指向前一个节点的引用。
• 后继指针：指向下一个节点的引用。

特点

• 双向性：每个节点可以向前和向后访问，操作灵活。
• 动态大小：动态调整链表的大小。
• 占用空间多：相较于单向链表，节点需要更多的空间来存储前驱指针。

图示

大体格式：

public class Dtest {//创建对象@Testpublic void test(){DNode node1 = new DNode("Aa",null,null);DNode node2 = new DNode("Bb",null,node1);DNode node3 = new DNode("Cc",null,node2);node1.next = node2;node2.next = node3;}  }
class DNode {Object data;   // 数据域DNode next;    // 后继指针DNode prev;    // 前驱指针public DNode(Object data) {this.data = data;}public DNode(Object data, DNode next, DNode prev) {this.data = data;this.next = next;this.prev = prev;}
}

应用场景

• 当需要频繁进行前向和后向遍历时。
• 适用于需要双向操作的场景，例如浏览器的前进和后退按钮。

1.3.3 二叉树

两个子节点被称为左子节点和右子节点。

节点：

• 数据
• 指向左子节点的引用
• 指向右子节点的引用

二叉树的遍历：

• 前序遍历：根 -> 左 -> 右
• 中序遍历：左 -> 根 -> 右
• 后序遍历：左 -> 右 -> 根
• 层序遍历：逐层访问，每一层从左到右。

大体格式：

class TreeNode {TreeNode left;Object date;TreeNode right;public TreeNode(Object date) {this.date = date;}public TreeNode(Object date, TreeNode left, TreeNode right) {this.date = date;this.left = left;this.right = right;}
}// 测试
public class BinaryTreeTest {@Testpublic void test1(){TreeNode treeNode = new TreeNode("A",null,null);TreeNode leftNode = new TreeNode("B",null,null);TreeNode rightNode = new TreeNode("V",null,null);treeNode.left = leftNode;treeNode.right = rightNode;}
}

1.3.4 栈（FILO，先进后出）

 栈的基本概念

• 栈的特性：

  • 只能在栈顶进行插入和删除操作。
  • 具有栈顶和栈底两个指针，栈顶指针指向最近添加的元素，栈底指针指向最早添加的元素。

• 基本操作：

  • push：将元素压入栈顶。
  • pop：将栈顶元素弹出并返回。
  • peek（或 top）：查看栈顶元素但不弹出。
  • isEmpty：检查栈是否为空。
  • size：获取栈中元素的数量。

图示

使用数组实现栈

class ArrayStack {private int maxSize; // 栈的最大容量private int[] stack; // 存放栈元素的数组private int top; // 栈顶指针// 构造函数public ArrayStack(int size) {this.maxSize = size;this.stack = new int[maxSize];this.top = -1; // 初始时栈为空}// 入栈public void push(int value) {if (top >= maxSize - 1) {throw new RuntimeException("栈空间已满，入栈失败！");}stack[++top] = value;}// 出栈public int pop() {if (isEmpty()) {throw new RuntimeException("栈空间已空，出栈失败！");}return stack[top--];}
}

使用链表实现栈

class Node {int data;Node next;public Node(int data) {this.data = data;this.next = null;}
}class LinkedListStack {private Node top; // 栈顶节点// 构造函数public LinkedListStack() {this.top = null;}// 入栈public void push(int value) {Node newNode = new Node(value);newNode.next = top;top = newNode;}// 出栈public int pop() {if (isEmpty()) {throw new RuntimeException("栈空间已空，出栈失败！");}int value = top.data;top = top.next;return value;}
}

1.3.5 队列（FIFO，先进先出）

图示

代码实现：

import java.util.LinkedList;
import java.util.Queue;public class QueueExample {public static void main(String[] args) {// 创建一个队列Queue<Integer> queue = new LinkedList<>();// 插入元素System.out.println("入队操作：");queue.offer(10);queue.offer(20);queue.offer(30);System.out.println("队列状态：" + queue);// 删除元素System.out.println("\n出队操作：");int removedElement = queue.poll(); // 从队列中删除并返回队头元素System.out.println("出队元素：" + removedElement);System.out.println("队列状态：" + queue);// 查看队头元素但不删除System.out.println("\n查看队头元素：");int headElement = queue.peek(); // 查看队头元素System.out.println("队头元素：" + headElement);System.out.println("队列状态：" + queue);// 遍历队列System.out.println("\n遍历队列：");for (Integer element : queue) {System.out.println(element);}}
}

二、集合源码

2.1 List

2.1.1 ArrayList

1.ArrayList的特点:

• 实现了List接口，存储有序的、可以重复的数据
• 底层使用0bject[]数组存储
• 线程不安全的

2.ArrayList源码解析:

2.1 jdk7版本:(以jdk1.7.0_07为例)

/*如下代码的执行:底层会初始化数组，数组的长度为10。

0bject[]elementData= new 0bject[10];*/

ArrayList<String> list = new ArrayList<>();
list.add("AA");   //elementData[0]= "AA";

list.add("BB");   //elementData[1]= "BB";

2.2 jdk8版本:(以jdk1.8.0_271内例)

//如下代码的执行:底层会初始化数组，即:0bject[]elementData= new 0bject[]{};
ArrayList<String> list =new ArrayList<>();
List.add("AA");

//首次添加元素时，会初始化数组elementData= new 0bject[10]; elementData[0]="AA

List.add("BB");       //elementData[1]="BB";

小结：

• jdk1.7.0_07类似 饿汉式
• jdk1.8.0_271类似 懒汉式
• 两者都是：当要添加第11个元素的时候，底层的elementData数组已满，则需要扩容。默认扩容为原来长度的1.5倍。并将原有数组中的元素复制到新的数组中。

2.1.2 Vector

1.Vector的特点:

• 实现了List接口，存储有序的、可以重复的数据
• 底层使用0bject[]数组存储
• 线程安全的

2.Vector源码解析:(以jdk1.8.0-271为例)

Vector v= new Vector();//底层初始化数组，长度为10.0bject[]elementData = new bject[10];
v.add("AA");//elementData[0] = "AA":
v.add("BB");//elementData[1]="BB";

当添加第11个元素时，需要扩容。默认扩容为原来的2倍

2.1.3 Linkedlist

1.LinkedList的特点:

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

2.LinkedList在jdk8中的源码解析:

LinkedList<String>list = new LinkedList<>();//底层也没做啥
List,add("AA")://将"AA"封装到一个Node对象1中，list对象的属性first、last都指向此Node对象1。

List.add("BB");//将"BB"封装到一个Node对象2中，对象1和对象2构成一个双向链表，同时last指向此Node对象2。

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

LinkedList内部声明:

private static class Node<E>{E item;Node<E> next;Node<E> prel.
}

2.1.4 小结

1. Vector基本不使用了。
2. ArrayList底层使用数组结构，查找和添加(尾部添加)操作效率高，时间复杂度为0(1)，删除和插入操作效率低，时间复杂度为0(n)
3. LinkedList底层使用双向链表结构，删除和插入操作效率高，时间复杂度为0(1)，查找和添加(尾部添加)操作效率高，时间复杂度为0(n)(有可能添加操作是0(1)

在选择了ArrayList的前提下，

• new ArrayList():底层创建长度为10的数组。                                             
• new ArrayList(int capacity):底层创建指定capacity长度的数组。（推荐大体确认数组的长度）

2.2 Map

2.2.1 HashMap

1. HashMap中元素的特点

• HashMap中的所有的key彼此之间是不可重复的、无序的。所有的key就构成一个Set集合。--->key 所在的类要重写 hashcode()和equals()
• HashMap中的所有的value彼此之间是可重复的、无序的。所有的value就构成一个Collection集合。--->valve 所在的类要重写 equals()
• HashMap中的一个 key-value ,就构成了一个 entry。
• HashMap中的所有的 entry 彼此之间是不可重复的、无序的。所有的entry就构成了一个Set集合。

图示：

2.HashMap源码解析

2.1 jdk7中创建对象和添加数据过程(以JDK1.7.0_07为例说明):

//创建对象的过程中，底层会初始化数组Entry[]table=new Entry[16];
HashMap<String,Integer> map = new HashMap<>();

...
map.put("AA",78);//"AA"和78封装到一个Entry对象中，考虑将此对象添加到table数组中。

...

添加/修改的过程

说明

• 情况1:将(key1,value1)存放到数组的索引i的位置
• 情况2,情况3:(key1,valve1)元素与现有的(key2，value2)构成单向链表结构，(key1,value1)指向(key2,vaue2)

注意

随着不断的添加元素，在满足如下的条件的情况下，考虑扩容:

• (eize >= threshold)&&(null != table[i])

当元素的个数达到临界值(->数组的长度 *加载因子)时，就考虑扩容。

• 默认的临界值 = 16 *0.75 --> 12
• 默认扩容为原来的2倍。

2.2 jdk8与jdk7 的区别

2.2.2 LinkedHashMap

1.LinkedHashMap与HashMap 的关系:

• >LinkedHashMap是HashMap的子类。
• >LinkedHashMap在HashMap使用的数组+单向链表+红黑树的基础上，又增加了一对双向链表，记录添加的(key，value)的先后顺序。便于我们遍历所有的key-valve。

2.LinkedHashMap重写了HashMap的如下方法：

Node<K,V> newNode(int hash, K key, V value, Node<K,V>  e){LinkedHashMap.Entry<K,V> p = new LinkedHashMap.EntrykK,V>(hash, key, value, e);linkNodeLast(p);return p;
}

2.底层结构:LinkedHashMap内部定义了一个Entry

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);}
}

2.3 Set

HashSet和LinkedHashSet的问题可以转换成他们”父级“的内容来回答

• HashSet底层使用的是HashMap
• LinkedHashSet底层使用的是LinkedHashMap

2.4 练习

题目1：分析此map的内存结构

public class BinaryTreeTest {public static void main(String[] args) {HashMap<Integer, String> map = new HashMap<>();map.put(31, "张三");map.put(31,"李四");map.put(47, "王五");map.put(45,"赵六");}
}

解析：