[Algorithm] 해시 테이블(Hash Table)

📌 해시 테이블(Hash Table)?

• 어떤 특정 값을 받으면 그 값을 해시 함수에 통과 시켜 나온 인덱스에 저장하는 자료구조
• 해시 함수를 사용하여 특정 값을 신속하게 찾는 자료구조
• 자바스크립트 객체는 해시 테이블과 같은 방식으로 키와 해당 키의 연관된 값을 정의하는 방식으로 동작한다.

 

✅ 해시 함수 (Hash Function) = 해시(Hash)

임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수

• 해시 함수의 특성
  • 압축성: 다양한 가변 길이의 입력에 대해 고정된 크기의 결과값을 반환하는 성질을 가진다.
  • 효율성: 어떤 입력 값에 대해서도 많은 자원과 시간이 소요되지 않고 처리되는 성질을 가진다.
  • 저항성: 결과값을 바탕으로 입력 값을 찾는 것이 불가능한 성질을 가진다.

 

✅ 해시 충돌(Hash Collision) 

데이터를 Key로 간소화하여 저장하지만 다른 ㅐㄴ용의 데이터가 같은 키를 갖는 경우 생기는 것을 해시 충돌이라고 한다.

해시테이블의 성능능을 떨어뜨리는 원인이 된다.

• 해결방법
  • 해시 함수 변경: 더 큰 숫자의 공간과 모듈 산술 값을 이용해 충돌을 최소화한다.
    (같은 수가 나오는 경우의 수를 줄인다.)
  • 자료구조 확장: 선형 조사법, 이중해시, 채이닝
• 구현 메서드(Method)
  • clear
  • size
  • getBuffer
  • print
  • put
  • remove
  • get