[Data] 자료 구조란?(3) : key - value 데이터, Direct Access Table, 해시 테이블, Chainig, Open Addressing

 

 

💡 key - value 데이터 : 순서가 아닌 key 나 value 를 이용해 정보를 검색한다.

• key - value 쌍 : key 와 그 key 에 해당하는 value 를 합쳐 부른다.
• 하나의 key 에는 하나의 value 만 있어야 한다.

 

Direct Access Table : key 를 배열의 인덱스처럼 활용해 데이터를 구성한 것

• key(이 땐 인덱스와 같다.)를 이용한 value 접근 시간 복잡도 : O(1)
• 하지만 공간을 너무 낭비할 수 있다.(key 가 1, 3, 5, 7, 9 일 때 필요한 공간은 5이지만 1~9 까지의 공간을 차지해버림)

 

해시 함수 : 특정 값을 원하는 범위의 자연수로 바꿔주는 함수

• 101, 204, 302, 711, 943 ➡️ (0 ~100 사이 자연수로 바꿔주는 함수) ➡️ 20, 30, 90, 5, 80
• 같은 key 를 넣으면 항상 같은 값이 나온다.
• 빨라야 한다.

 

Hash Table : 해시 함수와 배열을 같이 사용하는 자료 구조

• 고정된 크기의 배열을 만든다.
• key 를 바로 사용하지 않고 해시 함수에 넣어 반환된 값을 인덱스로 사용한다.
• 711 : '김현승' ➡️ 해시 함수 ➡️ 30(인덱스)에 key 와 value 모두(쌍) 저장

 

Chainig : 해시 테이블 충돌 Collision 처리 방법(인덱스가 같을 때)

• 배열 인덱스에 링크드 리스트 저장해서 충돌 해결

해시 테이블 탐색 연산 : 해시 테이블은 데이터를 순서대로 저장하지 않으니 접근이 아니라 탐색 연산을 한다.

• 원하는 key 에 해당하는 value 를 찾는 연산
• 해시 함수를 통해 받은 인덱스에 접근해 원하는 key 를 찾을 때까지 링크드 리스트를 탐색한다.

탐색 연산 각 단계들	시간 복잡도
해시 함수 계산	O(1)
배열 인덱스 접근	O(1)
링크드 리스트 노드 탐색	O(n) 최악의 경우
총 합	O(n)

 

해시 테이블 삽입 연산 : 해시 테이블에 key - value 쌍을 저장 또는 수정

• 해시 함수로 받은 인덱스에 접근해 링크드 리스트에 저장하려는 key 가 이미 있는지 확인한다. 있다면 덮어쓰고 아니라면 새로 저장

삽입 연산 각 단계들	시간 복잡도
해시 함수 계산	O(1)
배열 인덱스 접근	O(1)
링크드 리스트 노드 탐색	O(n) 최악의 경우
링크드 리스트 저장 / 노드 수정	O(1)
총 합	O(n)

 

해시 테이블 삭제 연산 : 해시 테이블에서 원하는 key 에 대한 key - value 쌍을 삭제

• 해시 함수로 받은 인덱스에 접근해 링크드 리스트에 삭제하려는 key 를 찾아 삭제

삭제 연산 각 단계들	시간 복잡도
해시 함수 계산	O(1)
배열 인덱스 접근	O(1)
링크드 리스트 노드 탐색	O(n) 최악의 경우
링크드 리스트 노드 삭제	O(1)
총 합	O(n)

 

🥸 여기서 세 연산 모두 O(n) 이 걸린다 했지만, 사실 key -value 쌍이 하나의 인덱스에 저장되는 일이 일어나긴 쉽지 않다.

그러므로, 최악의 경우엔 O(n) 이 걸리지만, 평균적으로는 O(1) 이 걸린다고 말할 수 있다.

 

Open Addressing 삽입 연산 : 충돌 시 다른 비어있는 인덱스에 데이터를 저장(삽입)하는 방식

• 선형 탐사 Linear Probing : 충돌 시 한 칸씩 다음 인덱스가 비었는지 확인
• 제곱 탐사 Quadratic Probing : 충돌 시 제곱한 값만큼 이동해 인덱스가 비었는지 확인

 

Open Addressing 탐색 연산

• 선형 탐사로 확인
• 차례대로 찾다가 빈 인덱스가 나오면 데이터가 저장되지 않았다고 인식하고 탐색 종료

 

Open Addressing 삭제 연산

• 선형 탐사로 확인
• 삭제하려는 데이터를 찾으면 비우지 않고 'DELETED' 를 넣어 삭제된 값이라는 것을 표시(빈 값이 나와 탐색을 종료할 경우를 방지)

연산	최악의 경우 시간 복잡도	평균 시간 복잡도
삽입	O(n)	O(1)
탐색	O(n)	O(1)
삭제	O(n)	O(1)