iOS 中isEqual和Hash的笔记（一）

HashABC

hash是一种用于处理查找时非常高效的数据结构。时间复杂度一般情况下可以直接认为是O(1)。

散列技术是在记录的存储位置和它的关键字之间确立一个对应关系 f，使得关键字 key对应的存储位置 f(key)。函数 f被称之为哈希函数(hash function)，使用哈希技术将数据存储在一块连续的地址区域中，该连续的存储空间我们称之为散列表，也就是哈希表（hash table）。

我们在存储的时候，是用过哈希函数计算得到哈希地址，并按照哈希地址存储该记录；查找的时候，通过通过同样的哈希函数计算记录的哈希地址，并按照地址访问该记录。

如果两个值在一个地址，就是 冲突（collision）。

解决冲突的方法主要是下边几种

• 开放定址法
• 再散列函数法
• 链地址法（拉链法）
• 公共溢出区法

假如在理想的状态下完全没有冲突，哈希表是所有查找中性能最高的，但是在极端情况下（全是一个地址），就是一个链表（链地址法）了。

测量性能我们主要是以下边几个标准：

• 散列表是否均匀
• 处理冲突的方式
• 散列表的负载因子
  负载因子 = 表中记录个数 / 散列表的长度

优点：在理想的状态下，查找、插入、删除操作的效率是最高的，是O(1)，树的相同操作也是需要O(n)的时间级的。

缺点：要时刻注意散列表的负载因子，准备扩容；要在面对真实的场景的时候，采用正确的冲突处理方法。

对象等同性

哈希表在iOS中使用时相当多的，比如说weak的地址就是由一个哈希表实现的，NSDictionary和NSSet的底层实现也是哈希表，NSObject也有hash值（但是要特别注意，这几种的hash实现并不相同）。与其说巧合，不如说这表明了在移动开发中的一种思想：

响应时间是比内存空间相对更重要的东西。移动端的App是面向用户的，用户体验最直观的体现就是时间！响应时间、动画流畅度、屏幕帧数等等，都是这一思想的体现，而在很多优秀的第三方，也都使用了这一思路。当然，这一思想的主要也会造成很多问题，比如说内存暴涨以及OOM问题，这就是另外的问题了。

话回正题。

“==”代表的是两个对象的指针的直接对比两个对象的指针，也就是内存地址；而“isEqual”是对比对象的值。以下边代码为例：

NSString *stringA = @"BiBoyang";  NSMutableString *stringB = [stringA mutableCopy];  
  BOOL equalA = (stringA == stringB);//0
  BOOL equalB = [stringA isEqual:stringB];//1
  BOOL equalC = [stringA isEqualToString:stringB];//1

可以发现，在比较对象的指针的时候，是不相同的；但是在直接对比对象的值的时候，是相等的。

在 NSObject.h中，我们可以看到这种两个重要的方法。

- (BOOL)isEqual:(id)object;
@property (readonly) NSUInteger hash;

这里需要注意的是，如果isEqual判断两个对象相等，则两个对象的hash值相同；反之则不然。这里是在其他语言，比如Java中也是一样的&#x