[알고리즘] 해싱(Hashing) - 1
해싱(Hashing) - 1 해쉬 테이블은 다이나믹 셋을 구현하는 또 다른 방법이다.일반적으로 해쉬 테이블은 탐색, 삽입, 제거 3가지 연산들의 시간 복잡도에 대해 애매한 부분이 있으나적절한 가정하에서 평균적으로 O(1)의 복잡도를 가진다. 보통 최악의 경우에서는 O(n)이 된다.(해싱을 사용하는 경우 정확한 복잡도를 계산하기 어려우므로 가정하게된다.) 해쉬 테이블은 해쉬 함수라는 특별한 함수를 통해 어떤곳에 저장할것인지 지정하는것을 말한다.해쉬테이블은 큰 배열이라고 생각하면된다.위의 그림은 0번지부터 m-1 번째까지, m개의 슬롯을 가지고 있는 해쉬 테이블이다. h : U -> {0,1,2,3,4,5,6... m-1} 라고 할 때 U는 모든 가능한 키들의 집합을 말하며, m은 테이블의 크기를 뜻한다.이..
2017. 5. 9.
