[자료구조] HashMap

🎯 HashMap

1. HashMap

HashMap은 Java에서 가장 많이 사용되는 자료구조 중 하나로, 키와 값의 쌍을 저장하는 데 사용됩니다.

키는 객체를 식별하는 데 사용되는 고유한 값이고, 값은 키와 연관된 데이터입니다.

HashMap은 키에 대한 빠른 검색 및 접근성을 제공하는 해시 테이블을 기반으로 구현됩니다.

1.2 장점

• 빠른 검색 및 삽입 성능
• 동적 크기 조정
• 간단한 사용법
• 메모리 효율성

1.3 단점

• 정렬되지 않음
• 비동기화되지 않음 (ConcurrentHashMap 사용 필요)
• 해시 충돌 가능성 (별도 해결 방안 필요)

2. 해싱 및 해시 함수

해싱은 임의 길이의 데이터를 고정 길이의 데이터로 매핑하는 과정입니다. 이를 수행하는 함수를 해시 함수라고 합니다.

해시 함수는 키를 해시 값으로 변환하는 역할을 합니다. 해시 값은 키의 고유한 특징을 나타내는 정수입니다.

좋은 해시 함수는 다음과 같은 특징을 가져야 합니다.

• 고르게 분산된 해시 값: 해시 함수는 가능한 모든 해시 값을 균일하게 분산시켜야 합니다.
• 빠른 계산 속도: 해시 함수는 빠르게 계산될 수 있어야 합니다.
• 동일한 키에 대한 동일한 해시 값: 동일한 키는 항상 동일한 해시 값으로 변환되어야 합니다.
• 비슷한 키에 대한 서로 다른 해시 값: 비슷한 키는 서로 다른 해시 값으로 변환되어야 합니다.

3. HashMap 구현

HashMap은 해시 테이블을 사용하여 구현됩니다. 해시 테이블은 배열과 연관 목록의 조합으로 구성됩니다.

배열은 버킷(bucket)이라고 불리는 슬롯으로 구성되며, 각 버킷은 연관 목록을 저장합니다.

키를 해시 함수에 입력하면 해당 키에 대한 해시 값이 생성됩니다.

해시 값은 버킷의 인덱스로 사용되며, 해당 버킷의 연관 목록에 키-값 쌍이 저장됩니다.

4. 주요 메서드

• put(K key, V value): 키-값 쌍을 해시 테이블에 추가합니다.
• get(K key): 키에 해당하는 값을 반환합니다. 키가 없으면 null을 반환합니다.
• containsKey(K key): 키가 해시 테이블에 존재하는지 확인합니다.
• remove(K key): 키에 해당하는 키-값 쌍을 제거합니다.
• size(): 해시 테이블에 저장된 항목의 개수를 반환합니다.
• isEmpty(): 해시 테이블이 비어있는지 확인합니다.

5. 활용 예시

• 사용자 정보 저장: 사용자 ID를 키로 사용하고 사용자 이름, 이메일, 전화번호 등의 정보를 값으로 저장하는 데
  사용할 수 있습니다.
• 캐싱: 데이터베이스 또는 API 호출 결과를 캐싱하는 데 사용할 수 있습니다.
• 구성 정보 저장: 애플리케이션의 구성 정보를 저장하는 데 사용할 수 있습니다.

6. 주의사항

• 해시 충돌: 두 개 이상의 키가 동일한 해시 버킷으로 매핑되는 경우 해시 충돌이 발생합니다. 해시 충돌을
  해결하기 위해 다양한 해시 충돌 해결 전략이 사용됩니다.
• null 키: null 키를 사용할 수 있지만 주의가 필요합니다. HashMap에서 null 키는 다른 키와 구별됩니다.
• 동기화: 여러 스레드에서 HashMap을 동시에 사용하는 경우 동기화가 필요합니다. Java 8부터 ConcurrentHashMap 클래스가 제공되며, 이는 여러 스레드에서 안전하게 사용할 수 있는 동기화된 HashMap 구현입니다.