a) 해시 테이블

• key, value 를 사용하여 빠르게 데이터를 검색할 수 있는 자료구조
• 데이터 저장/삭제/조회 에 대한 평균 시간복잡도는 O(1) 이다
• 내부적으로 배열을 사용하여 데이터를 저장
• 실제로 값이 저장되는 곳을 버킷/슬롯 이라고 한다
• 각각의 key 값에 해시함수를 적용해 배열의 고유한 index 를 생성하고

이를 통해 값을 저장 및 검색한다

b) 해시함수

• 내부적으로는 같은 Array 구조 이지만, Hash Function 을 통해 Key 를 데이터에 접근 가능한 index 로 바꾸어주기 때문에 선형 시간으로 데이터의 저장/삭제/조회가 가능해진다

c) 해시 충돌

• 각기 다른 key 에 대해 해시 함수가 동일한 index를 출력한 경우를 충돌 이라고 한다
• 무한한 입력에 비해 한정된 버킷을 가지고 있기 때문에 반드시 충돌은 발생한다
• 해시 함수를 잘 정해서 충돌을 최소화 하는게 유리하다
• 해결 방법

  • 체이닝

    버킷 내에 연결 리스트를 할당하여 데이터를 삽입하다가 충돌이 발생하면 연결 리스트로 데이터들을 연결하는 방식

    • 장점 - 복잡한 계산식을 사용할 필요가 적어진다
    • 단전 - 해시 테이블이 채워질수록 성능저하가 비례해서 발생

  • 개방 주소법 (선형 탐색 / 제곱 탐색 / 이중 해시 )

    해시 충돌이 일어나면 다른 버킷에 데이터를 삽입하는 방식

    • 포인터가 필요 없고, 지정 메모리 외의 공간을 필요로 하지 않는다
    • 삽입/삭제 시 오버헤드가 적다
    • 저장할 데이터가 적을때 더 유리하다