iOS - Objective-C 底层实现中的哈希表

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));
}

主要使用场景总结：

关联对象存储
引用计数管理
弱引用表实现
方法缓存
性能优化

使用特点：

多采用 DenseMap 实现
注重性能优化
考虑线程安全
自动内存管理
哈希冲突处理

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]; // 内联存储};};
};

总结：