[자료구조] 해시 / 해시테이블

해시테이블 (Hash Table)

• 해시 & 해시테이블
  • 해시 (Hash) : 인덱스에 해시값을 사용하는 자료구조
  • 해시 함수를 사용하여 키를 해시값으로 매핑
  • 마치 key-value 형태로 이루어진 자료구조
• 해시함수 (Hash Function)
  • 원하는 값을 최대한 효율적으로 찾을 수 있도록 함
  • Key를 고정된 길이의 hash로 변경해주는 역할-> hashing
  • key를 해시 함수의 input으로 넣었을 때 나오는 Output을 Hash라 보면 됨.
  • 결론적으로 Hash는 저장위치가 되는 것이라 보면 됨

해시테이블 구성

• key
  • 해시 함수의 Input이자, 고유한 값
  • key값은 제각각의 길이를 가질 수도 있어 key의 길이만큼 정보를 저장해야되기 때문에, 고정된 길이의 해시로 변경한다.
• hash function
  • key를 고정된 길이의 hash로 변경해주는 역할
  • 서로 다른 key가 Hash된 이후 같은 hash값이 나오는 경우 -> 해시충돌, 이것이 적을 수록 좋다.
• value
  • 저장소에 최종적으로 저장되는 값
  • hash와 매칭되어 저장
• hash table
  • 해시함수를 사용하여 Key를 해시값으로 매핑
  • 이 해시값을 주소또는 색인 삼아 데이터(value)를 key와 함께 저장하는 자료구조
  • 데이터가 저장되는 곳을 버킷, 슬롯이라 명명

  장점 / 단점

• 장점
  • 해시테이블은 key- value가 1:1로 매핑되기에, 값 삽입이나 삭제와 같은 과정에서 평균적으로 O(1)의 시간 복잡도로 나타난다.
• 단점
  • 해시 충돌 (서로 다른 key가 Hash된 이후 같은 hash값이 나오는 경우)이 발생할 수도 있음
  • 공간 효율성이 좋지 않음.