Java中级编程大师班＜第一篇：初识数据结构与算法-数组(2)＞

数组（Array）

数组是计算机编程中最基本的数据结构之一。它是一个有序的元素集合，每个元素都可以通过索引进行访问。本文将详细介绍数组的特性、用法和注意事项。

数组的基本特性

数组具有以下基本特性：

• 有序性： 数组中的元素是有序排列的，可以通过索引访问。
• 固定长度： 数组的长度在创建时固定，无法动态改变。
• 相同数据类型： 数组中的元素通常是相同数据类型的。

示例代码 - 创建和访问数组

让我们首先了解如何创建和访问数组：

// 创建一个整数数组
int[] numbers = new int[5];// 插入元素
numbers[0] = 1;
numbers[1] = 2;
numbers[2] = 3;
numbers[3] = 4;
numbers[4] = 5;// 访问元素
int thirdNumber = numbers[2]; // 访问第三个元素，值为3

数组的源码分析

数组是一种非常基础的数据结构，通常由编程语言的底层机制直接支持。在 Java 中，数组是通过内存分配和索引访问实现的。你可以在 Java 的 java.util 包中找到一些与数组相关的工具类和方法，如 Arrays 类。

注意事项

在使用数组时，需要注意以下事项：

• 固定长度： 数组的长度一旦确定，就无法更改。如果需要动态添加或删除元素，可能需要使用其他数据结构。
• 索引越界： 访问数组元素时必须确保索引在有效范围内，否则会导致索引越界异常。
• 内存占用： 数组的内存占用是固定的，如果分配了过多的空间，可能会浪费内存。

数组的使用场景

数组在许多场景下都非常有用，包括：

• 列表存储： 数组可以用来存储列表数据，如学生成绩、购物清单等。
• 数据检索： 由于数组的有序性，可以快速检索元素，例如查找最大值或最小值。
• 算法实现： 数组是许多算法的基础，如排序算法和搜索算法。

主要知识点讲解

动态数组和静态数组的区别

动态数组和静态数组是两种常见的数组类型，它们在内存管理和使用灵活性方面存在显著的区别。以下是它们的主要区别：

1. 大小变化：

   • 静态数组： 静态数组在创建时需要指定固定的大小，一旦分配了空间，大小不能更改。如果需要更多的存储空间，必须创建一个新的数组，将数据复制到新数组中，然后释放旧数组。这导致了内存的浪费和复杂的操作。
   • 动态数组： 动态数组在创建时可以指定初始大小，但如果数组元素数量超过当前容量，动态数组会自动扩展，分配更多的内存空间。这使得动态数组能够有效地处理大小变化的数据。

2. 内存管理：

   • 静态数组： 静态数组在创建时分配了固定大小的内存，因此可能浪费内存（如果未充分利用）或不足以存储所有数据（如果超过容量）。
   • 动态数组： 动态数组能够根据需要分配和释放内存，以适应数据的大小。这减少了内存浪费，并确保有效使用可用内存。

3. 使用灵活性：

   • 静态数组： 静态数组的大小是固定的，因此对于不同大小的数据集可能不够灵活。如果需要存储的数据数量不确定，静态数组可能无法满足需求。
   • 动态数组： 动态数组的大小可以动态增加，因此适用于处理不同大小的数据集。这使得它们更灵活且适用于各种情况。

4. 实现复杂度：

   • 静态数组： 静态数组的实现通常比较简单，因为它们不需要处理大小变化的逻辑。
   • 动态数组： 动态数组的实现相对复杂，因为它们需要管理内存分配和复制数据的逻辑。通常，动态数组使用静态数组作为底层存储，以便动态扩展和收缩。

综上所述，动态数组在处理不确定数据大小的情况下更为灵活和高效，因为它们可以自动调整大小，而静态数组则需要在创建时指定大小，并且无法轻松适应不同的数据集。因此，大多数编程语言和应用程序更倾向于使用动态数组或提供动态数组的数据结构，如 Java 中的 ArrayList 或 Python 中的列表。

以下是Java中的一个简单示例，展示了静态数组和动态数组（ArrayList）的用法，以及它们之间的一些主要区别：

import java.util.ArrayList;public class ArrayExample {public static void main(String[] args) {// 静态数组（固定大小）int[] staticArray = new int[5]; // 创建一个包含5个整数的静态数组staticArray[0] = 10;staticArray[1] = 20;staticArray[2] = 30;staticArray[3] = 40;staticArray[4] = 50;// 注意：静态数组大小不可更改// staticArray[5] = 60; // 这将导致数组越界错误System.out.println("静态数组元素：");for (int i = 0; i < staticArray.length; i++) {System.out.print(staticArray[i] + " ");}System.out.println();// 动态数组（ArrayList）ArrayList<Integer> dynamicArray = new ArrayList<Integer>(); // 创建一个空的动态数组dynamicArray.add(10);dynamicArray.add(20);dynamicArray.add(30);System.out.println("动态数组元素：");for (int i = 0; i < dynamicArray.size(); i++) {System.out.print(dynamicArray.get(i) + " ");}System.out.println();// 动态数组可以根据需要自动扩展dynamicArray.add(40);dynamicArray.add(50);System.out.println("动态数组元素（添加后）：");for (int i = 0; i < dynamicArray.size(); i++) {System.out.print(dynamicArray.get(i) + " ");}System.out.println();}
}

在这个示例中，我们首先创建了一个静态数组 staticArray 和一个动态数组 dynamicArray（使用 ArrayList 实现）。静态数组的大小在创建时固定，无法更改，而动态数组可以根据需要自动扩展。我们演示了如何向这两种数组中添加和访问元素。

请注意，在使用动态数组时，我们使用 ArrayList 的 add 方法来添加元素，而使用 size 和 get 方法来访问元素。此外，动态数组的大小可以根据添加的元素自动增长，而静态数组的大小是固定的。

当进一步扩展示例以更好地理解静态数组和动态数组之间的差异时，我们可以考虑以下方面：

1. 动态数组的自动扩展： 通过向动态数组添加元素来展示其自动扩展的特性。

2. 静态数组的大小限制： 展示静态数组的大小限制以及如何处理超出容量的情况。

3. 性能比较： 比较静态数组和动态数组在插入、删除和访问元素方面的性能差异。

下面是一个扩展示例，演示了这些方面的比较：

import java.util.ArrayList;public class ArrayExample {public static void main(String[] args) {// 静态数组（固定大小）int[] staticArray = new int[5];// 添加元素到静态数组for (int i = 0; i < staticArray.length; i++) {staticArray[i] = i * 10;}// 试图添加超出容量的元素// staticArray[5] = 50; // 这将导致数组越界错误// 动态数组（ArrayList）ArrayList<Integer> dynamicArray = new ArrayList<Integer>();// 添加元素到动态数组for (int i = 0; i < 5; i++) {dynamicArray.add(i * 10);}// 展示动态数组的大小自动扩展for (int i = 5; i < 10; i++) {dynamicArray.add(i * 10);}// 访问静态数组的元素System.out.println("静态数组元素：");for (int i = 0; i < staticArray.length; i++) {System.out.print(staticArray[i] + " ");}System.out.println();// 访问动态数组的元素System.out.println("动态数组元素：");for (int i = 0; i < dynamicArray.size(); i++) {System.out.print(dynamicArray.get(i) + " ");}System.out.println();// 比较静态数组和动态数组的性能long startTime = System.nanoTime();// 在静态数组中执行一系列操作long endTime = System.nanoTime();System.out.println("静态数组操作耗时：" + (endTime - startTime) + "纳秒");startTime = System.nanoTime();// 在动态数组中执行相同系列操作endTime = System.nanoTime();System.out.println("动态数组操作耗时：" + (endTime - startTime) + "纳秒");}
}

在这个扩展示例中，我们添加了更多元素到动态数组，展示了其自动扩展的特性。我们还演示了如何访问静态数组和动态数组的元素，并进行性能比较。

请注意，在性能比较方面，动态数组通常具有更好的性能，因为它可以自动扩展，而不需要手动管理容量。但这也取决于具体的操作和场景。

多维数组的概念和使用

多维数组是一种特殊类型的数组，它可以包含其他数组作为其元素，从而形成多维数据结构。多维数组在处理复杂的数据和表格时非常有用，通常用于表示矩阵、图像、表格等具有多个维度的数据集。

以下是多维数组的概念和使用示例：

多维数组的概念

多维数组是一个包含多个维度的数组，每个维度都可以看作是一个单独的数组。通常，我们使用二维数组和三维数组最为常见，但我们可以创建具有任意数量维度的多维数组。

• 二维数组： 二维数组是一个表格状的数组，具有行和列。它可以看作是一个数组的数组，其中每个元素是一个数组，代表一行或一列的数据。

• 三维数组： 三维数组可以被视为一堆二维数组。每个元素是一个二维数组，代表了一个平面或一层的数据。

• 多维数组： 多维数组可以扩展到更多的维度，例如四维数组、五维数组等。每个维度都会增加一个方向，用于组织数据。

多维数组的声明和初始化

在Java中，声明和初始化多维数组的语法如下：

// 声明和初始化二维数组
dataType[][] arrayName = new dataType[rows][columns];// 例如，创建一个3x4的整数二维数组
int[][] twoDArray = new int[3][4];// 声明和初始化三维数组
dataType[][][] arrayName = new dataType[depth][rows][columns];// 例如，创建一个2x3x4的整数三维数组
int[][][] threeDArray = new int[2][3][4];

多维数组的访问和操作

多维数组的访问和操作涉及到多个索引，每个索引对应一个维度。例如，对于二维数组：

int value = twoDArray[rowIndex][columnIndex];

对于三维数组：

int value = threeDArray[layerIndex][rowIndex][columnIndex];

我们可以使用嵌套的循环来遍历和操作多维数组的元素，例如：

// 遍历二维数组
for (int i = 0; i < rows; i++) {for (int j = 0; j < columns; j++) {int value = twoDArray[i][j];// 进行操作}
}// 遍历三维数组
for (int i = 0; i < depth; i++) {for (int j = 0; j < rows; j++) {for (int k = 0; k < columns; k++) {int value = threeDArray[i][j][k];// 进行操作}}
}

示例：二维数组的应用

以下是一个示例，演示了如何使用二维数组表示一个矩阵，并进行一些基本的操作：

public class TwoDArrayExample {public static void main(String[] args) {// 创建一个3x4的整数二维数组int[][] matrix = {{1, 2, 3, 4},{5, 6, 7, 8},{9, 10, 11, 12}};// 访问元素int value = matrix[1][2]; // 访问第2行第3列的元素（值为7）// 遍历并打印矩阵for (int i = 0; i < matrix.length; i++) {for (int j = 0; j < matrix[i].length; j++) {System.out.print(matrix[i][j] + " ");}System.out.println();}}
}

这个示例创建了一个3x4的整数二维数组，访问了其中的元素，并遍历了整个矩阵。

多维数组在编程中具有广泛的应用，尤其是在处理矩阵、图像、游戏地图等需要多维数据结构的场景中。通过多维数组，我们可以更方便地组织和访问复杂的数据。

多维数组是一种包含多个维度的数组，每个维度可以看作是一个单独的数组。它们用于表示多维数据结构，例如矩阵、立方体、三维坐标等。在多维数组中，每个元素都由多个索引确定，每个索引对应一个维度。

以下是多维数组的更详细描述和代码示例：

二维数组

二维数组是最常见的多维数组类型，它包含两个维度：行和列。在Java中，可以通过嵌套数组来创建二维数组。下面是一个示例：

// 创建一个3x3的整数二维数组
int[][] matrix = {{1, 2, 3},{4, 5, 6},{7, 8, 9}
};// 访问元素
int value = matrix[1][2]; // 访问第2行第3列的元素（值为6）

三维数组

三维数组包含三个维度，通常用于表示立体数据。在Java中，可以使用嵌套的数组来创建三维数组。以下是一个示例：

// 创建一个2x3x4的整数三维数组
int[][][] cube = {{{1, 2, 3, 4},{5, 6, 7, 8},{9, 10, 11, 12}},{{13, 14, 15, 16},{17, 18, 19, 20},{21, 22, 23, 24}}
};// 访问元素
int value = cube[1][2][3]; // 访问第2层、第3行、第4列的元素（值为24）

多维数组的遍历

遍历多维数组需要嵌套循环，每个维度一个循环。以下是遍历二维数组和三维数组的示例：

// 遍历二维数组
for (int i = 0; i < matrix.length; i++) {for (int j = 0; j < matrix[i].length; j++) {int value = matrix[i][j];// 进行操作}
}// 遍历三维数组
for (int i = 0; i < cube.length; i++) {for (int j = 0; j < cube[i].length; j++) {for (int k = 0; k < cube[i][j].length; k++) {int value = cube[i][j][k];// 进行操作}}
}

多维数组的应用

多维数组在编程中有许多应用，例如：

• 图像处理： 图像通常表示为二维数组，其中每个元素代表像素的颜色或亮度值。

• 游戏开发： 游戏地图、三维模型等数据可以使用多维数组表示。

• 科学计算： 在科学和工程领域中，多维数组用于表示复杂的数据集，如物理模拟、地理信息系统（GIS）等。

• 数据分析： 在数据分析和机器学习中，多维数组用于存储和处理大规模数据集。

多维数组在处理需要多个维度的数据时非常有用，它们提供了一种有效的方式来组织和访问这些数据。根据需求，我们可以创建具有更多维度的多维数组，以满足特定的应用需求。

数组的时间复杂度分析，包括插入、删除和查找操作的性能分析

数组是一种基本的数据结构，其性能分析涉及到插入、删除和查找操作的时间复杂度。下面是关于数组各种操作的时间复杂度分析：

1. 插入操作：

   • 在末尾插入元素（尾部插入）：插入操作的时间复杂度为 O(1)。因为在数组末尾添加元素不需要移动其他元素，只需将新元素放在最后即可。

   • 在中间或开头插入元素：如果要在数组中间或开头插入元素，需要将插入位置之后的所有元素都向后移动一个位置。这样的操作的时间复杂度是 O(n)，其中 n 是数组中的元素数量，因为它需要线性时间来移动元素。

2. 删除操作：

   • 删除末尾元素（尾部删除）：与插入类似，删除操作的时间复杂度为 O(1)。只需将末尾元素标记为删除即可，不需要移动其他元素。

   • 删除中间或开头元素：与插入相同，删除中间或开头的元素需要将删除位置之后的所有元素向前移动一个位置，时间复杂度为 O(n)。

3. 查找操作：

   • 按索引查找元素：查找特定索引位置的元素的时间复杂度是 O(1)。因为可以通过数组的索引直接访问元素。

   • 线性查找：如果需要在数组中查找特定值，且数组未排序，那么最坏情况下需要遍历整个数组，时间复杂度为 O(n)。

   • 二分查找：如果数组已排序，可以使用二分查找来提高查找效率，时间复杂度为 O(log n)。但前提是数组必须是有序的。

总结：

• 插入和删除操作的性能受到插入或删除的位置以及元素数量的影响。在尾部插入或删除元素时性能最好，时间复杂度为 O(1)，而在中间或开头插入或删除元素时性能较差，时间复杂度为 O(n)。

• 查找操作的性能取决于具体情况。按索引查找元素的时间复杂度为 O(1)。在无序数组中线性查找的时间复杂度为 O(n)，而在有序数组中二分查找的时间复杂度为 O(log n)。

因此，对于需要频繁进行插入、删除和查找操作的情况，可能需要考虑使用其他数据结构，如链表或哈希表，以获得更好的性能。数组在具体应用中的选择应根据操作的频率和性能要求来决定。
以下是关于数组插入、删除和查找操作的Java代码示例：

import java.util.Arrays;public class ArrayOperationsExample {public static void main(String[] args) {// 创建一个整数数组int[] arr = {10, 20, 30, 40, 50};// 打印原始数组System.out.println("原始数组：" + Arrays.toString(arr));// 插入操作int insertValue = 60;int insertIndex = 2; // 在索引2处插入元素insertElement(arr, insertValue, insertIndex);System.out.println("插入元素 " + insertValue + " 后的数组：" + Arrays.toString(arr));// 删除操作int deleteIndex = 3; // 删除索引3处的元素deleteElement(arr, deleteIndex);System.out.println("删除索引 " + deleteIndex + " 处的元素后的数组：" + Arrays.toString(arr));// 查找操作int searchValue = 30;int searchIndex = searchElement(arr, searchValue);if (searchIndex != -1) {System.out.println("元素 " + searchValue + " 在数组中的索引位置为 " + searchIndex);} else {System.out.println("元素 " + searchValue + " 不在数组中。");}}// 插入元素public static void insertElement(int[] arr, int value, int index) {if (index < 0 || index > arr.length) {System.out.println("插入位置无效。");return;}// 创建一个新数组，比原数组多一个元素int[] newArr = new int[arr.length + 1];// 将原数组前半部分复制到新数组中for (int i = 0; i < index; i++) {newArr[i] = arr[i];}// 插入新元素newArr[index] = value;// 将原数组后半部分复制到新数组中for (int i = index; i < arr.length; i++) {newArr[i + 1] = arr[i];}// 更新原数组for (int i = 0; i < arr.length; i++) {arr[i] = newArr[i];}}// 删除元素public static void deleteElement(int[] arr, int index) {if (index < 0 || index >= arr.length) {System.out.println("删除位置无效。");return;}// 创建一个新数组，比原数组少一个元素int[] newArr = new int[arr.length - 1];// 将原数组前半部分复制到新数组中for (int i = 0; i < index; i++) {newArr[i] = arr[i];}// 将原数组后半部分复制到新数组中for (int i = index + 1; i < arr.length; i++) {newArr[i - 1] = arr[i];}// 更新原数组for (int i = 0; i < arr.length - 1; i++) {arr[i] = newArr[i];}}// 查找元素public static int searchElement(int[] arr, int value) {for (int i = 0; i < arr.length; i++) {if (arr[i] == value) {return i; // 找到元素并返回索引}}return -1; // 元素不在数组中}
}

当进行插入、删除和查找操作时，我们需要综合考虑时间复杂度和空间复杂度。在数组中执行这些操作时，它们的性能表现如下：

1. 插入操作：

• 时间复杂度： 对于数组的插入操作，最好的情况是在末尾插入，时间复杂度为O(1)。这是因为只需要在数组的末尾追加元素，不需要移动其他元素。但如果要在中间或开头插入元素，则需要将插入位置之后的元素向后移动，平均时间复杂度为O(n)，其中n是数组的大小。

• 空间复杂度： 插入操作的空间复杂度通常很低，仅包括新插入的元素所占用的空间。

示例代码 - 插入操作（数组）：

public class ArrayExample {public static void main(String[] args) {int[] arr = {10, 20, 30, 40, 50};int insertValue = 60;int insertIndex = 2; // 在索引2处插入元素insertElement(arr, insertValue, insertIndex);}// 插入元素public static void insertElement(int[] arr, int value, int index) {if (index < 0 || index > arr.length) {System.out.println("插入位置无效。");return;}// 创建一个新数组，比原数组多一个元素int[] newArr = new int[arr.length + 1];// 将原数组前半部分复制到新数组中for (int i = 0; i < index; i++) {newArr[i] = arr[i];}// 插入新元素newArr[index] = value;// 将原数组后半部分复制到新数组中for (int i = index; i < arr.length; i++) {newArr[i + 1] = arr[i];}// 更新原数组for (int i = 0; i < arr.length; i++) {arr[i] = newArr[i];}}
}

2. 删除操作：

• 时间复杂度： 删除操作的时间复杂度与插入类似，最好的情况是删除末尾元素，时间复杂度为O(1)。但如果要删除中间或开头的元素，则需要将删除位置之后的元素向前移动，平均时间复杂度为O(n)，其中n是数组的大小。

• 空间复杂度： 删除操作的空间复杂度通常很低，仅包括被删除元素的空间。

示例代码 - 删除操作（数组）：

public class ArrayExample {public static void main(String[] args) {int[] arr = {10, 20, 30, 40, 50};int deleteIndex = 2; // 删除索引2处的元素deleteElement(arr, deleteIndex);}// 删除元素public static void deleteElement(int[] arr, int index) {if (index < 0 || index >= arr.length) {System.out.println("删除位置无效。");return;}// 创建一个新数组，比原数组少一个元素int[] newArr = new int[arr.length - 1];// 将原数组前半部分复制到新数组中for (int i = 0; i < index; i++) {newArr[i] = arr[i];}// 将原数组后半部分复制到新数组中for (int i = index + 1; i < arr.length; i++) {newArr[i - 1] = arr[i];}// 更新原数组for (int i = 0; i < arr.length - 1; i++) {arr[i] = newArr[i];}}
}

3. 查找操作：

• 时间复杂度： 在数组中查找操作通常需要线性搜索，时间复杂度为O(n)，其中n是数组的大小。如果数组是有序的，可以使用二分查找，时间复杂度为O(log n)。

• 空间复杂度： 查找操作的空间复杂度通常很低，仅包括存储查找结果所需的空间。

示例代码 - 查找操作（数组）：

public class ArrayExample {public static void main(String[] args) {int[] arr = {10, 20, 30, 40, 50};int searchValue = 30;int searchIndex = searchElement(arr, searchValue);if (searchIndex != -1) {System.out.println("元素 " + searchValue + " 在数组中的索引位置为 " + searchIndex);} else {System.out.println("元素 " + searchValue + " 不在数组中。");}}// 线性查找元素public static int searchElement(int[] arr, int value) {for (int i = 0; i < arr.length; i++) {if (arr[i] == value) {return i; // 找到并返回元素的索引}}return -1; // 元素不在数组中}
}

总结：

• 数组在插入和删除操作中的性能通常受到插入或删除位置和数组大小的影响。查找操作的性能取决于数组是否有序。
• 在选择数据结构和算法时，需要根据特定的需求和性能要求来做出决策。不同的数据结构和算法适用于不同的情况。

数组的应用扩展

除了基本的数组，还有其他高级的数据结构，用于更复杂的数据存储和检索需求。其中，HashMap 和 HashTable 是两个重要的数据结构，它们在实际编程中具有广泛的应用。

HashMap 和 HashTable

HashMap 和 HashTable 都是键值对存储的数据结构，它们可以用于快速查找和检索数据。虽然它们在用法上很相似，但也存在一些重要的区别：

• HashMap： HashMap 是 Java 集合框架中的一部分，它允许空键（key）和空值（value），并且是非线程安全的。HashMap 使用了哈希表的数据结构，能够在常数时间内查找元素。

• HashTable： HashTable 也是键值对存储的数据结构，但它不允许空键和空值，而且是线程安全的。HashTable 使用了类似于 HashMap 的哈希表实现，但在多线程环境下性能更好。

示例代码 - 使用 HashMap

让我们看一下如何使用 HashMap 存储和检索数据：

// 创建一个 HashMap
HashMap<String, Integer> scores = new HashMap<>();// 插入键值对
scores.put("Alice", 95);
scores.put("Bob", 88);
scores.put("Charlie", 92);// 检索值
int aliceScore = scores.get("Alice"); // 获取 Alice 的成绩

示例代码 - 使用 HashTable

使用 HashTable 与 HashMap 类似，但需要注意不允许空键或空值：

// 创建一个 HashTable
Hashtable<String, Integer> scores = new Hashtable<>();// 插入键值对
scores.put("Alice", 95);
scores.put("Bob", 88);
scores.put("Charlie", 92);// 检索值
int aliceScore = scores.get("Alice"); // 获取 Alice 的成绩

HashMap底层代码解析

理解 HashMap 内部工作原理的关键部分是研究其核心方法，如 resize、treeifyBin 和 putVal。以下是这些方法的简要源码示例和解释：

1. resize 方法

resize 方法用于对 HashMap 进行扩容。当键值对数量达到阈值时，调用 resize 方法进行扩容，通常将容量翻倍。

final Node<K,V>[] resize() {Node<K,V>[] oldTab = table; // 保存旧的桶数组int oldCap = (oldTab == null) ? 0 : oldTab.length; // 旧容量int oldThr = threshold; // 旧的阈值int newCap, newThr = 0; // 新容量和新阈值if (oldCap > 0) { // 如果旧容量大于0if (oldCap >= MAXIMUM_CAPACITY) { // 如果旧容量已经达到最大值threshold = Integer.MAX_VALUE; // 阈值设置为最大值，禁止再次扩容return oldTab; // 返回旧的桶数组} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // 扩容为原容量的两倍，并更新新阈值} else if (oldThr > 0) // 如果旧的阈值大于0newCap = oldThr; // 使用阈值作为新容量else { // 如果没有指定容量和阈值，使用默认值newCap = DEFAULT_INITIAL_CAPACITY; // 默认初始容量newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 默认阈值}if (newThr == 0) { // 如果新阈值为0float ft = (float)newCap * loadFactor; // 计算新阈值newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE); // 如果未超过最大容量，使用计算值，否则使用最大值}threshold = newThr; // 更新阈值@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // 创建新的桶数组table = newTab; // 将桶数组引用指向新的桶数组if (oldTab != null) { // 如果旧桶数组不为空for (int j = 0; j < oldCap; ++j) { // 遍历旧桶数组Node<K,V> e;if ((e = oldTab[j]) != null) { // 如果当前位置有节点oldTab[j] = null; // 清空旧桶位置if (e.next == null)newTab[e.hash & (newCap - 1)] = e; // 如果只有一个节点，直接放入新桶位置else if (e instanceof TreeNode) // 如果节点是红黑树节点((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // 进行拆分else { // 如果是链表Node<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {next = e.next;if ((e.hash & oldCap) == 0) { // 如果哈希码对旧容量求与为0if (loTail == null)loHead = e; // 放入低位链表头部elseloTail.next = e; // 放入低位链表尾部loTail = e; // 更新低位链表尾节点}else { // 否则放入高位链表if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);if (loTail != null) {loTail.next = null;newTab[j] = loHead; // 更新旧桶位置为低位链表}if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead; // 更新旧桶位置为高位链表}}}}}return newTab; // 返回新的桶数组
}

• resize 方法首先计算新的容量和阈值。
• 如果旧表（oldTab）不为空，它将遍历旧表的桶，根据哈希值重新分配节点到新表（newTab）中。
• 如果节点的数量超过一定阈值，它可能会将链表转化为红黑树，以提高性能。

2. treeifyBin 方法

treeifyBin 方法用于将链表转换为红黑树，以提高查找性能。该方法通常在链表长度超过8时被调用。

final void treeifyBin(Node<K,V>[] tab, int hash) {int n, index; Node<K,V> e;if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)resize(); // 扩容else if ((e = tab[index = (n - 1) & hash]) != null) { // 获取当前位置的节点TreeNode<K,V> hd = null, tl = null;do {TreeNode<K,V> p = replacementTreeNode(e, null); // 创建红黑树节点if (tl == null)hd = p; // 如果链表为空，将红黑树节点设置为头节点else {p.prev = tl;tl.next = p;}tl = p;} while ((e = e.next) != null);if ((tab[index] = hd) != null) // 如果头节点不为空，将链表转化为红黑树hd.treeify(tab);}
}

• treeifyBin 方法首先检查表的容量，如果小于 MIN_TREEIFY_CAPACITY，则会调用 resize 方法进行扩容。
• 如果表的容量足够大，它将遍历桶中的链表，将每个节点替换为红黑树节点，并构建红黑树。

3. pubVal 方法

putVal 方法是 HashMap 中用于向哈希表中添加键值对的核心方法。

/*** Associates the specified value with the specified key in this map.* If the map previously contained a mapping for the key, the old* value is replaced.** @param hash hash for key* @param key the key* @param value the value to put* @param onlyIfAbsent if true, don't change existing value* @param evict if false, the table is in creation mode.* @return previous value, or null if none*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {Node<K,V>[] tab; // 声明桶数组Node<K,V> p; // 声明当前节点int n, i; // n为桶数组的长度，i为计算出的槽位索引// 如果桶数组为空或长度为0，需要初始化//判断tab是不是为空，如果为空，则将容量进行初始化，也就是说，初始换操作不是在new HashMap()的时候进行的，而是在第一次put的时候进行的if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// 计算槽位索引:初始化操作以后，根据当前key的哈希值算出最终命中到哪个桶上去，并且这个桶上如果没有元素的话，则直接new一个新节点放进去if ((p = tab[i = (n - 1) & hash]) == null) // 如果当前槽位为空tab[i] = newNode(hash, key, value, null); // 直接创建新节点并放入槽位else {Node<K,V> e; K k;// 先判断一下这个桶里的第一个Node元素的key是不是和即将要存的key值相同，如果相同，则把当前桶里第一个Node元素赋值给e，这个else的最下边进行了判断，如果e!=null就执行把新value进行替换的操作if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p; // 如果找到相同键的节点，将e指向该节点else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {for (int binCount = 0; ; ++binCount) {// 如果遍历到链表尾部仍未找到相同键的节点，将新节点添加到链表尾部if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);// 如果链表长度达到阈值，将链表转化为红黑树if (binCount >= TREEIFY_THRESHOLD - 1)treeifyBin(tab, hash);break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break; // 如果找到相同键的节点，退出循环p = e;}}/*** 只要e不为空，说明要插入的key已经存在了，覆盖旧的value值，然后返回原来oldValue* 因为只是替换了旧的value值，并没有插入新的元素，所以不需要下边的扩容判断，直接* return掉*/if (e != null) { // 如果找到相同键的节点V oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value; // 替换值afterNodeAccess(e);return oldValue; // 返回旧值}}++modCount;/*** 判断容量是否已经到了需要扩充的阈值了，如果到了，则进行扩充* 如果上一步已经判断key是存在的，只是替换了value值，并没有插入新的元素，所以不需要判断* 扩容，不会走这一步的*/if (++size > threshold)resize(); // 如果超过阈值，进行扩容afterNodeInsertion(evict);return null; // 返回null表示插入成功
}

putVal 方法用于将键值对放入HashMap中。此方法涵盖了查找、替换、插入和扩容等关键操作，是HashMap内部工作的核心部分。

JDK1.7和1.8对比

HashMap 在 JDK 1.7 和 JDK 1.8 中都有存在，但在 JDK 1.8 中进行了一些重要的改进。以下是 JDK 1.7 和 JDK 1.8 中 HashMap 的主要区别：

1. 数据结构：

   • JDK 1.7：JDK 1.7 中的 HashMap 使用数组 + 链表的数据结构。具体说，它使用数组存储桶（buckets），每个桶存储一个链表。这意味着当多个键映射到同一个桶时，它们会在同一个链表上存储。

   • JDK 1.8：JDK 1.8 中的 HashMap 在链表长度达到一定阈值（8）时，将链表转化为红黑树。这一改进在处理大量键值对时提高了查找性能，因为红黑树的查找时间复杂度为 O(log n)。
     

2. 哈希冲突解决：

   • JDK 1.7：JDK 1.7 使用链表来解决哈希冲突。当多个键映射到同一个桶时，它们会形成一个链表，需要遍历链表来查找。

   • JDK 1.8：JDK 1.8 在链表长度达到一定阈值时，会将链表转化为红黑树，这大大提高了处理长链表的性能。

3. 并发性能：

   • JDK 1.7：JDK 1.7 中的 HashMap 不是线程安全的，如果多个线程同时操作一个 HashMap，可能会导致数据不一致或死锁等问题。为了在多线程环境下使用 HashMap，需要自行添加同步机制。

   • JDK 1.8：JDK 1.8 中的 HashMap 在处理并发操作时进行了优化。它引入了更高效的锁机制，例如分段锁和 CAS 操作，以提高并发性能。此外，JDK 1.8 还引入了 ConcurrentHashMap 类，专门用于高并发环境。

4. 迭代性能：

   • JDK 1.7：JDK 1.7 中的 HashMap 在迭代时性能较差，因为即使没有哈希冲突，它也需要遍历整个桶数组，包括空桶。

   • JDK 1.8：JDK 1.8 中的 HashMap 在迭代时性能得到了提升，特别是在没有哈希冲突的情况下。这是由于它使用了更好的数据结构和算法来加速迭代。

5. 空间利用：

   • JDK 1.7：JDK 1.7 中的 HashMap 对空间的利用不是很高，因为桶的数量必须是 2 的幂次方，可能会导致浪费空间。

   • JDK 1.8：JDK 1.8 中的 HashMap 在一定程度上改进了空间利用，通过采用树结构来存储哈希冲突的键值对，减少了空间浪费。
     

总的来说，JDK 1.8 中的 HashMap 在性能和并发性能上有重大改进，特别是在处理大量数据和高并发访问时表现更优越。因此，如果使用 Java 8 或更高版本，通常建议使用 JDK 1.8 中的 HashMap 实现。但要注意，如果需要在多线程环境中使用 HashMap，最好考虑使用 ConcurrentHashMap 或其他线程安全的数据结构。

注意事项

在使用 HashMap 时，有一些重要的注意事项和最佳实践，以确保正确性和性能。以下是一些关键的注意事项：

1. 线程安全性：HashMap 不是线程安全的数据结构，如果在多线程环境下使用，需要考虑采取适当的同步机制，或者使用线程安全的替代品，如 ConcurrentHashMap。

2. 键的不可变性：HashMap 中的键应该是不可变的对象。如果键发生了变化，可能导致无法正常获取或删除值。

3. 哈希冲突：哈希冲突是指不同的键映射到相同的哈希桶。为了处理冲突，HashMap 使用链表或红黑树。为了获得良好的性能，尽量避免大量哈希冲突，可以考虑使用良好的哈希函数或合适的数据分布。

4. 哈希函数重写：如果自定义对象作为键，应该确保重写了 hashCode() 和 equals() 方法，以确保正确的哈希和相等性比较。

5. 初始化容量和负载因子：在创建 HashMap 时，可以指定初始容量和负载因子。根据预期的键值对数量，选择适当的初始容量可以提高性能。负载因子是用于触发扩容的阈值，通常选择合适的默认值即可。

6. 遍历：在遍历 HashMap 时，尽量不要修改其结构（添加或删除键值对），否则可能会导致不确定的行为或异常。

7. Null 键和 Null 值：HashMap 允许键和值为 null。但要小心处理 null 键，以防止 NullPointerException。

8. 性能考虑：HashMap 在查找操作上有很好的性能，但在插入和删除操作上可能会有较差的性能，特别是在存在大量哈希冲突时。在需要频繁插入和删除的场景中，可以考虑使用 LinkedHashMap 或 ConcurrentHashMap。

9. 扩容代价：HashMap 在达到负载因子阈值时会自动进行扩容，这涉及到重新分配键值对到新的桶数组。频繁的扩容操作可能会影响性能，因此应根据应用的需求选择适当的初始容量和负载因子。

10. equals 和 hashCode 方法：如果自定义对象作为键，确保正确实现了 equals 和 hashCode 方法，以便正确地比较和查找键。

总的来说，HashMap 是一个非常有用的数据结构，但在使用时需要谨慎考虑上述注意事项，以确保其正确性和性能。根据应用的需求，还可以考虑使用其他实现了特定场景需求的 Map 接口的实现类，如 ConcurrentHashMap、LinkedHashMap 等。

HashTable底层代码解析

HashTable 是 Java 中的一个古老的哈希表实现，它在 Java 的早期版本中被引入。虽然它在新的 Java 版本中不太常用，但仍然值得了解其内部实现。
HashTable 使用一个哈希函数将键映射到存储桶（buckets ）中，并在每个桶中存储一个键值对。每个桶实际上是一个链表，用于处理哈希冲突。当多个键映射到同一个桶时，它们会以链表的形式存储在该桶中。如果链表变得太长，性能会下降，因此 HashTable 需要定期进行 rehash 操作来重新分配键值对到新的桶中，以保持性能。

以下是 HashTable 的主要代码片段，我会添加注释来解释其关键部分。

public class Hashtable<K,V> extends Dictionary<K,V>implements Map<K,V>, Cloneable, java.io.Serializable {// 哈希表的默认初始容量private static final int DEFAULT_INITIAL_CAPACITY = 11;// 哈希表的默认负载因子private static final float DEFAULT_LOAD_FACTOR = 0.75f;// 哈希表的键值对数量private transient int count;// 哈希表的容量private int threshold;// 哈希表的装载因子private float loadFactor;// 存储键值对的数组，每个元素是一个链表头private transient Entry<?,?>[] table;// 哈希表结构发生变化的次数，用于支持快速失败机制private transient int modCount;// ...// 内部类，表示键值对的节点private static class Entry<K,V> implements Map.Entry<K,V> {final int hash;final K key;V value;Entry<K,V> next;// ...}// 构造函数，初始化哈希表public Hashtable(int initialCapacity, float loadFactor) {// ...}// 计算键的哈希码private static int hash(int h) {// ...}// 扩容哈希表protected void rehash() {// ...}// 在哈希表中查找键对应的值public synchronized V get(Object key) {// ...}// 在哈希表中插入键值对public synchronized V put(K key, V value) {// ...}// ...// 内部方法，用于枚举哈希表中的键private static class Enumerator<K,V> implements Enumeration<K>, Iterator<K> {// ...}// ...// 复制哈希表public synchronized Object clone() {// ...}// ...// 其他方法，如remove, contains, clear, keys, values, size 等
}

HashTable 的 rehash 原理可以概括如下：

1. 初始化：当创建一个新的 HashTable 实例时，它会分配一定数量的桶（通常是默认大小的素数）。这些桶会存储键值对，每个桶可以存储多个键值对。

2. 插入操作：当执行插入操作时，HashTable 首先使用哈希函数确定键应该存储在哪个桶中。然后，它将键值对插入到相应的桶中。如果该桶中已经存在键值对，它会将新键值对追加到链表的末尾。

3. Rehash 触发：当 HashTable 中的键值对数量达到一定阈值（通常是桶数量的 75%）时，触发 rehash 操作。这个阈值被称为负载因子。

4. Rehash 过程：在 rehash 过程中，HashTable 将创建一个新的更大的桶数组。新的桶数量通常是原来的两倍。然后，它会遍历旧桶数组中的每个桶，将其中的键值对重新分配到新的桶数组中，根据它们的哈希值重新计算它们应该存储的位置。这个过程可能会导致链表被重新排列，以便更均匀地分布键值对。

5. 完成 Rehash：一旦所有键值对都被重新分配到新的桶数组中，旧的桶数组会被丢弃，完成了 rehash 过程。

6. 继续操作：在 rehash 过程中，HashTable 仍然可以处理其他操作，例如查询和删除。但是，新的插入操作可能需要等待 rehash 完成。

以下是 HashTable 的部分 rehash 源码分析。请注意，HashTable 是一个古老的类，不建议在新代码中使用，但仍然有助于理解其内部工作原理。

private void rehash() {int oldCapacity = table.length;Entry<?,?>[] oldMap = table;// 计算新的桶数组大小，通常是原来的两倍int newCapacity = (oldCapacity << 1) + 1;if (newCapacity - MAX_ARRAY_SIZE > 0) {if (oldCapacity == MAX_ARRAY_SIZE)// Keep running with MAX_ARRAY_SIZE bucketsreturn;newCapacity = MAX_ARRAY_SIZE;}// 创建新的桶数组Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];modCount++;threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);table = newMap;// 重新分配旧桶中的键值对到新桶数组中for (int i = oldCapacity ; i-- > 0 ;) {for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {Entry<K,V> e = old;old = old.next;// 计算新的桶索引并插入到新的桶中int index = (e.hash & 0x7FFFFFFF) % newCapacity;e.next = (Entry<K,V>)newMap[index];newMap[index] = e;}}
}

这段代码展示了 HashTable 的 rehash 过程：

• 首先，计算新的桶数组大小 newCapacity，通常是原来的两倍，并确保不会超过 MAX_ARRAY_SIZE。

• 创建新的桶数组 newMap。

• 更新 threshold，它表示下一次触发 rehash 的阈值。

• 遍历旧的桶数组，将每个桶中的键值对重新分配到新的桶数组中，根据它们的哈希值计算新的桶索引。

• 最后，更新 table，将旧的桶数组替换为新的桶数组。

这样就完成了 HashTable 的 rehash 过程，以保持性能并维护负载因子。需要注意的是，HashTable 的 rehash 过程是同步的，因此可能会影响其他线程的操作，需要小心使用。在现代 Java 中，推荐使用 HashMap 或 ConcurrentHashMap，它们提供更好的性能和灵活性。

上述代码摘录展示了 HashTable 类的关键部分。它使用了一个数组来存储键值对，每个数组元素是一个链表的头节点，解决哈希冲突。哈希表的扩容、查找、插入等操作都有对应的方法来实现。

需要注意的是，HashTable 是线程安全的，但性能不如后续引入的 ConcurrentHashMap，因为 HashTable 使用了全表锁来保证线程安全。在多线程环境中，通常建议使用 ConcurrentHashMap 来获得更好的性能。

此外，HashTable 在现代 Java 中很少使用，因为它的功能有限，不支持 null 键和值，而且性能相对较差。通常情况下，推荐使用 HashMap 或 ConcurrentHashMap 来替代 HashTable。

注意事项

在使用 HashTable 时，有一些重要的注意事项，特别是在多线程环境下。以下是一些关键的注意事项：

1. 线程安全性：HashTable 是线程安全的数据结构，所有公共方法都是同步的。这意味着多个线程可以同时访问和修改 HashTable 的内容而不会出现数据不一致的情况。但要注意，虽然它是线程安全的，但性能相对较低，不适用于高度并发的场景。

2. null 键和值：HashTable 不允许键或值为 null。如果尝试将 null 键或值放入 HashTable，将会抛出 NullPointerException。这一点与 HashMap 不同，后者允许键和值都为 null。

3. 遍历：在遍历 HashTable 时，可以使用迭代器或枚举器。请注意，在遍历期间修改 HashTable 的结构可能会导致 ConcurrentModificationException 异常。

4. 初始化容量和负载因子：与 HashMap 类似，HashTable 也有初始容量和负载因子的概念。可以在构造函数中指定这些参数，以适应不同的应用场景。

5. 性能考虑：HashTable 在多线程环境下提供了线程安全，但其性能可能相对较低。如果需要更高性能的线程安全哈希表，可以考虑使用 ConcurrentHashMap。

6. 不建议使用：尽管 HashTable 是一个线程安全的数据结构，但由于其性能相对较差，不允许 null 键和值，以及其他限制，通常不建议在新的 Java 代码中使用它。更常见的做法是使用 HashMap 或 ConcurrentHashMap，根据需求选择合适的实现。

总的来说，HashTable 是一个古老而受限的数据结构，虽然它具有线程安全性，但在现代 Java 中有更好的替代方案。在编写新的 Java 代码时，通常建议选择更现代的线程安全哈希表实现，以获得更好的性能和更多的灵活性。

结语

下一章我们将继续探讨其他与 HashMap 相关的关键数据结构，包括 ConcurrentHashMap、HashSet、LinkedHashMap 。这些数据结构在特定的应用场景中发挥了重要作用，它们具有不同的特性和性能特点，我将详细介绍它们的使用方法、优势以及适用的情况。如果您在这些内容中发现任何不准确或需要进一步说明的地方，欢迎提出，我将尽力提供准确和有用的信息。让我们共同学习，共同进步。