해시(Hash)

해시는 데이터를 빠르게 찾기 위해 만들어진 자료구조이자 개념이다. 핵심 아이디어는 간단하다. 값을 그대로 저장하거나 그대로 비교하는 대신, 특정 규칙을 이용해 ‘숫자 형태의 고유한 값(해시 값)’으로 바꿔 저장하고, 그 숫자를 기반으로 데이터를 바로 찾아가는 방식이다. 이렇게 변환하는 과정을 해싱(hashing)이라고 하고, 변환에 사용되는 함수를 해시 함수(hash function)라고 부른다.

해시의 강점은 속도다. 배열처럼 인덱스로 접근할 수 있는 구조는 빠르지만, 인덱스를 미리 알지 못하면 결국 찾기 위해 전체를 훑어야 한다. 반면 해시는 데이터를 넣을 때부터 “어디에 저장할지”를 해시 함수가 결정해주기 때문에, 나중에 같은 함수를 이용해 그 자리를 바로 찾아갈 수 있다. 이 때문에 해시는 평균적으로 탐색·삽입·삭제가 모두 O(1)이라는 매우 강력한 성능을 갖는다.

예를 들어 “apple”이라는 문자열을 저장한다고 해보자. 해시 함수는 이 문자열을 입력받아 특정 규칙을 적용해 하나의 숫자를 만든다. 예를 들면 각 문자의 코드 값을 더하거나, 특정 계산을 적용해 1074 같은 숫자로 바꾼다. 그러면 해시 테이블(hash table)은 1074라는 인덱스 위치에 “apple”을 저장한다. 나중에 문자열 “apple”을 찾고 싶다면, 전체 데이터를 뒤질 필요 없이 똑같은 규칙으로 해시 값을 계산하고, 계산된 인덱스로 바로 이동하면 된다. 이것이 해시가 빠른 이유다.

물론 현실에서는 문제가 하나 있다. 서로 다른 두 값이 같은 해시 값을 갖는 경우, 즉 충돌(collision)이 발생한다는 점이다. 해시 함수가 아무리 정교해도 해시 테이블의 크기보다 데이터가 많아지면 충돌은 피할 수 없다. 이를 해결하기 위한 전략이 체이닝(chaining) 또는 오픈 어드레싱(open addressing) 방식이다. 체이닝은 같은 인덱스에 여러 값을 연결 리스트로 이어붙여 저장하는 방식이고, 오픈 어드레싱은 충돌 발생 시 다른 빈 칸을 탐색해 저장하는 방식이다. 충돌이 있더라도 적절히 해결하면 해시는 여전히 평균적으로 매우 빠른 성능을 낸다.

해시는 실제 소프트웨어 개발에서 매우 자주 등장한다. 파이썬의 dict, 자바스크립트의 Object와 Map, 자바의 HashMap 등이 모두 해시를 기반으로 만들어졌다. 데이터베이스의 인덱싱, 캐싱 시스템, 중복 탐지, 암호화, 블록체인까지 다양한 분야에서도 해시 함수가 핵심 역할을 한다. 그만큼 실전에서 가장 널리 쓰이는 자료구조 중 하나다.

해시를 이해할 때 기억해야 할 가장 중요한 포인트는 첫째, 데이터를 “해시 값”이라는 규칙 기반 숫자로 바꿔 저장한다는 것, 둘째, 이 덕분에 평균적으로 O(1)에 가까운 속도로 탐색·삽입·삭제가 가능하다는 것이다. 충돌이라는 단점은 있지만, 이를 해결하는 방식이 잘 갖춰져 있어 해시는 실제 개발 현장에서 여전히 가장 사랑받는 자료구조다.