圖解LinkedHashSet數據結構設計與應用案例
LinkedHashSet 是 Java 中的一個集合類，它繼承自 HashSet 并實現了 Set 接口。與 HashSet 一樣， LinkedHashSet 不允許重復元素，但它維護了元素插入的順序，即元素迭代的順序與它們插入的順序相同。 LinkedHashSet 在內部使用鏈表來維護元素的插入順序，同時使用哈希表來快速定位元素，這使得它在保持快速查找性能的同時，還能夠按插入順序遍歷元素。由于其基于哈希表和鏈表的實現， LinkedHashSet 在進行元素插入和刪除操作時具有較高的性能，但在隨機訪問操作上的性能不如基于動態數組的 ArrayList。 LinkedHashSet 是非線程安全的，適用于需要保持插入順序的場景，如需要有序去重或有序集合操作。
1、 LinkedHashSet
LinkedHashSet 是 Java 集合框架中的一個成員，它結合了 HashSet 的快速查找特性和 LinkedList 的插入順序保持功能。以下是 LinkedHashSet 的設計：
設計思考：
- 需求場景：
在很多應用場景中，需要快速地插入、刪除和查找元素，同時也需要保持元素的插入順序。
例如，在處理用戶會話、緩存實現、任務調度等場景時，保持元素的添加順序是非常重要的。
- 現有技術局限性：
HashSet 提供了常數時間的添加、刪除和查找性能，但它不保持元素的插入順序。
TreeSet 保持了元素的排序順序，但不是插入順序，且它的性能不如 HashSet。
ArrayList 和 LinkedList 保持了插入順序，但它們的查找性能為線性時間復雜度。
技術融合：
為了結合 HashSet 的快速查找能力和 LinkedList 的插入順序保持能力， LinkedHashSet 應運而生。
設計理念：
LinkedHashSet 底層使用 HashMap 來存儲元素，保證了快速的查找性能。
同時，它在每個 HashMap 的條目上使用一個雙向鏈表來維護元素的插入順序。
實現方式：
LinkedHashSet 繼承自 HashSet，但重寫了 add、 iterator 等方法，以維護插入順序。
它在內部維護了與 HashMap 條目關聯的雙向鏈表的節點，這些節點鏈接了具有相同哈希值但插入順序不同的元素。
2、 數據結構
圖片
圖說明：
- LinkedHashSet:
表示 LinkedHashSet 類的實例，它繼承自 HashSet 并維護元素的插入順序。
- HashMap:
LinkedHashSet 的實現基于 HashMap，用來存儲集合中的元素。
數組 (Buckets) :
HashMap 使用一個數組來存儲桶（Buckets），桶是用于存儲 Entry 對象的容器。
哈希桶:
每個桶內部使用鏈表來解決哈希沖突。
鏈表 Entry:
每個桶包含多個 Entry 對象，它們通過鏈表連接。
紅黑樹 Entry:
當鏈表長度超過閾值時，鏈表可能會被轉換成紅黑樹以提高搜索效率。
鏈表 節點1 和 鏈表 節點2:
表示鏈表中的節點，每個節點存儲著集合中的一個元素，并指向前一個和后一個節點，形成雙向鏈表。
元素:
存儲在 LinkedHashSet 中的最終數據。
3、 執行流程
圖片
圖說明：
- 創建 LinkedHashSet 實例:
初始化 LinkedHashSet 對象。
- 添加元素:
將元素添加到 LinkedHashSet。
計算元素的hashCode:
調用元素的 hashCode() 方法計算其哈希碼。
確定數組索引位置:
根據哈希碼和數組長度確定數組索引位置。
找到對應的哈希桶:
定位到數組中對應的哈希桶。
檢查哈希桶中的鏈表/紅黑樹:
檢查哈希桶中是否已有鏈表或紅黑樹結構。
處理哈希沖突:
如果桶中已有元素，處理哈希沖突。
元素添加至鏈表/紅黑樹:
將新元素添加至對應索引的鏈表或紅黑樹中。
刪除元素:
從 LinkedHashSet 刪除元素。
重新計算元素的hashCode:
調用元素的 hashCode() 方法計算其哈希碼。
確定刪除元素的數組索引位置:
根據哈希碼和數組長度確定數組索引位置。
找到刪除元素的哈希桶:
定位到數組中對應的哈希桶。
從鏈表/紅黑樹中刪除元素:
從對應索引的鏈表或紅黑樹中刪除元素。
遍歷 LinkedHashSet:
遍歷 LinkedHashSet 中的所有元素。
獲取數組:
獲取 LinkedHashSet 內部的數組。
遍歷每個桶:
遍歷數組的每個桶。
遍歷鏈表/紅黑樹:
遍歷桶內的鏈表或紅黑樹中的所有元素。
讀取元素:
讀取鏈表或紅黑樹中的元素。
4、優點：
- 快速查找：
繼承自 HashSet，具有快速的查找、添加和刪除操作。
- 保持插入順序：
通過內部維護的雙向鏈表，保持了元素的插入順序。
空間和時間效率：
相對于 TreeSet， LinkedHashSet 在大多數情況下具有更好的性能。
5、缺點：
- 內存占用：
相比于 HashSet， LinkedHashSet 需要額外的內存來維護雙向鏈表。
- 復雜性：
相比于簡單的 HashSet， LinkedHashSet 的實現和使用復雜度稍高。
6、使用場景：
- 需要快速查找和保持插入順序的場景，如 LRU 緩存、任務調度、用戶會話管理等。
7、類設計
圖片
8、應用案例
LinkedHashSet 通常用于需要保持元素插入順序的場景。這是一個用戶會話管理器，用于跟蹤用戶的登錄狀態和最后活躍時間：
import java.util.LinkedHashSet;
import java.util.Set;
// 用戶類，用于表示系統中的用戶
class User {
private String id;
private String username;
private long lastActiveTime;
public User(String id, String username, long lastActiveTime) {
this.id = id;
this.username = username;
this.lastActiveTime = lastActiveTime;
}
// 省略 getter 和 setter 方法
@Override
public String toString() {
return "User{" +
"id='" + id + ''' +
", username='" + username + ''' +
", lastActiveTime=" + lastActiveTime +
'}';
}
}
// 用戶會話管理器類
class UserSessionManager {
private Set<User> activeUsers;
public UserSessionManager() {
activeUsers = new LinkedHashSet<>();
}
// 添加或更新用戶會話
public void addUser(User user) {
activeUsers.add(user);
}
// 獲取所有活躍用戶
public Set<User> getActiveUsers() {
return activeUsers;
}
// 移除用戶會話
public void removeUser(String userId) {
// 遍歷 LinkedHashSet 以找到并移除指定用戶
for (User user : activeUsers) {
if (user.getId().equals(userId)) {
activeUsers.remove(user);
break;
}
}
}
}
public class Main {
public static void main(String[] args) {
UserSessionManager sessionManager = new UserSessionManager();
// 模擬用戶登錄
sessionManager.addUser(new User("1", "Alice", System.currentTimeMillis()));
sessionManager.addUser(new User("2", "Bob", System.currentTimeMillis()));
// 獲取并打印所有活躍用戶
Set<User> activeUsers = sessionManager.getActiveUsers();
for (User user : activeUsers) {
System.out.println("Active User: " + user);
}
// 模擬用戶注銷
sessionManager.removeUser("1");
// 再次獲取并打印所有活躍用戶
activeUsers = sessionManager.getActiveUsers();
for (User user : activeUsers) {
System.out.println("Active User: " + user);
}
}
}
