1. 數(shù)組

2. 鏈表

3. 棧

4. 隊(duì)列

5. 樹

1. 紅黑樹（自平衡二叉樹）
   增刪改查時(shí)間復(fù)雜度 O（log n）
   二叉搜索樹（BST）：左子節(jié)點(diǎn) < 父節(jié)點(diǎn) < 右子節(jié)點(diǎn)。

• 問題：若插入順序不當(dāng)（如從小到大插入），BST 會退化為鏈表，查找效率從 O(log n) 降為 O(n)。

平衡二叉樹（Balanced Binary Tree）

• 核心思想：通過調(diào)整樹的結(jié)構(gòu)，避免退化為鏈表，保證左右子樹高度差不超過 1。
• 目標(biāo)：維持操作（插入、刪除、查找）的時(shí)間復(fù)雜度為 O(log n)。
• 常見類型：
  • AVL 樹：通過旋轉(zhuǎn)（左旋/右旋）保持平衡，高度差 ≤1。
  • 紅黑樹：通過顏色標(biāo)記和規(guī)則約束，近似平衡（高度差 ≤2 倍）。

6. 哈希表

在理想情況下，插入、刪除和查找的平均時(shí)間復(fù)雜度是O(1)。

1. 主要：哈希函數(shù)：給定一個(gè)函數(shù)輸入，將輸入映射到某個(gè)值，得出當(dāng)前元素如何存儲（哈希函數(shù)示例？）
   哈希函數(shù)是將鍵（Key）轉(zhuǎn)換為哈希值（size_t 類型整數(shù)）的核心組件。哈希值決定了鍵值對存儲在哈希表的哪個(gè)“桶”（bucket）中，每個(gè)桶維護(hù)一個(gè)鏈表數(shù)據(jù)結(jié)構(gòu)，解決哈希沖突問題。

2. 哈希沖突：不同輸入，得到同樣哈希值，如何解決？

   • 鏈表存儲，元素多了使用樹存儲（增刪改查時(shí)間復(fù)雜度log(n)）。

3. c++ unorder_set 實(shí)現(xiàn)
   unordered_set是無序的，那么它應(yīng)該也是基于哈希表的。每個(gè)元素本身就是鍵，不需要關(guān)聯(lián)額外的值。因此，哈希表在這里存儲的是單個(gè)元素，而不是鍵值對。當(dāng)插入一個(gè)元素時(shí)，計(jì)算該元素的哈希值，找到對應(yīng)的桶，然后將元素存入該桶中。如果發(fā)生哈希沖突，比如兩個(gè)不同的元素有相同的哈希值，那么它們會被放在同一個(gè)桶里，通常通過鏈表連接。

4. c++ unorder_map實(shí)現(xiàn)
   C++標(biāo)準(zhǔn)庫中unordered_set的實(shí)現(xiàn)機(jī)制。哈希表的基本結(jié)構(gòu)是將鍵通過哈希函數(shù)映射到桶（bucket），然后處理可能的沖突，通常使用鏈地址法（每個(gè)桶是一個(gè)鏈表）或者開放尋址法。對于unordered_map來說，每個(gè)鍵值對被存儲在哈希表的某個(gè)桶中，鍵用于計(jì)算哈希值，值則與鍵關(guān)聯(lián)存儲。
   unordered_map和unordered_set都是基于哈希表，但unordered_map存儲的是鍵值對，而unordered_set只存儲鍵。

/**< Hash 函數(shù)實(shí)現(xiàn) unorder_map 示例 **/
// std 庫內(nèi)實(shí)現(xiàn)的哈希函數(shù)對象模版，在<bits/functional_hash.h> 中定義
namespace std {
	template<typename T>
	struct hash {
		size_t operator()(const T& key) const {
			// hash函數(shù)實(shí)現(xiàn)（若未特化，編譯報(bào)錯(cuò)）
			return __hash__impl<T>::hash(key);
		}
	};
	
	// 對 int 特化
	template<> // 表明是模版特化
	struct hash<int> {
		size_t operator()(const int& key) const {
			return static_cast<size_t>(key);
		}
	};
};

// unordered_map 實(shí)現(xiàn)示例，在<bits/unordered_map.h> 中定義
template<typename Key, 
		typename Value,
		typename Hash = std::hash<key>, // 默認(rèn)使用 std::hash
		typename KeyEqual = std::equal_to<key>>
class unordered_map {
private:
	// 桶鏈表簡化版
	struct Bucket {
		std::list<std::pair<kay, value>> entries;
	};
	std::vector<Bucket> buckets; // 哈希表桶數(shù)組
	Hash hasher;					// 哈希函數(shù)對象
	KeyEqual key_eq;		// 鍵相等比較

public:
	void insert(const Key& key, const Value& value) {
		size_t hash_value = hasher(key);
		size_t bucket_idx = hash_value % buckets.size();
	
		// 處理沖突（鏈表法）
		for (auto& entry : buckets[bucket_idx]) {
			if (entry.first == key) {
				entry.second = value;
				return;
			}
		}
	
		// 保存新元素
		buckets[bucket_idx].entries.push_back(std::pair<key, value>);
	}
};

對于自定義的鍵，需要特化hash函數(shù)模版或者自定義哈希函數(shù)，才能使用unordered_map
補(bǔ)充：c++模版特化

• 在 C++ 中，模板（Template） 允許你編寫通用的代碼，適用于多種數(shù)據(jù)類型。但某些類型需要特殊處理，這時(shí)就需要 模板特化（Template Specialization） —— 為特定類型定制專門的實(shí)現(xiàn)。
• 模板特化是指為特定的數(shù)據(jù)類型提供一個(gè)特定的實(shí)現(xiàn)，覆蓋通用模板的默認(rèn)行為。
• 默認(rèn)情況下可能沒有為所有類型實(shí)現(xiàn)，特別是用戶自定義的類型。當(dāng)嘗試使用一個(gè)沒有特化std::hash的自定義類型作為unordered_map或unordered_set的鍵時(shí)，編譯器找不到對應(yīng)的哈希函數(shù)，因此會報(bào)錯(cuò)。
• 類模板的特化，通常需要重新定義整個(gè)類，而不僅僅是某些成員函數(shù)。但如果是函數(shù)模板的特化，可以只特化某個(gè)函數(shù)。
• 通過模板特化，你為自定義類型“賦能”，使其無縫融入 C++ 標(biāo)準(zhǔn)庫的生態(tài)系統(tǒng)。

// 自定義鍵
/**
為什么需要定義 operator==？
哈希表處理沖突時(shí)（不同鍵映射到同一桶），需要比較鍵是否真正相等。
**/
class Person {
public:
	int age;
	std::string name;
	// 對于作為鍵的類，需要重載 ==(用于沖突解決)
	bool operator==(const Person& p) const {
		return age == p.age && name == p.name;
	}
}

// hash 模版特化方式定義哈希函數(shù)對象
namespace std {
	template<> // 表示這是模板特化
	hash<Person> {
		size_t operator()(const Person& person) const {
			return hash<int>()(person.age) ^ (hash<string>()(person.name) << 1);
		}
	};
};
std::unordered_map<Persion, int> mp;

// 自定義哈希函數(shù)對象
struct HashMy {
	size_t operator()(const Person& person) const {
		return hash<int>()(person.age) ^( hash<string>()(person.name) << 1);
	}
}

// 使用時(shí)顯示指定哈希函數(shù)類型
std::unordered_map<Persion, int, HashMy> mp;

• std::list 雙向鏈表

7. 補(bǔ)充

1. unordered_map中的負(fù)載因子和rehashing機(jī)制？

2. 繼承/模版

   • 繼承：父類實(shí)現(xiàn)基本功能，子類對功能進(jìn)行擴(kuò)展（繼承：基礎(chǔ) -> 擴(kuò)展）
   • 模版：寫框架的，對于個(gè)別獨(dú)特的個(gè)體，可以通過特化模版，實(shí)現(xiàn)模版內(nèi)功能 （模版特化：框架 -> 個(gè)例）
     • 如果模版類寫的足夠詳細(xì)，可以實(shí)現(xiàn)處理不同數(shù)據(jù)類型的通用類。
   • 通俗講：繼承，由粗到細(xì)；模版：通用實(shí)現(xiàn)（個(gè)別特例通過模版特化解決）。