소개글

면접 대비겸 여러 블로그들을 참고하면서 정리해본 CS 지식들을 포스팅하고 있습니다.
만약 틀린 내용이 있다면 피드백은 언제나 환영합니다.
제 나름대로 요약한 내용이기 때문에 자세한 내용은 제일 아래쪽 참고 사이트에서 확인하면 좋을 것 같습니다!
말투는 편한 말투로 작성하니 양해 부탁드립니다.

Hash Table

• 내부적으로 Array를 사용하여 데이터를 저장 - 조회가 빠름
• 특정 알고리즘을 사용하여 고유 숫자(키)를 만들어낸 뒤 이를 인덱스로 사용

Hash Function

• 이를 이용해 데이터의 인덱스 값을 만들어냄
• Collision - 같은 값이 도출되어서 같은 곳에 저장할 수가 없음
• 무조건 1대1로 만드는 것은 불가능에 가까움
• Collision을 최소화하고 대응을 잘하는 것이 중요

Collision 대응

Open Address (개방 주소법)

• 충돌이 발생하면 다른 공간에 데이터를 저장
• 데이터 밀도가 높으면 Collision이 자주 발생
• 비교적 연속된 공간에 저장하기 때문에, 캐시 효율이 높음 - 지역성의 원리
• 종류
  • Linear Probing - 순차적으로 비어있는 버킷을 찾음
  • Quadratic Probing - 2차 함수를 이용해 비어있는 버킷을 찾음
  • Double Hashing Probing - 2차 해쉬 함수를 이용해 비어있는 버킷을 찾음

Separate Chaning (분리 연결법)

• 같은 공간에 자료구조를 활용하여 데이터를 저장 - 추가 메모리 필요
• 테이블의 확장을 늦출 수 있음
• 데이터가 많아지면 버킷 안에서 찾는데 오래 걸림
• 캐시 효율이 떨어짐 (링크드 리스트 = 불연속적 저장)
• 종류
  • 링크드 리스트 활용 - 각각의 버킷을 링크드 리스트로 만들고 이어붙임 (키-값 쌍이 적을 때 사용)
  • 트리 활용 - 마찬가지로 트리로 만들고 이어붙임 (키-값 쌍이 많을 때 사용)

참고 사이트

https://velog.io/@edie_ko/hashtable-with-js
https://becomeweasel.me/hash-table/