해시 함수
해시 함수에 관한 일반적인 사실
- 문자열을 받아서 숫자를 반환하는 함수. 문자열에 숫자를 할당(mapping)한다.
- 해시함수에는 일관성이 있어야 한다. "apple"을 넣을 때마다 항상 반환되는 숫자는 같아야 한다.
- 다른 단어가 들어가면 다른 숫자가 나와야 한다. 예컨대 어떤 값이 들어가든 "1"이 나오는 함수는 좋지 않다.
- 해시함수는 같은 이름에 대해 항상 같은 인덱스를 할당한다. 값이 저장된 위치(인덱스)를 정확하게 알려주므로 탐색을 할 필요가 없다.(ex. 이진탐색, 단순탐색) 그렇기 때문에 빅오표기법으로 O(1)의 시간이 걸린다. O(1)은 상수 시간(constant time)이라고 불린다. 이는 테이블의 크기에 관계없이 항상 똑같은 시간이 걸린다는 의미이다. (항목이 10억개라고 해서, 한 개의 값을 찾는 시간이 늘어나지는 않는다)
- 해시함수와 배열을 합치면 해시테이블이라는 자료구조가 된다. 해시테이블은 해시맵, 맵, 딕셔너리, 연관배열이라는 이름으로도 불린다.
- 해시테이블은 중복을 방지하고, 어떤 항목과 다른 항목의 관계를 모형화하는 데에도 좋다.
해시테이블을 캐시로 사용하기
- 정보를 다시 계산하지 않고 저장했다가 알려주는 것이 캐싱(caching)이다.
- 캐싱은 작업속도를 올리는 일반적인 방법이다. 그리고 캐싱 자료는 해시테이블에 저장된다.
- 예를 들어, 페이스북 페이지에 방문할 때마다 서버는 먼저 해시테이블에 저장된 페이지가 있는지 확인한다. 있으면 테이블의 내용을 전송하고, 없으면 서버가 작업을 하여 전송한다.
충돌(해시테이블의 성능에 대하여)
- 서로 다른 키에 대해 서로 다른 위치(인덱스)를 할당하는 것은 거의 불가능하다.
- 예컨대 두개의 키를 같은 공간에 할당하면 충돌(collision)이 발생한다. 한개의 키가 다른 것을 덮어쓰게 된다.
- 충돌을 해결하는 방법 중 하나는 여러 개의 키를 연결 리스트로 만들어 넣는 것이다.
- 그러나 만약, 연결 리스트가 매우 길어지거나, 연결 리스트에만 키를 할당하고 나머지 인덱스는 비어있다면 매우 비효율적이게 된다.
성능
| 해시테이블(평균적인 경우) | 해시테이블(최악의 경우) | 배열 | 연결리스트 | |
|---|---|---|---|---|
| 탐색 | O(1) | O(n) | O(1) | O(n) |
| 삽입 | O(1) | O(n) | O(n) | O(1) |
| 삭제 | O(1) | O(n) | O(n) | O(1) |
해시테이블은 평균적인 경우 배열과 연결리스트의 장점만 가지고 있지만, 최악의 경우에는 단점만 갖게 되므로 최악의 경우를 피하는 것이 매우 중요하다. 이를 피하려면 낮은 사용률 과 좋은 해시 함수 가 필요하다.
사용률(load factor)
- 사용률: 해시테이블에 있는 항목의 수 / 해시테이블에 있는 공간의 수
- 사용률이 커지기 시작하면(키를 할당할 공간이 부족해지기 시작하면, 충돌의 확률이 높아지기 시작하면) 리사이징(resizing)을 한다.
- 리사이징이란 해시테이블에 공간을 추가하는 것이다. 즉 리사이징을 통해 분모값을 크게 만들어 사용률을 낮추면 성능이 좋아진다.
좋은 해시함수란
- 좋은 해시함수란 배열에 값을 고루 분포시키는 함수이다.
- 나쁜 해시함수는 값이 뭉쳐있어서 충돌이 자주 발생한다.