[자료구조] 고급 자료구조 Set, Hash, HashMap, HashTable, 해쉬충돌, 해쉬함수 에 대해서

- Set은 Key로 되어있는 자료구조이다. 집합이기 때문에 중복된 데이터는 들어갈 수 없으며 순서가 없다.

- Map은 자료 탐색에 이진 탐색 트리를 사용한다. Map 역시 key와 value로 구성되어있지만 hash보다 느리다 (O(longN)), 또한 내부 데이터를 자동으로 정렬해 준다. 이 역시 key에는 중복된 값이 들어갈 수 없다.

- Hash Table : 해쉬테이블은 키(Key), 해시함수(Hash function), 해시(hash), 값(value), 저장소(bucket, slot)로 이루어져 있다.

- Hash function : 테이블을 입력으로 받아 데이터에 산술 연산을 수행하여 하나의 수를 반환하는 함수이다. 반환한 수는 데이터를 인출하기 위한 테이블의 인덱스로 사용할 수 있다.

- Hash는 1개의 Key와 1개의 Value가 서로 1:1로 pair되어있는 자료구조있다. 따라서 key를 이용하여 value를 도출할 수 있다. 해시 함수의 결과물이며 저장수(Bucket, Slot)에 값(Value)과 매칭되어 저장된다. 이 역시 key에는 중복된 값이 들어갈 수 없다. hash는 map과 다르게 저장된 내부 자료는 정렬되지 않는다.

- Hashing : key-value를 매핑시키는 과정 자체

- value : 저장소에 최종적으로 저장되는 값으로 키와 매칭되어 저장, 삭제, 검색, 접근이 가능해야 한다.

- Bucket : 하나의 주소를 갖는 파일의 한 구역을 의미한다. 버킷의 크기는 같은 주소에 포함될 수 있는 레코드 수를 의미한다.

- Slot : 1개의 레코드를 저장할 수 있는 공간으로, n개의 슬롯이 모여 하나의 버킷을 형성한다.

- Overflow : 계산된 메모리 공간에 버킷 내에 저장할 공간이 없는 상태  /  버킷을 구성하는 slot이 여러개 일떄는 collision이 발생해도 overflow가 발생하지 않을 수 있다.

- 테이블에서 자료탐색은 해싱을 사용하게 되는데 시간복잡도 O(1)이라는 굉장히 빠른 속도를 보장한다. 하지만 최악의 경우 O(n)이 된다. 이는 해시 충돌에 의해 발생되는 문제이다. 

해시 충돌

- Hash Collision : 해시 함수로 해시를 산출하는 과정에서 서로 다른 key가 같은 hash로 변경되는 문제가 발생될 때 이를 해시 충돌이라고 한다. 왜냐하면 key-value는 각각 1:1로 매칭이되어야 하는 규칙이 유배되었기 때문이다. 즉, 두 개의 입력이 하나의 출력값을 가질 수 없는데 이를 위배하여 두 개의 입력이 하나의 value를 공유한다면 이를 해시 충돌이라고 한다.

- 해시 충돌은 테이블의 각 항에 연결리스트를 두어 동일한 해시 값을 갖는 모든 항을 수록하게 한다. 충돌이 많을 수록 해시 함수의 효율이 떨어진다.

- 해시 충돌이 있음에도 해시 테이블을 사용하는 이유는 적은 리소스로 효율적으로 데이터를 관리하기 위해서이다.

• 검색 속도가 빠르다.
• 삽입, 삭제 작업이 O(1) 이기 때문에 이런 작업이 많을 때 유리하다.

- 해시 테이블의 단점

• 순서가 있는 배열에는 어울리지 않다.
• 공간 복잡도가 높다
• 해쉬 함수의 의존도가 높다.

- 이중해싱(double hasing) : 탐사할 해시 값의 규칙성을 없애버려서 clustering을 방지하는 기법

 

---

1. HashMap : Key-Value를 사용하여 Hash Table의 값을 찾는다. (자바 쓰임새)

HashMap<int, String> list = new HashMap<int, String>();
// HashMap<key데이터타입, value 데이터 타입> 데이터명

list.put(1, "DNF"); // index 0
list.put(2, "mabinogi"); // index1
System.out.println(lsit.size);
System.out.println(list.containsKey(1)); // list 안에 1번의 key값 문자 있는지 확인
System.out.println(list.get(2)); // key값 2인 value 출력 get 함수는 해쉬 테이블에 저장된 데이터를 확인할 수 있다. 키값을 넣어 리턴
list.remove(1); // key 1번 삭제 메소드 안에 키값을 넣어 리턴
list.clear(); //모두 제거
// hashTable의 기 값 번호는 "int hasCode()" 메소드를 활용하여 구현한다. 

 

2. HashSet : 중복해서 저장하지 않는 집합으로 사용할 수 있는 클래스 (자바 쓰임새)

Hash는 데이터에 순서가 없기 떄문에 순차적으로 읽어오기에 Iterator 반복자를 사용하여 데이터를 접근할 수 있다.

HashSet<String> set = new HashSet<String>();
// HashSet(타입 파라미터> 이름 = new HashSet<타입 파라미터>();
// String 타입만 저장 가능
set.add("DNF");
set.add("mabinogi");
set.add("Battle-Ground");
System.out.println(set.size());

Iterator<String> iter = set.iterator();
while(iterator.hasNext()){
	String stl = iter.next();
    System.out.println(stl);
}