# CityHash

**CityHash**는 Google에서 개발한 해시 함수의 계열로, 특히 메모리 내 데이터 구조(예: 해시 테이블)에서의 빠른 연산 속도와 높은 품질의 분산 성능을 목표로 설계되었습니다. 이 함수는 64비트 및 128비트 해시 값을 생성할 수 있으며, 특히 짧은 문자열에 대해 뛰어난 성능을 보입니다. CityHash는 MurmurHash와 함께 현대적인 해시 함수 중 하나로 널리 인정받고 있으며, 대규모 데이터 처리 및 인메모리 데이터베이스 시스템에서 효율적인 키 매핑을 위해 자주 활용됩니다.

## 개요 및 배경

2011년 Google의 연구원인 Geoff Pike와 Jyrki Alakuijala는 기존 해시 함수들의 한계를 극복하기 위해 CityHash를 개발했습니다. 당시 널리 사용되던 해시 함수들은 긴 문자열 처리에는 강점이 있었으나, 짧은 문자열(예: URL, DNS 이름, 짧은 키)에서의 충돌(Collision) 발생률이 높거나, 특정 패턴에 취약한 문제가 있었습니다.

CityHash는 이러한 문제를 해결하기 위해 "City"라는 이름에 걸맞게 도시의 복잡한 네트워크 구조처럼 다양한 길이의 데이터를 효율적으로 혼합(Mixing)하는 알고리즘을 채택했습니다. 특히 x86-64 아키텍처 환경에서 최적화되어 있으며, SIMD(Single Instruction, Multiple Data) 명령어를 활용하여 병렬 처리 성능을 극대화했습니다.

## 주요 특징

CityHash는 다음과 같은 기술적 특징을 가지고 있어 다양한 시스템에 적합합니다.

*   **고속 성능**: 특히 64비트 환경에서 매우 빠른 연산 속도를 자랑합니다. 짧은 문자열의 경우 다른 경쟁 해시 함수들보다 더 적은 사이클로 해시 값을 계산합니다.
*   **높은 분산도**: 입력 데이터의 작은 변화에도 출력 값이 크게 달라지도록 설계되어, 해시 테이블의 버킷 분산을 균일하게 유지합니다. 이는 해시 충돌을 최소화하고 검색 성능을 향상시키는 데 필수적입니다.
*   **짧은 문자열 최적화**: 기존 해시 함수들이 긴 데이터 블록을 처리하는 데 중점을 둔 반면, CityHash는 16바이트 미만의 짧은 데이터에 대해 특별히 최적화된 알고리즘을 포함하고 있습니다.
*   **64비트 및 128비트 출력 지원**: 필요에 따라 64비트 해시 값이나 128비트 해시 값을 생성할 수 있습니다. 128비트 버전은 충돌 확률을 더욱 낮추고자 할 때 유용합니다.
*   **오픈 소스 및 플랫폼 독립성**: C++로 구현되어 있으며, BSD 스타일 라이선스로 공개되어 있어 다양한 운영 체제와 프로그래밍 언어에서 쉽게 통합할 수 있습니다.

## 알고리즘 원리

CityHash의 핵심은 데이터를 효율적으로 혼합하는 과정입니다. 일반적인 해시 함수가 단순히 데이터를 더하거나 곱하는 방식과 달리, CityHash는 다음과 같은 단계를 거칩니다.

1.  **데이터 분할**: 입력 문자열을 고정된 크기(예: 16바이트)의 블록으로 나눕니다.
2.  **블록 혼합**: 각 블록을 고유한 상수(Constant)와 결합하여 초기 해시 값을 생성합니다. 이 과정에서 회전(Rotation) 및 XOR 연산을 사용하여 비트의 분산을 촉진합니다.
3.  **최종 혼합**: 모든 블록을 처리한 후, 남은 잔여 데이터(Remaining bytes)를 처리하고 최종적으로 해시 값을 압축합니다. 이때 64비트 곱셈 연산을 활용하여 높은 엔트로피를 유지합니다.

CityHash는 특히 `CityHash64`와 `CityHash128` 두 가지 주요 함수를 제공합니다. `CityHash64`는 메모리 사용량을 줄이고 속도를 중시할 때, `CityHash128`은 충돌 저항성이 더 중요한 경우에 사용됩니다.

## 사용 사례 및 적용 분야

CityHash는 다음과 같은 분야에서 널리 사용됩니다.

*   **인메모리 데이터베이스**: Redis, Memcached 등의 키-값 저장소에서 해시 테이블의 버킷 분산을 위해 사용됩니다.
*   **대규모 데이터 처리 시스템**: Hadoop, Spark 등의 분산 컴퓨팅 프레임워크에서 데이터 파티셔닝(Partitioning) 및 샤딩(Sharding) 키 생성에 활용됩니다.
*   **네트워크 및 보안**: DNS 캐싱, URL 정규화, 그리고 빠른 체크섬(Checksum) 계산이 필요한 네트워크 프로토콜에서 사용됩니다.
*   **검색 엔진**: Google의 내부 시스템에서 인덱싱 및 데이터 중복 제거(Deduplication) 작업에 적용되었습니다.

## 관련 해시 함수 비교

CityHash와 유사한 목적을 가진 다른 해시 함수들과의 비교는 다음과 같습니다.

| 해시 함수 | 개발사/기관 | 주요 특징 | 비고 |
| :--- | :--- | :--- | :--- |
| **CityHash** | Google | 빠른 속도, 짧은 문자열 최적화 | x86-64 최적화됨 |
| **MurmurHash** | Austin Appleby | 범용성, 높은 분산도 | 널리 쓰이는 표준 중 하나 |
| **xxHash** | Yann Collet | 극한의 속도, SIMD 최적화 | CityHash보다 더 빠른 경우多 |
| **SipHash** | Jean-Philippe Aumasson | 충돌 저항성(보안) | DoS 공격 방어에 적합 |

## 결론

CityHash는 Google의 기술적 요구사항을 반영하여 설계된 고품질 해시 함수로, 특히 짧은 문자열 처리와 빠른 연산 속도가 필요한 환경에서 여전히 유용한 도구입니다. 비록 최근에는 xxHash와 같은 더 빠른 대안들이 등장하고 있지만, CityHash의 알고리즘적 안정성과 광범위한 통합 사례는 여전히 많은 시스템에서 신뢰할 수 있는 선택지입니다. 개발자는 시스템의 특정 요구사항(속도 vs. 충돌 저항성 vs. 보안)에 따라 CityHash를 포함한 다양한 해시 함수를 비교·검토한 후 최적의 솔루션을 선택해야 합니다.

## 참고 자료

*   Google开源代码库: [CityHash GitHub Repository](https://github.com/google/cityhash)
*   Google Research Blog: "CityHash: A Fast Non-Cryptographic Hash Function"
*   Wikipedia: [CityHash](https://en.wikipedia.org/wiki/CityHash)