자바의 HashMap 심층분석 (1)

HashMap은 자바에서 매우 유용한 자료구조 중 하나로, 키와 값(key-value)의 쌍을 저장하는 해시 테이블 기반의 자료구조입니다.

이 자료구조는 키(key)를 해시함수를 사용하여 해시 코드(hash code)로 변환하고, 이를 기반으로 배열에 저장된 버킷(bucket) 내에 해당 키와 연관된 값을 저장합니다.

이번 글에서는 HashMap의 개념과 작동 방법에 대해 살펴보겠습니다.

 

<HashMap 심층분석>

---

HashMap 이란?

HashMap은 Map 인터페이스를 구현한 클래스로서 key-value 쌍으로 이루어진 데이터 저장과 검색을 할 수 있게 해주는 자료구조입니다.

Key와 Value 형태로 이루어져 있으며, 각 요소들을 키로 설정함으로써 중복되지 않는 고유한 값을 가질 수 있도록 합니다.

또한, 기존의 배열과는 다르게 순서가 없고, 삽입/삭제 시 맵 전체 내용이 수정되는 것이 아니라 일부 항목만 수정됩니다.

하지만, HashMap은 동기화가 안되기 때문에 멀티스레드 환경에서는 동시에 여러 개의 스레드가 접근하는 경우에는 문제가 발생할 수 있습니다. 이때에는 외부에서 동기화를 보장해야 합니다.

 

1. Hashtable 과의 비교

Hashtable 역시 Map 인터페이스를 구현한 클래스로, HashMap과 마찬가지로 키와 값의 쌍을 저장합니다.

하지만, Hashtable은 null 키와  null 값을 허용하지 않습니다.

또한, Hashtable은 동기화되어 있기 때문에 멀티스레드 환경에서도 안전하게 사용할 수 있지만  HashMap에 비해 성능이 떨어질 수도 있습니다.

이 두가지 자료구조는 서로 비슷한 기능을 가지고 있지만, 사용 환경과 요구사항에 따라 적절하게 선택하여 사용해야 합니다.

예를 들어, 멀티스레드 환경에서는 Hashtable을, null 값을 허용해야 하는 경우에는 HashMap을 사용하는 것이 좋습니다.

 

2. 다른 언어와의 비교

대부분의 프로그래밍 언어는 해시 기반의 자료구조를 제공하고 있습니다.
이는 키와 값을 연결하여 빠르게 데이터를 검색할 수 있는 구조가 필요하기 때문입니다.
여기에는 Python의 Dictionary, JavaScript의 Object 또는 Map, C++의 Unordered_map 등이 포함됩니다.
Python의 Dictionary: Python에서는 Dictionary라는 해시 기반의 자료구조를 제공합니다. 이는 중괄호({})를 사용하여 표현하며, 키와 값의 쌍으로 구성됩니다.

 

[JavaScript의 Object 또는 Map]

JavaScript에서는 Object 또는 Map을 해시 기반의 자료구조로 사용할 수 있습니다.

Object는 기본적으로 속성과 값을 연결하는 구조를 가지며, Map은 키와 값을 연결하는 구조를 가집니다.

[C++의 Unordered_map]

 STL(Standard Template Library)의 일부인 Unordered_map을 제공합니다.

이는 해시 테이블을 기반으로 한 자료구조로, 키와 값의 쌍을 저장하는 데 사용됩니다.

이처럼 언어마다 이름은 조금씩 다르지만, 대부분 해시 기반의 자료구조를 제공하고 있으며, 그 기능은 대체로 비슷합니다. 이들은 모두 데이터의 빠른 접근을 가능하게 하는 동일한 원리에 기반을 두고 있습니다.

 

3. Key는 왜 쓸까?

키란 위에서 언급했듯이 일종의 주소라고 보시면 됩니다.

만약 우리가 원하는 정보가 100번지에 있다면 그것을 알기 위해서는 100번지를 알아야 하는데

이것을 인덱스라고 부릅니다.

따라서 인덱스로써 활용될 수 있는 모든 필드들이 키가 될 수 있습니다.

한 가지 주의해야 할 점은 같은 이름의 필드는 존재할 수 없다는 것입니다.

hashmap<String, Integer> map = new HashMap<String, Integer>();

 

즉 위 와 같이 선언한다면 String타입의 key필드와 Integer타입의 value필드가 동시에 존재할 수 없습니다.

 

4. HashMap 사용 시 정렬이 반드시 필요한가?

HashMap은 기본적으로 키-값 쌍을 저장하고 검색하는 데 있어서 '효율성'을 중점으로 두는 자료구조입니다.

그래서 HashMap은 데이터를 저장하고 검색할 때 정렬을 전혀 고려하지 않기 때문에 HashMap은 기본적으로 정렬되지 않은 상태에서 사용할 수 있습니다.

HashMap의 각 키는 해시 함수를 통해 특정 위치에 매핑되고, 이 위치는 키-값 쌍을 저장하거나 검색하는 데 사용됩니다.

 

이러한 방식 덕분에 해시 맵은 데이터의 양에 상관없이 일정한 시간 내에 특정한 키에 대한 값(value)을 빠르게 검색할 수 있습니다.

따라서 특정 키를 사용해 빠르게 값을 찾아야 하는 경우, 데이터의 입력 순서나 키의 순서에 상관없이 데이터를 저장하고 검색해야 하는 경우에는 해시 맵이 아주 유용합니다.

 

결론적으로, HashMap을 사용하는 주된 이유는 빠른 검색 속도를 위한 것이며, 이를 위해 내부적으로 정렬하지 않고도 데이터를 효율적으로 저장/검색할 수 있는 방식을 사용하고 있습니다.

 

---

HashMap의 동작 원리

HashMap은 키-값(key-value) 을 쌍으로 저장하는 자료구조로, hash table을 기반으로 동작합니다.

hash table 은 키(key)를 해시 함수를 사용하여 해시 코드(hash code)로 변환하고,  배열에 저장된 버킷(bucket) 내에 해당 키와 연관된 값을 저장합니다.

HashMap의 동작 원리는 다음과 같습니다.

 

1. 해시 함수를 사용한 키의 해시 코드 생성

해시 함수를 사용하여 키의 해시 코드를 생성하는 과정입니다.

 

• 해시 코드 획득
  : 객체의 hashCode() 메서드 호출하여 키의 해시 코드를 얻습니다.
  자바의 모든 객체는 hashCode() 메서드를 가지고 있으며, 이 메서드는 객체의 해시 코드를 반환합니다.
• 해시 코드 변환
  : hashCode() 메서드를 통해 얻은 해시 코드는 일반적으로 객체의 메모리 주소를 기반으로 생성되며, 일반적으로 큰 정수 값으로 표현됩니다.
• 해시 코드 축소
  : 해시 함수는 얻은 해시 코드를 해시 테이블의 크기에 맞추기 위해 축소하는데 일반적으로 해시 테이블의 크기를 나누고 나머지를 취하는 방식으로 수행되고, 이를 통해 해시 코드를 버킷(bucket)의 인덱스로 매핑합니다.
•  해시 코드 반환
  : 최종적으로 변환된 해시 코드를 반환하여 해당 키를 저장할 버킷(bucket)을 결정합니다.
  이 과정은 HashMap과 같은 해시 기반 자료구조에서 키의 해시 코드를 생성하는 핵심적인 역할을 합니다.

해시 함수의 품질은 해시 충돌을 최소화하고 데이터를 균일하게 분산시키는 데 중요한 역할을 하기 때문에 효율적인 해시 함수를 선택하는 것이 중요합니다.

 

2. HashMap에 키-값 쌍 저장

HashMap에 키-값(key-value) 을 저장하는 과정은 HashMap은 해시테이블(hash table)을 기반으로 동작하며, 키(key)를 해시 코드(hash code)로 변환하여 해당 위치에 값을 저장합니다.

 

// 예시코드
  import java.util.HashMap;
  public class HashMapExamples {
     public static void main(String[] args) {
    // HashMap 객체 생성
        HashMap<String, Integer> hashMap = new HashMap<>();
    // 키-값 쌍 추가
       hashMap.put("apple", 100);
       hashMap.put("banana", 200);
       hashMap.put("orange", 300);
   // HashMap 출력
      System.out.println("HashMap: " + hashMap);
      }
  }

 

위의 예시 코드에서는 문자열(String)을 키로, 정수(Integer)를 값으로 사용하고 있습니다.

HashMap에는 동일한 키를 중복하여 저장할 수 없으며, 기존에 동일한 키가 이미 존재하는 경우에는 이전 값이 덮어 쓰입니다.

따라서 HashMap은 키를 기반으로 유일한 값을 관리하는데 유용합니다.

 

3. 값의 검색 및 업데이트

검색 시에도 키의 해시 코드를 계산하여 해당 버킷을 찾고, 연결 리스트나 트리 등을 사용하여 해당 버킷에 저장된 값들을 검색합니다.

값의 업데이트나 수정도 마찬가지로 해당 버킷을 찾아서 수행됩니다.

 

1) 값의 검색(Search)

HashMap에서 값의 검색은 주어진 키에 해당하는 값을 찾는 과정입니다.

get() 메서드를 이용하여 특정 키에 해당되는 값을 검색할 수 있습니다.

이 메서드는 주어진 키에 해당하는 값이 있으면 해당 값을 반환하고,  없으면 null을 반환합니다.

// 예시 코드
HashMap<String, Integer> hashMap = new HashMap<>();
hashMap.put("apple", 100);
hashMap.put("banana", 200);
Integer value = hashMap.get("apple"); // "apple" 키값 검색
System.out.println("Value: " + value); // 출력: Value: 100

2) 값의 업데이트(Update)

HashMap에서 값의 업데이트는 주어진 키에 해당하는 값을 새로운 값으로 업데이트하는 과정입니다.

put() 메서드를 사용하여 값을 추가하거나 덮어쓸 수 있습니다.

만약 주어진 키가 이미 존재하는 경우에는 기존 값이 새로운 값으로 대체됩니다.

// 예시 코드
HashMap<String, Integer> hashMap = new HashMap<>();
hashMap.put("apple", 100);
hashMap.put("banana", 200);
hashMap.put("apple", 150); // "apple" 키값을 새로운 값으로 업데이트
Integer updatedValue = hashMap.get("apple");
System.out.println("Updated Value: " + updatedValue); // 출력: Updated Value: 150

 

 

4. 해시 충돌 해결

해시 충돌(hash collision)은 해시 함수가 서로 다른 키에 대해 동일한 해시 코드를 생성할 때 발생합니다.
해시 충돌은 HashMap과 같은 해시 기반 자료구조에서 중요한 문제이며, 이를 해결하기 위해 체이닝(Chaining), 개방주소(Open Addressing) 또는 이중해싱(Double Hashing) 같은 방법들이 사용됩니다.

특히 자바의 HashMap은 체이닝 방식을 사용하여 해시 충돌을 해결합니다.

체이닝은 각 버킷(bucket)을 연결 리스트로 구성하여 충돌된 키-값 쌍을 저장하는 방식입니다.

해시 충돌이 발생하면 동일한 버킷에 연결 리스트에 추가하여 저장합니다.

이 방법은 간단하고 효율적이지만, 많은 충돌이 발생할 경우 연결 리스트의 길이가 길어져 성능 저하가 발생할 수 있습니다.
하지만 JDK 8부터는 해시 충돌 발생 시에는 연결 리스트 대신 트리 구조로 변경하여 성능을 향상시키는 개선이 이루어졌기 때문에 충돌이 발생하더라도 HashMap은 충돌을 해결하여 안정적으로 동작합니다.

---

지금까지 자바에서 매우 중요한 자료구조 중 하나로, 데이터를 빠르고 효율적으로 관리하고 검색할 수 있는 핵심적인 역할을 수행하는 HashMap의 개념과 작동 방법에 대해 살펴보았습니다.

 

다음 글에서는 HashMap 사용시 발생할 수 있는 문제들과 문제해결을 위한 몇 가지 해결방안을 알아보겠습니다.