Direct Address Table

key 값을 주소로 사용하는 테이블

• 한계점
  최대 키 값에 따라 크기가 다르기 때문에 키 값이 작을 때 효과적이다.
  키 값이 골고루 분포되지 않으면 메모리 낭비가 심할 수 있다.

위 한계점의 방안으로 해시 테이블을 사용할 수 있다.

해시 테이블

해시 함수를 사용하여 변환한 값을 index로 key, value를 저장하는 자료 구조

해시 함수

key를 넣었을 때 원하는 범위의 자연수를 리턴해주는 함수


해시 함수의 조건

1. 결정론적이어야 한다.
   똑같은 key를 넣었을 때는 항상 같은 결과가 나와야 한다.

2. 원하는 범위의 자연수 하나하나가 리턴될 확률이 최대한 비슷해야 한다.
   결과 해시값이 치우치치 않고 고르가 나와야 한다.

3. 빨리 계산을 할 수 있어야 한다.
   해시 테이블은 모든 연산을 할 때마다 해시 함수를 써야하기 때문에

키 값이 다르지만 해시 결과값이 같으면 충돌(Collision)이 일어나기 때문에 이를 완화하기 위해 해시 테이블의 구조를 개선하는 2가지 방법이 있다.

Chaining

key, value를 저장하는 Linked List를 사용하는 것으로 충돌이 일어날 경우 이전에 저장된 데이터에 새로운 데이터를 연결하도록 구조를 Linked List로 설계하여 사용하는 방법이다.

Chaining 시간 복잡도

연산	시간 복잡도	평균 시간 복잡도
탐색	O(n)	O(1)
삽입/저장	O(n)	O(1)
삭제	O(n)	O(1)

Open Addressing

동일한 주소에 데이터가 존재하는 경우 다른 주소를 사용하여 key, value를 저장하는 방법
다른 주소로의 처리 방법은 선형 탐사(Linear Probing)와 제곱 탐사(Quadratic Probing) 등이 있다.

Open Addressing 시간 복잡도

연산	시간 복잡도	평균 시간 복잡도
탐색	O(n)	O(1)
삽입/저장	O(n)	O(1)
삭제	O(n)	O(1)