해시

해시

해시법

데이터를 저장할 위치(인덱스)를 간단한 연산으로 구하는 것으로 검색, 추가, 삭제를 효율적으로 수행할 수 있다.

해시값을 인덱스가 되도록 하는 것이 일반적이며 해시값으로는 보통 나머지를 구하는 연산 또는 나머지 연산을 응용한 방식을 이용한다.

• 해시 테이블: 해시값이 인덱스가 되도록 키 값을 저장한 배열
• 버킷: 해시 테이블의 각 요소

충돌

해시값을 13으로 나눈 나머지라 하면 18은 5에 삽입하게 된다. 하지만 이미 5라는 키값이 5에 삽입되어 있는 경우 중복되기 때문에 이렇게 버킷이 중복되는 것을 충돌이라고 한다.

따라서 해시함수는 가능하면 해시값이 치우치지 않도록 고르게 분포된 값을 만들어야 한다.

• 충돌에 대한 대처
  • 체인법
  • 오픈주소법

체인법

같은 해시 값을 갖는 데이터를 쇠사슬 모양으로 연결 리스트에서 연결하는 방법으로 오픈 해시법 이라고도 한다.

• 버킷 클래스 Node<K,V> : key, data, next
• 해시클래스 ChainHash<K,V>: size, table

위의 예시로 들면 index 5, 즉 버킷 5에 저장하는 값은 18을 참조하게 되고 18은 그 다음 키값인 5 Node를 참조하게 되는 것이다.

오픈주소법

충돌이 발생했을 때 재해시를 수행하여 비어 있는 버킷을 찾아내는 방법으로 닫힌 해시법이라고도 한다.

예시로 재해시할 경우 키값에 1을 더한 값을 13으로 나눈 나머지를 해시값으로 할 수 있다.