圖解LinkedHashSet數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)與應(yīng)用案例
LinkedHashSet 是 Java 中的一個(gè)集合類，它繼承自 HashSet 并實(shí)現(xiàn)了 Set 接口。與 HashSet 一樣， LinkedHashSet 不允許重復(fù)元素，但它維護(hù)了元素插入的順序，即元素迭代的順序與它們插入的順序相同。 LinkedHashSet 在內(nèi)部使用鏈表來(lái)維護(hù)元素的插入順序，同時(shí)使用哈希表來(lái)快速定位元素，這使得它在保持快速查找性能的同時(shí)，還能夠按插入順序遍歷元素。由于其基于哈希表和鏈表的實(shí)現(xiàn)， LinkedHashSet 在進(jìn)行元素插入和刪除操作時(shí)具有較高的性能，但在隨機(jī)訪問(wèn)操作上的性能不如基于動(dòng)態(tài)數(shù)組的 ArrayList。 LinkedHashSet 是非線程安全的，適用于需要保持插入順序的場(chǎng)景，如需要有序去重或有序集合操作。
1、 LinkedHashSet
LinkedHashSet 是 Java 集合框架中的一個(gè)成員，它結(jié)合了 HashSet 的快速查找特性和 LinkedList 的插入順序保持功能。以下是 LinkedHashSet 的設(shè)計(jì)：
設(shè)計(jì)思考：
- 需求場(chǎng)景：
在很多應(yīng)用場(chǎng)景中，需要快速地插入、刪除和查找元素，同時(shí)也需要保持元素的插入順序。
例如，在處理用戶會(huì)話、緩存實(shí)現(xiàn)、任務(wù)調(diào)度等場(chǎng)景時(shí)，保持元素的添加順序是非常重要的。
- 現(xiàn)有技術(shù)局限性：
HashSet 提供了常數(shù)時(shí)間的添加、刪除和查找性能，但它不保持元素的插入順序。
TreeSet 保持了元素的排序順序，但不是插入順序，且它的性能不如 HashSet。
ArrayList 和 LinkedList 保持了插入順序，但它們的查找性能為線性時(shí)間復(fù)雜度。
技術(shù)融合：
為了結(jié)合 HashSet 的快速查找能力和 LinkedList 的插入順序保持能力， LinkedHashSet 應(yīng)運(yùn)而生。
設(shè)計(jì)理念：
LinkedHashSet 底層使用 HashMap 來(lái)存儲(chǔ)元素，保證了快速的查找性能。
同時(shí)，它在每個(gè) HashMap 的條目上使用一個(gè)雙向鏈表來(lái)維護(hù)元素的插入順序。
實(shí)現(xiàn)方式：
LinkedHashSet 繼承自 HashSet，但重寫了 add、 iterator 等方法，以維護(hù)插入順序。
它在內(nèi)部維護(hù)了與 HashMap 條目關(guān)聯(lián)的雙向鏈表的節(jié)點(diǎn)，這些節(jié)點(diǎn)鏈接了具有相同哈希值但插入順序不同的元素。
2、 數(shù)據(jù)結(jié)構(gòu)
圖片
圖說(shuō)明：
- LinkedHashSet:
表示 LinkedHashSet 類的實(shí)例，它繼承自 HashSet 并維護(hù)元素的插入順序。
- HashMap:
LinkedHashSet 的實(shí)現(xiàn)基于 HashMap，用來(lái)存儲(chǔ)集合中的元素。
數(shù)組 (Buckets) :
HashMap 使用一個(gè)數(shù)組來(lái)存儲(chǔ)桶（Buckets），桶是用于存儲(chǔ) Entry 對(duì)象的容器。
哈希桶:
每個(gè)桶內(nèi)部使用鏈表來(lái)解決哈希沖突。
鏈表 Entry:
每個(gè)桶包含多個(gè) Entry 對(duì)象，它們通過(guò)鏈表連接。
紅黑樹(shù) Entry:
當(dāng)鏈表長(zhǎng)度超過(guò)閾值時(shí)，鏈表可能會(huì)被轉(zhuǎn)換成紅黑樹(shù)以提高搜索效率。
鏈表 節(jié)點(diǎn)1 和 鏈表 節(jié)點(diǎn)2:
表示鏈表中的節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)存儲(chǔ)著集合中的一個(gè)元素，并指向前一個(gè)和后一個(gè)節(jié)點(diǎn)，形成雙向鏈表。
元素:
存儲(chǔ)在 LinkedHashSet 中的最終數(shù)據(jù)。
3、 執(zhí)行流程
圖片
圖說(shuō)明：
- 創(chuàng)建 LinkedHashSet 實(shí)例:
初始化 LinkedHashSet 對(duì)象。
- 添加元素:
將元素添加到 LinkedHashSet。
計(jì)算元素的hashCode:
調(diào)用元素的 hashCode() 方法計(jì)算其哈希碼。
確定數(shù)組索引位置:
根據(jù)哈希碼和數(shù)組長(zhǎng)度確定數(shù)組索引位置。
找到對(duì)應(yīng)的哈希桶:
定位到數(shù)組中對(duì)應(yīng)的哈希桶。
檢查哈希桶中的鏈表/紅黑樹(shù):
檢查哈希桶中是否已有鏈表或紅黑樹(shù)結(jié)構(gòu)。
處理哈希沖突:
如果桶中已有元素，處理哈希沖突。
元素添加至鏈表/紅黑樹(shù):
將新元素添加至對(duì)應(yīng)索引的鏈表或紅黑樹(shù)中。
刪除元素:
從 LinkedHashSet 刪除元素。
重新計(jì)算元素的hashCode:
調(diào)用元素的 hashCode() 方法計(jì)算其哈希碼。
確定刪除元素的數(shù)組索引位置:
根據(jù)哈希碼和數(shù)組長(zhǎng)度確定數(shù)組索引位置。
找到刪除元素的哈希桶:
定位到數(shù)組中對(duì)應(yīng)的哈希桶。
從鏈表/紅黑樹(shù)中刪除元素:
從對(duì)應(yīng)索引的鏈表或紅黑樹(shù)中刪除元素。
遍歷 LinkedHashSet:
遍歷 LinkedHashSet 中的所有元素。
獲取數(shù)組:
獲取 LinkedHashSet 內(nèi)部的數(shù)組。
遍歷每個(gè)桶:
遍歷數(shù)組的每個(gè)桶。
遍歷鏈表/紅黑樹(shù):
遍歷桶內(nèi)的鏈表或紅黑樹(shù)中的所有元素。
讀取元素:
讀取鏈表或紅黑樹(shù)中的元素。
4、優(yōu)點(diǎn)：
- 快速查找：
繼承自 HashSet，具有快速的查找、添加和刪除操作。
- 保持插入順序：
通過(guò)內(nèi)部維護(hù)的雙向鏈表，保持了元素的插入順序。
空間和時(shí)間效率：
相對(duì)于 TreeSet， LinkedHashSet 在大多數(shù)情況下具有更好的性能。
5、缺點(diǎn)：
- 內(nèi)存占用：
相比于 HashSet， LinkedHashSet 需要額外的內(nèi)存來(lái)維護(hù)雙向鏈表。
- 復(fù)雜性：
相比于簡(jiǎn)單的 HashSet， LinkedHashSet 的實(shí)現(xiàn)和使用復(fù)雜度稍高。
6、使用場(chǎng)景：
- 需要快速查找和保持插入順序的場(chǎng)景，如 LRU 緩存、任務(wù)調(diào)度、用戶會(huì)話管理等。
7、類設(shè)計(jì)
圖片
8、應(yīng)用案例
LinkedHashSet 通常用于需要保持元素插入順序的場(chǎng)景。這是一個(gè)用戶會(huì)話管理器，用于跟蹤用戶的登錄狀態(tài)和最后活躍時(shí)間：
import java.util.LinkedHashSet;
import java.util.Set;
// 用戶類，用于表示系統(tǒng)中的用戶
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 +
'}';
}
}
// 用戶會(huì)話管理器類
class UserSessionManager {
private Set<User> activeUsers;
public UserSessionManager() {
activeUsers = new LinkedHashSet<>();
}
// 添加或更新用戶會(huì)話
public void addUser(User user) {
activeUsers.add(user);
}
// 獲取所有活躍用戶
public Set<User> getActiveUsers() {
return activeUsers;
}
// 移除用戶會(huì)話
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);
}
}
}
