본문 바로가기

Computer Science/Data Structure

Hash Map 구조의 이해

 

 

Hash Map의 개념

 

 

Hash Map 자료구조는 key-value 쌍을 저장할 때 사용하는 방법 중 하나로서, 빠른 검색 속도와 효율적인 메모리 사용의 장점으로 인해 자주 사용된다.

 

 

Hash Map은 key와 value의 쌍으로 구성되어 있다.

 

 

Hash Map은 객체 식별을 위해 hashcode() 메소드와 equals() 메소드를 이용한 동등 비교를 수행한다.

 

hashcode() 메소드를 통해 각 key에 대해 고유한 hashcode를 생성하고, 이 값을 배열의 index로 사용하여 데이터를 저장한다. 이후 검색을 할 때에도 hashcode() 메소드를 통해 key를 hashcode로 변환하여 index를 찾고, 해당 index에 저장된 데이터를 찾아서 반환한다. 해당 과정은 O(1)의 시간 복잡도로 이루어지기 때문에 매우 빠른 검색 속도를 보장하는 장점이 있다.

 

그러나 모든 key에 대해 고유한 hashcode를 부여할 수는 없기 때문에, 충돌(Collision)이 발생할 수 있다. 이 때문에 동일한 hashcode를 갖는 key들은 equals() 메소드를 통해 value를 비교하여 식별한다. 이때 hashcode() 메소드와 equals() 메소드의 결괏값 중 하나만 달라도 서로 다른 객체로 인식하게 되므로, equals() 메소드에서 같은 값으로 판명된 객체는 반드시 같은 hashcode를 가진다.

 

 

Hash Map 구조에서의 명칭

 

 

Hash Map은 Java의 key-value 쌍을 저장, 활용하는 인터페이스인 Map을 구현한다.

 

 

Hash Map의 응용

 

 

  • Java에서의 활용 예시
String str = "abcbdeacb";

Map<Character, Integer> map = new HashMap<>();
for(char key : str.toCharArray()) {
    map.put(key, map.getOrDefault(key, 0) + 1);
}

System.out.println(map); // {a=2, b=3, c=2, d=1, e=1}

for (char key : map.keySet()) {
    System.out.print(key + " ");
    System.out.println(map.get(key));
}
/*
a 2
b 3
c 2
d 1
e 1
*/

System.out.println(map.containsKey('a')); // true
System.out.println(map.size()); // 5

Map map2 = map;
System.out.println(map2.equals(map)); // true

 

Map의 주요 method에 대해 포스팅한 바 있다(https://hellmir.tistory.com/entry/collection-framework%EC%9D%98-interface-%EC%A2%85%EB%A5%98list-Set-Map%EC%99%80-%EC%A3%BC%EC%9A%94-method-%EC%A0%95%EB%A6%AC).

 

 

collection framework의 interface(List, Set, Map)별 주요 method 정리

공식문서에서는 method에 대해 서술할 때 타입을 일일이 설명해 주기 때문에 직관적으로 외우기 불편하다. 그래서 이곳에 내가 기억하기 편한 방식으로 정리해 두려 한다. 각 구현 클래스들에 관

hellmir.tistory.com

 

위에서 언급한 것처럼 Hash Map의 시간 복잡도는 key를 해싱하는 과정에서 O(1)이 소요되며, 이후 배열에서 데이터를 읽어오는 과정에서도 O(1)의 시간 복잡도가 소요되므로 검색 속도가 매우 빠르다. 그러나 충돌이 발생한 경우에는 LInked List를 탐색해야 하기 때문에, 최악의 경우(코딩 테스트에서 시간 복잡도를 계산할 때는 최악의 경우를 기준으로 시간 복잡도를 계산하는 빅오 표기법을 이용한다)에는 O(n)의 시간 복잡도가 소요될 수 있다. 따라서 충돌이 자주 발생한다면 Hash Map의 성능이 저하될 수 있다.

 

Hash Map은 자연어 처리에서 단어의 출현 빈도를 계산하거나 웹 애플리케이션에서 캐시를 구현하는 데 사용되며, Hash Map을 이용해 간단한 검색 기능을 구현할 수도 있다.

 

hashcode() 메소드와 equals() 메소드는 값 자체를 표현하는 객체인 VO(Value Object)에서도 활용된다. VO에 관련된 내용은 이전 포스팅(https://hellmir.tistory.com/entry/DDDDomain-Driven-Design%EC%97%90%EC%84%9C-Entity-DTO-VO%EC%9D%98-%EB%B9%84%EA%B5%90)에서 다룬 적이 있다.

 

 

DDD(Domain Driven Design)에서 Entity, DTO, VO 비교

Entity Entity는 데이터베이스의 테이블과 매핑되는 객체다. 값이 계속 변경되면 객체의 일관성이 유지되지 않으며 다른 객체들에도 영향을 끼치게 되므로, 데이터 전송용으로는 적합하지 않다. pub

hellmir.tistory.com

 

'Computer Science > Data Structure' 카테고리의 다른 글

Heap 구조의 이해  (0) 2023.06.17
Linked List 구조의 이해  (0) 2023.06.16
배열(Array) 구조의 이해  (0) 2023.06.14
큐(Queue) 구조의 이해  (0) 2023.06.13
스택(Stack) 구조의 이해  (0) 2023.06.12