Coding StudyRoom

C++ 에서 제공하는 map은 데이터를 정렬하여 저장. unordered_map은 정렬을 하지 않고 저장. unordered_map의 자료구조는 "해시 테이블"이다. : 좋은 경우 탐색 시간복잡도 O(1)이다. hash_function("key") : 해시함수에 key값을 대입하면 해시 테이블의 인덱스를 반환해줌 -> 이러한 인덱스를 가지고 배열로 구성된 hash table의 value 값에 상수시간 내에 접근가능. #include 선언 C++ STL 이기 때문에 using namespace std; 생성 unordered_map 변수명; ex) unordered_map um; 1. 삽입 insert( {key, value} ) , insert(make_pair(..

HashTable이란? - >> Key값과 Value 값으로 데이터를 저장하는 자료구조. 내부적으로 배열을 이용하여 구현하기 때문에 빠른다. (상수 시간내에 찾을 수 있다.) Key 값을 해시 함수에 매개변수로 입력하여 Value 값이 저장된 배열의 인덱스 값을 찾는다. ex) hash_function(Key) --> return index array[index] = Value 해시 함수에서 중요한것! 고유한 인덱스 값을 설정하는 것이 매우 중요 즉, 해시 함수 구현이 중요하다. - 해시 함수는 주로 해시 테이블의 크기로 모듈로(%) 연산을 사용한다. 이 외에도 다양한 방법 가능. ** 해시 값이 충돌하는 경우 ** 해시 값이 충돌할 때 해결 방안 Separate Chaining 버킷에 Value만 저장..