面试题：深入理解Objective-C键值对存储技术 - 冲突处理与性能优化

Question

在Objective-C字典中，当不同对象具有相同的哈希值（哈希冲突）时，系统是如何处理以确保键值对的正确存储和检索的？请从底层原理角度进行分析。并且，在处理大量键值对存储时，如何对字典进行性能优化？

Answer 1

哈希冲突处理原理

1. 链表法：在Objective - C字典（NSDictionary及其可变版本NSMutableDictionary，底层是哈希表）中，当不同对象具有相同哈希值（哈希冲突）时，通常采用链表法来解决。哈希表中的每个“桶”（bucket）实际上是一个链表的头节点。当计算出的哈希值指向同一个桶时，新的键值对会被添加到该桶对应的链表中。
2. 比较键对象：在检索键值对时，首先通过哈希值找到对应的桶。然后遍历该桶链表，对链表中的每个节点，使用isEqual:方法（或isEqualTo:等特定比较方法，取决于对象类型）来比较键对象。只有当哈希值相同且isEqual:方法返回YES时，才认为找到了正确的键值对。

大量键值对存储时的性能优化

1. 选择合适的哈希函数：
   • 确保哈希函数能够将键对象均匀地分布到哈希表的各个桶中，减少哈希冲突。良好的哈希函数可以使键值对在哈希表中更均匀地存储，提高查找效率。
   • 例如，自定义对象作为字典键时，需要重写hash和isEqual:方法，使hash方法返回的哈希值能够尽量均匀分布。
2. 调整哈希表容量：
   • 当哈希表中的键值对数量达到一定比例（负载因子）时，进行扩容。通常负载因子设置为0.75左右。扩容时，重新计算每个键值对的哈希值并将其重新分配到新的更大的哈希表中，这样可以减少哈希冲突，提高性能。
   • 对于NSDictionary，开发者无需手动处理扩容，NSDictionary内部会根据负载情况自动调整。
3. 使用缓存：
   • 对于经常访问的键值对，可以设置缓存。例如，使用最近最少使用（LRU）缓存策略，将最近使用过的键值对存储在缓存中，下次访问时先检查缓存，命中则直接返回，减少对字典的查找次数，提高整体性能。
4. 批量操作：
   • 对于NSMutableDictionary，如果需要进行大量的添加、删除操作，尽量采用批量操作的方式。例如，一次性添加多个键值对，而不是逐个添加，这样可以减少哈希表频繁调整带来的性能开销。