NSObject의 isEqual 및 hash 해결 및 재작성 방법

전언

NSObject는 우리에게 -isEqual와 -hash 방법을 제공했다. 다음은 이 두 가지 방법의 주요 기능이 무엇인지, 언제 호출되는지, 자신의 맞춤형 수요에 따라 어떻게 다시 쓰는지 구체적으로 소개한다.

isEqual

우리는 먼저 방법의 성명- (BOOL)isEqual:(id)object;을 살펴보고 다른 대상과 현재object를 비교하여 브리 값을 되돌려 이 두 대상의 여부를 확인한다 .이 방법을 한층 더 설명하기 전에, 우리는 먼저 의 정의를 보았다.

무엇이 상등한가

우리는 == 연산자와 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:

사용자 정의 - isEqual 방법

가령 우리가 Person류가 있다고 가정하면

@interface Person
@property(nonatomic, copy) NSString *firstName;
@property(nonatomic, copy) NSString *secondName
@property(nonatomic, strong) NSDate *birthday;
@end

우리는 먼저 의 개념을 사용자 정의했다. 여기서 예를 들어 firstName와 secondName가 같으면 person가 같다고 본다.다음은 사용자 정의의 동일한 방법을 먼저 추가하는 것이다. - (BOOL)isEqualToPerson:(Person *)person;.m에서의 실현은 다음과 같다.

@implementation Person

- (BOOL)isEqualToPerson:(Person *)person {
  if (!person) {
    return NO;
  }

  BOOL isFirstNameEqual = (!self.firstName && !person.firstName) || [self.firstName isEqualToString:person.firstName];
  BOOL isSecondNameEqual = (!self.secondName && !person.secondName) || [self.secondName isEqualToString:person.secondName];

  return isFirstNameEqual && isSecondNameEqual;
}

#pragma mark - NSObject

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

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

  return [self isEqualToPerson:(Person *)object];
}

- (NSUInteger)hash {
  return [self.firstName hash << 8] ^ [self.secondName hash];
}

다음은 단계별로 살펴보겠습니다.

부류를 다시 쓰는 isEqual 방법은 우선 메모리 주소가 같은지 판단self == object

판단![object isKindOfClass:[Person class]]Class이 같지 않으면 바로 되돌아오기NO

우리가 정의한 판정 방법- (BOOL)isEqualToPerson:(Person *)person을 호출합니다.

isEqual 언제 호출될까

우리는 isEqual 방법을 직접 호출하여 두 대상이 같은지 아닌지를 판단할 수 있다

NSArray의 containObject: 방법은 수조의 원소를 두루 훑어보고 isEqual를 통해 동일 여부를 판단한다

NSSet의containObject:방법은 먼저 -hash,-hash같지 않으면 바로false로 되돌아오고hash같으면 다시 isEqual

여기까지 하겠습니다. -hash 방법이 무엇입니까? 그 역할은 무엇입니까?

hash 방법

- (NSUInteger)hash가 정수를 되돌려준다. 이 수는 현재 대상의 해시 값에 매우 중요한 규범이 있다는 것을 대표한다. 만약에 두 대상 이 hash의 값은 반드시 같아야 한다. 만약에 어떤 종류가 isEqual 방법을 사용자 정의했다면 이 종류의 실례가 집합에 들어갈 수 있다. 하나는 hash 방법이 다시 정의되었음을 확보해야 한다.
수조가 원소를 일련의 연속된 주소에 저장하는 것과 달리 해시 알고리즘은 NSSet와NSDictionary를 매우 빠르게 (O(1))원소 검색을 할 수 있게 한다. 해시표는 메모리에서 n개의 위치를 분배한 다음에 함수를 사용하여 위치 범위 내의 특정한 위치를 계산한다.수조와hash표에서 하나의 원소가 존재하는지 아닌지를 판단하는 알고리즘과 효율이 다르다. 수조는 수조에 있는 모든 원소의 위치를 검사해야 한다hash는 더욱 빠른 검색 방식을 가진다.
좋은 hash 함수는 너무 많은 계산량을 필요로 하지 않는 상황에서 생성된 위치의 분포를 균등한 분포에 가깝게 할 수 있다. 두 개의 서로 다른 대상이 같은 산열 값을 계산할 때 우리는 이를 해시 충돌이 발생했다고 부른다.충돌이 발생할 때 해시표는 충돌이 발생하는 위치에서 뒤로 찾기 시작하여 새로운 원소를 첫 번째로 배치할 수 있는 위치에 놓는다. 해시표가 점점 치밀해지면서 충돌이 발생할 가능성도 증가하고 사용 가능한 위치를 찾는 데 걸리는 시간도 증가한다(이것도 우리가 해시 함수의 결과 분포가 균등한 분포에 가깝기를 바라는 이유이다).여러분은 과 에 대한 기본적인 개념이 있으면 됩니다. 이 부분은 따로 꺼내서 분석할 예정이니 기대해 주십시오.자, 우리는 계속해서 우리 위의 isEqual 수요에 대해 설명한다.
사용자 정의-hash 방법
만약에 두 대상 이 같다면 그들의 hash 값은 반드시 같아야 한다. 만약에 어떤 클래스가 isEqual 방법을 사용자 정의했고 이 클래스의 실례가 집합에 포함될 수 있다. 하나는 hash 방법이 두 개의 이미지가 같은 규칙을 다시 정의했음을 확보해야 한다. hash 규칙 아래 대상의 hash 값이 같아야 한다는 것을 보장해야 한다.우리는 통과할 수 있다

- (NSUInteger)hash {
  // 
  return [self.firstName hash] ^ [self.secondName hash];
}

실현하는데 왜 firstName에 대해 위치를 옮겨야 합니까?위에서 말했듯이 hash의 디자인은 신속하게 찾기 위한 것이다. 가능한 한 hash 충돌을 피해야 한다. 즉, isEqueal의 두 요소를 만족시키지 못하면 hash가 같지 않다. 디자인hash을 할 때 두 개의 서로 다른 대상hash의 값을 비교적 쉽게 같게 할 수 있는지 고려해야 한다. 그렇다면hash 알고리즘은 다시 디자인해야 한다.상기의 예시에서 볼 때 john smith와smith john는 문제가 있을 수 있다. hash 충돌을 피할 수 없지만 이렇게 쉽게 충돌해서는 안 된다. 이 보기 쉬운 hash 충돌을 해결하기 위해 다음과 같은 것을 사용할 수 있다.

- (NSUInteger)hash {
  return [self.firstName hash << 8] ^ [self.secondName hash];
}

총결산

이상의 설명과 예시를 통해 우리는 이미 사용자 정의isEqual와 hash 방법을 실현할 수 있다.hash 방법에 대해 우리는 해시 함수의 결과 분포가 균등한 분포에 가깝기를 바란다. 즉, 뻔한 해시 충돌을 피하는 전제에서 해시 알고리즘이 우리가 현재 가지고 있는 범위 내에서 어느 정도 충돌을 일으키기를 바란다. 그 목적은 신속하게 찾기 위해서이다. 이 내용은 본 편에 약간의 초강이 있다. 만약에 네가 흥미가 있다면 내 이후의 글을 계속 주목할 수 있다.나는 에 대해 비교적 전면적인 분석을 할 것이다.