STL - unordered_map / unordered_set

📒 unordered_map / unordered_set

🔍 들어가기에 앞서...

• 해시 테이블에 대해 먼저 알아야 한다. 아래 링크는 해시 테이블에 대한 정리이다.
• https://velog.io/@liz/%ED%95%B4%EC%8B%9C-%ED%95%B4%EC%8B%9C-%ED%85%8C%EC%9D%B4%EB%B8%94Hash-Table
  
  

📌 unordered_map이란?

• 표준이 아닌 hash_map에서 unordered_map이라는 이름으로, 표준으로 정의 되었다.
• hash_map보다는 unordered_map 사용을 권장한다. (hash_map은 성능이 보장되지 않기 때문)
• 연관 컨테이너 기반으로, map과는 다르게 정렬되지 않은 상태로 자료를 보관한다.
• 입력받은 자료를 해시 함수를 통해 테이블 형태로 저장한다.
• map과 동일하게 const key, value의 형태로 자료를 저장한다.
  
  

📌 unordered_map의 특징

• 해시 테이블로 구현하여 탐색 시간 복잡도는 O(1)이다. (충돌이 없다는 가정하에)
• 중복된 데이터를 허용하지 않는다.
• 각각의 key 값을 해시 함수를 통해 고유한 index로 변환하여 buckets[index]에 저장하게 되는데, index 값이 많을 시(해시 충돌) 성능이 떨어지게 된다.
  
  

📌 unordered_map의 멤버 함수와 연산자

• https://learn.microsoft.com/ko-kr/cpp/standard-library/unordered-map-class?view=msvc-170
  
  

📌 unordered_set이란?

• 표준이 아닌 hash_set에서 unordered_set이라는 이름으로, 표준으로 정의 되었다.
• hash_set보다는 unordered_set 사용을 권장한다. (hash_set은 성능이 보장되지 않기 때문)
• 연관 컨테이너 기반으로, set과는 다르게 정렬되지 않은 상태로 자료를 보관한다.
• 입력받은 자료를 해시 함수를 통해 테이블 형태로 저장한다.
• set과 동일하게 const key의 형태로 자료를 저장한다.
  
  

📌 unordered_set의 특징

• 해시 테이블로 구현하여 탐색 시간 복잡도는 O(1)이다. (충돌이 없다는 가정하에)
• 중복된 데이터를 허용하지 않는다.
• 각각의 key 값을 해시 함수를 통해 고유한 index로 변환하여 buckets[index]에 저장하게 되는데, index 값이 많을 시(해시 충돌) 성능이 떨어지게 된다.
  
  

📌 unordered_set 멤버 함수와 연산자

• https://learn.microsoft.com/ko-kr/cpp/standard-library/unordered-set-class?view=msvc-170
  
  

⛳ 마치며...

• unordered_map과 unordered_set은 모두 해시 테이블로 구현되어 있기 때문에 특징이 유사하다.
• 그러나 unordered_map은 데이터를 key와 value 쌍으로 이루어 저장하고, unordered_set은 key 값 자체가 하나의 데이터이다.