HashSet, LinkedHashSet 성능비교

Q. LinkedHashSet은 저장 순서를 보장하는데, 얼마나 큰 성능 차이가 있으며, 내부 구현은 어떻게 되어있을까?

객체 생성

n	HashSet (ns)	LinkedHashSet (ns)
10	3353	3497
100	6172	18972
1000	32944	37453
10000	96258	106902
100000	458945	370427
1000000	32231112	2526962
10000000	20254271	20579414

• 대부분의 경우에서 비슷한 성능을 보였다.

add

n	HashSet (ns)	LinkedHashSet (ns)
10	4302	2864
100	11580	13354
1000	58418	59937
10000	229795	248593
100000	3299830	3540409
1000000	31071945	51004127
10000000	302512767	511996641

• n이 10만 까지는 비슷한 성능을 보였지만, 100만 이상인 순간부터 큰 성능차이를 보였다.

remove

n	HashSet (ns)	LinkedHashSet (ns)
10	6130	2170
100	12563	6195
1000	61362	68315
10000	303161	264687
100000	784125	1010511
1000000	5604166	6298848
10000000	60914850	91865556

• n이 1만 까지는 HashSet이 더 느린 경향을 보였지만, 그 이후에는 큰 성능차이를 보였다.

contains (in)

n	HashSet (ns)	LinkedHashSet (ns)
10	4579	1324
100	8169	4304
1000	51522	26121
10000	204362	99145
100000	869085	664588
1000000	6513278	4773900
10000000	38283442	28933217

• 대체적으로 약 2배가량 LinkedHashSet의 성능이 더 좋다.

Answer

• HashSet의 add, remove, contains은 HashMap 구조를 따라간다.
• LinkedHashSet의 내부구조는 살펴볼 수 없었다.
• add, remove 성능은 HashSet이 전반적으로 좋았지만, contains 성능은 LinkedHashSet이 좋았다.

결론

• HashSet의 내부구현은 HashMap을 참고하자
• 원소 추가, 삭제가 많다면 HashSet을 사용하고, 원소 유무 판단이 많다면 LinkedHashSet을 사용하자

느낀점

• LinkedHashSet의 내부구현은 볼 수 없었지만, 성능 비교를 통해 어느 상황에 어느 자료구조를 써야 좋을지 알 수 있었던 계기가 되었다.