CS 지식/자료구조

맵(Map) 이란?

헬창코딩 2023. 5. 15. 23:22

Map은 Key와 Value 한쌍으로 이루어진 자료형이다.

  • Map은 리스트나 배열처럼 순차적으로 해당 요소 값을 구하지 않고 Key를 통해 Value를 얻는다.
  • 값(Value)은 중복될 수 있지만, **Key는 고유한 값(Unique)**을 가져야 한다.
  • Map은 저장 순서를 유지할 필요가 없고, Key를 통해 Value를 얻어내기 때문에 Key는 중복을 허용하지 않는다.
  • 구조도

HashMap, HashTable

키와 값(key, value)이 하나의 쌍을 이루는 데이터 구조이다. 즉, 키와 배열의 인덱스를 이용하여 키를 저장하는 자료구조이다. HashTable은 키를 해시함수(Hash Function)로 계산하여 그 값을 배열의 인덱스로 사용한다. 이때, 해시 함수에 의해 반환된 데이터의 고유 숫자값을 해시값 또는 해시코드라고 한다.

key 값을 해시함수를 통해서 배열의 인덱스로 바꿔주고, 그 자리에 데이터를 저장한다.

원래 데이터 값(Key) -> Hash Function -> Hash Function의 결과(Hash Code) ->
Hash Code를 배열의 index로 사용 -> 해당하는 index의 data 넣기

예를들어 이름을 키로하여 번호를 저장하는 해시테이블은 다음과 같이 만들 수 있다. 전체 데이터 양을 10이라고 하면 John의 데이터를 저장할 떄, 배열의 인덱스는 HashFunction("John") % 10 을 통해 인덱스 값을 계산한다. 여기서는 인덱스 값은 2이다.

이런식으로 데이터를 저장하다 보면 계산된 인덱스 값이 중복될 수가 있다. 예를들어 저장하고자 하는 키가 정수이고 hash_function이 key % 10이다. 전체 사이즈가 10일때, key 1,11,21은 같은 인덱스 값을 가지게 된다. 이를 충돌(collision)이라고 한다.

장점

  • 배열의 인덱스를 사용해서 검색, 삽입, 삭제가 빠름
  • 키와 해시값이 연관성이 없어 보안에도 많이 사용
    • 적은 리소스로 많은 데이터를 효율적으로 관리할 수 있음
  • 데이터 캐싱에 많이 사용

단점

  • 충돌
  • 공간 복잡도가 커짐
  • 순서가 있는 배열에는 어울리지 않음
  • 해시 함수 의존도가 높아짐

HashMap vs HashTable

자바에서 HashTable과 HashMap의 차이는 동기화 지원 여부이다.

  • HashMap-Null 값 허용
  • -병렬 처리를 하지 않을 때(동기화를 고려하지 않는 상황)
  • HashTable-Null 값 허용하지 않음
  • -병렬 처리를 할 때(동기화 고려)
  • HashMap은 보조해시를 사용하기 때문에 보조 해시 함수를 사용하지 않는 Hashtable에 비하여 해시 충돌(hash collision)이 덜 발생할 수 있어 상대적으로 성능상 이점이 있습니다.
  • 최근까지 Hashtable은 구현에 거의 변화가 없지만, HashMap은 현재까지도 지속적으로 개선되고 있습니다.

Hash

데이터를 다루는 기법 중 하나

Hash Function

  • 데이터를 효율적으로 관리하기 위해서 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수
  • 매핑전 원래 데이터의 값을 키(Key), 매핑 후 데이터의 값을 해시값(Hash Value) 또는 해시코드라고 하며, 키와 값으로 매핑되는 과정 자체를 Hashing(해싱) 이라고 한다.

Collision

  • 키에 대한 해시값이 같은 경우 = 사용하고자하는 해시 버킷이 이미 사용중인 경우
  • 충돌 해결을 위해
    • Chaining
      • 충돌이 일어날 경우 데이터들을 포인터를 이용해 서로 링크드 리스트(체인)형태로 연결하는 것
      • key값을 포인터로 이어서 연결
      • 최악의 경우 모든 데이터가 같은 해시값을 가져 O(n)의 복잡도를 가짐
      • JDK 라이브러리에 구현된 HashMap 은 chaining 방식을 사용하며 해당 버킷의 길이에 따라 LinkedList에서 Tree로 변경될수 있다
    • Open Addressing
      • 모든 데이터를 테이블에 저장하는 방법
      • 사용하려는 해시 버킷(테이블)이 이미 사용중인 경우 다른 버킷을 사용
      • 포인터를 쓰지 않아 오버헤드를 방지할 수 있고 데이터가 적을 경우 연속된 공간에 인자를 저장하기 때문에 공간 효율이 높다
      • 하지만 테이블의 크기가 커질수록 장점이 사라진다
      • Linear Probing
        • 충돌이 발생한다면 바로 다음 인덱스에 데이터를 저장하는 방식 다음으로 이동한 이후에도 충돌이 발생했다면 또 다시 바로 다음인덱스에 저장
      • Quadratic Probing
        • 충돌시 i^2 만큼씩 이동

TreeMap

  • 이진검색트리의 형태로 키와 값의 쌍으로 이루어진 데이터를 저장한다.
  • Map의 장점인 빠른 검색과 Tree의 장점인 정렬과 범위검색의 장점을 모두 갖고 있다.
  • 이진검색트리처럼, 데이터를 저장할 때 정렬하기 때문에 저장시간이 길다는 단점이 있다.
  • 정렬된 상태로 데이터를 조회하는 경우가 빈번하다면, 데이터를 조회할 때 정렬해야 하는 hashMap보다는 이미 정렬된 상태로 저장되어 있는 TreeMap이 빠른 조회결과를 얻을 수 있다.
  • 주로 HashMap을 사용하고, 정렬이나 범위검색이 필요한 경우에만 TreeMap을 사용하는 것이 좋다.

HashMap과 HashSet의 차이점

크게 아래 6가지로 나눌 수 있다.

1. 정의

HashMap은 Map 인터페이스의 구현체로, HashTable과 유사한 자료구조로 데이터를 저장한다.

HashSet은 Set 인터페이스의 구현체로, 내부적으로 HashMap을 사용하기 때문에 HashTable과 유사한 자료구조로 데이터를 저장한다.

2. 데이터 저장 형태

HashMap은 Key-Value 쌍 형태로 데이터를 저장하며, Key와 Value의 mapping을 유지하고 있다.

HashSet은 객체 그 자체를 저장한다.

위에서 HashMap을 내부적으로 사용한다고 했는데,

Key 값으로는 삽입되는 객체 그 자체를, Value 값으로는 HashSet 내부 구현 코드에서 미리 선언해둔 dummy 객체를 사용한다.

3. 중복 허용 여부

HashMap은 중복 Key 값을 허용하지 않지만, 중복 Value 값은 허용한다.

ex. {'a': 1, 'b': 1, 'c': 2}

HashSet은 객체 자체를 데이터로 저장하기 때문에 중복을 허용하지 않는다.

ex. {'a', 'b', 'c'}

4. NULL 허용 여부

HashMap은 (중복 Key 값을 허용하지 않기 때문에) 단 하나의 NULL 값을 Key 값으로 가질 수 있고, 여러 NULL 값을 Value 값으로 가질 수 있다.

HashSet은 단 하나의 NULL 값을 가질 수 있다.

5. 데이터 삽입 방법

HashMap은 put() 메서드를 사용하여 데이터를 삽입하는데, Key-Value 쌍 데이터의 형태를 저장하기 때문에

삽입 연산 동안 단 하나의 객체가 생성된다.

HashSet은 add() 메서드를 사용하여 데이터를 삽입하는데,

객체 그 자체를 저장하고 내부적으로 HashMap을 사용하기 때문에 삽입되는 **객체(Key값)**와 dummy 객체(Value 값),

총 두 개의 객체가 삽입 연산 동안 생성된다.

6. 성능

이전 글에서도 언급한 것처럼, HashMap이 HashSet보다 빠르다.

이유는 HashSet에 대해 작성한 이전 글을 참고하자.

그래서 데이터의 유일함(Uniqueness)을 유지하기 위해 항상 HashMap이 HashSet보다 선호된다.