Swift Hashable은 왜 Equatable을 상속할까?

0. 서론

Swift에서 Hashable 프로토콜은 Equatable을 상속한다.

즉 Hashable을 채택하려면 == 비교가 가능한 타입이어야 한다는 뜻이다.

이를 처음 봤을 때 “해시만 있으면 되지 왜 equality까지 언어 차원에서 강제할까”라는 의문을 갖게 되었다.

 

이 의문을 해결하기 위해 Dictionary/Set의 동작 방식과 해시 충돌(collision)에 대해 학습하고 내용을 정리해본다.

---

1. Dictionary의 Key와 Set의 Element는 Hashable이어야 한다

Swift 표준 라이브러리에서 다음은 이미 결정되어 있다.

• Dictionary<Key, Value>에서 Key는 Hashable이어야 한다.
• Set<Element>에서 Element는 Hashable이어야 한다.

즉, 해시 기반 컬렉션의 구성원이 되려면 Hashable은 필수 조건이다.

여기서 자연스럽게 질문이 생긴다.

“해시만 있으면 되지 왜 Equatable까지 강제하는가”

---

2. 해시는 ‘유일한 키’가 아니다

해시는 입력(키)을 작은 값(해시)으로 압축한 결과다.

입력 공간이 충분히 크면, 서로 다른 키가 같은 해시 값을 갖는 상황이 원리적으로 발생한다.

이를 해시 충돌(collision) 이라고 한다.

 

해시 충돌이 존재한다면, 다음 문은이 성립되지 않는다.

• hash(a) == hash(b)라면 a == b다. (성립 불가)

즉, 해시는 “대충 어디에 있을지”를 알려주는 힌트일 뿐, “이게 진짜 같은 키다”를 확정할 수 있는 값이 아니다.

---

3. Dictionary/Set은 해시만으로 동작하지 않는다

Dictionary[key] 조회나 set.contains(x)는 해시로 끝나지 않는다. 일반적인 흐름은 다음과 같다.

• 해시로 후보 위치(버킷/슬롯)를 찾는다.
• 후보 위치의 엔트리가 “내가 찾는 키”인지 ==로 확인한다.
• 같으면 조회/업데이트를 수행한다.
• 다르면 충돌 처리로 다음 후보를 탐색한다.

이 구조 때문에 Hashable은 결국 Equatable이 필요하다.

충돌이 가능한데 equality가 없다면 “같은 키인지, 다른 키인지”를 구분할 수 없기 때문이다.

---

(+) 4. Swift Dictionary: open addressing + linear probing

Swift 표준 라이브러리 구현 노트에 따르면 Dictionary의 native storage는 다음과 같다.

• native storage는 open addressing 해시 테이블이다.
• 충돌 해결 방식은 linear probing이다.

이를 글의 맥락으로 번역하면 다음 의미가 된다.

 

open addressing은 키/값을 별도 체인(연결 리스트)에 붙이지 않고, 해시 테이블의 슬롯(배열) 자체에 직접 저장하는 방식이다.

그리고 linear probing은 충돌이 나면 다음 슬롯, 그 다음 슬롯… 처럼 순차적으로 빈 자리를 찾거나 동일 키를 찾는 방식이다.

 

이 방식에서는 충돌이 발생했을 때, 후보 슬롯을 따라가며 엔트리를 만날 수 있다.

그런데 해시가 같다고 해서 같은 키라고 확정할 수 없으므로, 탐색 과정에서 매번 이런 질문이 필요하다.

• “이 슬롯의 key가 내가 찾는 key와 같은가?”

이 질문이 바로 == 비교다. 따라서 Dictionary의 구조는 자연스럽게 Equatable을 요구하게 된다.

---

5. (if) 만약 Equatable이 없다면 어떻게 되는가 

Equatable이 없는 해시 기반 컬렉션은 정확성을 보장하기 어렵다.

충돌이 가능한 순간부터 동일 키 판정이 불가능해지기 때문이다.

• 해시만으로는 동일 키를 확정할 수 없다(충돌 가능).
• equality(==)가 없으면 충돌한 다른 키와 동일 키를 구분할 수 없다.

따라서 다음 문제가 생긴다.

5-1. 업데이트와 삽입을 구분할 수 없다

• “해시가 같으면 업데이트한다” → 서로 다른 키가 덮어써져 데이터 손실이 발생한다.
• “해시가 같아도 무조건 새로 넣는다” → 동일 키가 중복 저장되어 조회/수정의 일관성이 깨진다.

5-2. 조회(get)의 정확성을 보장하기 어렵다

dict[key]는 후보 위치를 찾은 뒤 “정말 그 key인가”를 확인해야 한다.

==가 없으면 이 확인이 불가능해져 잘못된 값을 반환할 수 있다.

5-3. 결국 equality는 반드시 필요하다

프로토콜 이름이 Equatable이 아니더라도, 정확성을 위해서는 어떤 형태로든 “동일성 판정”이 필요하다.

Swift는 이를 명시적으로 강제하기 위해 Hashable : Equatable을 택한 것이다.

---

6. Hashable : Equatable의 의미

해시는 충돌이 가능하므로, Dictionary/Set은 해시로 후보를 좁힌 뒤 최종적으로 ==로 동일 키/요소인지 확정해야 정확성을 보장할 수 있다. 따라서 Swift는 이를 타입 시스템에서 강제하기 위해 Hashable이 Equatable을 상속하도록 설계했다.

---

7. 반드시 지켜야 하는 계약(Contract)

키 타입이 Hashable을 준수하려면 ==와 hash(into:)가 반드시 일관되어야 한다.

• a == b이면 반드시 hash(a) == hash(b)여야 한다.
• hash(a) == hash(b)여도 a == b일 필요는 없다(충돌 가능).

---

8. 충돌은 괜찮다. 불일치는 위험하다

여기서 정확성과 성능을 구분하면 이해가 더 깔끔해진다.

• 충돌(hash 같음, == 다름)
  • 정확성은 유지되나 성능이 악화될 수 있다(추가 비교/탐색 증가).
• 불일치(== 같음, hash 다름)
  • 정확성 문제가 발생할 수 있다(같은 키를 못 찾거나 중복처럼 동작).

즉, 충돌은 “성능 문제”가 될 수 있지만, ==/hash 불일치는 “정확성 문제”가 된다.

---

9. String 키는 Int 키보다 불리할 수 있다

iOS 앱에서는 Dictionary의 키로 String을 쓰는 경우가 흔하다.

다만 같은 조회 횟수/같은 알고리즘이라도, 키 타입에 따라 체감 성능이 달라질 수 있다.

일반적으로 String 키는 Int 키보다 비용이 커질 가능성이 있다.

 

그 이유는 다음과 같다.

• Int는 고정 크기 값이라 해시 계산이 매우 싸고, == 비교도 한 번에 끝난다.
• String은 해시 계산과 == 비교가 내용 기반이라 길이/내용에 따라 더 많은 바이트를 처리해야 할 수 있다.
  • String은 유니코드 기반의 가변 길이 문자열
• 충돌이 발생하거나 후보 엔트리가 여러 개일수록 == 비교가 늘어날 수 있는데, 이때 String 비교 비용이 더 부담이 된다.

따라서 아래 방식으로 대처할 수 있다.

9-1. 가능하면 “가벼운 키”로 바꾼다

키가 본질적으로 식별자라면, 내부 표현을 Int 같은 고정 크기 값으로 바꾸는 편이 유리한 경우가 많다.

예를 들어 문자열 ID를 앱 내부에서 정수 ID로 매핑해 Dictionary<Int, …>로 운용하는 방식이다.

• 장점: 해시/비교 비용이 줄어 성능이 안정적이다.
• 단점: 매핑 테이블을 별도로 관리해야 한다.

9-2. String 키를 유지해야 한다면 “정규화(normalize)”를 먼저 한다

같은 의미인데 표현이 다른 문자열이 섞이면 딕셔너리가 의미적으로 쪼개지고 lookup이 늘어난다.

예를 들어 아래처럼 “의미는 같은데 문자열만 다른” 케이스가 생길 수 있다.

• https://a.com/img.png
• https://a.com/img.png?utm=...
• https://a.com:443/img.png

이 경우 같은 대상을 서로 다른 키로 저장해 중복 저장/중복 작업이 생길 수 있다.

그래서 키로 쓰기 전에 표준 형태로 맞춘다.

• 대소문자 통일(예: lowercased())
• 불필요 공백 제거(trim)
• 포맷 통일(예: 날짜/버전/경로 문자열을 한 포맷으로 고정)

이 작업은 해시 충돌을 “직접 줄인다”기보다는, 같은 의미의 키가 여러 개로 분산되는 것을 막아 히트율과 성능을 안정화하는 데 도움이 된다.

9-3. 키 조회보다 더 비싼 작업이 있다면, 그 결과를 캐시한다

많은 iOS 병목은 “딕셔너리 조회”보다 “딕셔너리 조회 후 수행되는 비싼 작업(파싱, 변환, 디코드, 레이아웃 계산 등)”에서 발생한다.

이 경우 키 타입을 바꾸기 전에, 비싼 작업 결과를 캐시하는 것이 체감 성능에 더 크게 기여할 수 있다.

---

10. 결론

Hashable : Equatable은 의도된 설계다.

해시는 충돌이 가능하고, Dictionary/Set은 충돌 상황에서도 정확한 동작을 보장해야 한다.

이를 위해 해시는 후보를 좁히는 용도로 쓰고, 최종 확정은 ==로 수행한다.

이 요구사항을 타입 시스템에서 강제한 결과가 Hashable이 Equatable을 상속하는 구조다.