#️⃣ 어떤 브랜치인가요?

• basic
• baekjoon
• other:

📝 구현 설명 (Describe)

HashMap

Hash 값을 이용한 Map 자료구조

모든 데이터(Node)를 ArrayList에 저장하는 하는 ListMap의 경우 정보의 탐색에서 O(N)의 시간복잡도를 가지게 됨.

해당 시간 복잡도를 줄이기 위해 특정 조건으로 데이터들을 나누고 이를 각기 다른 배열에 모아서 저장하는 방식으로 이해.

HashMap은 내부적으로 일정 크기의 배열(ArrayList 등)을 갖고 있고,
각 배열의 인덱스에는 충돌이 발생했을 경우 여러 데이터를 저장할 수 있도록 LinkedList를 연결해 놓음.

이런 방식으로 자료를 저장하여 기존 O(N)이었던 시간 복잡도를 평균 O(1), 최악 O(N)으로 향상 시킴.

이때 특정 조건으로 이용하는값이 Hash 함수를 통해 얻은 int 값이라 Hash 맵이라는 이름을 사용.

왜 이런 복잡한 구조를 쓰는가?

이유는 간단하게 탐색에 드는 시간을 줄일 수 있도록 하기 위해서

앞서 개발했던 ListMap의 경우 특정 Key 값을 가진 데이터가 있는지 탐색하기 위해서는 모든 데이터(Node)를 탐색해야했음.

하지만 HashMap의 방식으로 탐색을 하게 될 경우 Key 값에 따라 특정 조건 속 데이턴들만 찾으면 되니 일반적으로 탐색 시간이 크게 줄어들게 됨.

원래 한 바구니에서 데이터를 찾다가 여러 바구니에서 특정 바구니만찾으면 되니 탐색 시간이 줄어든다고 판단하면 좋음.
대신 별도의 저장 공간을 가져야하니 공간 복잡도는 ListMap에 비해 크게 차지하게 됨.

현재 구현 코드의 문제점.

현재 구현한 HashMap의 경우에는 데이터가 많아짐에따라 ArrayList의 Index에 저장된 데이터가 많아지고 그 영향으로 탐색 시간이 O(N)에 가까워 질 수 있음.

그렇기에 저장된 데이터가 전체 특정 비율을 넘어가면 ArrayList를 확장(resize)하는 작업을 수행해야하는데 아직 거기까지는 구현하지 않음.

또한 Set이나 Iterator 관련한 자료구조를 개발하지 않아 keySet 이나 iterator 같은 메소드는 구현하지 못함.