해쉬테이블(with JAVA HashMap)

• 해쉬 테이블은 일반적으로 배열이다.
• h(key)의 결과를 index로 갖는다.
• 이 배열(해쉬 테이블)에 어떤 key:value를 저장하고 싶다면 h(key)의 결과를 인덱스로 활용하여 저장한다.
  • 만일 key:value가 msg:hello라면 T[h(msg)] = hello와 같이 저장되는 것.
  • KEY의 해쉬값이 배열의 인덱스가 된다는 점을 기억하자.

충돌

해슁에서 충돌은 피할 수 없는 문제이다. 데이터를 저장하는 해쉬 테이블의 크기가 한정되어 있기 때문에 해쉬 함수의 결과(해쉬값)은 중복 될 수 있다.

이를테면 h(hello) = 12, h(hi) = 12와 같은 상황이 발생할 수 있다.

이에 따라 T[12]에는 충돌이 생겨버린다.

충돌이 생길 수 밖에 없는 문제라면 대처 방법은 무엇일까. 체이닝과 오픈 어드레싱이 존재한다.

Chaning

체이닝은 이름 그대로 해쉬 테이블과 함께 연결 리스트를 사용하는 방법이다.

즉, 동일한 장소로 해슁되어 충돌된 모든 키들을 하나의 연결 리스트로 저장한다.

• KEY 삽입(INSERT)
  • key를 연결리스트 T[h(key)]에 삽입 시 : O(1)
  • 중복 키 저장을 허용하지 않는다면 삽입 시 리스트를 검색해야 하므로 시간복잡도는 리스트의 길이에 비례
• KEY 검색(SELECT)
  • 연결 리스트 T[h(key)]에서 순차 탐색해야 하므로 시간복잡도는 리스트 길이에 비례
• 키의 삭제(Delete)
  • 연결 리스트 T[h(key)]로부터 키를 검색 후 삭제
  • 검색을 하는데 걸리는 시간복잡도 + 삭제 시간복잡도는 O(1)

체이닝을 이용한 충돌 해결 방법에서 최악의 경우는 모든 키가 하나의 슬롯으로 해슁되는 경우이다.

이 때 길이가 n인 하나의 연결리스트가 만들어 지고 이 때의 탐색 시간 복잡도는 O(N)이다.

Open Addressing

체이닝이 각 슬롯에 연결 리스트를 사용해서 충돌된 KEY들을 저장하는 방식이라면 Open Addressing은 해쉬테이블 자체에 저장한다. 그렇다면 충돌은 어떻게 해결할까?

기본적으로 해슁된 결과를 이용해 슬롯에 저장한 후, 충돌이 발생하면 그 다음 슬롯(+1) 순서로 검사하여 처음으로 빈 슬롯에 저장한다.

좋은 해쉬 함수

해슁에 있어 중요하게 고려해야 하는 부분은 key를 저장할 위치를 적절하게 계산해주는 해쉬 함수이다.

해쉬 함수를 어떻게 구현하느냐에 따라 해슁의 성능이 결정된다

즉, key들이 해쉬 테이블에 골고루 분포되어 있는 정도가 성능에 영향을 미친다.

Hashing in java

Java의 Object 클래스는 hashCode() 메서드를 갖는다. 따라서 모든 클래스는 hashCode() 메서드를 상속받는다.

• 만일 x.equals(y)라면 x.hashCode() == y.hashCode()가 성립한다. 역은 성립하지 않는다.
• Object 클래스의 hashCode() 메서드는 객체의 메모리 주소를 반환하는 것으로 알려져 있다.
• 필요에 따라서 각 클래스마다 hashCode() 메서드를 오버라이딩 해서 사용한다.
  

HashMap in Java

자바에서 HashMap은 HashTable, hashCode(), load factor, chaining으로 요약된다.

• HashTable : 자바에서 HashMap은 HashTable 즉 하나의 배열을 해쉬 테이블로 사용한다.
• hashCode() : HashMap은 key.hashCode() 메서드를 이용한다.
• chaining : 내부적으로 충돌 해결을 위해 chaining을 사용하기 때문에 배열의 각 슬롯에 연결 리스트를 두어 충돌을 해결한다.