Hashing

Hash Table이란?

• 해시 알고리즘을 위한 자료구조
• key와 value로 저장되며 빠른 검색 속도를 제공
• hash function을 이용하여 만들어진 해시 주소를 테이블의 index로 사용하며, 이 index를 통해 자료 저장, 접근 진행
  

Hash function이란?

• 데이터의 효율적인 관리를 목적으로 키 값을 hash table의 주소로 변환하는 함수
• 설계 주의 사항
  • 충돌이 적어야함
  • 해시 함수의 값이 테이블 주소 영역 내에 고르게 분포
  • 계산이 빨라야 함
• 주로 사용하는 해시 함수
  • 제산 함수: 나머지 연산자를 사용해 나머지를 해시 주소로 사용
  • 폴딩 함수: 키를 여러 부분으로 나누어 더하거나 비트별로 XOR 같은 bool 연산 한 값을 주소로 사용
  • 중간 제곱 함수: 키를 제곱한 다음, 중간의 몇개의 비트를 취한 값을 주소로 사용
  • 비트 추출 방법: 해시 태이블의 크기가 M=2**k 일 때, 키를 이진수로 간주하여 임의의 위치의 k개 비트를 주소로 사용
  • 숫자 분석 방법: 키 각각의 위치에 있는 숫자 중 편중되지 않는 수들을 해시 테이블의 크기에 적합한 만큼 조합해 해시 주소로 사용

collision & overflow

• hash value 개수 보다 많은 키 값을 hash value로 변환 시키는 many-to-one 을 진행
• 서로 다른 두 개의 키에 대해서 동일한 해시값을 갖는 collision이 발생
• 이로 인해 overflow 발생

해결 방안

• 개방 주소법
  1. 선형 조사법: k에서 충돌 발생시 k+1로 진행, 충돌 발견이 안될때 까지 반복(만일 빈 위치가 없다면, 처음으로)
  2. 이차 조사법: 빈공간 조사시, 충돌 횟수의 제곱을 한 수를 더함(k, k+1, k+4, k+9...)
  3. 이중 해시법: 오버플로우 발생 시, 별개의 해시 함수를 따로 사용하는 방법
• 체이닝: 해시테이블 구조를 변경해 각 버킷이 하나 이상의 값을 저장할 수 있도록 하는 것
  

성능

	Average	Worst
Search	O(1)	O(n)
Insert	O(1)	O(n)
Delete	O(1)	O(n)