Hash

해시, 해쉬 어쩌구저쩌구 논하는 이것은 먹을 것에 논하는 것은 아니다.
대신, 자료구조에서 각각의 데이터를 고유한 숫자 값으로 변환을 하고 이 변환된 값을 이용하여 특정 데이터의 존재 여부를 확인하거나 데이터를 추출하는 작업을 말한다.

• 보통 이 과정에서 데이터는 고정된 길이로, 그 자체로는 특별한 의미가 없는 데이터로 변환된다.
• 이러한 Hashing의 과정에서는, 데이터를 고정된 길이로 바꿔줄 해시 함수와 해시 테이블이 사용 된다.

Hash Function

해시 함수란, 주어진 데이터(Key)를 고유한 숫자 값인 Hash Value으로 표현해주는 함수이다.

• 키(Key)란, 해시 함수의 입력 부분이며, 입력 데이터 자체이거나 입력 데이터를 구분하는 값을 의미한다.
• 해쉬 값(Hash Value)란, 해시 함수의 출력 부분이며, 이러한 해시 값은 뒤에 후술할 해시 테이블(Hash Table)의 인덱스가 된다.
• 이러한 해시 함수를 통해 데이터를 고유한 숫자 값으로 변환하고, 해시 테이블에 접근하여 데이터를 조회하거나, 추출하게 된다.
  
  
  

Hash Table

해시 테이블은 데이터가 저장되는 곳으로, 해시 함수를 통해 산출된 Hash Value를 인덱스로 하여 해당 데이터를 저장하게 된다.

해시 테이블을 사용하려면 일반적으로 Hash Value를 일단 얻어야한다.
이것은 앞에서 이야기했듯 Hash Function 이용 과정에서 이루어진다.

Hash Function을 통해 산출된 해시 값은 해시 테이블의 인덱스가 된다.
데이터가 [콜라, 2300]으로 해시 함수에 들어간다고 할 때
"콜라"라는 부분만 해시 값으로 변환을 위한 원본으로 쓸 수 있고 그에 대한 Hash Value가 n이 나온다고 하자.
그럼 n위치 인덱스에 해시 테이블에는 2300이 저장된다.

즉, 콜라를 n 이라고 mapping 하는 과정을 Hash Function이라고 생각하면 되고, Hash Table은 그 mapping의 결과를 모아둔 것이다.

Hash Table 사용에는 Hash Function도 동반된다. 즉, 데이터 삽입, 삭제, 수정 모두 Function 사용이 필요하다.

이렇게 이상적인 자료구조 형태이지만 그래도 신경써야 할 게 있다.

 

해시 충돌 : Collision

• Hash의 사용의의를 위해선 Hash Function 이 무자비하게 중복이 절대 나올 수 없는 알고리즘으로 만들지는 못한다. 그렇다는건, 언젠가 한번은 Function을 거쳐 나오는 값은 중복이 발생 할 수 밖에 없다. 이렇게 치명적인 단점을 해결하지 못하면 있으나 마나한 자료 구조 였을지도 모른다.
  
  
  
• 하지만 인류의 척척박사들, 한가지도 아니고 두 가지나 충돌을 회피하는 법을 만들었다. 하나씩 논해보기로 하자.

Chaining Solution

Chaining은 Open Hashing 기법 중 하나이다. 빠르게 Open Hashing에 대해 논하고 가자.

• Open Hashing : 충돌이 발생한 키를 별도의 데이터 구조(보통 연결 리스트)에 저장하게 된다. 따라서, 오픈 해싱은 테이블 내에서 저장 공간을 초과하지 않고, 필요할 경우 외부 데이터를 활용한다는 특징을 가진다.

그렇다면 Chaining은 Table 공간 밖의 공간을 활용한다고 간주 할 수 있겠다.
즉, 충돌이 일어나게 되면 해당 인덱스가 가리키는 해쉬 테이블 공간  뒤로 연결 리스트를 사용하여 추가적으로 연결시킨 다음 저장한다.

Linear Probing

Linear Probing은 Close Hashing 기법 중 하나이다.

• Close Hashing : 테이블 저장공간 내에서 충돌 문제를 해결한다.

충돌이 일어나게 되면, 해당 해시 값의 다음 값부터 순회를 시작한다. 처음으로 나오는 해시 테이블의 빈 공간에 저장한다.

 

이거 왜 씁니까?

Hash Table 형식은 데이터 저장과 검색 속도가 빠르다는 장점을 가진다.

• 저장된 데이터들 중에서, 특정 데이터를 검색 할 때 나타나는 시간 복잡도는 O(1)이다. (충돌이 없음을 전제한 경우)
• 또한, 해당 키에 대한 데이터가 이미 존재하는지 중복 확인이 쉽다는 장점이 있다.

하지만, 저장 공간이 많이 필요하다는 점과, 여러 키에 해당하는 해시 값이 동일 한 경우, 충돌 방지를 위해 별도의 자료구조가 필요하다는 단점도 존재한다.

용도는 이렇게 생각 해 볼 수 있다 :

• 데이터의 저장, 삭제, 검색이 잦게 일어나는 경우 사용한다.
• 중복 확인이 쉽기 때문에, 웹 페이지에서 흔히들 볼 수 있는 캐시를 구현 할 때 사용한다.