[자료구조]기본4_해시테이블

 

Key-value데이터

순서와 상관없이,  key값을 검색하여 그 값을 찾도록 하는 자료구조

 

배열의 장점은 key(인덱스)를 이용해 O(n)으로 배열에 접근할 수 있다는것

 

Direct Access Table : 배열 인덱스를 key로 저장해서 값을 가져오는것 

장점 : O(1)으로 빠르게 접근해서 데이터를 주고받고 할 수 있다

단점 : 인덱스를 key로 지정해서 배열화 하면 너무 큰 메모리를 낭비할 수 있다 

 

해시테이블

- 고정된 크기의 배열을 만들고

- 해시함수 이용하여 key를 원하는 범위의 자연수로 바꾼다

- 해시함수 결과 값 인덱스에 key-value값을 저장한다

 

 

해시테이블의 충돌 해시함수를 통해 key값을 받았는데, 다른 key값과 동일해서, 배열에서 충돌함 한 인덱스에서 충동했을때에는 chaining or openaddressing으로 충돌을 해결해야만 한다.

 

1. chaining

특정인덱스에서 key값이 충돌난 경우, 이 인덱스에서 링크드리스트로 계속 엮어서 추가해주는것

그럼 특정인덱스에도 많은 key-value값을 저장해나갈 수 있다. 

   

chaining을 쓰는 해시테이블의 시간복잡도

탐색연산O(n) : 해시함수계산O(1) + 배열인덱스 접근O(1) + 링크드리스트탐색 O(n)

삽입연산O(n) : 해시함수계산O(1) + 배열인덱스 접근O(1) + 링크드리스트탐색 O(n) + 링크드리스트저장/노드수정 O(1) 

삭제연산O(n) : 해시함수계산O(1) + 배열인덱스 접근O(1) + 링크드리스트탐색 O(n) + 링크드리스트삭제 O(1) 

 

but, 위의 경우는 하나의 모든인덱스가 하나의 링크드리스트에 저장되어있다고 가정했을때이다.

하지만 이럴일이 없으므로, 이렇게 시간복잡도를 생각하는건 불합리함.

 

그래서 나왔다. 해시테이블 평균시간복잡도!

배열에 저장되어있는 링크드리스트의 길이를 average_length로 계산하기!

O(n) -> O(average_length)

average_length = key-value의 쌍 수 / 인덱스 수

탐색연산O(1)

삽입연산O(1)

삭제연산O(1)

 

“해시 테이블 삽입, 삭제, 탐색 연산들은 최악의 경우 O(n)이 걸리지만, 평균적으로는 O(1)이 걸린다”

 

 

 

2. open addressing

특정인덱스에서 key값이 충돌난 경우, 다음 인덱스가 비어있는지 확인

 

open addressing 삽입 O(n)

선형탐사-linear probing / cf-제곱탐사quadratic probing

 

open addressing 탐색 O(n)

해시함수계산 -> 선형탐색

주의 : 탐색하다가 빈 인덱스가 나오면, 탐색을 멈춘다.

(빈 인덱스가 나온다 = 삭제 했을때 진짜 삭제만 한 경우면 곤란.. / 원래 비었던 인덱스면 저장하면 끝!)

 

open addressing 삭제 O(n)

해시함수계산 -> 선형탐색

삭제만! 하면 다음 탐색때 오류가 있을 수 있으므로, "DELETED - 있었는데 지금은 없어요" 표시를 해준다