Hash

해시

인덱스의 범위가 상당히 큰데에 비해 사용되는 공간이 적은 경우를 생각해보자. 예를 들어 인덱스 범위가 1 ~ 1억인 경우 1억 크기 배열을 사용해야하는데 이는 공간 낭비이다.

또한 인덱스가 정수가 아닌 문자열이나 객체인 경우 어떻게 해야할까? 이 경우 해시 함수와 해시 테이블을 사용할만 하다.

 

키로 원소를 O(1)에 찾는 검색 알고리즘

• 해시 테이블 - 원소를 저장하고 있는 공간(배열)
• 해시 함수 - 키를 해시 테이블의 인덱스로 바꾸는 함수. 키를 해시 테이블 인덱스로 쓸 수 있다면 해시 함수가 필요 없겠지만 보통 키의 범위가 너무 크고, 정수형이 아닐기 있기에 변환 함수인 해시 함수가 필요하다. 해시 함수의 결과값을 해시 값이라 한다.

충돌

서로 다른 키의 해시 값이 동일 할 때 충돌이 발생했다고 한다. 키의 범위가 해시 값 범위보다 크므로 충돌이 발생할 수 있다.

 

충돌이 발생할 경우 아래 두 가지 방법으로 해결할 수 있다.

• Chaining : 동일 해시값 데이터들을 연결리스트로 묶어 저장하는 방식이다. 추가 메모리를 사용하며 구현이 단순하다. Java 8의 HashMap은 체이닝 기법을 사용한다. 충돌이 발생할 경우 연결리스트를 순회하기에 O(N)의 시간 복잡도가 소요된다.
• Open Addressing : 추가적인 메모리를 사용하는 체이닝 기법과 다르게 해시 테이블의 비어있는 공간을 찾아 넣는 방식이다