About Hash Collision

수까락님의 블로그에서 관심있는 부분을 다시 요약함.
출처 : http://sweeper.egloos.com/925740

Hash Collision

좋은 해쉬 함수는 해쉬 테이블, 해쉬맵등의 성능 향상에 필수적인 요소들이다.
질 낮은 해쉬 함수는 데이터들의 key를 같은 bucket에 유도하는 경우가 많아짐으로써 충동리 증가하게 되고, 이는 곧 해쉬테이블/맵의 성능 저하로 이어진다.

100만개의 크기를 가지는 해쉬 테이블에 뛰어난 해쉬 함수로 가지고 있다고 해도, 대략 2500개의 레코드가 찼을 때 충돌이 발생활 확률은 95%에 이른다고 한다.출처:Hash table

충돌이 발생했을때 이를 해결 할 수 있는 방안으로 chainning, open addressing 방식이 널리 사용된다.

Chaining

모든 bucket을 linked-list로 만들어 충돌이 발생하면 해당 bucket의 list에 해당 아이템을 추가하는 방식이다.

• 장점
  1) 삭제 작업이 간단하다.
  2) 모든 bucket이 사용중이더라도 충돌된 아이템 추가에 따른 성능 저하가 더디게 나타난다.
  3) 효과적으로 구현이 간단. 기본 자료구조정도만 요구
  4) 클러스터링에 영향을 받지 않아 충돌 최소화에만 집중할 수 있다.
  5) 테이블(bucket을 위한)이 채워져도 성능저하가 linear하게 발생
  6) 데이터의 크기가 5words and more라면 open-addressing보다 적은 메모리를 사용한다
• 단점
  1) 충돌이 발생하지 않는 경우라면 bucket의 list길이가 대부분 짧은 상태이며, 이런 경우 linked-list가 가지는 오버헤드가 부담이 된다.

Open Addressing

배열내에 데이터를 바로 저장할 수 있다.

충돌은 probing 방식으로 해결하며 이를 위해 다음 probe sequence를 사용한다

1. Linear probing
   비어있는 bucket을 찾을때까지 순차적으로 탐색.
   최악의 경우 탐색을 시작한 위치까지 돌아오게되어 종료된다.
   캐쉬효율이 좋다.데이터의 클러스터링에 가장 취약한 단점
2. Quadratic probing
   2차 함수를 이용해 탐색할 위치를 찾는다.
   캐쉬효율, 클러스터링 강점면에서는 중간정도
3. Double hashing probing
   하나의 해수함수에 충돌발생시 2차 해쉬함수 이용하여 새로운 주소 할당
   캐쉬 효율을 좋지 않으나 클러스터링에 거의 영향을 받지 않는다
   연산량이 많다

• 장점
  1) 포인터를 저장할 필요가 없다(->serialization용이) 테이블 외부에 어떠한 추가공간이 필요없어 chaining방식보다 메모리 효율이 높다
  2) 삽입시 메모리 할당 오버헤드가 없다.
  3) 별도의 외부공간(linked-list 같은)이 필요없다.
  4) 사용하는 데이터가 테이블에 모두 저장될 수 있고, 캐쉬라인에 적합할정도의 데이터크기가 작을 수도록 성능이 좋다

Coleasced hasing

Chaining, Open-Addressing 혼합방식
테이블의 bucket끼리 서로 chain 링크를 갖는다. -> 테이블 슬록보다 많은 수의 데이터를 저장할 수 없다.

hash의 단점

데이터를 pseudo-random 위치에 저장하기 때문에 데이터를 정렬된 순서로 접근하는 것에 엄청난 비용이 발생한다.

해쉬테이블은 일반적으로 locality-of-reference(하나의 자원에 여러번 접근하는 process)에 취약. 데이터 수가 적고 key type이 integer처럼 비교 비용이 적게 든다면 linear search를 하는 배열 같은 자료구조가 lookup에 더 나은 성능을 보인다.