Python으로 프로그래밍 할때 dictionary가 hash table을 사용하기 때문에
dictionary에서 key값을 찾을때 시간 복잡도가 O(1)라는 사실을 알고 신기해 한적이 있다.
Hash Table이 어떤 개념인지는 대략적으로 들어는 봤지만 원리를 제대로 알아놔야 한다고 생각해서 공부한 내용을 정리해 보았다.
Hash Table의 개념
['Mia','Tim','Bea','Zoe','Jan','Ada','Leo','Sam','Lou','Max','Ted']위와 같은 배열을 Hash Table에 넣고 index를 매기는 것이라 보면 된다.
이때 Mia나 Tim은 Hash Function(Hash Algorithm)에 의해 Hash Table안의 주소 위치를 Hash로 부여되게 된다.
Hash Function(Hash Algorithm)
예시로 사용할 Hash Function은 영어 이름의 알파멧을 ASCII코드값으로 변환한 뒤,
그 값을 모두 더한 다음 데이터 배열의 크기만큼 나누는 값을 받환하기로 한다.
Mia의 경우,
알파벳 M의 ASCII 값은 77
알파벳 i의 ASCII 값은 105
알파벳 a의 ASCII 값은 97
이므로 모두를 더하면 279이고
이를 배열의 크기 11로 나누면 4가 된다.
다시 말해 Mia의 Hash(Hash Table에서의 Index)는 4다.
Miya는 Hash Table안에 들어가게 된다
Javascript로 배열들의 위 Hash Function의 Hash값을 반환하도록 해보자
const getASCII =(str)=>{
let ans = 0;
for(const char of str.split("")){
ans += char.charCodeAt(0);
}
//console.log(str,' ASCII sum:',ans)
return ans;
}
console.log(['Mia','Tim','Bea','Zoe','Jan','Ada','Leo','Sam','Lou','Max','Ted'].map((el,index,array)=>getASCII(el)%array.length))
//[4,1,0,5,6,9,2,3,7,8,10]위 스크립트를 실행해보면 차례대로 [4,1,0,5,6,9,2,3,7,8,10] 을 반환하는 것을 볼 수 있다.
자 그러면 이름을 Hash값에 맞게 Hash Table에 넣어본다.
이제 Sam이라는 이름이 Hash Table내에 어디에 위치해 있는지 바로 알 수 있다.
물론 완벽한 건 아니다. 위에도 서술 했듯이 O(1)탐색이 가능한것은 BEST CASE일때이다.
위의 배열은 Hash값들의 충돌(중복)이 일어나지 않았기 때문에 별다른 추가 과정없이 Hash Table을 완성할 수 있고 O(1)의 탐색이 가능하다.
Hash Table을 어느 풍족한 나라라고 보고 여기에 들어가는 자료들이 국민들이 각자 고유한 집주소(Hash)를 가지고 있는 행복한 상황이라고 할 수 있다.
하지만 어디든지 비극은 일어난다.
Hash Collision
Hash Collision이란, Hash값이 고유하지 않고 충돌(중복)이 일어나는 것이다.
중복되는 index를 가지므로 같은 Hash값을 가진 자료는 저장할 수 있는 다른 주소를 찾아야만 한다.
다른 주소를 찾는 과정에서 Worst Case 시간복잡도가 발생한다.
아까의 배열에서 맨뒤 세 명의 이름이 바뀐 배열의 Hash Table을 생성해보자.
['Mia','Tim','Bea','Zoe','Jan','Ada','Leo','Sam','Lou','Max','Ted']
['Mia','Tim','Bea','Zoe','Jan','Ada','Leo','Sam','Sue','Len','Moe']첫번째 배열은 운좋게 ASCII 값의 합을 배열의 길이로 나눠서 얻은 Hash값들이 모두 고유했지만 두밴째도 그러리란 보장은 없다.
const getASCII =(str)=>{
let ans = 0;
for(const char of str.split("")){
ans += char.charCodeAt(0);
}
//console.log(str,' ASCII sum:',ans)
return ans;
}
console.log(['Mia','Tim','Bea','Zoe','Jan','Ada','Leo','Sam','Sue','Len','Moe'].map((el,index,array)=>getASCII(el)%array.length))
//[4,1,0,5,6,9,2,3,4,1,3]이전에 만들어둔 스크립트를 사용해서 Hash값들을 뽑아보니 4,1 그리고 3이 각각 두개씩 있다.
Hash Table을 만드는 과정에서 Hash Collision이 생긴 것이다.
집주소를 받아들고 동네에 가보니 이미 자기가 살집에 다른 사람이 살고 있는 격이다.
불쌍한 이들에게 다른 집이라도 얻어줘야 하지 않겠는가
Hash Collision을 해결하는 과정은 크게 Open Addressing이라고 하는 방법과
Closed Addressing이라고 하는 방법이 있다.
이 방법들에 대해서는 다음번에 알아보도록 하자
