[PS] Hastable vs HashMap vs TreeMap (HashSet, TreeSet): HashMap을 사용하는 이유

https://seminrevolution.tistory.com/11

[PS] Stack와 Queue로 ArrayDeque를 사용하는 이유(Stack과 LinkedList가 아니라)

^ 오랜만에 자료구조 PS를 공부하며 코딩테스트 문제를 풀 때 Stack 대신 ArrayDeque을 사용하는 이유에 관해서 공부해보았다.

 

 

 

사진 참고 - https://velog.io/@kimunche/HashMap-TreeMap-%EC%B0%A8%EC%9D%B4%EB%A5%BC-%EC%95%8C%EC%95%84boza

 

1. Hastable vs HashMap

 PS에서 Stack 대신 ArrayDeque를 사용하는 이유는 동기화 유무때문인데, 단일 스레드 환경의 PS에서는 동기화로 인한 오버헤드가 발생한다. 따라서, 동기화 기능이 있는 Stack보다는 동기화 기능이 없는 ArrayDeque를 사용하는 것을 권장한다.

 

 Hastable vs HashMap의 경우에도 동기화 기능 유무의 차이가 있다. 게다가 Hashtable은 old하다는 특징이 있다. 해당 내용은 출처에 남겨둔 글을 참고하면 좋다. (아래 링크 글에서 'Thread-safe 여부, Null 값 허용 여부, Enumeration 여부, 보조해시를 사용 여부, 지속적인 개선'의 차이가 있음을 확인할 수 있다.)

참고 - https://devlog-wjdrbs96.tistory.com/253

 

 

 

2. HashMap vs TreeMap

 이 둘은 서로 기능이 다른데, HashMap은 DS시간에 배운 전형적인 Hashtable이라면 TreeMap은 key를 정렬해주는 기능이 추가 된다. key는 이진트리로 저장되고, 특별히 Red-Black Tree 구조를 이용하여 효율적으로 정렬된다. 아래의 링크에서 자세한 설명과 메소드들을 확인할 수 있다.

참고 - https://velog.io/@kimunche/HashMap-TreeMap-%EC%B0%A8%EC%9D%B4%EB%A5%BC-%EC%95%8C%EC%95%84boza

 

 HashSet, TreeSet의 경우도 마찬가지의 차이가 있다. 또한, Set이기에 key-value 쌍이 아니라 원소 하나가 저장된다.

 

 

 

P.S. 빨리 코테 풀고 싶어서 호다닥 읽어보고 정리하고 간다