비선형 데이터구조, 해시(Hash) #1 해시소개

개요

대표적인 선형 데이터 구조인 연결리스트(LinkedList)는 삽입과 삭제와 같은 연산에서 낮은 비용으로 수행할 수 있습니다. 그러나 대표적인 단점인 어떤 값을 찾기 위해서는 맨 앞의 노드에서부터 탐색하기 때문에 탐색 속도에서 O(n)의 시간이 소요됩니다. 그렇다고 배열 기반의 리스트를 사용하기에는 삽입과 삭제 연산에서 많은 비용이 발생합니다. 이 문제를 해결하기 위해서 해시를 소개하겠습니다.

 

• 해시소개
• 해시함수 작성시 고려사항
• 해시충돌이란 무엇인가?

 

1. 해시 소개

해시는 특정한 키(key)값을 해시 함수(HashFunction)의 수식에 대입시켜 계산 후 나온 결과를 주소로 사용하여 값(Value)에 접근하는 방법입니다.

 

예를 들어 학생의 아이디(Student ID)와 점수(Grade)가 아래와 같다고 가정합니다.

Student ID	Grade
CSSC10	92
CSSC11	100
...	...
CSSC99	84

만약 연결리스트로 학생들의 ID와 점수를 저장한다면 99번째 학생의 정보를 찾기 위해서는 89번의 탐색(O(n))을 수행해야 할 것입니다. 하지만 Student ID에서 CSSC 부분을 제외한 끝에 숫자 부분을 이용하면 배열에 저장할 수 있을 것 같습니다. 그러나 배열은 0번째부터 시작하기 때문에 0번째부터 시작하기 위해서 -10을 연산하면 0번재부터 저장이 가능할 것입니다. 위와 같은 과정이 해시 함수의 수식의 내용이며 정리하면 아래와 같습니다.

int hashFunction(String id)
{
    remove CSSC		// StudentID에서 CSSC 문자열 제거
    convert to int	// 문자열 타입의 숫자를 정수로 변환
    int - 10		// 정수에서 -10 수행
    return int		// -10 수행한 것을 반환 (인덱스 반환)
}

 위의 해시 함수를 예제에 적용하면 아래와 같습니다.

StudentID	hashFunction(String id)
CSSC10	0
CSSC11	1
CSSC12	2
...	...
CSSC99	89

위의 예제에서 StudentID와 Grade를 배열에 저장한다면 아래와 같이 저장될 것입니다.

위와 같이 해시를 사용하면 배열처럼 빠르게 데이터를 탐색할 수 있고 연결리스트처럼 데이터를 빠르게 추가하거나 제거할 수있습니다. 그리고 연결리스트처럼 모든 노드의 데이터를 확인하는 것이 아닌 키(key)가 주어지면 값이 저장된 위치를 바로 접근할 수 있습니다.

 

2. 해시 함수 작성시 고려사항

• 데이터의 속성 : 예를 들어, CSSC 아이디가 존재한다면 CSSC 부분을 제거해야 함
• 연산이 빨라야 함
• 두 요소가 "같다면" 같은 값을 반환해야 함
• 같은 실행 환경일 경우 같은 객체라면 같은 값이 나와야 함
• 코드를 새로 실행하면 객체가 같더라도 다른 값이 나올 수 있음
  • 예를 들어 Object 클래스의 hashcode 메서드는 메모리 위치 기반으로 실행됩니다. 객체의 hashcode 메서드는 함수를 호출하지 않으면 실행할때 마다 객체는 메모리 위에서 다른 위치에 저장되기 때문에 다른 값이 반환됩니다.)
• 코드에서 최대한 충돌(Collision)이 일어나지 않도록 해야함

 

3. 해시 충돌이란 무엇인가?

해시 충돌이란 서로 다른 값을 가진 키가 일치하는 상황을 의미합니다. 예를 들어 전화번호를 3분할 한 것을 키로 지정했을때 아래와 같은 상황이 발생할 수 있습니다.

위 상황은 핸드폰 번호를 키값으로 하여 해시 함수에 넣어 저장될 인덱스를 계산하는 상황입니다. 해시 함수 수식의 내용은 핸드번 번호를 입력으로 받으면 앞에서부터 3자리씩 분할하여 더하는 수식입니다. 그런데 위의 그림과 같이 010-1234-5678, 010-1204-5681 두 번호는 키값이 다른데도 불구하고 해시 함수의 결과로 같은 값이 나오게 되어 중복되는 상황이 발생하였습니다. 위와 같이 해시 함수의 결과가 같게 나오는 현상을 해시 충돌이라고 부릅니다.

 

References

[부스트코스] 자바로 구현하고 배우는 자료구조