[Data Structure] 해시 (Hash)

✔ 해시

해시(Hash)란?

• 해시 테이블이라고도 불림
• 내부적으로 배열을 이용하여 데이터를 저장

해시의 특징

1. key와 value를 1:1로 연관지어 저장
   • key를 이용하여 value를 도출
   • 데이터의 고유 인덱스로 접근하여 값을 검색하므로 시간 복잡도가 O(1)
2.  해시 함수를 이용하여 저장할 데이터와 연관된 고유한 숫자인 해시 코드를 만들어낸 뒤 이를 인덱스로 사용
3. 특정 데이터가 저장되는 인덱스는 그 데이터만의 고유한 위치이기 때문에
   삽입 연산 시 다른 데이터의 사이에 끼어들어나, 삭제 시 다른 데이터로 채울 필요가 없으므로 연산에 추가적인 비용이 없음

해시 함수

• 고유한 인덱스 값을 설정하기 위한 특별한 알고리즘
• 임의의 길이의 데이터를 수학적 연산을 통해 고정된 길이의 데이터로 매핑
• 해시 함수를 이용해 반횐된 데이터의 고유 숫자 값을 해시 코드라고 하며
  어설픈 해시 함수를 통해 key 값들을 결정한다면 동일한 값이 도출되어 
  동일한 key 값에 복수 개의 데이터가 하나의 테이블에 존재하게 되어 충돌이 발생할 수 있음
• 일반적으로 좋은 해시 함수는 키의 일부분을 참조하여 해시 값을 만들지 않고 키 전체를 참조하여 해시 값을 만들어 냄
• 해시 함수는 키가 어떤 특성을 가지고 있느냐에 따라 달라지게 됨
• 또한 충돌을 최소화하는 방향으로 설계하고, 발생하는 충돌에 대비해 어떻게 대비할지가 더 중요

충돌 해결

1. 개방 주소법 (공개 주소 방식)
   • 삽입하려는 해시 버킷이 이미 사용 중이어서 충돌이 발생하면 다른 해시 버킷에 해당 자료를 삽입하는 방식
   • 순차적으로 탐색하여 비어있는 버킷을 찾거나,
     2차 해시 함수를 이용해 탐색할 위치를 찾거나,
     2차 해시 함수를 사용해 새로운 주소를 할당함
   • 분리 연결법보다 캐시 효율이 높음
2. 분리 연결법
   • 각각의 버킷들을 연결 리스트 또는 트리로 만들어 충돌이 발생하면 해당 버킷의 리스트에 추가하도록 함
   • 하나의 해시 버킷에 할당된 key-value 쌍의 개수가 6개 이하면 연결 리스트를 사용
   • 개방 주소법보다 테이블의 확장을 늦출 수 있음
3. 이 외로 선형 탐사, 제곱 탐사 등이 존재
4. 해시 버킷 동적 확장
   • 해시 버킷의 개수가 적다면 메모리 사용을 아낄 수 있지만 해시 충돌로 인해 성능 상 손실이 발생
   • HashMap은 key-value 쌍 데이터 개수가 일정 개수 이상(현재 데이터 개수가 해시 버킷의 개수의 75%가 될 때)이 되면
     해시 버킷의 개수를 두 배로 늘리게 됨