3-1) 해시(Hash), 해시 함수, 해시 충돌

 

아래 내용은 부스트코스 <자바로 구현하고 배우는 자료구조> 강의를 들으며 정리한 것입니다.

 

 

해시(Hash)

key와 연관된 value로 구성

연결 리스트에서는 어떤 요소를 찾고자 할 때, 시작 지점에서부터 순차적으로 살펴봐야 했기에 시간 복잡도가 O(n)이었다.

해시는 데이터를 검색할 때 사용할 key와 key를 통해 찾을 수 있는 연관된 값 value를 갖고 있어, 키가 주어지면 바로 연관된 값을 찾을 수 있다. 따라서 일반적으로 검색의 시간 복잡도가 O(1)이다.

즉, 해시는 모든 요소를 살펴본 후 동일한 노드를 찾아야 하는 연결 리스트와 달리 데이터를 빠르게 추가하고 제거하며 빠른 검색이 가능한 데이터 구조이다. 

 

 

해시 함수 (Hash Function)

해시 함수(hash function)은 임의의 길이를 갖는 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 

 

해시 함수 작성 시 고려할 점 

1. 데이터의 속성 

2. 연산이 빨라야 한다.

3. 두 요소가 "같다면(equals가 true 반환)" 몇 번을 호출해도 항상 일관되게 같은 값을 반환해야 한다.

4. 같은 실행 환경일 경우 같은 객체라면 같은 값이 나와야 한다.

5. 코드를 새로 다시 실행하면 같은 객체라도 다른 값이 나올 수 있다. (재실행 될 때까지 같을 필요는 없다)

6. 코드에서 최대한 충돌이 일어나지 않도록 해야 한다.

 + 객체가 같지 않더라도 hashCode가 같을 수는 있다.

 

생각해보기

Q. 코드를 새로 실행한다는 것이 어떤 의미일까? 왜 다른 값이 나올 수 있을까?

A. Object 클래스의 hashCode 메소드는 힙 메모리에 저장된 객체의 주소값을 해싱한 값을 반환하는데, 코드가 재실행되면 주소값이 변경되어 다른 값을 가질 수 있다.

 

해시 충돌 (Hash Collsions)

앞서 서로 객체가 같지 않더라도 hashCode는 같을 수 있다고 했는데, 이렇게 서로 다른 값을 가진 경우임에도 해싱된 key가 일치하는 경우를 해시 충돌이라고 한다. 많은 해시 충돌은 해시테이블의 성능을 떨어뜨리기 때문에, 좋은 해시 함수는 이러한 해시충돌이 적어야 한다. 

 

폴딩 (Folding)

긴 숫자를 작은 숫자로 분해하고, 작은 숫자들의 합을 구한다. 아래와 같이 해시 충돌이 발생할 수 있다.

전화번호를 3분할한 것의 합을 키로 지정