자료구조(Map, Set, HashTable)

1. 맵(Map)

맵이란 key 와 value 가 매칭 되는 것을 매핑이라고 하는데, 이러한 매핑을 통해 키와 값이 하나의쌍으로 연결되어 키를 통해 값에 접근할 수 있도록 만들어진 자료구조를 맵이라고 합니다. 순서 보다는 정의된 이름(key)과 상응하는 데이터들을 묶기 위한 자료구조라고 할 수 있습니다.

맵의 특성:

Key값은 중복 될 수 없다. Value는 중복 될 수 있다. 순서를 보장하지 않는다.

맵의 장점:

key를 통해 value를 얻어내기 때문에 어떤 값을 찾을 때 평균 O(1)의 속도로 찾을 수 있다. 뛰어난 검색 속도를 가집니다.

맵의 단점:

순서가 없다. (단 정렬은 가능)

맵에 사용하는 함수

맵을 사용한 자료구조의 종류

1. HashMap

• Key 에 대한 중복이 없고, 순서를 보장하지 않는다.
• Key 와 Value 값으로 NULL을 허용한다.
• 동기화가 보장되지 않는다.
• 검색에 가장 뛰어난 성능을 가진다.

---

자바에서 map 관련 함수

put(key,value) 값 넣기

get(key) 값 읽기

 

파이썬에서 map관련 함수들(딕셔너리)

keys() - 키 리스트 만들기

values() - 밸류 리스트 만들기

items() - 키와 밸류를 튜플로 묶은 값을 dict_items 객체로 돌려준다.

clear() 모든 요소를 삭제한다.

get(key) - value얻기, 잘못입력시 none 값을 반환

 

## HashTable

• 동기화가 보장되어병렬 프로그래밍이 가능하고 HashMap 보다 처리속도가 느리다.
• Key와 Value 값으로 NULL 값을 허용하지 않는다. (뒤쪽에 자세히)

1. LinkedHashMap

• 입력된 순서를 보장한다.

1. TreeMap

• 이진 탐색트리(Red-Black-Tree)를 기반으로 키와 값을 저장한다.
• Key와 Value를 기준으로 오름차순 정렬하고 빠른 검색이 가능하다.
• 저장 시 정렬을 하기 때문에 시간이 다소 오래걸린다.

셋(Set)

셋 이란 집합형 자료구조이며, 순서가 없고 중복된 데이터가 들어갈 수 없는 자료구조 입니다.

장점: 빠른 속도 단점: 단순 집합의 개념으로, 정렬하려면 별도의 처리가 필요하다. (Iterator 사용해서

• Set 관련 메소드

add(value) - 값추가

remove(value) 값 삭제- 제거하려는 값이 없으면 오류발생

discard() - 값 삭제 -> 제거하려는 값이 없으면

size() - 셋의 크기 구하기

pop() - 랜덤으로 한가지의 값 빼오기( 순서가 없기 때문에 랜덤으로 출력됨 )

셋을 이용한 자료구조

1. HashSet
   • 순서 x,
   • null값도 허용
   • 중복 허용 x

• 중복을 걸러내는 과정: 객체의 hashCode() 메소드를 호출 -> 해시코드 얻어냄 -> 저장되어있는 객체들의 Hash코드와 비교한뒤 같은 해시코드가 있다면 ->equal() 메소드로 비교 -> ture 반혼시 동일한 객체로 판단하고 중복 저장하지 않음.

---

1. LinkedHashSet HashSet과 동일한 구조를 가지지만 HashSet은 순서를 관리하지 않아 값을 출력할 때마다 다른 순서대로 출력이 됩니다. 하지만 링크드해쉬셋은 삽입된 순서대로 반복합니다. 중복값 허용 x
2. TreeSet 중복 x 저장순서 x 레드 블랙 트리로 되어있음 데이터를 정렬해줌

해시테이블(HashTable)

해시 테이블은 Key, Value 로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조입니다.

빠른이유?

내부적으로 Bucket 을 사용하여 데이터를 저장하기 때문입니다. 각각의 고유한 Key 값에 해시함수를 적용해 고유한 index를 만들어내고, 버킷배열의 index에 값을 저장해서 검색 속도를 높였습니다.

해시값이 충돌하는 경우는?

충돌에 의한 문제를 분리연결법(Separate Chaining) 과 개방 주소법(Open Addressing) 으로 크게 2가지로 해결하고 있습니다. 정확한 내용은 모름.

해시테이블의 시간 복잡도

각각의 key값은 해시함수에 의해 고유한 index를 가지게 되어 바로 접근할 수 있으므로 평균 O(1)의 시간 복잡도로 데이터를 조회 할 수 있습니다. 하지만 데이터 충돌이 발생한 경우 연결된 리스트까지 검색해야 하므로 O(N)까지 시간 복잡도가 증가할 수 있다.

해시맵(HashMap) vs 해시테이블(HashTable)?

키워드: 동기화, 병렬처리

해시맵은 동기화를 지원하지 않지만 해시테이블은 동기화를 지원합니다. 그러므로 병렬 처리를 하면서 지원의 동기화를 고려해야하는 상황이라면 해시테이블을 사용하고 병렬처리를 하지않거나 자원의 동기를 고려하지 않는 상황이라면 해시맵을 사용하면 됩니다.