安卓开发工程师-Java 常用数据结构

1. Java 中的数组和集合有什么区别？

数组：

• 长度固定：一旦声明，长度不能改变。
• 类型单一：只能存储相同类型的元素。
• 存储效率高：底层是连续的内存空间，访问速度快。
• 示例代码：

int[] arr = new int[5]; // 声明一个长度为5的整型数组
arr[0] = 10;
arr[1] = 20;
System.out.println(arr[0]); // 输出10

集合：

• 长度可变：可以根据需要动态调整大小。
• 类型灵活：可以存储不同类型的对象（通过泛型可以限制类型）。
• 功能丰富：提供了许多操作元素的方法，如添加、删除、查找等。
• 示例代码：

import java.util.ArrayList;
import java.util.List;public class Main {public static void main(String[] args) {List<Integer> list = new ArrayList<>(); // 创建一个ArrayList集合list.add(10); // 添加元素list.add(20);System.out.println(list.get(0)); // 输出10list.remove(0); // 删除元素System.out.println(list.size()); // 输出集合大小}
}

总结：数组适合存储固定数量的同类型数据，集合适合存储动态数量的灵活类型数据。

2. 介绍 Java 中的 List 接口及其常用实现类

List 接口：

• 是一个有序的集合，可以存储重复的元素。
• 提供了按索引访问、添加、删除等操作。

常用实现类：

• ArrayList：基于动态数组实现，随机访问速度快，增删操作较慢。
• LinkedList：基于双向链表实现，增删操作快，随机访问较慢。
• Vector：与 ArrayList 类似，但是线程安全的，性能稍差。

示例代码：

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;public class Main {public static void main(String[] args) {// ArrayList示例List<String> arrayList = new ArrayList<>();arrayList.add("Java");arrayList.add("Python");System.out.println(arrayList.get(0)); // 输出Java// LinkedList示例List<String> linkedList = new LinkedList<>();linkedList.add("Java");linkedList.add("Python");linkedList.addFirst("C++"); // 在头部添加元素System.out.println(linkedList.get(0)); // 输出C++}
}

3. Set 接口和 Map 接口的区别是什么？

Set 接口：

• 是一个不包含重复元素的集合。
• 不保证元素的顺序，可以使用 LinkedHashSet 保证插入顺序。

Map 接口：

• 是一个键值对的集合，键是唯一的，值可以重复。
• 根据键快速查找对应的值。

区别：

• Set 存储单个元素，Map 存储键值对。
• Set 不能有重复元素，Map 的键不能重复。

示例代码：

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;public class Main {public static void main(String[] args) {// Set示例Set<String> set = new HashSet<>();set.add("Java");set.add("Python");set.add("Java"); // 重复元素不会被添加System.out.println(set.size()); // 输出2// Map示例Map<String, Integer> map = new HashMap<>();map.put("Java", 1);map.put("Python", 2);map.put("Java", 3); // 键重复，值会被覆盖System.out.println(map.get("Java")); // 输出3}
}

4. 如何实现一个自定义的集合类？

可以通过实现 Collection 或 List 等接口来实现自定义集合类。以下是一个简单的自定义集合类示例，实现 List 接口：

import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;public class MyArrayList<T> implements List<T> {private Object[] elements;private int size;public MyArrayList() {elements = new Object[10]; // 初始容量size = 0;}@Overridepublic int size() {return size;}@Overridepublic boolean isEmpty() {return size == 0;}@Overridepublic boolean contains(Object o) {for (int i = 0; i < size; i++) {if (elements[i].equals(o)) {return true;}}return false;}@Overridepublic Iterator<T> iterator() {return new Iterator<T>() {private int currentIndex = 0;@Overridepublic boolean hasNext() {return currentIndex < size;}@Overridepublic T next() {if (!hasNext()) {throw new NoSuchElementException();}return (T) elements[currentIndex++];}};}@Overridepublic Object[] toArray() {return new Object[0];}@Overridepublic <T1> T1[] toArray(T1[] a) {return null;}@Overridepublic boolean add(T t) {if (size == elements.length) {resize();}elements[size++] = t;return true;}private void resize() {Object[] newElements = new Object[elements.length * 2];System.arraycopy(elements, 0, newElements, 0, elements.length);elements = newElements;}@Overridepublic boolean remove(Object o) {for (int i = 0; i < size; i++) {if (elements[i].equals(o)) {System.arraycopy(elements, i + 1, elements, i, size - i - 1);elements[--size] = null;return true;}}return false;}@Overridepublic boolean containsAll(Collection<?> c) {return false;}@Overridepublic boolean addAll(Collection<? extends T> c) {return false;}@Overridepublic boolean addAll(int index, Collection<? extends T> c) {return false;}@Overridepublic boolean removeAll(Collection<?> c) {return false;}@Overridepublic boolean retainAll(Collection<?> c) {return false;}@Overridepublic void clear() {for (int i = 0; i < size; i++) {elements[i] = null;}size = 0;}@Overridepublic T get(int index) {if (index < 0 || index >= size) {throw new IndexOutOfBoundsException();}return (T) elements[index];}@Overridepublic T set(int index, T element) {if (index < 0 || index >= size) {throw new IndexOutOfBoundsException();}T oldElement = (T) elements[index];elements[index] = element;return oldElement;}@Overridepublic void add(int index, T element) {if (index < 0 || index > size) {throw new IndexOutOfBoundsException();}if (size == elements.length) {resize();}System.arraycopy(elements, index, elements, index + 1, size - index);elements[index] = element;size++;}@Overridepublic T remove(int index) {if (index < 0 || index >= size) {throw new IndexOutOfBoundsException();}T removedElement = (T) elements[index];System.arraycopy(elements, index + 1, elements, index, size - index - 1);elements[--size] = null;return removedElement;}@Overridepublic int indexOf(Object o) {for (int i = 0; i < size; i++) {if (elements[i].equals(o)) {return i;}}return -1;}@Overridepublic int lastIndexOf(Object o) {for (int i = size - 1; i >= 0; i--) {if (elements[i].equals(o)) {return i;}}return -1;}@Overridepublic ListIterator<T> listIterator() {return null;}@Overridepublic ListIterator<T> listIterator(int index) {return null;}@Overridepublic List<T> subList(int fromIndex, int toIndex) {return null;}
}

5. Java 中的队列和栈是如何实现的？

队列：

• 是一种先进先出（FIFO）的数据结构。
• Java 中的 Queue 接口提供了队列的基本操作，如 add、remove、peek 等。
• 常用实现类有 LinkedList（实现了 Queue 接口）、ArrayDeque 等。

栈：

• 是一种后进先出（LIFO）的数据结构。
• Java 中的 Stack 类提供了栈的基本操作，如 push、pop、peek 等。
• 也可以使用 Deque 接口的实现类（如 ArrayDeque）来模拟栈。

示例代码：

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;public class Main {public static void main(String[] args) {// 队列示例Queue<String> queue = new LinkedList<>();queue.add("Java");queue.add("Python");System.out.println(queue.poll()); // 输出JavaSystem.out.println(queue.peek()); // 输出Python// 栈示例Deque<String> stack = new ArrayDeque<>();stack.push("Java");stack.push("Python");System.out.println(stack.pop()); // 输出PythonSystem.out.println(stack.peek()); // 输出Java}
}

6. 什么是二叉树，Java 中如何实现一个二叉树？

二叉树：

• 是一种树形数据结构，每个节点最多有两个子节点，通常称为左子节点和右子节点。
• 常见的二叉树有二叉查找树、平衡二叉树、红黑树等。

Java 实现：

class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int val) {this.val = val;}
}public class BinaryTree {private TreeNode root;public BinaryTree() {root = null;}public void insert(int val) {root = insertRecursive(root, val);}private TreeNode insertRecursive(TreeNode root, int val) {if (root == null) {return new TreeNode(val);}if (val < root.val) {root.left = insertRecursive(root.left, val);} else if (val > root.val) {root.right = insertRecursive(root.right, val);}return root;}public void inorderTraversal() {inorderRecursive(root);}private void inorderRecursive(TreeNode root) {if (root != null) {inorderRecursive(root.left);System.out.print(root.val + " ");inorderRecursive(root.right);}}public static void main(String[] args) {BinaryTree tree = new BinaryTree();tree.insert(5);tree.insert(3);tree.insert(7);tree.insert(2);tree.insert(4);tree.insert(6);tree.insert(8);System.out.println("中序遍历结果：");tree.inorderTraversal(); // 输出2 3 4 5 6 7 8}
}

7. 如何实现一个哈希表？

哈希表是一种通过哈希函数将键映射到值的数据结构。以下是简单的哈希表实现：

import java.util.LinkedList;
import java.util.List;public class SimpleHashTable<K, V> {private static final int DEFAULT_CAPACITY = 16;private List<Entry<K, V>>[] table;public SimpleHashTable() {table = new List[DEFAULT_CAPACITY];for (int i = 0; i < DEFAULT_CAPACITY; i++) {table[i] = new LinkedList<>();}}public void put(K key, V value) {int index = key.hashCode() % table.length;List<Entry<K, V>> bucket = table[index];for (Entry<K, V> entry : bucket) {if (entry.getKey().equals(key)) {entry.setValue(value);return;}}bucket.add(new Entry<>(key, value));}public V get(K key) {int index = key.hashCode() % table.length;List<Entry<K, V>> bucket = table[index];for (Entry<K, V> entry : bucket) {if (entry.getKey().equals(key)) {return entry.getValue();}}return null;}private static class Entry<K, V> {private K key;private V value;public Entry(K key, V value) {this.key = key;this.value = value;}public K getKey() {return key;}public V getValue() {return value;}public void setValue(V value) {this.value = value;}}public static void main(String[] args) {SimpleHashTable<String, Integer> hashTable = new SimpleHashTable<>();hashTable.put("Java", 1);hashTable.put("Python", 2);System.out.println(hashTable.get("Java")); // 输出1System.out.println(hashTable.get("Python")); // 输出2}
}

8. 介绍 Java 中的排序算法，如冒泡排序、快速排序等

冒泡排序：

• 通过相邻元素的比较和交换，将较大的元素“冒泡”到数组的末尾。
• 时间复杂度：O(n²)。

示例代码：

public class BubbleSort {public static void bubbleSort(int[] arr) {int n = arr.length;for (int i = 0; i < n - 1; i++) {for (int j = 0; j < n - 1 - i; j++) {if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}}public static void main(String[] args) {int[] arr = {64, 34, 25, 12, 22, 11, 90};bubbleSort(arr);for (int i : arr) {System.out.print(i + " ");} // 输出11 12 22 25 34 64 90}
}

快速排序：

• 通过分治法，选择一个基准元素，将数组分为小于基准和大于基准的两部分，递归排序。
• 时间复杂度：平均 O(nlogn)，最坏 O(n²)。

示例代码：

public class QuickSort {public static void quickSort(int[] arr, int low, int high) {if (low < high) {int pivotIndex = partition(arr, low, high);quickSort(arr, low, pivotIndex - 1);quickSort(arr, pivotIndex + 1, high);}}private static int partition(int[] arr, int low, int high) {int pivot = arr[high];int i = low - 1;for (int j = low; j < high; j++) {if (arr[j] <= pivot) {i++;int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}int temp = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp;return i + 1;}public static void main(String[] args) {int[] arr = {10, 7, 8, 9, 1, 5};quickSort(arr, 0, arr.length - 1);for (int i : arr) {System.out.print(i + " ");} // 输出1 5 7 8 9 10}
}

9. 如何实现一个链表？

链表是一种线性数据结构，由节点组成，每个节点包含数据部分和指向下一个节点的指针。

单链表实现：

class Node {int data;Node next;Node(int data) {this.data = data;this.next = null;}
}public class LinkedList {private Node head;public LinkedList() {head = null;}public void add(int data) {Node newNode = new Node(data);if (head == null) {head = newNode;} else {Node current = head;while (current.next != null) {current = current.next;}current.next = newNode;}}public void display() {Node current = head;while (current != null) {System.out.print(current.data + " ");current = current.next;}System.out.println();}public static void main(String[] args) {LinkedList list = new LinkedList();list.add(10);list.add(20);list.add(30);list.display(); // 输出10 20 30}
}

10. Java 中的字符串是如何存储和操作的？

存储：

• Java 中的字符串是不可变的（immutable），一旦创建，内容不能修改。
• 字符串底层是通过字符数组 char[] 存储的。
• 使用 String 类表示字符串，String 是一个 final 类，不能被继承。

操作：

• 常见操作包括拼接、查找、替换、比较等。
• 示例代码：

public class StringExample {public static void main(String[] args) {String str1 = "Hello";String str2 = "World";String str3 = str1 + " " + str2; // 拼接System.out.println(str3); // 输出Hello WorldSystem.out.println(str3.length()); // 输出11System.out.println(str3.charAt(0)); // 输出HSystem.out.println(str3.indexOf("World")); // 输出6System.out.println(str3.replace("World", "Java")); // 输出Hello JavaSystem.out.println(str3.equals("Hello World")); // 输出true}
}

如果需要频繁修改字符串，建议使用 StringBuilder 或 StringBuffer，因为它们是可变的，性能更好。