[Java] Hash, HashMap

Hash의 개요

설명에 앞서 배열은 인덱스를 이용하여 자료의 검색이 한 번에 이루어지기 때문에 빠른 검색 속도를 가지는 장점이 있지만, data의 추가/삭제에 있어서는 데이터가 이동해야 하기 때문에 많은 시간이 소요된다.

 

연결리스트는 데이터의 추가/삭제시 노드의 참조값만 수정해 줌으로써 빠른 처리가 가능하다. 그러나 데이터를 검색할 때는 해당 노드를 찾기 위하여 일일이 탐색을 해야하기 때문에 데이터의 수가 많아질수록 효율이 떨어지는 구조이다.

 

이러한 한계를 극복하기 위하여 제시된 방법이 바로 Hash이다.

 

 

Hash의 기본 개념

Hash는 내부적으로 배열을 사용하기 때문에 배열의 장점인 빠른 검색 속도를 갖는다. 또한 데이터의 추가/삭제시 이루어지는 비효율적인 이동을 극복할 수 있도록 특별한 알고리즘을 이용하여 데이터는 자신만의 고유한 인덱스를 사용한다.

 

특정 데이터가 저장되는 인덱스는 그 데이터만의 고유한 위치이기 때문에 추가/삭제시 다른 데이터의 사이에 끼어들거나 이동할 필요가 없으므로 배열의 단점을 극복할 수 있게 만들어진 구조이다.

 

Hash가 내부적으로 사용하는 배열을 Hash Table이라고 하며, 그 크기에 따라서 성능 차이가 날 수 있다.

 

 

Hash Method

Hash는 Hash Table에 데이터를 저장한다. 이때 특별한 알고리즘을 이용하여 데이터의 고유한 인덱스를 만드는데, 이 알고리즘을 구현한 메서드를 Hash Method라고 하며 Hash Method에 의해 반환된 고유한 인덱스를 Hash Code라고 한다.

 

Java에서는 Object 클래스의 hashCode() 라는 메서드를 이용하여 모든 객체의 Hash Code를 쉽게 구할 수 있다.

 

Hash Method를 구현하는 방법은 여러가지가 있지만 가장 간단한 방법으로는 나머지 연산자를 이용하는 것이다. 데이터의 고유한 Hash Code를 구한 뒤 Hash Code를 테이블의 크기로 나머지 연산을 한 결과를 해당 데이터의 인덱스로 사용하는 것이다.

 

그러나 Hash Code가 다르더라도 나머지 연산을 한 결과는 같을 수 있으므로 Hash Table의 동일한 인덱스에 저장을 시도하려 하는 경우 문제가 발생한다.

 

이렇게 저장하려는 위치에 이미 다른 데이터가 있어서 저장을 할 수 없는 현상을 충돌(collision)이라고 하며, 이런 충돌을 최소화 하기 위한 방법으로는 나머지 연산의 값이 최대한 중복되지 않도록 테이블의 크기를 소수(prime number)로 만드는 것이다.

 

그럼에도 충돌이 발생한 경우 이를 해결하기 위한 방법이 필요했고 개방주소법과 분리연결법 두 가지가 있다.

 

 

충돌 해결 방법 : 분리연결법

분리연결법은 Hash Table에 연결리스트에서 사용하는 Node 객체를 저장하는 것이다. 즉 Hash Table의 셀마다 연결 리스트를 하나씩 저장하도록 하고 충돌이 발생하는 데이터는 연결리스트의 다음 노드로 계속 추가하는 것이다.

 

이후에 데이터를 검색할 때에는 Hash Table의 인덱스를 찾은 후 셀에 연결된 리스트를 순차적으로 탐색하며 찾으려는 hashCode와 저장된 노드의 hashCode를 비교하는 것이다.

 

 

 

Java의 HashMap

 

Java에서 제공하는 Map 인터페이스는 키(key)와 값(value)을 묶어서 하나의 데이터로 저장하는 구조이다. Set 구조와 달리 중복을 허용하는 특징이 있다.

 

키key)의 경우에는 유일해야 하지만 값(value)은 데이터의 중복을 허용한다.

 

HashMap은 내부적으로 Hashing을 이용해서 구현한 컬렉션이기 때문에 많은 양의 데이터를 검색하는데 있어 뛰어난 성능을 보인다. 

HashTable 또한 Map 인터페이스를 구현한 구조이지만, 1.2 버전 이후부터 HashMap이 나오면서 HashTable에 비해 다양한 함수를 제공하는 HashMap으로 대체되었다. 

 

또 다른 차이로는 HashTable은 null 값을 허용하지 않지만 HashMap은 null 값을 허용한다.

 

 

 

Java의 HashMap Method

 

Method	Description
void clear()	HashMap에 저장된 모든 객체를 제거
Set entrySet()	HashMap에 저장된 키와 값을 결합된 형태로 저장 후 반환
Object get(key)	지정된 키의 객체를 반환
Set keySet()	HashMap에 저장된 모든 Key의 Set을 반환
Object put(key, value)	지정된 키와 값을 HashMap에 저장
Object remove(key)	HashMap에 지정된 키로 저장된 값을 제거
int size()	HashMap에 저장된 요소의 개수를 반환
Collection values()	HashMap에 저장된 모든 값을 컬렉션의 형태로 반환

 

 

 

참고

HashMap API 문서에 따르면, HashMap은 해당 map의 순서를 보장하지 않는다고 명시되어 있다.

하지만, LinkedHashMap 클래스를 사용하면 삽입된 순서대로 반복문을 수행하도록 할 수 있다.

 

출처

• https://hyeonstorage.tistory.com/265 [개발이 하고 싶어요]
• https://swalloow.tistory.com/40?category=667489 [MyCloud]