Hash Table의 기본 개념은 Key가 존재하며, hash function 이 존재하고, buckets이 존재한다.
- 기본개념과 용어
- Keys
- hash function :
- key 값을 입력을 받아 가능한 매번 균등한 일정 값 이 나와야 한다.
- key 값을 입력을 받으면 결과 값은 매번 동일해야 한다.
- buckets
- key와 bucket을 1:1 mapping이 되도록 하기 위해서 만들어 놓은 저장장소
- hash function은 완전한 1:1 mapping 제공하지 않는다 (충돌문제 발생)
key는 아래와 같이 data가 될 수있으며, hash function 을 통하여 bucket 에 균등하게 mapping 되도록 노력한다.
쉽게 설명하면, 어떤 이름을 가진 table을 빠르게 검색하고 싶은 경우를 생각을 해보자.
이 이름을 Key로 사용하고 Hash Function의 이 이름을 분석하여, bucket list 중 하나에 이를 1:1 mapping 하도록 하면 빠른 검색이 가능하다.
이렇게 하면, 빠른 검색이 가능하지만, 여기서 기본적인 문제점이 있다.
Hash 함수의 균일성 유지 문제이다. 그래서 여분의 Bucket 있음에도 불구하고
Key값의 충돌이 발생이 한다.
가능한 Hash 함수가 균일성을 유지하고 Key값과 Bucket을 1:1 Mapping 유지하도록 했다면,
균일성 문제로 충돌을 해결하는 방안으로 찾아보자.
이에 따라 Hash Table의 종류가 변경이 된다.
 |
| https://en.wikipedia.org/wiki/Hash_table |
2. Hash Table의 종류
위의 설명을 보면, hash function이 중요하다는 것을 알 수 있으며, 충돌문제가 발생할 수 있다는 것을 알수 있다.
key 값을 넣어 hash table을 가능하면, 균등하게 매번 동일하게 mapping하여 빠른 검색을 해야한다.
하지만, Key 값을 Hashing 하여 bucket 값이 충돌이 될 경우
이를 해결하는 방법은 크게 두가지로 나누어지며, 아래와 같이 볼수 있다.
2.1 Chained Hash Table
사용할 Bucket 숫자 와 함께 Linked List를 만들어, 데이타를 추가 할 경우 기존에 이미 해당 Bucket에 존재 할 경우,
이는 충돌이 되어, 아래와 같이 같은 Bucket에 linked list를 만들어 관리한다.
이는 Bucket의 충돌을 허용하여, 이를 Linked List로 별도로 관리를 한다.
2.2 Open-Addressed Hash Table
충돌을 해결법은 다시 빈 Hash Table을 찾을 때까지 검색하여, 이를 그 곳에 넣는것이다.
이때 Hash 하는 방법은 아래와 같은데, 아래 예제는 Hash 함수를 두개 사용한 Double hasing 이다.
A. 충돌문제방법(Collision resolution)
아래와 같이 충돌이 발생할 경우, Open-Addressed Hash Table은 이 충돌을 피하기 위해,
다양한 방식을 제공을 한다.
1. Linear Probe 방식
충돌이 발생할 경우, 충돌 지점부터 순서대로 빈칸 bucket을 찾아 그곳에 Data를 삽입.
아래사이트 참고
https://en.wikipedia.org/wiki/Linear_probing
2. Quadratic Probe 방식
충돌이 발생할 경우, Hash 함수에 패턴을 가지고 변형을 가해 빈칸을 찾아 그곳에 삽입.
아래 사이트 참고
https://en.wikipedia.org/wiki/Quadratic_probing
3. Double Hash 방식
충돌이 발생할 경우, 기본적으로 Hash함수를 두개를 사용하고 하나는 기본 Hash함수와
별도의 하나는 값의 변경에의해 변경될 Hash 함수로
매번 다른 값을 균일하게 나오도록 하여, 빈칸을 찾아 그곳에 삽입
한마디로, 빈 Bucket 을 찾을 때까지 2개의 hash 함수로 찾는 것이다.
https://en.wikipedia.org/wiki/Double_hashing
4. 기타 방식들
아래 사이트가면 자세히 설명
https://en.wikipedia.org/wiki/Hash_table
위 방식들은 빈 Bucket을 찾는 방식은 서로 다르나, 기본적인 취지는 동일하다.
충돌이 일어날 경우, 다시 빈 Bucket을 찾는 것이다.
B. 충돌문제방법 예
- Double Hash 방식
아래의 예제는 Double Hash 기준으로 작성된 예제이다.
소스로만 보면, 최악의 경우 최대 Bucket 수 까지 검색해야 한다.
하지만, 핵심은 Hash 함수가 동일한 Key 입력을 받을 경우 동일한 Bucket 값으로 Mapping이 되기에
이 문제는 최악으로 가지는 않을 것이다.
/*
htbl->positions : 전체 사용할 bucket 수
htbl->h1 , htbl->2 : 2개의 hash 함수
position : bucket
refer to : Mastering Algorithms with C
*/
for(i=0; i < htbl->position;i++) // 자료를 찾을 때까지 , 전체 bucket 수 까지 반복하면서 찾는다.
{
position = (htbl->h1(*data) + (i * htbl->h2(*data))) % htbl->positions;
if(htbl->table[position] == NULL){ //자료를 없을 경우
return -1;
}else if(htbl->match(htbl->table[position],*data)){ // 자료를 찾을 경우,
*data = htble->table[position];
}
}
위의 Double Hashing 과 함께 예제를 통해 간단히 알아보자.
전체 Bucket 수가 10개 있을 경우, 초기 값이 00일 경우
h(k,i)
k : 삽입되는 key data
i : 반복되는 횟수
0 1 2 3 4 5 6 7 8 9
1: [00] [00] [00] [00] [00] [00] [00] [00] [00] [00] : i=0 일 때 k = 23, 45, 55, 77 삽입
2: [00] [23] [00] [45] [00] [55] [44] [77] [00] [00] : i=0,1 로 k = 44 (1번 충돌)
3: [00] [23] [66] [45] [00] [55] [44] [77] [11] [00] : i=0,1,2,3,4 로 k = 66, 11 (4번 충돌)
참조 : C로 구현한 알고리즘
- Linear Probe 방식
아래의 그림은 기본적으로 Linear Probe 방식이을 나타낸다.
C. 참고사항
Open addressed Hash Table 2번 이상 충돌된 Bucket을 삭제할 경우,
1번째 충돌이 된 Bucket을 삭제를 하면 이 상태가 모호해지므로, 이부분의 상태를 구분을 해주는데,
만약 이 부분도 무시하고 싶다면, loop에서 continue로 넘어가면되지만, 좀 성능저하가
발생된다.
그래서, remove시 이때 unique한 다른 값을 넣어, 초기 값과 remove 상태를 구분지어 주는 것이다.
예를 들면, Bucket에 Pointer 주소를 넣어준다. 위와 같이 구현을 한다.
참조 : C로 구현한 알고리즘 ( vacated 사용부분)
http://bcho.tistory.com/1072
3. Hash Table의 비교 및 성능분석
위 상위 두개 Hash Table을 성능을 찾기를 했을 경우, 평균 Cache Miss가 일어나는 경우를
나타내는 그림이며, 상위 두개의 Hash Table을 비교를 해보자.
잘 알다시피 Cache Miss가 일어나며, CPU는 Cache에 Data가 없기에, RAM에서 다시 가져와야한다.
아래는 Cache HIT가 아니라 Cache Miss임을 알아두자, 높으면 높을 수록 안좋다.
X의 좌표의 Load Factor는 아래와 같이 설명된다.
- Load factor = n/k
- n: the number of entries ( 현재 사용하고 있는 entry)
- k: the number of buckets ( 총 bucket 수 )
그래서 Open Addressed 경우 사용률을 80%가 넘어가면 안되겠다.
상위 그림을 보면, 내 개인적인 생각으로는 Load factor 기준으로 비교해 보면
Chaining은 평균 Cache Miss 2~ 3정도로 꾸준히 유지하는이유는 처음 나도 궁금했으나, 생각을 해보니
이유를 알것 같다. Chaining은 Linked List 가 필요하며, 이때 매번 새로운 Access 문제가 발생한다.
충돌을 하든 안하든 새로운 Linked List Access 요구가 필요하고, 충돌이 될 경우는
Linked List의 에서
다음 Element를 검색을 한번 더 해야하니 2~3정도로 유지하는 것이 맞는것 같다.
Open-Addressing는 Data 를 Table에 직접 Mapping하여 상위문제는 없어 빠르다.
하지만, Load Factor가 증가하면 할 수록 확률적으로 충돌횟수는 증가할 것이고,
이는 곳 Cache Miss 횟수가 늘어날 수 밖에 없는 구조이다.
현재 위 그림은 Open-Addressing의 (Linear Probing) 경우 이지만, 다른 모델도 거의 비슷할 것으로 생각한다.
상위기본 문서는 아래의 wiki 참조하여 작성했으며, 더 자세한 내용 아래의 Wiki 참조.
https://en.wikipedia.org/wiki/Hash_table
https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%ED%85%8C%EC%9D%B4%EB%B8%94
4. Hash Table 예제
4.1 Open-addressed Hash Table
아래의 예제는 open-addressed hash table이며, vacated 로 remove시
이를 구분하도록하였지만, 2번 이상 remove를 하면 이것도 사실 필요가 없다.
처음 코딩할때 부터 여러번 remove를 할 것이면, 구지 만들필요가 없는 개념이다.