數據結構第18節散列表

散列表（Hash Table），也被稱為哈希表，是一種數據結構，它通過使用哈希函數將鍵映射到數組的某個位置來實現快速查找。散列表通常提供平均時間復雜度為O(1)的查找、插入和刪除操作，這使得它們在處理大量數據時非常高效。

基本概念

哈希函數：一個將鍵轉換為數組索引的函數。理想情況下，這個函數應該均勻地分布鍵，以避免沖突。
沖突：當兩個或多個不同的鍵被哈希函數映射到同一個數組索引時，就發生了沖突。解決沖突的方法包括開放尋址法和鏈地址法。
負載因子：是散列表中元素的數量與散列表大小的比例。當負載因子過高時，散列表可能需要重新調整大小（擴容）以減少沖突。

Java中的散列表實現

在Java中，散列表可以通過HashMap類實現，它是Java集合框架的一部分。HashMap允許我們存儲鍵值對，并且提供了快速的查找、插入和刪除操作。

示例代碼

假設我們要創建一個簡單的散列表，用于存儲學生ID和他們的成績。以下是一個使用HashMap的示例：

import java.util.HashMap;public class StudentScores {public static void main(String[] args) {HashMap<Integer, Integer> scores = new HashMap<>();// 插入數據scores.put(101, 90);scores.put(102, 85);scores.put(103, 95);// 查找數據System.out.println("Score of student 101: " + scores.get(101));// 更新數據scores.put(101, 92);System.out.println("Updated score of student 101: " + scores.get(101));// 刪除數據scores.remove(102);System.out.println("After removing student 102: " + scores);// 檢查是否包含鍵System.out.println("Does the map contain student 101? " + scores.containsKey(101));}
}

在這個例子中，HashMap<Integer, Integer>表示散列表的鍵類型是整數，值類型也是整數。我們使用put方法插入數據，get方法查找數據，remove方法刪除數據，以及containsKey方法檢查散列表是否包含特定的鍵。

散列表的內部工作原理

HashMap的內部使用一個數組來存儲鍵值對，每個位置上可以是一個鏈表或者紅黑樹（當鏈表長度達到一定閾值時）。當向HashMap中添加元素時，它會計算鍵的哈希碼，然后使用該哈希碼確定元素在數組中的位置。如果發生沖突，即多個鍵的哈希碼指向同一位置，那么這些鍵值對會被鏈接在一起形成一個鏈表或紅黑樹。

當從HashMap中查找元素時，同樣的哈希計算過程被用來定位元素。如果存在沖突，則遍歷鏈表或紅黑樹直到找到正確的元素。

總結

散列表通過哈希函數和解決沖突的策略來實現高效的鍵值存儲和檢索。在Java中，HashMap是實現這一功能的常用工具。理解其內部工作原理有助于更有效地使用它并優化應用程序的性能。

讓我們通過另一個案例來深入理解散列表（哈希表）的應用。這次我們將創建一個簡單的圖書管理系統，使用散列表來存儲和管理圖書館中的書籍信息。

案例：圖書管理系統

在這個案例中，我們將使用HashMap來存儲圖書的ISBN（國際標準書號）作為鍵，以及每本書的詳細信息作為值。圖書的詳細信息可以用一個自定義的Book類來表示，其中包含書名、作者和出版年份等屬性。

創建`Book`類

首先，我們需要創建一個Book類，用于存儲圖書的詳細信息。

public class Book {private String title;private String author;private int publicationYear;public Book(String title, String author, int publicationYear) {this.title = title;this.author = author;this.publicationYear = publicationYear;}@Overridepublic String toString() {return "Book{" +"title='" + title + '\'' +", author='" + author + '\'' +", publicationYear=" + publicationYear +'}';}
}

使用`HashMap`創建圖書管理系統

接下來，我們使用HashMap<String, Book>來創建圖書管理系統。我們將ISBN作為鍵，因為它是圖書的唯一標識符。

import java.util.HashMap;public class LibrarySystem {private HashMap<String, Book> books;public LibrarySystem() {this.books = new HashMap<>();}public void addBook(String isbn, String title, String author, int publicationYear) {Book book = new Book(title, author, publicationYear);books.put(isbn, book);}public Book getBook(String isbn) {return books.get(isbn);}public void removeBook(String isbn) {books.remove(isbn);}public boolean containsBook(String isbn) {return books.containsKey(isbn);}
}

測試圖書管理系統

現在我們可以創建一個LibrarySystem實例，并測試添加、獲取和刪除圖書的功能。

public class Main {public static void main(String[] args) {LibrarySystem library = new LibrarySystem();// 添加圖書library.addBook("978-0-306-40615-7", "The C Programming Language", "Brian W. Kernighan", 1978);library.addBook("978-0-201-63361-0", "Clean Code: A Handbook of Agile Software Craftsmanship", "Robert C. Martin", 2008);// 獲取圖書信息Book book = library.getBook("978-0-306-40615-7");System.out.println(book); // 輸出: Book{title='The C Programming Language', author='Brian W. Kernighan', publicationYear=1978}// 檢查圖書是否存在System.out.println(library.containsBook("978-0-201-63361-0")); // 輸出: true// 刪除圖書library.removeBook("978-0-201-63361-0");System.out.println(library.containsBook("978-0-201-63361-0")); // 輸出: false}
}

在這個案例中，我們利用散列表的快速查找特性來高效地管理圖書館中的圖書信息。由于ISBN是唯一的，因此使用它作為散列表的鍵可以確保沒有重復的條目，同時也簡化了查找和刪除操作。

通過這個案例，你可以看到散列表在實際應用中如何提高數據訪問效率，尤其是在處理具有唯一標識符的大數據集時。

好的，讓我們繼續擴展案例，這次我們將構建一個更復雜的場景——一個任務管理器，它能夠幫助用戶跟蹤個人的任務清單。我們將使用散列表來存儲任務，以便于快速查找和管理。

案例：任務管理器

定義`Task`類

首先，我們需要定義一個Task類來存儲任務的信息，比如任務的名稱、描述、優先級和截止日期。

import java.time.LocalDate;public class Task {private String name;private String description;private int priority;private LocalDate dueDate;public Task(String name, String description, int priority, LocalDate dueDate) {this.name = name;this.description = description;this.priority = priority;this.dueDate = dueDate;}public String getName() {return name;}public String getDescription() {return description;}public int getPriority() {return priority;}public LocalDate getDueDate() {return dueDate;}@Overridepublic String toString() {return "Task{" +"name='" + name + '\'' +", description='" + description + '\'' +", priority=" + priority +", dueDate=" + dueDate +'}';}
}

創建任務管理器

接下來，我們創建一個TaskManager類，使用HashMap來存儲任務。我們將使用任務的名稱作為鍵，因為任務的名稱應該是唯一的，以避免混淆。

import java.util.HashMap;public class TaskManager {private HashMap<String, Task> tasks;public TaskManager() {this.tasks = new HashMap<>();}public void addTask(Task task) {tasks.put(task.getName(), task);}public Task getTask(String name) {return tasks.get(name);}public void removeTask(String name) {tasks.remove(name);}public boolean containsTask(String name) {return tasks.containsKey(name);}
}

測試任務管理器

現在，我們可以創建一個TaskManager實例，并測試添加、獲取和刪除任務的功能。

import java.time.LocalDate;public class Main {public static void main(String[] args) {TaskManager manager = new TaskManager();// 添加任務manager.addTask(new Task("Buy groceries", "Milk, bread, eggs", 2, LocalDate.of(2024, 7, 12)));manager.addTask(new Task("Write report", "Finish Q2 sales report", 1, LocalDate.of(2024, 7, 15)));// 獲取任務Task task = manager.getTask("Write report");System.out.println(task); // 輸出: Task{name='Write report', description='Finish Q2 sales report', priority=1, dueDate=2024-07-15}// 檢查任務是否存在System.out.println(manager.containsTask("Buy groceries")); // 輸出: true// 刪除任務manager.removeTask("Buy groceries");System.out.println(manager.containsTask("Buy groceries")); // 輸出: false}
}

擴展功能：按優先級排序

為了使任務管理器更加實用，我們可以添加一個功能來按優先級對任務進行排序。雖然HashMap不保證順序，但我們可以在TaskManager類中添加一個方法，使用優先級對任務進行排序并返回一個新的List。

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;public class TaskManager {// ...public List<Task> getTasksSortedByPriority() {List<Task> sortedTasks = new ArrayList<>(tasks.values());Collections.sort(sortedTasks, Comparator.comparingInt(Task::getPriority));return sortedTasks;}
}

然后，在Main類中，我們可以調用getTasksSortedByPriority方法來獲取按優先級排序的任務列表。

// 在Main類中
List<Task> sortedTasks = manager.getTasksSortedByPriority();
sortedTasks.forEach(System.out::println);

通過這些擴展，我們不僅能夠有效地存儲和管理任務，還能根據優先級對它們進行排序，從而幫助用戶更好地組織和規劃他們的工作。這個案例展示了散列表如何與其他數據結構如列表結合使用，以滿足更復雜的需求。