알고리즘 해시법
해시법은 검색과 더불어 데이터의 추가와 삭제도 효율적으로 수행할 수 있는 방법이다.
해시법
해시법(hashing) 은 데이터를 저장할 위치(인덱스)를 간단한 연산으로 구하는 것으로, 검색뿐만 아니라 추가, 삭제도 효율적으로 수행할 수 있다.
배열의 키 값을(각 요소의 값)을 배열의 요솟수로 나눈 나머지가 해시 값(hash value) 이며, 이 해시 값은 데이터에 접근할 때 사용한다.
해시 값이 인덱스가 되도록 원래의 키 값을 저장한 배열이 해시 테이블(hash table) 이다.
키 값을 가지고 해시 값을 만드는 과정을 해시 함수(hash function)라고 한다.
보통은 나머지를 구하는 연산 또는 이런 나머지 연산을 다시 응용한 연산을 사용한다.
해시 테이블의 각 요소를 버킷(bucket)이라고 한다.
충돌
키 값과 해시 값의 대응 관계가 반드시 1개1이라는 보증은 없다(보통을 n대1). 저장할 버킷이 중복되는 현상을 충돌(collision)이라고 한다. 해시 함수는 가능하면 해시 값이 치우치지 않도록 고르게 분포된 값을 만들어야 한다.
충돌에 대한 대처
- 체인법 : 같은 해시 값을 갖는 요소를 연결 리스트로 관리한다.
- 오픈 주소법 : 빈 버킷을 찾을 때까지 해시를 반복한다.
체인법
체인법(chaining) 은 같은 해시 값을 갖는 데이터를 chain 모양으로 연결 리스트에서 연결하는 방법으로, 오픈 해시법(open hashing) 이라고도 한다.
배열의 각 버킷(해시 테이블)에 저장하는 값은 그 인덱스를 해시 값으로 하는 연결 리스트의 첫 번째 노드(node)에 대한 참조이다.
버킷용 클래스 Node<K, V>
개별 버킷을 나타낸 것이 클래스 Node<K, V>이다.
- key : 키 값(자료형 K는 임의의 자료형)
- data : 데이터(자료형 V는 임의의 자료형)
- next : 체인의 다음 노드에 대한 참조
해시 클래스 ChainHash<K, V> 필드
- size : 해시 테이블의 크기(table(배열)의 요솟수)
- table : 해시 테이블을 저장하는 배열
생성자 ChainHash
클래스 ChainHash<K, V>의 생성자는 비어 있는 해시 테이블을 생성하며, 매개변수 capacity에 전달받는 것은 해시 테이블의 용량이다.
요솟수가 capacity인 배열 table의 본체를 생성하고 capacity 값을 필드 size에 복사한다.
생성자가 호출된 직후 배열 table의 모든 요소는 널(null)을 참조하며, 모든 버킷이 비어 있는 상태가 된다(메모리 확보에 실패하면 필드 size에 0을 넣는다).
hashValue 메서드
해시 값을 구하는 메서드.
key의 해시 값을 해시 테이블의 크기 size로 나눈 나머지를 반환한다.
검색 과정
- 해시 함수가 키 값을 해시 값으로 변환한다.
- 해시 값을 인덱스로 하는 버킷을 선택한다.
- 선택한 버킷의 연결 리스트를 처음부터 순서대로 검색한다. 키 값과 같은 값을 찾으면 검색 성공. 끝까지 스캔하여 찾지 못하면 검색 실패.
요소 추가 과정
- 해시 함수가 키 값을 해시 값으로 변환한다.
- 해시 값을 인덱스로 하는 버킷을 선택한다.
- 버킷이 가리키는 연결 리스트를 처음부터 순서대로 검색한다. 키 값과 같은 값을 찾으면 키 값이 이미 등록된 상태이므로 추가에 실패한다. 끝까지 스캔하여 찾지 못하면 리스트의 맨 앞 위치에 노드를 삽입한다.
요소 삭제 과정
- 해시 함수가 키 값을 해시 값으로 변환한다.
- 해시 값을 인덱스로 하는 버킷을 선택한다.
- 버킷이 가리키는 연결 리스트를 처음부터 순서대로 검색한다. 키 값과 같은 값을 찾으면 그 노드를 리스트에서 삭제한다. 그렇지 않으면 실패한다.
오픈 주소법
오픈 주소법(open addressing) 은 충돌이 발생했을 때 재해시(rehashing)를 수행하여 비어 있는 버킷을 찾아내는 방법으로, 닫히 해시법(closed hashing)이라고도 한다.
빈 버킷을 만날 때까지 재해시를 여러 번 반복하므로 선형 탐사법이라고도 한다.
요소 삭제
버킷의 데이터를 비우면 같은 해시 값을 갖는 값을 검색할 때 존재하지 않는다고 생각하여 검색에 실패하기 때문에 비우면 안된다.
- 데이터 저장 속성값
- 비어 있음 속성값(-) : 같은 해시 값의 데이터가 존재하지 않는다.
- 삭제 마침 속성값(*) : 같은 해시 값의 데이터가 다른 버킷에 저장되어 있다.
요소 검색
삭제 마침인 경우 재해시를 수행하여 버킷을 재검색한다.