java list vs map

list vs map

 

이번엔 java의 list와 map의 차이점에 대해 알아보겠습니다.

 

list와 map의 설명은 추후 포스팅 하도록 하고 해당 포스팅에서는 두개의 자료구조를 어떤 상황에서 사용하면 좋을지에 대해 알아보겠습니다.

설명은 List 인터페이스의 구현체인 ArrayList와 Map 인터페이스의 구현체인 HashMap으로 설명하겠습니다.

 

ArrayList

ArrayList는 순서대로 번호(index)가 붙은 원소들이 연속적인 형태로 구성된 자료구조 입니다.

• 특정 인덱스의 검색 O(1)
• 특정 인덱스에 원소의 삽입 O(n)
• 마지막 인덱스에 원소의 삽입 O(1)
• 특정 인덱스의 삭제 O(n)

우선 ArrayList는 유의미한 index를 사용할때 유용하게 사용할 수 있습니다. item들에 index가 필요할때나 순차적으로 무엇인가를 담고 출력해야 한다면 유용할 것 입니다.

그리고 원소의 삽입과 삭제가 빈번하다면 좋은 성능을 기대하기 어려울 것 입니다.

 

HashMap

HashMap은 key, value 형태로 데이터를 저장할 수 있는 자료구조 입니다.

• 특정 원소의 검색 O(1)
• 특정 원소의 삭제 O(1)
• 특정 원소의 삽입 O(1)

HashMap은 특정한 key를 통한 원소의 검색과 삽입, 삭제가 빈번하다면 쓰기 좋은 자료구조 입니다. 물론 HashMap 또한 List와 같이 반복문을 돌려 값을 뽑아낼 수 있습니다. 단 List처럼 index 기반으로 뽑아내는 것이 아님으로 순서를 보장할 수 없습니다. 이렇게 사용해야 한다면 List를 이용합시다.

 

TEST

이제 간단한 테스트를 통해 두 자료구조의 처리과정 속도의 차이를 한번 알아보겠습니다.

테스트는 아래와 같이 10000000개의 원소를 채워놓고 진행하도록 하겠습니다.

for (int i=0; i<10000000; i++) {
    arrayList.add("");
    hashMap.put(i, "");
}

반복문을 통한 삽입 속도

우선 위의 10000000개의 원소 삽입을 할 경우 두 자료구조의 경과 시간입니다.

ArrayList = 420ms (평균치)

HashMap = 1000ms (평균치)

 

ArrayList에 비해 HashMap의 삽입 속도가 두배 넘게 차이가 나는것을 확인 할 수 있습니다.

이처럼 HashMap은 단순 삽입에 있어 ArrayList.add(value) 보다 꽤나 성능이 좋지 않은것을 알 수 있습니다. 

 

특정 원소의 삽입

arrayList.add(10, "");
hashMap.put(10, "");

이번엔 삽입을 해보겠습니다.

ArrayList = 20ms

HashMap = 0ms 

 

10000000개의 원소가 있는데도 arrayList index 10번째 원소 삽입이 생각보단 많은 시간을 잡아먹진 않았습니다.

하지만 특정 인덱스가 아닌 특정 값(key)을 찾아야 한다면 해당 값을 찾기위해 추가로 O(n)의 시간복잡도가 추가되게 됩니다.

그리고 위의 원소의 갯수보다 많은 데이터가 있거나 삽입과 삭제가 정말 빈번하게 일어난다면 굳이 소모되지 않아도 될 비용이 추가되는 것 입니다.

 

위의 경과시간은 remove 또한 같습니다.

 

두개의 자료구조에 대해 간단히 알아봤습니다.

직접 테스트하며 작성하였습니다. 틀린 내용이 있다면 지적해주세요.

읽어주셔서 감사합니다.