数据结构



绪论

数据结构是计算机科学中研究数据组织、存储和管理的一门学科。它关注如何以及在何种方式下组织和存储数据，以便能够高效地操作和访问数据。

数据结构可以看作是一种特定的数据组织形式，它定义了数据元素之间的关系、操作和访问规则。常见的数据结构包括数组、链表、栈、队列、树、图等。

数据结构的设计和选择直接影响到算法的效率和性能。通过合理地选择和设计数据结构，可以提高程序的运行效率、节省存储空间，并使代码更易于理解和维护。

线性表

数据结构中的线性表是一种最基本的数据结构，它是由一组按照顺序排列的元素组成的数据集合。线性表中的元素之间存在一对一的关系，每个元素除了第一个元素和最后一个元素外，都有且仅有一个前驱元素和后继元素。

线性表可以用来表示一组具有顺序关系的数据，例如数组、链表等。线性表中的元素可以是任意类型的数据，如整数、字符、对象等。

线性表的特点包括：

  1. 顺序存储：线性表的元素按照顺序存储在内存中的连续空间中，可以通过下标或索引来访问元素。
  2. 大小可变：线性表的大小可以根据需要进行动态调整，可以随时添加或删除元素。
  3. 元素之间有序：线性表中的元素按照一定的顺序排列，每个元素都有唯一的前驱元素和后继元素。

线性表的常见操作包括插入（在指定位置插入元素）、删除（删除指定位置的元素）、查找（根据索引或值查找元素）、修改（修改指定位置的元素）等。

线性表是许多其他数据结构的基础，如栈、队列和链表等。它提供了一种简单而常用的数据组织方式，适用于各种应用场景。

在Java中，可以使用数组或链表来实现线性表。下面是一个使用Java语言实现线性表的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class ArrayListExample {
    public static void main(String[] args) {
        // 创建线性表
        ArrayList<Integer> list = new ArrayList<>();
        
        // 添加元素
        list.add(10);
        list.add(20);
        list.add(30);
        
        // 获取元素
        System.out.println("Element at index 1: " + list.get(1));
        
        // 修改元素
        list.set(0, 5);
        
        // 删除元素
        list.remove(2);
        
        // 遍历元素
        for (int i = 0; i < list.size(); i++) {
            System.out.println("Element at index " + i + ": " + list.get(i));
        }
    }
}

在上述代码中，我们使用Java的ArrayList类来实现线性表。ArrayList是基于数组实现的动态数组，它提供了一系列方法来操作线性表。我们可以使用add方法向线性表中添加元素，使用get方法获取指定位置的元素，使用set方法修改指定位置的元素，使用remove方法删除指定位置的元素，使用size方法获取线性表的长度。

需要注意的是，ArrayList类会自动进行扩容和缩容操作，以适应元素的增加和删除。此外，ArrayList还提供了一些其他常用的方法，如contains用于检查线性表是否包含指定元素，indexOf用于获取指定元素在线性表中的索引位置等。

数组

数据结构中的数组是一种线性表的实现方式，它是由一组连续的内存空间组成，用于存储相同类型的元素。数组中的每个元素都可以通过索引来访问，索引通常从0开始，依次递增。

数组的特点包括：

  1. 连续的内存空间：数组中的元素在内存中是连续存储的，这样可以通过索引计算出元素的地址，实现快速的访问。
  2. 固定大小：数组在创建时需要指定大小，一旦创建后，大小通常是固定的，无法动态调整。如果需要存储更多的元素，可能需要重新创建一个更大的数组，并将原有元素复制到新数组中。
  3. 相同类型的元素：数组中的元素类型必须相同，例如都是整数、字符、对象等。这是因为数组的内存空间是连续的，需要保证每个元素占用相同的字节数。
  4. 快速访问：由于数组中的元素在内存中是连续存储的，可以通过索引直接计算出元素的地址，从而实现快速的访问。

数组的优点是可以快速访问和修改指定位置的元素，时间复杂度为O(1)。然而，数组的缺点是大小固定，无法动态调整，插入和删除元素的操作比较耗时，需要移动其他元素。

在许多编程语言中，数组是一种内置的数据类型，并提供了一系列操作数组的方法和语法糖。例如，可以通过索引访问和修改数组元素，使用循环遍历数组，获取数组的长度等。


以下是一个使用Java语言实现的数组的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class ArrayExample {
    public static void main(String[] args) {
        // 创建一个整型数组，存储5个元素
        int[] array = new int[5];
        
        // 给数组赋值
        array[0] = 1;
        array[1] = 2;
        array[2] = 3;
        array[3] = 4;
        array[4] = 5;
        
        // 访问数组元素
        System.out.println("第一个元素：" + array[0]);
        System.out.println("第三个元素：" + array[2]);
        
        // 修改数组元素
        array[1] = 10;
        
        // 遍历数组
        for (int i = 0; i < array.length; i++) {
            System.out.println("第 " + (i+1) + " 个元素：" + array[i]);
        }
    }
}

在上述代码中，我们创建了一个大小为5的整型数组 array。通过索引访问和修改数组元素，例如 array[0] 表示第一个元素。最后使用循环遍历数组，输出每个元素的值。

需要注意的是，数组的大小是固定的，一旦创建后无法改变。如果需要存储更多的元素，就需要创建一个更大的数组，并将原来的元素复制到新数组中。

链表

数据结构中的链表是一种基本的数据结构，它由一组结点（Node）组成，每个结点包含两部分：数据域（Data）和指针域（Next）。

数据域用于存储数据，可以是任意类型的数据，如整数、字符、对象等。指针域用于指向下一个结点的地址，从而将所有结点连接起来形成一个链式结构。

链表的特点包括：

  1. 动态存储：链表的大小可以根据需要进行动态调整，可以随时添加或删除结点。
  2. 非连续存储：链表中的结点在内存中不是连续存储的，每个结点可以存储在任意的内存位置上，通过指针来链接各个结点。
  3. 有序存储：链表中的结点按照一定的顺序排列，每个结点都有唯一的后继结点。
  4. 灵活性高：由于链表的大小可以动态调整，因此非常适合于需要频繁插入和删除元素的场景。

链表的常见操作包括插入（在指定位置插入结点）、删除（删除指定位置的结点）、查找（根据值查找结点）、修改（修改指定位置的结点）等。

链表分为单向链表、双向链表和循环链表等不同类型，它们的实现方式和特点略有不同。单向链表只有一个指针域，指向下一个结点；双向链表有两个指针域，分别指向前一个结点和后一个结点；循环链表的最后一个结点的指针指向头结点，形成一个环。

链表是许多其他数据结构的基础，如栈、队列和哈希表等。它提供了一种灵活而高效的数据组织方式，适用于各种应用场景。


以下是一个使用Java语言实现的链表的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class LinkedListExample {
    public static void main(String[] args) {
        // 创建一个整型链表
        LinkedList<Integer> linkedList = new LinkedList<>();
        
        // 在链表末尾添加元素
        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);
        
        // 在链表指定位置插入元素
        linkedList.add(1, 10);
        
        // 获取链表元素个数
        System.out.println("链表中元素个数：" + linkedList.size());
        
        // 获取链表第一个元素
        System.out.println("链表第一个元素：" + linkedList.getFirst());
        
        // 获取链表最后一个元素
        System.out.println("链表最后一个元素：" + linkedList.getLast());
        
        // 遍历链表
        for (int i = 0; i < linkedList.size(); i++) {
            System.out.println("第 " + (i+1) + " 个元素：" + linkedList.get(i));
        }
        
        // 删除链表中指定位置的元素
        linkedList.remove(1);
        
        // 删除链表中指定元素
        linkedList.remove(Integer.valueOf(3));
    }
}

在上述代码中，我们创建了一个整型链表 linkedList。通过调用 add() 方法向链表中添加元素，使用 getFirst() 和 getLast() 方法获取链表的第一个和最后一个元素。最后使用循环遍历链表，输出每个元素的值。

需要注意的是，Java语言中的LinkedList类是双向链表，它的每个节点包含前驱节点和后继节点的指针。这使得在链表中插入和删除元素的操作更加高效。

栈

数据结构中的栈（Stack）是一种基本的数据结构，它可以看作是一种特殊的线性表。栈是一种后进先出（Last-In-First-Out，LIFO）的数据结构，只允许在栈顶进行插入和删除操作。

栈的特点包括：

  1. 只能在栈顶进行插入和删除操作。
  2. 先进后出：最后插入的元素最先被删除，即后进先出（Last-In-First-Out，LIFO）。
  3. 限制性：栈的容量是固定的，当栈满时无法再插入新元素；当栈为空时，无法再删除元素。

栈的常见操作包括压入（Push，将元素插入到栈顶）、弹出（Pop，从栈顶删除元素）、查看栈顶元素（Top，返回栈顶元素但不删除）、判断栈是否为空（Empty，如果栈空则返回真，否则返回假）等。

栈在计算机科学中有广泛的应用，例如在函数调用中，每次调用函数时都会将当前程序的状态（如寄存器、局部变量等）保存在栈中，当函数返回时再从栈中恢复状态。栈还可以用于表达式求值、括号匹配、迷宫问题等。

栈的实现方式有多种，可以使用数组或链表实现。使用数组实现的栈称为顺序栈，使用链表实现的栈称为链式栈。顺序栈的优点是访问元素速度快，缺点是容量固定；链式栈的优点是容量可以动态扩展，缺点是访问元素速度相对较慢。

需要注意的是，在栈中插入和删除元素的时间复杂度都是O(1)，即常数时间，因此栈是一种非常高效的数据结构。


以下是一个使用Java语言实现的栈的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        // 创建一个字符串类型的栈
        Stack<String> stack = new Stack<>();
        
        // 入栈操作
        stack.push("Java");
        stack.push("Python");
        stack.push("C++");
        
        // 获取栈顶元素
        System.out.println("栈顶元素：" + stack.peek());
        
        // 出栈操作
        String element = stack.pop();
        System.out.println("出栈元素：" + element);
        
        // 判断栈是否为空
        System.out.println("栈是否为空：" + stack.isEmpty());
        
        // 遍历栈
        for (String str : stack) {
            System.out.println("栈中元素：" + str);
        }
    }
}

在上述代码中，我们使用Java中的Stack类实现了一个字符串类型的栈。通过调用push()方法将元素压入栈中，使用peek()方法获取栈顶元素，使用pop()方法弹出栈顶元素。可以使用isEmpty()方法判断栈是否为空。最后使用增强型for循环遍历栈中的元素。

需要注意的是，Java中的Stack类是通过继承Vector类实现的，但在实际开发中，推荐使用Deque接口的实现类LinkedList来代替Stack类，因为Stack类在多线程环境下不安全。

队列

数据结构中的队列（Queue）是一种基本的数据结构，它可以看作是一种特殊的线性表。队列是一种先进先出（First-In-First-Out，FIFO）的数据结构，只允许在队尾插入元素，在队头删除元素。

队列的特点包括：

  1. 只能在队尾插入元素，在队头删除元素。
  2. 先进先出：最先插入的元素最先被删除，即先进先出（First-In-First-Out，FIFO）。
  3. 限制性：队列的容量是固定的，当队列满时无法再插入新元素；当队列为空时，无法再删除元素。

队列的常见操作包括入队（Enqueue，将元素插入到队尾）、出队（Dequeue，从队头删除元素）、获取队头元素（Front，返回队头元素但不删除）、判断队列是否为空（Empty，如果队列空则返回真，否则返回假）等。

队列在计算机科学中有广泛的应用，例如任务调度、缓冲区管理、广度优先搜索等。在实际应用中，队列通常用于存储需要按照顺序处理的数据或任务。

队列的实现方式有多种，可以使用数组或链表实现。使用数组实现的队列称为顺序队列，使用链表实现的队列称为链式队列。顺序队列的优点是访问元素速度快，缺点是容量固定；链式队列的优点是容量可以动态扩展，缺点是访问元素速度相对较慢。

需要注意的是，在队列中插入和删除元素的时间复杂度都是O(1)，即常数时间，因此队列也是一种非常高效的数据结构。


以下是一个使用Java语言实现的队列的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        // 创建一个整型队列
        Queue<Integer> queue = new LinkedList<>();
        
        // 入队操作
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        
        // 获取队头元素
        System.out.println("队头元素：" + queue.peek());
        
        // 出队操作
        int element = queue.poll();
        System.out.println("出队元素：" + element);
        
        // 判断队列是否为空
        System.out.println("队列是否为空：" + queue.isEmpty());
        
        // 遍历队列
        for (int i : queue) {
            System.out.println("队列中元素：" + i);
        }
    }
}

在上述代码中，我们使用Java中的Queue接口的实现类LinkedList实现了一个整型队列。通过调用offer()方法将元素加入队列，使用peek()方法获取队头元素，使用poll()方法弹出队头元素。可以使用isEmpty()方法判断队列是否为空。最后使用增强型for循环遍历队列中的元素。

需要注意的是，Java中的Queue接口定义了常用的队列操作方法，但是它本身并没有实现类，因此需要使用其子接口Deque的实现类LinkedList来实现队列。

树

数据结构中的树（Tree）是一种非线性的数据结构，它由若干个节点（Node）和若干条边（Edge）组成。每个节点都有一个值（Value）和若干个子节点（Children），除了根节点（Root）之外，每个节点都有一个父节点（Parent）。

树的特点包括：

  1. 根节点：树的顶部节点，没有父节点。
  2. 叶子节点：没有子节点的节点称为叶子节点（Leaf）。
  3. 父节点和子节点：除了根节点之外，每个节点都有一个父节点和若干个子节点。
  4. 兄弟节点：具有相同父节点的节点称为兄弟节点（Sibling）。
  5. 深度和高度：树中每个节点的深度（Depth）表示从根节点到该节点的路径长度；树的高度（Height）表示从根节点到最远叶子节点的路径长度。
  6. 无环：树中不存在环（Cycle），即任意两个节点之间只存在唯一的路径。

树在计算机科学中有广泛的应用，例如文件系统、HTML文档、数据库索引等。在实际应用中，树通常用于存储需要按照层次结构组织的数据或信息。

树的实现方式有多种，包括二叉树、平衡树、红黑树、B树等。其中二叉树是最简单的一种树结构，每个节点最多只有两个子节点。二叉树的实现方式包括链式存储和顺序存储两种。

需要注意的是，在树中查找、插入和删除节点的时间复杂度与树的形态相关，例如对于平衡树，这些操作的时间复杂度通常是O(log n)，其中n是树中节点的数量。因此，选择合适的树结构对于数据结构的性能非常重要。


以下是一个使用Java语言实现的二叉树的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
public class BinaryTreeExample {
    public static void main(String[] args) {
        // 创建一个二叉树
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        
        // 遍历二叉树
        System.out.println("前序遍历：");
        preOrderTraversal(root);
        System.out.println();
        
        System.out.println("中序遍历：");
        inOrderTraversal(root);
        System.out.println();
        
        System.out.println("后序遍历：");
        postOrderTraversal(root);
        System.out.println();
    }
    
    // 前序遍历
    public static void preOrderTraversal(Node node) {
        if (node != null) {
            System.out.print(node.value + " ");
            preOrderTraversal(node.left);
            preOrderTraversal(node.right);
        }
    }
    
    // 中序遍历
    public static void inOrderTraversal(Node node) {
        if (node != null) {
            inOrderTraversal(node.left);
            System.out.print(node.value + " ");
            inOrderTraversal(node.right);
        }
    }
    
    // 后序遍历
    public static void postOrderTraversal(Node node) {
        if (node != null) {
            postOrderTraversal(node.left);
            postOrderTraversal(node.right);
            System.out.print(node.value + " ");
        }
    }
}

class Node {
    int value;
    Node left;
    Node right;
    
    public Node(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

在上述代码中，我们使用Java语言实现了一个二叉树。通过创建Node类表示二叉树的节点，并使用left和right属性来表示节点的左子节点和右子节点。我们使用前序遍历、中序遍历和后序遍历三种方式遍历二叉树。其中，前序遍历的顺序是先访问根节点，再访问左子树和右子树；中序遍历的顺序是先访问左子树，再访问根节点和右子树；后序遍历的顺序是先访问左子树和右子树，再访问根节点。

需要注意的是，在实际开发中，二叉树的实现方式有很多种，可以使用数组、链表等数据结构来实现。此外，还有其他类型的树，如二叉搜索树、AVL树、红黑树等。

图

数据结构中的图（Graph）是一种非线性的数据结构，它由若干个节点（Vertex）和若干条边（Edge）组成。每个节点都有一个值（Value），边则表示节点之间的关系。

图的特点包括：

  1. 节点：图中的节点也称为顶点（Vertex），每个节点通常包含一个值和若干个相邻节点。
  2. 边：图中的边表示节点之间的关系，可以是有向边或无向边。有向边表示从一个节点到另一个节点的方向是固定的，无向边表示两个节点之间的关系是相互的。
  3. 权重：在某些图中，边还可以带有权重（Weight），表示从一个节点到另一个节点的代价或距离。
  4. 连通性：如果两个节点之间存在路径，则它们是连通的（Connected）。如果图中任意两个节点都是连通的，则称该图是连通图（Connected Graph）；否则称该图是非连通图（Disconnected Graph）。
  5. 环：如果一条边的起始节点和结束节点是同一个节点，则称该边是一个环（Cycle）。
  6. 度数：节点的度数（Degree）表示与该节点相邻的边的数量。

图在计算机科学中有广泛的应用，例如社交网络、路线规划、最短路径算法等。在实际应用中，图通常用于存储需要描述节点之间关系的数据或信息。

图的实现方式有多种，包括邻接矩阵、邻接表、十字链表等。其中邻接矩阵是最简单的一种实现方式，使用一个二维数组表示节点之间的关系。邻接表则使用链表来表示节点之间的关系，可以更好地处理稀疏图。

需要注意的是，在图中查找、插入和删除节点的时间复杂度与图的形态相关，例如对于稠密图，使用邻接矩阵实现可以获得更好的性能；对于稀疏图，使用邻接表实现可以获得更好的性能。因此，在实际应用中，选择合适的图结构对于数据结构的性能非常重要。


以下是一个使用Java语言实现的无向图的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
import java.util.ArrayList;
import java.util.List;

public class GraphExample {
    public static void main(String[] args) {
        // 创建一个无向图
        Graph graph = new Graph(5);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);
        
        // 遍历无向图
        System.out.println("深度优先遍历：");
        graph.dfs();
        System.out.println();
        
        System.out.println("广度优先遍历：");
        graph.bfs();
        System.out.println();
    }
}

class Graph {
    private int V; // 图的顶点数
    private List<Integer>[] adj; // 邻接表表示图
    
    public Graph(int V) {
        this.V = V;
        adj = new ArrayList[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new ArrayList<>();
        }
    }
    
    // 添加边
    public void addEdge(int v, int w) {
        adj[v].add(w);
        adj[w].add(v);
    }
    
    // 深度优先遍历
    public void dfs() {
        boolean[] visited = new boolean[V];
        dfsUtil(0, visited);
    }
    
    private void dfsUtil(int v, boolean[] visited) {
        visited[v] = true;
        System.out.print(v + " ");
        
        for (int i : adj[v]) {
            if (!visited[i]) {
                dfsUtil(i, visited);
            }
        }
    }
    
    // 广度优先遍历
    public void bfs() {
        boolean[] visited = new boolean[V];
        List<Integer> queue = new ArrayList<>();
        
        visited[0] = true;
        queue.add(0);
        
        while (!queue.isEmpty()) {
            int v = queue.remove(0);
            System.out.print(v + " ");
            
            for (int i : adj[v]) {
                if (!visited[i]) {
                    visited[i] = true;
                    queue.add(i);
                }
            }
        }
    }
}

在上述代码中，我们使用Java语言实现了一个无向图。通过创建Graph类表示图，并使用邻接表来表示节点之间的关系。我们使用深度优先遍历和广度优先遍历两种方式遍历无向图。其中，深度优先遍历的过程是从某个节点开始，沿着一条路径访问到最后一个节点，然后回溯到前一个节点，重复这个过程直到遍历完整个图；广度优先遍历的过程是从某个节点开始，依次访问它的所有邻居节点，再访问邻居节点的邻居节点，以此类推。

需要注意的是，在实际开发中，图的实现方式有很多种，如邻接矩阵、邻接表、关联矩阵等。此外，还有其他类型的图，如有向图、加权图等。

哈希表

哈希表（Hash Table），也称为散列表，是一种基于哈希函数（Hash Function）实现的数据结构。它通过将关键字（Key）映射到数组中的特定位置来实现高效的数据存储和检索。

哈希表的特点包括：

  1. 哈希函数：哈希表使用哈希函数将关键字映射到数组的特定位置，这个位置称为哈希值（Hash Value）。哈希函数应该能够将关键字均匀地分布到数组中的不同位置，以避免冲突。
  2. 数组：哈希表使用一个数组来存储数据，数组的每个元素称为哈希桶（Hash Bucket）。每个哈希桶可以存储一个或多个键值对（Key-Value Pair）。
  3. 冲突处理：由于哈希函数的映射可能导致不同的关键字映射到相同的位置，这就产生了冲突。哈希表使用冲突处理方法来解决冲突，常见的方法有链地址法（Chaining）和开放地址法（Open Addressing）。
    • 链地址法：每个哈希桶使用链表或其他数据结构来存储冲突的键值对。当发生冲突时，新的键值对可以直接添加到对应哈希桶的链表中。
    • 开放地址法：当发生冲突时，新的键值对会尝试在其他哈希桶中寻找空闲位置进行存储，常见的开放地址法包括线性探测（Linear Probing）和二次探测（Quadratic Probing）等。
  4. 快速查找：通过哈希函数和数组的结构，哈希表可以在平均情况下实现常数时间复杂度的查找、插入和删除操作。

哈希表在实际应用中非常常见，例如数据库索引、缓存系统、字典等。它提供了高效的数据检索能力，但也需要注意哈希函数的设计和冲突处理方法的选择，以避免性能下降和数据丢失的问题。此外，哈希表的性能也受到负载因子（Load Factor）的影响，负载因子过高可能导致冲突增加，而负载因子过低则会浪费存储空间。因此，在使用哈希表时需要综合考虑这些因素，选择合适的哈希函数和冲突处理方法，并根据实际情况调整负载因子。


以下是一个使用Java语言实现的简单哈希表的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
public class HashTableExample {
    public static void main(String[] args) {
        // 创建哈希表
        HashTable<String, Integer> hashTable = new HashTable<>();
        
        // 插入键值对
        hashTable.put("Alice", 25);
        hashTable.put("Bob", 30);
        hashTable.put("Charlie", 35);
        
        // 获取值
        System.out.println("Bob's age: " + hashTable.get("Bob"));
        
        // 删除键值对
        hashTable.remove("Charlie");
        
        // 检查是否包含键
        System.out.println("Contains key 'Charlie': " + hashTable.containsKey("Charlie"));
        
        // 检查是否包含值
        System.out.println("Contains value 30: " + hashTable.containsValue(30));
    }
}

class HashTable<K, V> {
    private static final int INITIAL_CAPACITY = 10;
    private Entry<K, V>[] table;
    private int size;
    
    public HashTable() {
        table = new Entry[INITIAL_CAPACITY];
        size = 0;
    }
    
    // 哈希函数
    private int hash(K key) {
        return Math.abs(key.hashCode()) % table.length;
    }
    
    // 插入键值对
    public void put(K key, V value) {
        int index = hash(key);
        
        Entry<K, V> entry = table[index];
        while (entry != null) {
            if (entry.key.equals(key)) {
                entry.value = value;
                return;
            }
            entry = entry.next;
        }
        
        Entry<K, V> newEntry = new Entry<>(key, value);
        newEntry.next = table[index];
        table[index] = newEntry;
        size++;
    }
    
    // 获取值
    public V get(K key) {
        int index = hash(key);
        
        Entry<K, V> entry = table[index];
        while (entry != null) {
            if (entry.key.equals(key)) {
                return entry.value;
            }
            entry = entry.next;
        }
        
        return null;
    }
    
    // 删除键值对
    public void remove(K key) {
        int index = hash(key);
        
        Entry<K, V> prev = null;
        Entry<K, V> entry = table[index];
        while (entry != null) {
            if (entry.key.equals(key)) {
                if (prev == null) {
                    table[index] = entry.next;
                } else {
                    prev.next = entry.next;
                }
                size--;
                return;
            }
            prev = entry;
            entry = entry.next;
        }
    }
    
    // 检查是否包含键
    public boolean containsKey(K key) {
        int index = hash(key);
        
        Entry<K, V> entry = table[index];
        while (entry != null) {
            if (entry.key.equals(key)) {
                return true;
            }
            entry = entry.next;
        }
        
        return false;
    }
    
    // 检查是否包含值
    public boolean containsValue(V value) {
        for (int i = 0; i < table.length; i++) {
            Entry<K, V> entry = table[i];
            while (entry != null) {
                if (entry.value.equals(value)) {
                    return true;
                }
                entry = entry.next;
            }
        }
        
        return false;
    }
    
    // 哈希表的键值对
    private static class Entry<K, V> {
        K key;
        V value;
        Entry<K, V> next;
        
        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
}

在上述代码中，我们使用Java语言实现了一个简单的哈希表。通过创建HashTable类来表示哈希表，并使用数组和链表的组合来处理哈希冲突。我们使用哈希函数将键映射到数组的索引位置，然后在该位置的链表中进行查找、插入和删除操作。

需要注意的是，在实际开发中，哈希表的实现方式有很多种，如开放寻址法、链地址法等。此外，还有其他一些优化技术，如动态扩容、负载因子等，以提高哈希表的性能和效率。

总结

数据结构主要分为线性结构和非线性结构两种。

线性结构是指数据元素之间存在一对一的关系，即除了第一个和最后一个元素，其他元素都有前驱和后继。常见的线性结构包括：

  1. 数组（Array）：一组连续的内存空间，用于存储同类型的数据元素。
  2. 链表（Linked List）：由若干个节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。
  3. 栈（Stack）：一种特殊的线性结构，只允许在一端进行插入和删除操作，即后进先出（LIFO）。
  4. 队列（Queue）：与栈相反，队列只允许在两端进行插入和删除操作，即先进先出（FIFO）。

非线性结构是指数据元素之间存在一对多或多对多的关系，即一个元素可能有多个前驱或后继。常见的非线性结构包括：

  1. 树（Tree）：由若干个节点组成，每个节点可以有若干个子节点，但只有一个父节点。
  2. 图（Graph）：由若干个节点和若干条边组成，每个节点可以与其他节点相连。
  3. 堆（Heap）：一种特殊的树形结构，用于实现优先队列等应用场景。

每种数据结构都有其独特的特点和适用场景，选择合适的数据结构可以提高算法的效率和性能。在实际应用中，根据问题的需求和特点选择合适的数据结构是非常重要的。