Hashing
정보를 최대한 빨리 저장하고 꺼내오는 기법
O(1)시간에 연산을 하려면 해싱이 한 방법
-
hash table ADT
CreateHashTable : hash table 생성
HashSearch : hash table 안에서 key 검색
HashInsert : hash table에 새로운 key 삽입
HashDelete : hash table로부터 key 삭제
DeleteHash : hash table 삭제
어떤 문제를 해결할 때, 가능한 모든 키를 가능한 메모리 위치에 어떤 식으로든 매핑해야 합니다. 이때, 다수의 키를 적절한 장소에 매핑하는 과정을 해싱이라고 합니다.
-
해시 테이블
- 배열에서 우리는 키가 k인 항목을 배열의 k위치에 저장
주어진 키 k에 대해, 해당 항목을 배열의 k번째 위치를 통해 찾는다는 것입니다.
이것을 Direct Addressing 이라고 합니다.
- Direct Addressing은 모든 가능한 키에 대해 하나의 장소를 할당할 수 있을 때에 사용할 수 있습니다.
만약 모든 가능한 키를 할당할 만큼 충분한 공간이 없을 때는 새로운 방법이 필요
즉 굉장히 많은 가능한 키가 있을 때는 배열만 이용해서는 충분한 처리가 불가
- 이 때 가능한 한 가지 방법은 해시 테이블을 사용하는 것
일반적으로 실제 저장되는 키의 개수가 가능한 키의 모든 개수에 비해 상대적으로 적을 때 해시 테이블을 사용
-
해시 함수
-
키를 인덱스로 변환할 때 사용
-
해시 함수를 어떻게 선택?
삽입된 객체들을 테이블에 균일하게 분배할 수 있도록 효율적인 해시 함수가 설계되어야 함
계산이 빨리 이루어지고, 충돌을 최소화하는 해시 함수를 선택해야함
해시 인덱스가 해시 테이블에 이미 다른 객체가 삽입된 위치를 가리킬 때, 또 다른 인덱스를 계산할 수 있는 효율적인 충돌 해결 알고리즘이 설계되어야 함
- 좋은 해시 함수의 특성
충돌 최소화
쉽고 빠른 계산
해시 테이블 안에 키를 균등하게 분배
키에서 제공되는 모든 정보를 사용
주어진 키 집합에 대해 높은 적재율(load factor)을 가져야 합니다.
-
-
적재율
적재율 = ${해시 테이블\ 안의\ 항목\ 개수\over 해시테이블\ 크기}$
함수의 효율성을 계산할 때 사용
해시 함수가 키들을 균등하게 분포하는지 여부를 알 수 있게 해줍니다.
-
충돌
충돌은 두 개의 항목이 같은 장소에 저장되어 버리는 상황
해시 함수는 각 키를 서로 다른 주소 공간으로 할당하기 위해 사용되는데, 잘못 구현하면 충돌이 빈번히 일어납니다.
-
충돌 해결 기법
대체 장소를 찾는 과정을 충돌 해결(Collision Resolution)이라고 합니다.
Chaining : 연결 리스트들의 배열
Open Addressing : 배열에 기반한 구현
Linear Probing : 선형 검색
Quadratic Probing : 비선형 검색
Double Hashing : 두 개의 해시 함수 사용
-
Separate Chaining(분리 체인법)
체인법에 의한 충돌 해결은 연결 리스트 표현과 해시 테이블의 결합입니다.
두 개 이상의 항목이 같은 장소로 해싱되면 이 항목들은 체인(chain)라고 불리는 단일 연결 리스트를 만듭니다.
