[자료구조](18)[map & 해시함수]

Map

key-value 쌍의 ADT
-> key를 이용한 빠른 선형 탐색에 특화됨

• key: 탐색을 위한 값
• value: 실제 저장할 데이터
• 연산
  get(key)
  insert(key, value)
  remove(key)

Map VS 우선순위 큐
    map은 key로, 우선순위 큐는 우선순위로 검색하나 사용 목적이 약간 다름
        map: 빠른 탐색
        우선순위 큐: 순서대로 프로세스 실행

해시 함수

암호학에서도 이용됨 (암호학 둘러보기 9 참고)
특징

• 비가역적
  해시 -> 평문은 매우 힘듬
• 출력값의 길이가 고정됨
• 랜덤이 아님
  같은 입력을 넣으면 무조건 같은 출력이 나옴

좋은 해시의 특징

• 충돌이 적음
  다른 입력으로 같은 해시 값이 나오는 것을 충돌이라 한다.
  좋은 해시는 '최대한' 다른 입력이면 다른 값이 나오는게 좋다.
  (물론 해시를 쓰는 이유가 큰 범위 -> 작은 범위 이므로 충돌은 불가피하다)
• 해시 값이 균등한 분포를 띤다.
  충돌도 최대한 방지할 수 있고
  해시 테이블에서 사용할 때 특정 인덱스에 몰리는 걸 방지할 수 있다
• 계산이 빠름

magic number
좋은 해시 함수를 만들기 위해 쓰는 상수
대부분은 휴리스틱한 방법으로 정해짐
걍 써보니 좋은 상수를 채택

예)

• djb2
• sdbm
• FNV1a
• SHA-256
  이 중에 SHA-256은 암호화에도 쓰일 만큼 충돌 저항도 높고 길이도 길고 해시 추측도 어렵다.