해시테이블 / 맵(Map) / 셋(Set)

[ 목차 ]

 

해시테이블

- 해시테이블(Hash Table)은 키(Key)-값(Value) 쌍을 저장하는 자료구조로, 해시 함수(Hash Function)을 사용하여 특정 위치(Buckets)에 매핑한다.

- 해시(Hash): 데이터를 고정된 길이의 값으로 매핑한 결과.
- 해싱(Hashing): 데이터를 해시 값으로 변환하는 과정.
- 해시 함수(Hash Function): 데이터를 해시 값으로 변환하는 함수.

해시테이블의 특징

• 빠른 접근: 해시 함수로 인해 키를 기반으로 값을 빠르게 조회 가능.
• 중복 키 없음: 동일한 키를 허용하지 않음.
• 충돌 해결 필요: 다른 키가 동일한 해시값을 갖는 경우(충돌) 처리 방법 필요

충돌해결 방법

1. 체이닝(Chaining): 같은 해시값을 가지는 키들을 연결 리스트로 저장.
2. 개방 주소법(Open Addressing): 충돌 시 다른 빈 버킷을 찾아 저장.

 

해시테이블의 장단점

• 장점:
  • 검색, 삽입, 삭제가 평균적으로 O(1).
  • 대규모 데이터 처리에 적합.
• 단점:
  • 해시 함수의 품질에 따라 성능 저하 가능.
  • 메모리 사용량이 많아질 수 있음.

해시테이블 시간 복잡도

• 검색/삽입/삭제:
  • 평균적으로 O(1).
  • 최악의 경우 O(n) (모든 키가 동일한 해시값을 가질 경우).

 

자바에서의 해시테이블

• 자바의 Hashtable 클래스는 키-값 쌍을 저장하며, 동기화(synchronized)가 기본적으로 적용된 구현체이다.
• HashMap과 달리 멀티스레드 환경에서 안전하게 사용할 수 있지만, 단일 스레드 환경에서는 성능이 떨어질 수 있다.
• null 키나 값을 허용하지 않는다.

해시테이블 주요 메서드

 

 

사용예시 : 

 

 

---

맵(Map)

- 맵(Map)은 키(Key)-값(Value) 쌍으로 데이터를 저장하는 인터페이스이다.

- 삽입 시 자동으로 정렬되며, 이는 Red-Black Tree를 사용해 구현한다.

- 자바의 대표적인 맵 구현체는 HashMap, TreeMap, LinkedHashMap이 있다.

 

맵의 특징

• 빠른 데이터 접근: 키를 사용해 값에 빠르게 접근 가능.
• 키의 중복 불허용: 각 키는 고유해야 하며, 동일 키 추가 시 기존 값을 대체.
• 가변적 크기: 동적으로 크기가 조정됨.
• 유연한 구현체 선택: 정렬, 삽입 순서 유지 등 다양한 요구사항에 맞는 구현체 제공.

주요 맵 구현체

1. HashMap : 
   • 해시테이블 기반 구현체
   • 순서가 보장되지 않음
   • 빠른 검색과 삽입/삭제 제공
2. TreeMap : 
   • 이진 탐색 트리를 기반으로 정렬된 키 순서 유지
   • 키 검색, 삽입, 삭제가 O(log n)
3. LinkedHashMap : 
   • 삽입 순서를 유지
   • 해시테이블과 연결리스트를 결합한 구조

맵의 장단점

• 장점:
  • 키를 통해 빠르게 데이터 접근 가능.
  • 다양한 구현체를 통해 특정 요구사항에 맞게 선택 가능.
  • 동적으로 크기 조정 가능.
• 단점:
  • 메모리 사용량이 증가할 수 있음.
  • 해시 충돌 시 성능 저하 가능.
  • 정렬이 필요한 경우 구현체에 따라 추가 비용 발생.

 

맵의 시간 복잡도

• 검색/삽입/삭제:
  • HashMap: O(1) (평균), O(n) (최악 충돌 발생 시).
  • TreeMap: O(log n).
  • LinkedHashMap: O(1) (평균, HashMap과 동일 성능).

 

맵의 주요 메서드

 

---

셋(Set)

- 셋(Set)은 중복을 허용하지 않는 데이터 컬렉션으로, 고유한 요소만을 저장한다.

- 맵과 유사하게 자동 정렬되며, 메서드도 맵과 유사하다.

- 자바의 대표적인 셋 구현체는 HashSet, TreeSet, LinkedHashSet이다.

 

셋의 특징

• 중복 허용 불가: 동일한 값은 한 번만 저장 가능.
• 빠른 데이터 접근: 해시 기반 구조(HashSet)는 평균 O(1)의 접근 시간 제공.
• 정렬 지원: TreeSet은 자동으로 정렬된 상태 유지.
• 삽입 순서 유지: LinkedHashSet은 요소의 삽입 순서 유지.

주요 셋 구현체

1. HashSet :
   • 해시테이블을 기반으로 한 구현체.
   • 순서가 보장되지 않음.
   • 빠른 삽입, 삭제, 검색 제공.
2. TreeSet : 
   • 이진 탐색 트리를 기반으로 정렬된 순서 유지
   • 검색, 삽입, 삭제가 O(log n)
3. LinkedHashSet : 
   • 삽입 순서를 유지
   • 해시테이블과 연결리스트를 결합한 구조

 

셋의 장단점

• 장점:
  • 중복 제거 기능 제공.
  • 다양한 셋 구현체를 통해 특정 요구사항에 맞는 선택 가능.
  • 빠른 데이터 탐색(HashSet) 및 정렬(TreeSet) 지원.
• 단점:
  • 순서가 중요한 경우 제한적일 수 있음(HashSet).
  • TreeSet의 경우 O(log n)으로 성능 저하 가능.

 

셋의 시간 복잡도

• 검색/삽입/삭제:
  • HashSet: O(1) (평균), O(n) (최악 충돌 발생 시).
  • TreeSet: O(log n).
  • LinkedHashSet: O(1) (HashSet과 동일 성능).

 

셋의 주요 메서드

 

 

---

 

해시테이블, 맵, 셋의 비교

특징	해시테이블 (Hash Table)	맵 (Map)	셋 (Set)
데이터 구조	키-값 저장	키-값 저장	중복없는 값 저장
순서 보장 여부	순서보장 X	LinkedHashMap : 삽입 순서 보장	LinkedHashSet : 삽입 순서 보장
정렬 여부	없음	TreeMap : 키 정렬	TreeSet : 값 정렬
중복 허용 여부	키 중복 불가, 값 중복 가능	키 중복 불가, 값 중복 가능	값 중복 불가
주요 활통 사례	데이터 캐싱, 키-값 매핑	데이터 매핑, 정렬된 데이터 저장	중복 제거, 집합 연산

 

 

---

 

 

출처

https://jinhos-devlog.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EB%A7%B5-%EC%85%8B-%ED%95%B4%EC%8B%9C%ED%85%8C%EC%9D%B4%EB%B8%94#%F0%9F%92%A1%20%ED%95%B4%EC%8B%9C%2C%20%ED%95%B4%EC%8B%B1%2C%20%ED%95%B4%EC%8B%9C%20%ED%95%A8%EC%88%98%20%3F%3F-1

[자료구조] 맵(Map), 셋(Set), 해시테이블(Hash Table)

https://velog.io/@jiyaho/CS-%EC%9E%90%EB%A3%8C-%EA%B5%AC%EC%A1%B0%EC%9D%98-%EB%B6%84%EB%A5%98-%EB%B9%84%EC%84%A0%ED%98%95-%EC%9E%90%EB%A3%8C-%EA%B5%AC%EC%A1%B0-3-%EB%A7%B5-%EC%85%8B-%ED%95%B4%EC%8B%9C-%ED%85%8C%EC%9D%B4%EB%B8%94

[CS] 자료 구조의 분류 - 비선형 자료 구조 #3 (맵, 셋, 해시 테이블)

https://dev-get-jop.tistory.com/19

자료구조(Map, Set, HashTable)

https://joooootopia.tistory.com/13

Java Collection Framework :: 자바의 자료구조 (List, Set, Map)