[Hashing] 해쉬를 핵심만

해시 테이블

• 키와 값으로 매우 빠르게 데이터를 저장하는 데이터 구조 오(1)검색할 데이터를 위한 기적의 구조
  • (어떻게 검색하시나요?) 내부적으로 배열(버킷)을 사용하여 데이터를 저장합니다.
    
    

• 해쉬함수는 고유한 KEY 값에 따라 Value(Bucket)에 전달되며, 암호화(내부는 고유한 키 값으로 외부에서만 접근할 수 있다는 원칙, 우리는 무엇을 알 수 없기 때문에)에도 사용됩니다.
  
  내부 해시 함수는 다음과 같습니다)!
  !
  
• 그러나 두 개의 다른 키가 동일한 값을 참조한다면 어떻게 될까요? -> 충돌. 이를 해결하려면 연결(연결 기술 사용)

• 연결의 이점:

1. 조회 및 삭제 시 연결 리스트에서 독립적으로 수행 -> 오버플로 발생 시에도 시간 효율적

2. 연결된 목록으로 구현, 메모리 낭비 없음

• 연결 단점:

1. 해시 값이 편향될 수 있습니다.

이 때문에 시간복잡도는 에)~이 되다

기본 C++ 구문(STL로 이동!
)(hashtable과 hashmap은 비슷하지만 hashmap은 비동기이며 테이블은 동기화될 때 사용됨)

• 선언: unordered_map hashmap %는 정렬되지 않은 해시맵을 생성합니다(unordered_set에는 키 값만 있음).
• 추가됨: hashmap(key)= value or hashmap.insert({key,value}) % 키를 인덱스로만 생각하지 말고 빨리 찾고 싶은 것을 입력하세요.
• 검색: hashmap.find(key) % 키가 해시맵에 있으면 true, 그렇지 않으면 false
• 지우기: hashmap.erase(key)