덕's IT Story

이전글 - 해슁(Hashing) / 해쉬 알고리즘 / 해쉬 함수 충동 해결(Collision Resolution)에는 크게 두 가지 방법이 있다. 첫 번째는 체이닝(Chaining)으로 해쉬 테이블의 각 주소가 연결 리스트의 헤더 역활을 하고, 여기에 해당 주소로 들어오는 원소들이 연결 리스트(Linked List)로 매달린다. 두 번째는 개방 주소 방법인데, 체이닝처럼 추가 공간을 사용하지 않고 해쉬 테이블 안에서 충돌을 해결한다. 원래 들어갈 자리가 아니더라도 테이블의 다른 자리를 찾아 들어가게 된다. ① 체이닝(Chaining) 체이닝에서는 같은 주소로 해슁되는 원소를 모두 하나의 연결 리스트에 매달아 관리한다. 위 의 그림처럼 h(39) = h(13) = 0 인 경우 해쉬테이블의 0 인덱스는 39..

해쉬 테이블(Hash Tables) 일반적인 검색트리는 원소 하나를 저장하고 검색하는 데 평균적으로 의 시간이 걸리고, 최악의 경우 의 시간이 걸린다. 저장된 자료의 양에 상관없이 원소 하나를 저장·검색하는 데 항상 상수 시간에 가능하게 할 수 없는지 사람들은 요구하게 되었고, 이 꿈을 실현한 것이 해시 테이블이다. 해시 테이블은 자료의 저장·검색에 있어 극단적인 효율에 다다른 자료구조이다. 해시(Hash) 테이블은 원소의 값에 의해 결정되는 자료구조이다. 즉, 저장된 자료와의 비교를 통해 자리를 찾지 않고 단 한번의 계산으로 자리를 찾는다. 해쉬 함수 임의의 원소를 해시 테이블에 저장하려면 먼저 해당 원소의 해시값을 계산한다. 해시값은 해시 함수에 의해 계산된다. 해시 함수는 키값을 입력으로 받아 해시..