[Java] Hashing
JavaHashing
해시 함수를 이용하여 데이터를 해시 테이블에 저장하고 검색하는 데이터 관리 기법.
해시 함수 Hash Funcion
넘겨 받은 데이터에 대해 고유한 숫자값을 만드는 알고리즘을 구현한 메서드.
반환값을 해시값, 해시 코드, 또는 간단하게 해시라고 한다.
간단히 말하자면 데이터를 키로 변환한다.
- 암호화
해시를 분석했을 때 해시 함수를 알아낼 수 없도록 해야 한다.
- 충돌 위험성 최소화
서로 다른 데이터에 대해 동일한 해시를 만들지 않도록 해야 한다.
해시 Hash
특정 데이터가 저장되는 고유한 위치(Index) → 추가/삭제 시 데이터의 이동이 없다.
내부적으로 배열(Hash Table)을 이용하여 데이터를 저장 → 검색 속도가 빠르다.
데이터가 저장되어 있는 곳을 알려 준다.
해시 테이블 Hash Table(Hash Map)
해시 함수가 해시를 생성할 때 참조하는 배열.
충돌 Collision
저장하려는 해시 == 기존 해시
데이터를 저장할 때 해시 테이블에 이미 다른 데이터가 있을 경우 → 데이터 저장 불가능
해결 방법으로 개방 주소법과 분리 연결법이 있다.
- 개방 주소법 Open Addressing
배열만을 사용한다.
버킷(bucket, 저장 공간)이 겹치면 다른 버킷에 데이터를 저장한다.
이때 다른 버킷과도 겹치면 버킷이 겹치지 않을 때까지 옆으로 계속 이동해야 하기 때문에
충돌이 많이 일어날 경우 심각한 성능 저하가 발생할 수 있다.
- 선형 탐색 Linear Probing : 비어있는 버킷을 찾을 때까지 순차적으로 탐색한다
- 제곱 탐색 Quadratic Probing : 제곱만큼 건너뛴 버킷에 데이터를 저장한다.
- 이중 해시 Double Hashing Probing: 해시 충돌 시 다른 해시 함수를 이용해 새로운 해시를 할당 받는다.
- 분리 연결법 Seperate Chaining
배열과 LinkedList를 조합하여 사용한다.
해시 테이블의 버킷마다 LinkedList를 하나씩 저장하여 충돌이 발생한 데이터는 Node로 추가한다.
데이터 검색 시 해시 테이블의 index를 찾은 후
셀에 연결된 LinkedList를 순차적으로 탐색하여 찾으려는 해시와 저장된 Node의 해시를 비교한다.
해싱 알고리즘 Hashing Algorithm
중복된 해시코드를 반환하는 경우를 최소화시킨다.
HashMap과 같이 해싱을 구현한 컬렉션 클래스에서는
Object 클래스에 정의된 hashCode()가 객체의 주소를 이용하는 알고리즘으로 해시코드를 만들어내기 때문에
모든 객체에 대해 hashCode()를 호출한 결과가 서로 겹치지 않는다.
단, String 클래스의 경우 hashCode()를 오버라이딩 했기 때문에 같은 내용의 문자열은 같은 해시코드를 얻는다.
- 완전 해싱 Perfect Hashing
서로 다른 키값이 해싱에 의해 주소값(해시)을 할당 받을 때, 해시가 절대로 겹치지 않는다.
일대일 대응 이외에는 존재하지 않는 방식.
- 정형 해싱 Conventional Hashing
데이터를 저장할 배열의 크기를 미리 지정해두는 방식.
필요한 만큼의 메모리를 미리 측정하여 할당 받아 둔다.
메모리의 범위를 넘어설 경우 다시 메모리 크기를 잡고 해싱해야 하는 단점이 있다.
- 동적 해싱 Dynamic Hashing
동적으로 메모리의 크기를 변화시킨다.
참고 서적: 자바의 정석 3판 2
