[CS] HashTable & Set & Map에 대해

Set

집합

순서가 없다. 집합이므로 중복된 데이터가 들어갈 수 없다.

중복되지 않는 숫자(데이터)를 구할 때 사용하면 유용하다.

순서가 없고, 중복을 허용하지 않는다

• HashSet
  • 순서를 보장 하지 않는 set
• TreeSet
  • Binary Search Tree 구조
  • 추가와 삭제에는 시간이 좀 더 걸리지만, 정렬 및 탐색에 성능이 좋음
  • 오름차순으로 데이터를 저장

TreeSet<Integer> set1 = new TreeSet<Integer>();//TreeSet생성

 

Map

Key와 Value로 이뤄진 데이터의 집합

Key의 중복은 허용되지 않고, Value의 중복은 가능하다.

 

• HashMap
  • 순서를 보장하지 않는 map, Key와 Value로 null이 허용된다.
• HashTable
  
  • 동기화를 지원하는 map, Key와 Value로 null이 허용되지 않는다.
• TreeMap
  • Binary Search Tree 구조의 Map
  • 오름차순으로 데이터를 저장
  • 정렬된 상태로 Map을 유지해야 하거나 정렬된 데이터를 조회해야 하는 범위 검색이 필요한 경우 TreeMap을 사용하는 것이 효율성면에서 좋다

TreeMap<Integer,String> map1 = new TreeMap<Integer,String>();//TreeMap생성

List & Set & Map의 차이

• List는 기본적으로 순서대로 데이터가 들어가며 중복을 허용한다.
• Set은 순서가 보장되지 않고 중복을 허용하지 않는다.
• Map은 순서가 보장되지 않고, Key 중복은 허용하지 않지만 Value의 중복은 허용된다.

 

Hashing

임의의 길이의 값을 해시함수(Hash Function)를 사용하여 고정된 크기의 값으로 변환하는 작업을 말한다.

하나의 문자열을 원래의 것을 상징하는 더 짧은 길이의 값이나 키로 변환하는 것

HashTable

해시함수를 사용하여 변환한 값을 색인(index)으로 삼아 키(key)와 데이터(value)를 저장하는 자료구조를 말한다.

HashMap과 차이점은?

• Hashtable은 key에 null을 허용하지 않지만, HashMap은 key에 null을 허용합니다.

key의 해시 처리 한 뒤 해시로 인덱싱을 완리하여 버킷에 저장하는 구조

 

해시함수(Hash Function)의 입력값은 "John Smith"이고 출력값은 "02"이다. 그리고 색인이 "02"인 bucket에서 "521-1234"을 찾는다.

 

그런데 만약 "John Smith"를 해시 함수를 돌려 나온 값과 "Lisa Smith"를 해시 함수를 돌려 나온 값이 동일하다면 어떻게 해야 할까? ==> 해시 충돌(Hash Collision)

 

분리 연결법(Separate Chaining)

버켓 내에 연결리스트(Linked List)를 할당하여, 버켓에 데이터를 삽입하다가 해시 충돌이 발생하면 연결리스트로 데이터들을 연결하는 방식

 

Sandra Dee라는 사람의 연락처를 삽입할 때, 충돌이 일어나니 버켓 내에서 연결리스트로 데이터를 연결하는 것을 확인할 수 있다.

 

개방 주소법(Open Addressing)

해시 충돌이 발생하면 근처 버킷에 자료를 저장하는 방식

 

John Smith가 152에 저장했는데 Sandra Dee가 152에 저장하려고 하자 근처인 153에 저장하는 모습

그 후 Ted Baker가 153에 저장하려니까 그 근처인 154에 저장

 

 

데이터 갯수가 적을 땐 Open Addressing, 데이터 개수가 많을 땐 Separate Chaining