해쉬 테이블(Hash Table)

해쉬 테이블(Hash Table)

• 키(Key)와 값(Value)을 갖는 구조
• 시간 복잡도
  • 평균 : O(1)
• 해쉬 충돌(Hash Collision) : 해쉬가 충돌하는 현상
  • 해결법 : 분리 연결법(Sperate Chaining)
    > 동일한 해쉬의 데이터에 대해 자료구조를 활용해 추가 메모리를 사용해, 다음 데이터의 주소를 저장하는 것
    > 예 : 동일한 해쉬(152)에 새로운 해쉬 테이블을 작성,
    그 테이블을 토대로 여러개의 값이 저장되게 하는 것으로 이해 중
• C# Dictionary 등
• 예 : 호텔의 키와 안의 고객 등