용어 정리

1. 키 값: 원본 데이터 값
2. Hash Function : (DAT에 넣기 위해) 값을 변환해주는 함수
3. Hash Code : 변환을 거쳐 인덱스로 사용할 수 있는 값
4. 버켓 : 값을 담는 곳

---

Hash란?

값(키 값)을 바로 인덱스로 저장하지 않고 변환하는 과정(Hash function)을 거쳐서 해시코드로 DAT로 저장해주는 방법

• 값을 빨리 찾기 위한 저장방법의 일종
• BST의 경쟁 상대
• Hash Code를 구하는데 걸리는 시간 : O(문자열 길이) => O(1)
• 값을 Hash에 등록할 때 걸리는 시간 : O(문자열 길이) => O(1) 확실!
• 값을 검색할 때 걸리는 시간 : O(문자열 길이) => O(1) 확실!
  (속도 부분은 대충 들어서 정확X, 공부 필요..)
• DAT의 단점을 보완

DAT 저장방식의 단점
: 값을 인덱스로 저장하는 것이므로, 음수값이나, 엄청 큰 값, 문자열은 저장이 어렵다.

---

Hash의 원리

(면접 출제 가능)

• DAT를 저장 방식을 이용하는데, DAT의 단점을 보완하기 위해 값에 적절한 처리를 해준 후 DAT방식으로 저장한다.
• 적절한 처리란? DAT에 저장가능한 값으로 변환하는 함수(change)를 거치는 것
• change함수를 거쳐 해시코드 값을 얻고, 그 값으로 DAT에 저장을 해준다.

만약, 해시테이블을 직접 구현한다면..? (원리만 이해하고 넘기기)
1. 음수값 : 인자를 넣을 때 unsigned를 붙여서 음수를 매우 큰 양수값으로 변환한다.

(unsigned int key)

2. 큰 숫자 : 모듈러(%)를 이용하거나 모듈러를 이용한 수식으로 값을 줄여 저장한다. (원래값을 식별하기 위해 키값도 저장해줘야 한다.)
3. 문자열 : for문을 돌려서 아스키코드값의 총합%50을 해시코드값으로 정하는 등.. Hash Function을 만들어 숫자값으로 변환해 저장해줘야 한다.

=> STL로 간편하게 사용 가능

---

STL로 Hash 사용하기

= unordered_map

• 해시는 매우 빠른 속도이므로, 대부분의 경우에 내장되어 있다.
• DAT / Hash는 쓸 수 있는 상황이 되면 무조건 쓰자.
• C++또한 STL에서 Hash를 사용할 수 있다.
• 자바에서 Hash : hash map
• C++에서 Hash : unordered map
• map의 의미 : 키값과 해시코드값이 매핑되어 있다는 의미.. (내 생각)

사용법
1. uno라고 치면 나오는 헤더파일을 삽입

#include <unordered_map>

2. 선언

• 의미 : string을 인덱스로 해서 버켓에 어떠한 값을 저장하는데, 그 값이 int형이다.
• 주의 : 키값(왼쪽에 들어갈 값)에 사용자 정의 데이터?(구조체) 사용불가

unordered_map <string, int> um;

3. 값 검색 방법 : count 메소드 사용

if(um[str] == 1) cout << "발견";

이렇게 배열처럼 해시값을 검색하면 등록돼버림
그래서, 이렇게 검색하면 안되고

if(um.count(str) > 0) cout << "발견";
else cout << "미발견";

이렇게 count 메소드 를 써서 검색해줘야 함

• 해시를 배열처럼 사용할 때는 값을 등록할때만이다!!

• 검색은 반드시 count 를 쓴다는 것 기억

(count 메소드 : 범위안의 원소들 중, 특정값과 일치하는 원소의 개수를 센다.
<algorithm> 헤더 필요, 관련 링크 )

---

Hash 연습 문제1

• 문자열을 인덱스로, 값을 숫자로 저장한 뒤,
  문자열을 입력받아 해당 문자열 위치에 저장된 숫자값이 있는지 체크하는 문제

#include <iostream>
#include <unordered_map>
using namespace std;

unordered_map<string, int> um;

int main() {
	um["BTS"] = 1;
	um["KFC"] = 2;
	um["BBQ"] = 3;
	um["QQQ"] = 4;

	string str;
	cin >> str;

	if (um.count(str) > 0) cout << "발견";
	else cout << "미발견";

	return 0;
}

---

Hash 연습 문제2 : 가장 많이 등장한 숫자 찾기

#include <iostream>
#include <unordered_map>
using namespace std;

unordered_map<int, int> um;

int main() {
	int arr[8] = { -7,5,3,2,-5,-7,-9,-7 };
	int max = 0;
	int maxNum = 0;

	for (int i = 0; i < 8; i++) {
		um[arr[i]]++;
		if (um[arr[i]] > max) {
			max = um[arr[i]];
			maxNum = arr[i];
		}
	}

	cout << maxNum; // 가장 많이 등장한 숫자

	return 0;
}

---

Hash 출력 : 해시에 저장된 것을 전부 출력하는 방법

=> iterator를 쓰면 됨.(auto, begin, end)

• 출력할 때는 i안의 first(키값: 실제 숫자값, 접근 인덱스), second(버켓 안에 들어가 있는 값: 숫자의 개수)를 포인터로 접근해서 출력할 수 있음.
• iterator 사용방법 잘 익혀놓기

#include <iostream>
#include <unordered_map>
using namespace std;

unordered_map<int, int> um;

int main() {
	int v[10] = { -5,-5,-3,4,1,4,-3,-5,-5,-5 };
	for (int i = 0; i < 10; i++) {
		um[v[i]]++;
	}

	for (auto i = um.begin(); i != um.end(); ++i) { // ++i가 더 속도가 빨라서 쓰는 것임
		cout << i->first << " : ";
		cout << i->second << endl;
	}

	return 0;
}

---