Life and IT

먼저 해시 함수가 가져야 할 특징 3가지가 있다. 충돌이 적어야 한다. 해시 테이블에 고르게 분포시킬 수 있는 주소의 연산 값이 나와야 한다. 이는 곧 1번을 충족할 수 있다. 계산이 빨라야 한다. 위 3가지를 고루 갖추지 못한다면 100개의 버킷 중에 하나의 버킷만 나와서 오버플로우가 발생하는 참사가 일어날 수 있다. 위의 특징을 고루 갖춘 함수 중 하나로 제산 함수라는 것이 있다. 제산 함수 레코드(키) 값을 소수로 나누어 나머지 값을 주소로 지정하는 해시 함수. ex) h(k) = k % 7 만약 위 특징을 갖춘 해시 함수를 만들었는데도 오버플로우가 발생한다면? 내가 아는 선에서 두 가지의 방법이 있다. 선형 탐사법 (Linear Probing) 분리 연결법 (Separate Chaining) 1...

해시 테이블이란? 어떤 특정 값을 받으면 그 값을 해시 함수에 통과시켜 나온 리턴 값을 인덱스에 저장하는 자료구조이다. 그렇다면 왜 해시 테이블을 사용할까? 직접 주소 테이블 (Direct Address Table) 해시 테이블은 직접 주소 테이블이라는 자료구조에서부터 출발한다. 직접 주소 테이블은 입력받은 value가 곧 key가 되는 데이터 매핑 방식이다. 내가 소수 찾기 알고리즘을 풀 때 소수만 남기기 위해서 0~n까지의 배열을 만들었는데 바로 그 방식인 것이다. index 0 1 2 3 4 5 6 7 8 value 0 1 2 3 4 5 6 7 8 찾고자 하는 값과 테이블의 인덱스가 동일하므로 값이 저장된 공간에 바로 접근해서 값을 가져올 수 있으므로 시간 복잡도는 O(1)이다. 마찬가지로 테이블에..