Data Structure, Hash Table

개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.
잘못된 부분이 있다면 댓글로 남겨주세요! :)

Hash Table

a large size of tables consisting of keys and values

• hash function > 특정 키를 입력하면 value 리턴
• key: a unique identifier of a value, a parameter to find its array index through hash functions
• value: a stored vlaue

특성

1. key는 무조건 index와 연결
2. 하나의 index는 여러개의 key와 연결 가능

Perfect hash function

• 가상의 hash function
• 가정상황: unlimited space & 한정된 input size
• a bijective(일대일 대응함수) hash function을 만들 수 있음

Good hash function

• uniform distribution (연속균등분포): 분포가 특정 범위내에서 균등하게 나타있는 경우를 의미
• 왜 좋은가 > 충돌이 적어지기 때문
• 왜 어려운가 > 랜덤하게 배정하는게 쉽지 않음
• Surjective Function: 공역의 모든 원소가 선택되었단는 말 > Y에 있는 원소에 대응되는 x가 존재
• Injective Function: 정의역의 원소하나는 단 하나이 공역의 원소에 대응된다는 것

Example of Hash Function

Modulo based hash function

• divide a numeric key with a number
• number = the size of the hash table
• Example: Index = Key MOD Size
• 자주 사용하는 이유
  • 장점: 다양한 범위가 나옴
  • 문제

주민번호를 사용하는 경우 나누는 숫자가 작은때 앞에 중요한 정보를 사용하지 않고 일부만 사용하는 문제가 발생함 > Quotient is not used

Square base hash function

• mid-square hash function
  1. square the key value
  2. take the N digit in the middel
  3. the selected digits to the modulo operation
• example
  • KEY = 123, Table size=100, Mid-square digit=3
  • f(123) = MidSquare(123) mod 100 = 512 mod 100 = 12
• 왜 좋은가 > 충돌횟수를 줄일수 있음

Digit analysis based hash function

• Digit analysis
  • ex) checksum hash function
• key = 8011171234567, Table size =100
• f(8011171234567) = (8+0+1..+7) mod 100 = 46
• 주어진 모든 숫자를 이용하는 점에서 좋음