[자료구조] 해쉬(Hash)란?

해쉬(Hash) 란?
- 데이터를 다루는 기법중에 하나로 검색과 저장이 아주 빠르다.
- 데이터를 검색할 때 사용할 key와 실제 데이터의 값이 (value가) 한 쌍으로 존재
- key값이 배열의 인덱스로 변환되기 때문에 검색과 저장의 평균적인 시간 복잡도가 O(1)이 된다. 

해시 함수
- 임의의 길이의 데이터를 입력받아 일정한 길이의 비트열로 반환 시켜주는 함수
- 결과로는 해쉬코드가 나온다.
- 동일한 값이 입력되면 언제나 동일한 출력값을 보장한다.

좋은 해쉬함수
- 충돌을 최소하하는 방향으로 설계
- 키의 일부분보다는 전체를 참조하여 키 생성


충돌이란 ?
- 해시함수를 통해서 결정된 key가 중복되는경우

충돌해결
Open Address 방식
- 충돌이 발생하면 다른 해시버킷에 데이터를 삽입하는 방식
- 충돌이 발생하면 데이터를 저장할 장소를 찾아 헤맨다. 최악의 경우에는 삽입할 버킷을 찾지 못하고 탐색을 시작한 위    치까지 되돌아 올 수 있다.
  여러가지 방식이 존재한다
  1. Linear Probing
  - 순차적으로 탐색하며 비어있는 버킷을 찾을때까지 계속 진행
  2. Quadratic Proving
  - 2차 함수를 이용하여 탐색할 위치를 탐색
  3. Double hashing Probing
  - 하나의 해쉬 함수에서 충돌이 발생하면 2차 해쉬 함수를 이용해 새로운주소 할당
    위 두가지 방식보다는 많은 계산량 요구

Separate Chaining 방식
1.Linked List를 이용하는 방식
- 각각의 버킷들을 연결리스트로 만들어 충돌이 발생한다면 해당 버킷의 리스트에 추가하는방식
  연결리스트의 특징을 그대로 이어받아 삽입 삭제가 간단하다.
  작은 데이터들을 저장할때 Open Address방식보다는 비효율적일수 있다.

해시 버킷 동적 확장(Resize)
- 해시 버킷의 개수가 적다면 메모리 사용을 아낄 수 있지만 해시 충돌로 인해 성능 상 손실이 발생한다.
  그래서 HashMap 은 key-value 쌍 데이터 개수가 일정 개수 이상이 되면 해시 버킷의 개수를 두 배로 늘린다.
  이렇게 늘리면 해시 충돌로 인한 성능 손실 문제를 어느 정도 해결할 수 있다.
  또 애매모호한 '일정 개수 이상'이라는 표현이 등장했다.
  해시 버킷 크기를 두 배로 확장하는 임계점은 현재 데이터 개수가 해시 버킷의 개수의 75%가 될 때이다.
  0.75라는 숫자는 load factor 라고 불린다.