HashMap과 Map에 대하여...

오늘은 HashMap과 Map에 대해서 알아볼려고 한다. 먼저 내가 이 두 단어를 들었을 때 처음 들었던 생각은 둘다 Map이라는 단어가 들어가는 어떤 부분에서 다른 거지? 어떤 부분이 다르게 작용하는 거지? 라는 궁금중이 들었다. 아마도 이 글을 읽고 이는 독자 분들도 그런 생각이 들었을 것이다. 그래서 나는 이 두가지 개념의 공통점과 차이점을 바탕으로 살펴보려고 한다.

 

1. HashMap과 Map의 공통점

 먼저 HashMap과 Map의 공통점은 어떤 데이터를 키와 값 형태로 관리하는 자료구조라는 점이다. 즉 이 2가지 개념은 모두 자료구조라는 것이다. 그렇다면 이 2가지 개념은 어떻게 데이터를 관리할까?

 

2. HashMap과 Map의 차이점

 그 방법에서 HashMap과 Map의 차이점이 발생한다. HashMap의 경우에는 HashTable이라는 자료구조를 통해서 자료를 관리한다. Map의 경우에는 Red-Black-Tree라는 알고리즘을 통해서 자료를 관리한다. 그렇다면 도대체 HashTable과 Red-Black-Tree은 무엇일까?

 

2-1. HashTable

  첫번째로 HashTable은 index,  bucket , key 이렇게 세가지로 이루어져 있다. key는 우리가 담고자 하는 자료의 key 값을 의미하고 , bucket은 우리가 담고자 하는 자료의 value 값을 의미한다. index는 key 값을 hashTable에 넣고 그 결과를 index로 삼는 것이다. 여기까지 들으신 분들은 다음과 같은 의문이 드실 것이다. "key , bucket 이거는 결국 key , value와 같은 개념이라서 ㅇㅋ 근데 index는 머야?" 그래서 이 index에 대해 좀 더 깊이 알아볼려고 한다. ("John Smith", "521-1234")인 데이터를 크기가 16인 해시 테이블에 저장한다고 하자. 여기서 key값은 "John Smith"에 해당되고 bucketdms "521-1234"에 해당 된다. 마지막으로 index는 hash_function("John Smith") % 16 연산을 통해 나온 값을 의미한다. 이러한 해싱 구조로 데이터를 저장하면 Key값으로 데이터를 찾을 때 해시 함수를 1번만 수행하면 되므로 매우 빠르게 데이터를 저장/삭제/조회할 수 있다. 해시테이블의 평균 시간복잡도는 O(1)이다.

 

2-2 Rad-Black-Tree

두번째로 Red-Black-Tree은 이진 검색 알고리즘이다. 우리가 흔히 아는 이진 검색 알고리즘의 시간 복잡도는 O(n)이다. 사실상 이렇게 말하면 O(logn)아니에요? 라는 반박이 들어온다. 하지만 엄밀히 말하면 O(n)이다. 그 이유는 우리가 이진 탐색을 만들기 위해서 사용하는 정렬 알고리즘 때문이다. 이때 사용되는 정렬 알고리즘의 시간복잡도가 이진 탐색 알고리즘의 시간 복잡도 보다 크기 때문에 O(logn)은 뭍이게 되는 것이다. 하지만 Red-Black-Tree은 이야기가 다르다. Red-Black-Tree 알고리즘은 정렬을 하는 과정 , 즉 이진 트리를 만드는 과정에서 특정한 규칙을 가지고 만들기 때문에 Read-Black-Tree의 평균 시간복잡도는 O(logn) 이다.