HashMap의 containsKey()는 왜 시간 복잡도가 O(1)일까?
혹시 HashMap의 containsKey() 메서드가 왜 평균적으로 O(1)의 시간 복잡도를 갖는지 아시나요?
그동안 사용할 때마다 궁금했습니다. Collection이 어떤 값을 포함하는지 확인하려면 내부의 자료를 순회해야할텐데 어떻게 O(1)의 시간 복잡도로 포함 여부를 확인할 수 있을까? 그래서 몇 번인가 찾아봤었지만 설명이 어려워서 이해하지 못했었는데, 오늘은 드디어 이해가 돼서 이해한 내용을 글로 정리해두려고 합니다!
이 글에서는
1. HashMap이란?
2. HashMap이 내부적으로 이용하는 HashTable
3. HashTable이 자료의 중복을 해결하는 방법
의 순서로 살펴보려고 합니다.
1. HashMap이란?
HashMap은 키(Key)와 값(Value)으로 구성된 Entry 객체를 저장하는 Map의 일종입니다. 처음 사용해보시는 분들은 말이 조금 어려울 수 있을 것 같아요. 우선 Map에 대해 먼저 설명하자면, 일종의 사전이라고 생각하면 편할 것 같아요. (실제로 Python 등의 언어에서는 Dictionary라는 이름을 사용해요) Array에서는 인덱스를 통해서 자료를 저장하잖아요? 0번 자료, 1번 자료, … 이런 식으로요. Map에서는 저장하는 자료에 각각 이름을 붙여줍니다. 여기서 이름을 Key, 저장하는 자료를 Value라고 해요. 왜 Map이나 Dictionary라는 이름을 쓰는지 이해가 되죠?
구체적인 사용법은 아래 글에서 볼 수 있어요.
[JAVA]Map이란? (HashMap, Hashtable, TreeMap)
Map 컬렉션 클래스 Map 인터페이스는 Collection 인터페이스와는 다른 저장 방식을 가집니다. Map 인터페이스를 구현한 Map 컬렉션 클래스들은 키와 값을 하나의 쌍으로 저장하는 방식(key-value 방식)을
devlogofchris.tistory.com
HashMap은 Map 중에서도 가장 흔하게 쓰이는 Map인데요, Map에는 HashMap, LinkedHashMap, TreeMap 등이 있어요. 사전에도 단어들을 일정한 순서에 따라 실어 놓았죠? 여러 Map은 자료를 저장하는 순서가 다른데요, 그 중에서 HashMap은 HashCode를 이용하는 Map이에요. 갑자기 어려운 단어가 나왔는데, 이 글의 나머지 부분에서 천천히 설명할거니까 겁먹지 않으셔도 돼요 ☺️ 그리고 모르셔도 상관없지만, LinkedHashMap은 자료들을 순서대로 저장하는 HashMap이고, TreeMap은 자료들을 오름차순으로 저장해요. 이름 그대로죠?
그럼 HashCode가 무엇인지에 대해 천천히 알아봐요. HashMap이 자료를 저장하기 위해서 내부적으로 HashTable을 사용하는데, 이때 사용되는 게 HashCode에요. 그래서 HashCode을 이해하려면 우선 HashTable을 알아야 해요.
2. HashMap이 내부적으로 이용하는 HashTable
HashTable은 우리가 아는 표와 비슷한 자료 구조라고 생각할 수 있어요.
| 키1 | 값1 |
| 키2 | 값2 |
와 같은 방식으로 자료를 저장하는데, 다만 내부적으로는 값을 저장하기 위해 Array를 이용해요. Array를 이용하려면 정수 형태의 Index가 필요한데 Key를 어떻게 Index로 변환할까요? 여기서 사용되는 게 HashCode에요. HashTable은 Key를 HashCode로, HashCode를 Index로 변환해요.
조금 더 구체적으로 얘기해볼까요? Java의 모든 클래스는 Object를 상속하는데, Object는 hashCode() 메서드를 가져요. 그래서 모든 클래스는 내부적으로 hashCode() 메서드를 가지고 있고, 이 메서드를 통해서 Key가 HashCode로 변환돼요. 그리고 HashTable이 자체적으로 함수(=Hash Function)를 통해 HashCode를 일정 범위 내의 Index로 바꿔줍니다.
예를 들어 "Fruit"이라는 Key에 "Apple"이라는 Value를 저장한다고 해볼까요? "Fruit"은 String이니까 String 내부의 hashCode() 메서드를 호출해서 29384783...과 같은HashCode 값을 얻을 거에요. 그리고 그 값을 Index인 17로 변환해서 HashTable이 내부적으로 가지는 배열의 17번 자료에 Value인 "Apple"이라는 값을 저장하는 거에요.
결론적으로 얘기하면 1️⃣ Map도 내부적으로 Value들을 저장하기 위해 Array를 이용하고, 2️⃣ Value를 저장할 Index를 결정하기 위해 hashCode()와 HashTable의 자체 함수를 이용해요.
근데 이 방식에는 한 가지 문제가 숨어 있어요. 그 문제는 Key와 Index가 꼭 일대일 대응이 아니라는 거에요. 즉, 서로 다른 Key가 어쩌다 보니 같은 Index로 변환될 수도 있어요. 같은 Key에 다른 Value를 가지면 그냥 덮어쓰기를 하면 되지만, 서로 다른 Key가 같은 Index를 가지면 어떻게 할까요? 이 경우에는 덮어쓰기를 하면 안돼요.
3. HashTable이 자료의 중복을 해결하는 방법
이러한 경우를 Collision이라고 해요. 그리고 위에서 얘기하지는 않았지만 HashTable은 Collision을 방지하기 위한 방법을 가지고 있어요. 아까 HashTable이 Value를 저장하기 위한 Array를 가지고 있다고 했죠? 그 Array는 단순히 Value의 타입의 배열이 아니라, Value의 타입의 LinkedList를 저장해요. 그래서 만약에 서로 다른 Key들이 같은 Index를 가지면, 해당 Index의 LinkedList에 Value들을 모두 저장해요.
설명이 조금 복잡하죠? HashTable을 구현하는 실제 코드는 아래 영상에서 볼 수 있어요. 아마 코드를 직접 확인해보면 이해가 안 갔던 내용을 이해하실 수 있을 거에요.
지금까지 1️⃣ Map은 내부적으로 LinkedList의 배열을 가지고, 2️⃣ 함수를 통해 각각의 Key에 대응하는 Value를 찾는다는 사실을 알아봤어요. 길고 긴 설명을 따라오느라 고생 많으셨습니다 😊 그럼 다시 첫 질문으로 돌아가볼까요?
HashMap의 containsKey() 메서드가 왜 평균적으로 O(1)의 시간 복잡도를 가질까요?
방금 말한대로 HashMap은 어떤 자료를 찾기 위해 내부 자료구조를 순회하는 것이 아니라, 단순히 함수에 Key를 대입하여 Value를 찾습니다. 이 때문에 평균 O(1)의 시간 복잡도로 어떤 자료를 포함하는 지를 알아낼 수 있는 거죠! 물론 최악의 경우 모든 자료가 똑같은 Index를 가지면 O(n)의 시간이 걸리겠지만요.
그럼 읽어주셔서 감사하고, 혹시라도 궁금한 내용이나 오류가 있다면 언제든지 댓글로 말씀해주세요. 감사합니다! ☺️
참고 자료
[JAVA]Map이란? (HashMap, Hashtable, TreeMap)
모의면접 복기 (1) - Hash, HashMap (완주하지 못한 선수)
[자료구조 알고리즘] 해쉬테이블(Hash Table)에 대해 알아보고 구현하기