1. 關聯對象存儲（AssociationsHashMap）

// 關聯對象的哈希表實現
typedef DenseMap<const void *, ObjcAssociation> ObjectAssociationMap;
typedef DenseMap<DisguisedPtr<objc_object>, ObjectAssociationMap> AssociationsHashMap;class AssociationsManager {static AssociationsHashMap *_map;  // 全局關聯對象表void set(id object, const void *key, id value) {// 雙層 map：對象 -> (key -> value)AssociationsHashMap::iterator i = _map->find(object);if (i != _map->end()) {ObjectAssociationMap &refs = i->second;refs[key] = ObjcAssociation(value);}}
};// 特點：
// 1. 雙層哈希表結構
// 2. 使用 DenseMap 實現
// 3. 支持動態擴容

注意事項：

• 需要考慮內存開銷

• 多層查找可能影響性能

• 需要正確管理關聯對象的生命周期

2. 引用計數表（RefcountMap）

// SideTable 中的引用計數表
class SideTable {RefcountMap refcnts;  // 存儲對象的引用計數void retain(id obj) {RefcountMap::iterator it = refcnts.find(obj);if (it != refcnts.end()) {it->second += SIDE_TABLE_RC_ONE;}}
};typedef objc::DenseMap<DisguisedPtr<objc_object>, size_t> RefcountMap;// 特點：
// 1. 使用 DenseMap 實現
// 2. Key 使用偽裝指針
// 3. 需要頻繁訪問和修改

注意事項：

• 需要保證原子性操作

• 性能要求高

• 內存管理要謹慎

3. 弱引用表（weak_table_t）

// 弱引用哈希表
struct weak_table_t {weak_entry_t *weak_entries;  // 哈希數組size_t num_entries;          // 實際條目數uintptr_t mask;             // 容量掩碼uintptr_t max_hash_displacement; // 最大哈希偏移weak_entry_t *get(id referent) {// 使用哈希查找size_t begin = hash_pointer(referent) & mask;size_t index = begin;size_t hash_displacement = 0;while (weak_entries[index].referent != referent) {index = (index + 1) & mask;if (index == begin) break;hash_displacement++;}return &weak_entries[index];}
};// 特點：
// 1. 開放尋址法處理沖突
// 2. 使用線性探測
// 3. 記錄最大偏移量

注意事項：

• 需要控制裝載因子，避免性能下降

• 刪除元素時需要特殊處理，避免破壞探測鏈

• 擴容時需要重新哈希所有元素

4. 方法緩存（cache_t）

// 類的方法緩存
struct cache_t {struct bucket_t *_buckets;  // 哈希表mask_t _mask;              // 容量掩碼mask_t _occupied;          // 已使用數量IMP imp(SEL sel) {// 使用哈希查找方法實現bucket_t *b = buckets();mask_t m = mask();return findMethod(b, m, sel);}
};// 特點：
// 1. 采用散列函數直接尋址
// 2. 緩存最近使用的方法
// 3. 固定大小，滿了就清空重建

注意事項：

• 緩存滿時會清空重建，而不是擴容

• 性能敏感，需要快速查找

• 線程安全問題需要特別注意

5. 性能優化

// 使用 DenseMap 優化內存使用
template <typename T, typename U, typename V>
class DenseMap {// 1. 開放尋址法處理沖突pair<iterator, bool> insert(const T& key, const U& value) {// 查找空位置unsigned index = findEmptyBucket(key);// 插入數據Buckets[index] = make_pair(key, value);}// 2. 自動擴容void grow() {unsigned NewSize = size() * 2;rehash(NewSize);}
};

6. 使用特點

6.1?線程安全

// 訪問 map 時加鎖保護
spinlock_t& lock = SideTables()[obj].lock;
lock.lock();
// 操作 map
lock.unlock();

6.2 內存管理

// 定期清理
void cleanup() {// 遍歷并清理無效條目for (iterator it = map.begin(); it != map.end();) {if (it->second.expired()) {it = map.erase(it);} else {++it;}}
}

6.3 哈希優化

// 優化的哈希函數
static inline uint32_t ptr_hash(const void *key) {uintptr_t k = (uintptr_t)key;return (uint32_t)(k ^ (k >> 7));
}

主要使用場景總結：

1. 關聯對象存儲
2. 引用計數管理
3. 弱引用表實現
4. 方法緩存
5. 性能優化

使用特點：

1. 多采用 DenseMap 實現
2. 注重性能優化
3. 考慮線程安全
4. 自動內存管理
5. 哈希沖突處理

7. 實現差異

7.1 沖突處理

// 開放尋址法
void insert(Key key, Value value) {size_t index = hash(key) & mask;while (table[index] != empty) {index = (index + 1) & mask;  // 線性探測}table[index] = value;
}// 鏈地址法
void insert(Key key, Value value) {size_t index = hash(key) & mask;table[index].push_back(value);  // 添加到鏈表
}

7.2 擴容策略

// weak_table_t 的擴容
void grow() {// 當使用率超過 3/4 時擴容if (num_entries >= capacity * 3/4) {resize(capacity * 2);}
}// cache_t 的重建
void rebuild() {// 緩存滿時直接清空重建clear();allocate(capacity);
}

7.3 內存管理

// DenseMap 的內存管理
template <typename Key, typename Value>
class DenseMap {// 使用連續內存pair<Key, Value> *Buckets;// 自動擴容void grow() {reallocate(NumEntries * 2);}
};

8. 性能考慮

8.1?查找效率

// 方法緩存優化
IMP cache_t::imp(SEL sel) {// 使用位運算優化mask_t index = (mask_t)(uintptr_t)sel & _mask;return _buckets[index].imp();
}

8.2 空間效率

// weak_table_t 的空間優化
struct weak_entry_t {union {struct {weak_referrer_t *referrers;      // 動態數組};struct {weak_referrer_t  inline_referrers[WEAK_INLINE_COUNT]; // 內聯存儲};};
};

總結：

1. 不同場景選擇不同的哈希表實現
2. 需要權衡時間和空間效率
3. 要考慮線程安全問題
4. 注意內存管理和性能優化
5. 合理處理哈希沖突
6. 選擇適當的擴容策略