값을 배열의 위치로 바꿔주는 함수를 두고, 그 위치에 값을 넣는 자료구조. 해시 함수는 크기가 제각각인 입력을 받아 정해진 범위의 수 하나를 내놓는다. 그 수를 인덱스로 쓰면 넣기, 찾기, 지우기가 전부 함수 한 번 통과에 배열 접근 한 번이라 O(1)이다.
들어온 순서가 상관없고 삽입, 삭제, 탐색이 계속 일어나는 상황에 맞는다. 반대로 정렬된 순회가 필요하면 이진 탐색 트리 쪽이다.
테이블 크기와 부하율
테이블은 넉넉하게 잡는다. 들어갈 데이터 개수의 세 배에서 네 배 크기가 보통이다. 빽빽할수록 서로 다른 값이 같은 자리를 차지하는 해시 충돌이 늘고, 충돌이 늘면 O(1)이 무너지기 때문이다.
전체 버킷에서 사용 중인 버킷의 비율을 부하율(load factor)이라고 한다. 100%에 가까울수록 삽입, 삭제, 검색의 효율이 급격히 떨어져서 보통 80%로 제한하는데, 자바 HashMap은 0.75를 넘으면 테이블 크기를 두 배로 늘린다. 꽉 차기 전에 미리 늘리는 것이다.
해시 함수를 만드는 방법
해시 함수를 만드는 방법은 여럿이다.
- 제산법(division): 키를 테이블 크기로 나눈 나머지.
hash = key % M - 폴딩법(folding): 키를 여러 조각으로 쪼개 더하거나 XOR.
(short)(key ^ key >> 16) - 곱셈법: 0과 1 사이 실수 A를 곱하고 소수부만 취해 테이블 크기 m을 곱한다.
h(k) = (kA % 1) * m - 중간 제곱법: 키를 제곱한 뒤 가운데 몇 자리
- 기수 변환법: 다른 진법으로 바꾼 값
- 숫자 분석법: 자릿수 중 고르게 분포한 것만 골라 씀
- 무작위 해싱: 여러 해시 함수를 만들어 두고 그중 하나를 무작위로
제산법을 쓸 때는 테이블 크기 M을 소수로 잡는 것이 중요하다. M이 짝수면 메모리 주소가 대체로 짝수라 해시값도 짝수로 몰린다. 소수, 그중에서도 2의 거듭제곱과 먼 소수를 쓰면 0부터 M-1까지 고르게 퍼진다.
무결성 검증에 쓰는 해시 알고리즘
MD 계열, SHA 계열, RIPEMD, Whirlpool 같은 이름은 해시 알고리즘이지 해시 함수가 아니다. 인덱스를 만들려는 게 아니라 데이터가 변조되지 않았는지 확인하려고 쓴다.
MD4는 128비트 축약으로 무결성을 검증했고, MD5는 널리 쓰였지만 충돌을 만들 수 있다는 분석이 나와 지금은 기존 응용과의 호환 목적으로만 남았다. SHA 계열이 그 자리를 대신했고, SHA256과 SHA384와 SHA512는 AES의 키 길이인 128, 192, 256비트에 맞춰 출력 길이를 늘린 것이다.
해싱할 수 없는 것
무엇이든 해싱할 수 있는 것은 아니다. 문자열과 숫자는 잘 되지만 배열은 안 된다. 배열 안의 값 개수가 정해져 있지 않아 고정 길이 값으로 줄일 기준이 없기 때문이다.