해쉬테이블(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
을 사용하기 때문에 배열의 각 슬롯에연결 리스트
를 두어 충돌을 해결한다.