[Code Tree] 해싱

해시 함수 

:임의의 데이터를 받아, 해당 데이터를 고정된 길이의 특정 값으로 반환하는 함수

 

- 어떤 값을 넣더라도 특정 범위에 해당하는 값을 반환

- 삽입, 삭제, 검색의 시간복잡도: O(1)

 

* 배열 내 값의 갯수가 불분명하기 때문에, 해시 함수에서 배열 타입은 다루지 않는다. 

 

해싱

: 특정 데이터가 들어온 순서 상관 없이 삽입, 삭제, 검색이 자주 발생하는 경우 사용하기 좋음

 

배열 대신 해싱을 항상 사용하는 것이 좋을까?

- NO. 배열은 index기반으로 담고 있는 데이터 간의 순서가 확실하다!

- 순서 상관 없이 데이터가 자주 들어오고 나가는 경우 해싱을 사용한다. 

 

 

해시 충돌

: 연결리스트를 사용한다. 

- 삽입, 삭제, 탐색의 경우, 연결리스트를 순회해야 하므로 O(N)의 시간복잡도를 갖는다. 

 

* 해시 함수를 적절하게 설정하여 충돌이 최대한 덜 일어나게 해야 한다. 

(각 프로그래밍 언어마다 이미 구현되어있는 해시 함수는 이러한 조건을 만족하고 있다고 가정해도 좋다.)

 

* 충돌 자체를 최대한 줄이기 위해, 보통 실제로 들어갈 데이터보다 몇 배 정도 더 크게 배열을 정의한다. 

 

해시 테이블

: 값이 저장되는 배열

- 일반적으로 최대 데이터의 3~4배 정도의 크기로 설정