권기식 님이 쓰신 글 :
: 안녕하세요?
: 자료구조론 수업을 듣고 있는데요...
: 해싱이라는 것을 배웠습니다.
: 그런데 이 해싱이라는 알고리즘이 실제로 어떤데 이용되는지 궁금합니다.
:
: 이런 질문을 어디다 올려야될지 좀 막막하군요...
:
: 도움 부탁드리겠습니다.

음... 강사가 해슁의 특징에 대해 정확하게 강조해서 설명하지 못했나보군요. -_-;

간단하게 설명하자면요...

길이가 N인 배열에서 원하는 원소를 찾는데 걸리는 평균 시간은
N에 비례합니다. 이런 경우 O(N)이라는 표현을 쓴다는 것도 아실 겁니다.
이진트리, B트리와 같은 트리 자료구조는 좀 더 빨라서, O(log N)이 되지요.
이와 같이 다른 자료구조는 N의 크기가 커질수록 접근하는 데 걸리는 시간이
늘어난다는 단점이 있습니다.

이에 비해, 해쉬 테이블의 경우는 항상 고정된 상수시간만 걸립니다: O(1)로 표기하지요.
대신 원소의 수에 관계없이 항상 고정된 크기를 차지한다는 단점이 있지요.
(만약, 해쉬테이블이 어느 한도 이상 차게 되면,
전체 크기를 2배씩 늘리는 방법으로 해결합니다.)

하여튼 가장 빠르게 원소에 접근하는 자료구조를 쓰려면
해쉬테이블이 가장 좋은 방법입니다.

참고: ANSI C++ 표준 STL에는 애석하게도 해쉬가 들어있지 않지만,
STLport와 같은 최근의 STL 배포본에는 hash_set, hash_map 등이 포함되어 있습니다.