Direct Access Table / 해쉬 테이블(Hash Table)

★KEYWORD★
📢 Direct Access Table : key를 바탕으로 배열의 인덱스에 데이터를 저장 / 각 key에 해당하는 value를 알고 싶으면 해당 인덱스에 접근하면 됨

📢 해시 테이블 (Hash Table) : 해시 함수와 배열을 같이 사용하는 자료구조 / 기본연산으로는 탐색(Search), 삽입(Insert), 삭제(Delete)가 있음 / 평균적으로 O(1)의 시간 복잡도를 가짐

Direct Access Table

배열에서 인덱스를 순서가 아니라 key라고 생각하고 key-value쌍을 저장하는 방식이다.

key를 바탕으로 배열의 인덱스에 데이터를 저장한다.

 

Ex)

• '27'키는 배열의 27번 인덱스에 저장
• '100'키는 배열의 100번 인덱스에 저장
• '999'키는 배열의 999번 인덱스에 저장

➡️ 각 key에 해당하는 value를 알고 싶으면 해당 인덱스에 접근하면 된다.

 

👍 장점

배열의 인덱스에 O(1)로 바로 접근할 수 있음

: 🔎 Big O(1), 즉 상수 시간 복잡도는 어떤 데이터의 크기와 관계없이 항상 일정한 시간이 걸리는 알고리즘을 나타냄. 한 번의 연산으로 결과를 도출할 수 있다는 의미

 

👎 단점

공간을 많이 낭비함 (저장하지 않은 나머지 인덱스를 낭비함)

---

해시 테이블 (Hash Table)

Direct Access Table의 개념을 확장하면서도 그 단점을 극복하기 위해 개발되었다.

검색하고자 하는 키값을 입력받아서 해쉬 함수를 통해 얻은 해시를 배열의 인덱스로 환산해서 데이터에 접근한다.

➡️ 해시함수를 사용하여 변환한 값을 색인(index)으로 삼아 키(key)와 데이터(value)를 저장하는 자료구조이다. (해시 함수와 배열을 같이 사용)

 

기본연산으로는 탐색(Search), 삽입(Insert), 삭제(Delete)가 있다.

평균적으로 O(1)의 시간 복잡도를 가진다.

 

모든 데이터에 key값은 무조건 존재해야 하고, 중복되는 key값이 있어서는 안된다.

---

해시 함수

• 해시 함수는 특정 값을 원하는 범위의 자연수로 바꿔주는 함수이다.
• 해시 함수에 아무 숫자를 넣었을 때 원하는 범위의 자연수가 나와야 한다.

 

💡 조건

1. 한 해시 테이블의 해시 함수는 결정론적이어야 한다 : 같은 key을 입력값으로 넣었을 때는 항상 같은 결과가 나와야 한다.
2. 결과 해시값이 치우치지 않고 고르게 나와야 한다 : 따라서 원하는 범위가 0 ~ 100 사이의 자연수라면 아무 숫자를 넣었을 때 결과가 0 ~ 100 사이에서 최대한 고르게 나와야 한다.
3. 빨리 계산할 수 있어야 한다 : 해시 테이블에서 모든 연산에 해시 함수가 사용되므로 최대한 효율적인 해시 함수를 사용해야 한다.

---

해싱 (Hashing)

임의의 길이의 값을 해시함수(Hash Function)를 사용하여 고정된 크기의 값으로 변환하는 작업

---

해시충돌(Hash Collision)

어떤 entry를 넣으려고 할때, Hash Function으로 찾은 위치에 이미 다른 entry가 존재하는 경우 발생한다.

즉, 다른 키 값일때, Hash Function을 통해 같은 값을 가지게 되는 경우 해시 충돌이 발생한다.

 

 

✅ 해결방법

1️⃣ 체이닝(Chaining)

• 같은 주소로 해싱 될 때, 연결 리스트(Linked List)로 연결하는 방식
• 추가 공간 활용

 

2️⃣ 개방 주소법(Open Addressing)

• 추가 공간을 활용하지 않고 충돌을 해결하는 방법

- 선형 탐색 (Linear Probing)

• 충돌이 일어났을 때, 충돌 주소의 바로 다음 위치에 저장하는 방식
• 빈 bucket이 있을 때 까지 다음 위치를 탐색

- 제곱 탐색 (Quadratic Probing)

• 충돌이 일어났을 때, 충돌 주소의 제곱만큼 건너뛴 위치에 저장하는 방식

 - 이중 해시 (Double Hashing)

• 충돌이 일어났을 때, 다른 해시함수를 한번 더 적용한 위치에 저장하는 방식

 

	체이닝	개방주소법
추가공간	필요	필요X
구현	연결리스트	새로운 위치를 나타내기 위한 구현이 조금 더 복잡 (해시함수, 제곱, 선형방식...)
오버헤드	해시테이블이 채워질 수록, Lookup 성능저하가 Linear하게 발생	삽입/삭제 시 오버헤드가 적다 저장할 데이터가 적을 때 더 유리

 

 

 

출처 및 참고 : nayu1105.log, https://zeus2141.tistory.com/94