Hash Map의 개념
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).
위에서 언급한 것처럼 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)에서 다룬 적이 있다.
'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 |