[Hashing] 해쉬를 핵심만 정리해보자

 해쉬 테이블 (hash table)

• key,value 로 데이터를 저장하는 자료구조 , 정말빠르게  O(1)으로 자료를 검색할 수 있는 기적의 구조
  • (어떻게 검색을하길래?) 내부적으로 배열(버킷) 을 사용하여 데이터를 저장해서.

해쉬 한눈에 확 (출처:https://mangkyu.tistory.com/102 )

• 해쉬 함수는 고유의 KEY값에 따라 Value(bucket)에 전달해주는데 이를 이용해 암호학(내부 해쉬 함수가 어떻게 생긴지 모르니 밖에서는 고유 key값으로만 내부에 접근할수있는 원리) 에도 사용!!
• 근데 만약 두개 다른  key가 같은 value를 지칭하게 된다면? -> 충돌. 이를 해결하기위해 체이닝(chaining기법을 사용)

value가 같게되면 저기 꼬리처럼 뒤로 이어져(linked list사용) ( 출처: https://twinparadox.tistory.com/518)

• 체이닝의 장점: 

1.  탐색 저장 삭제시 연결리스트(linked list)에서 독립적으로 수행 -> 오버플로우가 발생해도 시간이 효율적

2.  연결 리스트로 구현하여 메모리 낭비없음

• 체이닝 단점:

1. 해시값들이 한쪽으로 쏠림현상이 발생할 수 있음. 이에 시간복잡도는 O(N)으로 됨

---

기본 c++ 문법들(STL로 간다!)(해쉬테이블과 해쉬맵은 비슷하나 해쉬맵은 비동기화 테이블은 동기화일때 사용된다함)

• 선언: unordered_map<int,int> hashmap  %정렬되지않은 해쉬맵생성 ( unordered_set은 key 값만 가진다.)
• 추가: hashmap[key]= value 혹은 hashmap.insert({key,value}) % key를 인덱스라고만 생각하면 안됨, 빨리 찾고자하는것을 넣어라
• 탐색: hashmap.find(key) % key 가 hashmap에 있으면  key가 위치한 iteration반환 , 없다면 hashmap.end() 반환 
• 삭제: hashmap.erase(key)