Objective-C -- isEqual 및 hash

왜 isEqual 방법이 있어요?

객체 유형에 대해 == 연산자는 객체의 주소, 즉 동일한 객체인지 여부를 비교합니다.
대상 주소가 같다는 것은 대상이 같다는 것을 대표하지 않는다. 즉, 대상 주소가 같다는 것은 대상이 같다는 필수적인 비충분한 조건이다.
isEqual 방법은 두 대상이 동일한지 아닌지를 판단하는 데 쓰인다.

isEqual의 기본 구현

isEqual 메서드는 NSObject에서 설명한 것으로, 기본 구현은 간단한 비교 대상 주소입니다.

@implementation NSObject (Approximate)
- (BOOL)isEqual:(id)object {
  return self == object;
}
@end

NSObject의 하위 클래스는 다음과 같은 방법으로 자체 isEqual을 구현할 수 있습니다.

새로운 isEqualTo__ClassName__: 방법을 실현하여 구체적인 속성 값의 대비를 하는데 우리는 고층 비교 방법

이라고 부른다.

중재isEqual:, 먼저 대상 주소의 비교와 대상 유형의 비교를 한 다음에 고위층 비교 방법

을 호출한다.

중재hash:,이 방법은 뒤에 설명

집합 유형이라면 심층 판정 등 모든 구성원을 일일이 비교해야 한다.
예를 들면 다음과 같습니다.

@implementation NSArray (Approximate)
- (BOOL)isEqualToArray:(NSArray *)array {
  if (!array || [self count] != [array count]) {
    return NO;
  }

  for (NSUInteger idx = 0; idx < [array count]; idx++) {
      if (![self[idx] isEqual:array[idx]]) {
          return NO;
      }
  }

  return YES;
}

- (BOOL)isEqual:(id)object {
  if (self == object) {
    return YES;
  }

  if (![object isKindOfClass:[NSArray class]]) {
    return NO;
  }

  return [self isEqualToArray:(NSArray *)object];
}
@end

Foundation에서 많은 NSObject의 하위 클래스는 자신의 isEqual과 그 상위 클래스를 비교하는 방법을 정의했습니다.

NSAttributedString -isEqualToAttributedString:

NSData -isEqualToData:

NSDate -isEqualToDate:

NSDictionary -isEqualToDictionary:

NSHashTable -isEqualToHashTable:

NSIndexSet -isEqualToIndexSet:

NSNumber -isEqualToNumber:

NSOrderedSet -isEqualToOrderedSet:

NSSet -isEqualToSet:

NSString -isEqualToString:

NSTimeZone -isEqualToTimeZone:

NSValue -isEqualToValue:

NSArray에서 isEqual 관련 실천

예시 코드를 보다

    NSString* name1 = @"  ";
    NSMutableArray* array = [NSMutableArray arrayWithObjects:name1,nil];
    NSString* name2 = [NSString stringWithFormat:@"  "];
    NSLog(@"name1:%p,name2:%p",name1,name2);
    NSLog(@"[array contain:name2]=%d",[array containsObject:name2]);
    [array removeObject:name2];
    NSLog(@"[array remove:name2].count=%zd",array.count);

인쇄 결과

name1:0x108e58200,name2:0x600000436780
[array contain:name2]=1
[array remove:name2].count=0

이를 통해 알 수 있듯이 NSArraycontainsObject:와 removeObject: 방법은 모두 isEqual을 사용하여 구성원의 동등 여부를 판단한다.removeObject:는 모든 같은 멤버를 제거할 것이다.

왜 해시 방법이 있어요?

우리는 그룹에서 어떤 구성원을 찾습니다. 그룹이 정렬되지 않은 상황에서 찾는 시간의 복잡도는 O (array length) 입니다.
검색의 속도를 높이기 위해 해시테이블이 나타났다.구성원이HashTable에 가입되었을 때 그 구성원이 집합 중인 위치를 표시하기 위해hash값을 할당한다. 이 위치 표시를 통해 찾는 시간의 복잡도를 O(1)로 최적화할 수 있다. 물론 여러 구성원이 같은 위치 표시라면 찾기는 O(1)에 도달할 수 없다.
핵심은 다음과 같다.
분배된 이hash값(즉 집합 중인 구성원의 위치 표식을 찾는 데 사용)은 하쉬 방법으로 계산된 것이고hash 방법으로 되돌아온hash값이 가장 좋은 유일한 것이다.
수조에 비해hash값 인덱스를 기반으로 하는hashTable에서 어떤 구성원을 찾는 과정은
Step 1:hash 값을 사용하여 대상을 찾는 위치를 직접 찾습니다.
Step 2: 만약 목표 위치에 같은hash 구성원이 여러 명 있다면, 이 때 그룹으로 다시 찾습니다

hash 방법은 언제 호출됩니까?

해시테이블은 기본적인 데이터 구조로 NSSet과 NSDictionary는 모두 해시테이블을 사용하여 데이터를 저장하기 때문에 조회 구성원의 속도가 O(1)인 것을 확보할 수 있다.반면 NSArray는 순차표를 사용하여 데이터를 저장하고 조회 속도는 O(n)이다.
해시 방법은 대상이 NSSet에 추가되고 NSDictionary로 설정된 키만 호출할 때 NSSet에 새 구성원을 추가할 때hash값에 따라 구성원을 신속하게 찾아야 한다. 집합에 이 구성원이 존재하는지 확인하기 위해 NSDictionary가 키를 찾을 때도 키의hash값을 이용하여 검색의 효율을 높여야 한다.

hash와 isEqual의 관계

대상의 등판은 상호적이다([a isEqual:b]}[b isEqual:a])

만약 두 대상이 같다면 그것들의hash값은 반드시 같다([a isEqual:b]}[a hash]==[b hash])

값이 같고 두 객체가 반드시 같을 수는 없습니다([a hash] = [b hash]→ [a isEqual:b])

한 마디로 하면hash값은 대상 판정 등의 필요 비충분한 조건이다
판정 등의 효율을 최적화하기 위해hash 기반의 NSSet과 NSDictionary는 구성원의 동등 여부를 판단할 때 이렇게 한다
Step 1: 통합 구성원의hash값이 목표의hash값과 같은지, 같지 않으면 같지 않다고 직접 판단합니다
Step 2: hash 값이 같을 경우(즉, Step 1) 대상 판정 등을 진행하여 판정 등의 결과로 한다.

어떻게 자신의 해시를 다시 쓰는 방법

hash 메서드는 NSObject에 명시되어 있으며 기본적으로 객체의 메모리 주소를 반환합니다.
그렇다면 해시 방법의 가장 좋은 실천은 무엇일까?대신Matt Thompson이 Equality에서 내린 결론은
In reality, a simple XOR over the hashvalues of critical properties is sufficient 99% of the time(키 속성의 hash 값을 비트 또는 hash 값으로 연산)
예를 들어 Person 종류의hash 방법에 대해 다음과 같이 실현한다.

- (NSUInteger)hash {
    return [self.name hash] ^ [self.birthday hash];
}

참고 문장

iOS 개발은 나한테 말하지 마. 너 진짜 isEqual과hash 알아!Equality