Java 대용량 데이터 HashMap 기본개념 및 시간복잡도(예시)

HashMap

개요

안녕하세요! 빈코입니다. 오늘은 이전 포스팅에 다룬 자료구조 반복문과 배열의 시간복잡도 차이에 이어서 HashMap의 시간복잡도와 기본개념에 대해 포스팅하려 합니다. 많은 분들이 착각하시는 것 중에 하나가 '대용량 데이터는 무조건 Hash 알고리즘을 써야 한다!'인데, 사실 자료구조 선택은 각각의 개발 상황에 맞게 해야 하기 때문에, 어쩔 때는 반복문이 또 어쩔 때는 배열이 더 성능이 좋을 수도 있습니다.  그럼 한번 알아볼까요?

 

HashMap 기본 개념📙

HashMap이란 키에 대한 해시 값을 사용하여 값을 저장하고 조회하며, 키-값 쌍의 개수에 따라 동적으로 크기가 증가하는 associat array(Map, Dictionary, Symbol Table)라고 할 수 있습니다. map은 대응 관계를 지칭하는 용어로, 키의 집합인 정의역과 값의 집합인 공역의 대응합니다. 

 

예시 그림

 

여기서 HashMap의 특징은 값은 중복 저장될 수 있지만 키는 중복 저장될 수 없는 특징을 가집니다. 만약 기존에 저장된 키와 동일한 키로 값을 저장하면 기존의 값을 사라지고 새로운 값으로 넣어지게 됩니다. 또한, HashMap은 기본적으로 각 객체의 hashCode() 메서드가 반환하는 int형 자료를 인덱스로 사용하기 때문에, 대규모 데이터의 값을 조회할 때 빠른 성능을 보입니다.

 

하지만, HashMap은 값을 추가 할 때 해시 충돌을 피하기 위해서 버킷을 2배로 확장하는 특성이 있습니다. 그렇기 때문에, 다른 자료구조에 비해 메모리를 많이 잡아먹습니다. 버킷을 2배로 확장하는 것을 막기 위해서는 정확한 해시 사이즈를 명시해줘야 합니다. 

 

HashMap<Type,Type> firstMap = new HashMap<Type,Type>(); //HashMap생성
HashMap<Type,Type> secondMap = new HashMap<>(); // 제네릭 생략 가능
HashMap<Type,Type> thridMap = new HashMap<>(firstMap); //firstMap의 모든 값을 가진 HashMap생성
HashMap<Type,Type> fourthMap = new HashMap<>(100); //초기 용량 지정(capacity)
HashMap<Type,Type> fifthMap = new HashMap<>(100, 0.8f); //초기 capacity,load factor지정

 

하지만 개발을 하다보면 불가피하게 값을 추가해야 하는 경우도 생깁니다. 그렇기에, 초기 용량을 선정해 주는 부분은 어려울 가능성이 높습니다. 예를 들어, 한 기업의 조직도를 조회하는 로직 중에서 해당 기업이 대기업이어서 조직이 만개가 있다고 가정했을 때, 초기 용량을 만개로 잡는다면 추후에 조직이 추가될 경우에는 Hash 용량을 수기로 늘려줘야 하는 경우도 생길 수 있습니다.

 

그렇기에, 각자 개발 상황에 맞는 자료구조를 선택해야 합니다😃

 

HashMap 사용법📘

첫 번째로, HashMap에 값을 추가하는 방법은 put() 함수를 사용하면 됩니다. 해당 함수를 사용할 때는 HashMap을 선언했던 타입과 동일한 타입의 값만 저장할 수 있습니다.

HashMap<Integer,String> bincoMap = new HashMap<>();
map.put(1,"Binco"); 
map.put(2,"Blog");

 

 

두 번째로, HashMap에서 특정 값을 삭제하는 방법과 모든 값을 삭제하는 방법이 있습니다. 특정 값을 삭제할 때는 remove(Key 값) 함수를 사용하면 되고 모든 값을 삭제하려면 clear() 함수를 사용하면 됩니다.

HashMap<Integer,String> bincoMap = new HashMap<>();
map.put(1,"Binco"); 
map.put(2,"Blog");

map.remove(1); // Binco 삭제
map.clear(); // 남아있는 모든 값 삭제

 

 

세 번째로, 값을 출력하는 방법은 여러가지 방법이 있습니다. 전체를 출력하는 방법, entrySet() 함수를 활용하여 출력하는 방법, keySet() 함수를 사용하는 방법, 마지막으로 해당 Set들을 활용하여 Iterator를 사용하는 방법이 있습니다. 실무에서는 대부분 다음 값이 있는지 체크하는 로직이 필요하기 때문에 Iterator를 많이 사용합니다. 

 

HashMap<Integer,String> bincoMap = new HashMap<>();
map.put(1,"Binco"); 
map.put(2,"Blog"); // 초기값 지정

// 전체 조회
System.out.print(bincoMap); // 전체 출력 = {1:"Binco",2:"Blog"}
System.out.print(bincoMap.get(1)); // 개별 출력 = "Binco"

// entrySet() iterator 사용법
Iterator<Entry<Integer, String>> entries = bincoMap.entrySet().iterator();
while(entries.hasNext()){
    Map.Entry<Integer, String> entry = entries.next();
    System.out.println(entry.getKey() + " : " +  entry.getValue());
}

// 1 : Binco
// 2 : Blog

// keySet() iterator 사용법
Iterator<Integer> keys = bincoMap.keySet().iterator();
while(keys.hasNext()){
    int key = keys.next();
    System.out.println(key + " : " +  bincoMap.get(key));
}
// 1 : Binco
// 2 : Blog

 

위의 코드를 보면 아시겠지만 keySet() 메서드는 HashMap에 포함된 키들의 집합을 반환합니다. 하지만 키값만 반환하기 때문에, 키와 값 모두가 필요한 경우에는 추가적인 get() 호출이 필요하므로 성능에 영향을 미칠 수 있습니다.

 

반대로 entrySet() 메서드는 HashMap의 엔트리(키-값 쌍)을 모두 반환합니다. 개발 상황에 따라서 Key값만 필요하다면 keySet() 함수를, 키-값 엔트리가 필요하다면 entrySet()을 사용하는 것이 효율적입니다😁

 

시간복잡도📒

HashMap의 삽입 및 조회 시 일반적으로 O(1)의 시간복잡도를 가집니다. 하지만 위에서 설명했듯이, 해시 충돌이 발생할 경우에는 최대 O(n)의 시간복잡도를 가집니다. 해시 충돌이 발생할 경우에는 선형 탐사(linear probing) 또는 체이닝(chaining) 등의 충돌 해결 방법을 사용합니다. 자세한 내용은 하단 링크를 참조해 주세요 :) 

 

Reference : https://d2.naver.com/helloworld/831311

 

이전 포스팅에서 말씀드렸던 반복문의 시간복잡도는 O(n), 배열의 시간복잡도는 일반적으로 O(1)를 가지는데, 각 자료구조마다 장단점이 확실히 있기 때문에 각자 개발 상황에 맞는 자료구조를 선택하시는 것이 좋습니다. 제일 속도가 빠른 건 HashMap이지만 해시 충돌이 발생했을 경우를 생각해야 하고 데이터의 양 또한 고려해야 하는 부분입니다.

 

저는 실무에서 3만개의 데이터를 삽입, 조회해야 하는 경우가 있었는데 3만 개 정도는 배열로 해도 조회하는데 0.6초 정도 소요가 됐습니다. 대부분의 기능은 1초 이내면 Pass이기 때문에 3만 개 정도까지는 배열 자료구조를 사용해도 괜찮은 것 같네요!

 

마치며

지금까지 HashMap 자료구조를 사용한 시간복잡도에 대해 알아봤습니다. 혹여나 틀린 정보가 있거나, 더 좋은 방법들이 있다면 댓글로 알려주시면 감사하겠습니다😊 

 

 

---

👨‍👩‍👦‍👦 오픈채팅방 운영

취업을 준비하는 예비 개발자분들을 위한 질문&답변할 수 있는 공간을 만들었습니다. 취업과 이직을 하기 위해서 어떤 걸 중점적으로 준비해야 하는지부터 포트폴리오&이력서 작성법 등 다양한 질문들을 받고 답변을 드립니다. 참여하셔서 다양한 정보 얻고 가시면 좋을 것 같네요😁

 

참여코드 : 456456

https://open.kakao.com/o/gVHZP8dg

비전공 개발자 취업 준비방(질문&답변)

 

 

---

👨‍💻 전자책 출간

아울러 제가  🌟비전공자에서 2년만에 보안 전문 중견기업으로 이직 한 방법들을 정리한 전자책을 출간하게 되었습니다. 어떤 걸 공부해야 하는지, 이직을 위해서 무엇을 준비해야 하는지, 제가 받았던 기술 면접 리스트 등 다양한 목차로 구성되어 있습니다. 또한, 구매 시 1:1 채팅을 이용하여 포트폴리오 첨삭을 도와드리고 있습니다. 🐕전자책으로 얻은 모든 수익은 유기견 센터 '팅*벨 입양센터'에 후원될 예정입니다. 관심 있으신 분들은 아래 링크를 참고해 주세요😁

https://kmong.com/gig/480954

비전공개발자 2년만에 중견기업 들어간 방법 | 14000원부터 시작 가능한 총 평점 0점의 전자책, 취

---