Hash

  • Hash funciton은 데이터를 다른 형태로 변환해주는 함수
  • 자료구조와 연결하면 강력한 성능을 발휘
  • Hash Table (Insert, Delete, Search) -> Average O(1), Worst O(n)
  • key -> hash function -> h(key) 로 테이블에서 삽입/삭제/탐색
  • 같은 함수 값이 나온 경우 충돌(collision)이라하며 충돌 횟수가 작을수록 좋은 해시 함수라 평가
  • Hash Table은 충돌이 날 경우 데이터들을 해당 h(key)값에 연결리스트로 저장
  • 즉, 해시 테이블의 연산은  충돌 횟수만큼 시간이 걸림. 해당 키값에 충돌된 횟수만큼 쭉 저장되므로. 해시 함수가 충분히 좋으면 O(1)로 수렴, 충돌이 많을 경우 연산 한번에 O(n)시간이 걸릴 수도 있음.
  • 즉 성능은 해시 함수에 좌우됨

Hash 함수만 Data type에 따라 이용 할 수 있게 변경

예시문제)

Hash table은 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조이다. Hash table은 Hash 함수를 사용하여 색인(index, Key)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산한다. 주어진 N개의 key, data쌍을 Hash table에 입력한 후, Q개의 key를 입력 받아 key에 해당하는 data를 각 줄에 출력하시오. (1<=N, Q<=4096) * Key : 최대 64개의 문자열 * Data : 최대 128개의 문자열

Input

Output

Code

 

It's only fair to share...Share on Facebook
Facebook
Share on Tumblr
Tumblr
Share on Google+
Google+
Tweet about this on Twitter
Twitter
Email this to someone
email
Musicals, Travel, Photo, Coding, English, Cat