hash_map, map 질문 드립니다.
hash_map 같은 경우 그럼 큰 공간을 미리 할당해 놓고 할당된 공간 안에 key값을 기준으로 value 값을 채워 넣어 준다.그럼 예를 들면 map.reserve(100);과 같은 개념일까요??메모리를 희생하여 CPU 연산 속도를 올린다는 의미가
- reserve : 큰 공간을 미리 할당(메모리 희생)
- 이사비용 감소 (미리 큰 공간을 할당하여 사용하므로 new ...() 과 같은 동작을 안해도 되므로) -> CPU 연산 속도 증가?
- key값을 알면 빠르게 찾을 수 있다. -> map은 이진 탐색 O(logN)으로 찾지만, hash_map은 hm[key] O(1) -> m[key]도 가능하지 않나요? 그럼 map도 키 값을 알면 O(1) 즉 빠르게 찾을 수 있게 되는 건가요?
답변 1
3
그럼 map도 키 값을 알면 O(1) 즉 빠르게 찾을 수 있게 되는 건가요?
-> NO. 맵은 바로 접근이 되는게 아니라 이진트리 기반이라 한참을 타고 가야 합니다.
hash 기법을 이용해서 key값을 추출하는 이유가 보안 때문인건가요?
-> NO. 여기선 그런 용도의 hash의 의미가 아닙니다. 해쉬 자체는 어떤 값을 변형해 일종의 '지문'을 추출하는 셈인데요. 그것을 이용해 빠르게 어떤 버킷(상자)에 있는지를 찾는 것이 핵심입니다.
메모리를 늘릴 수 록 성능이 좋아지는 의미가 키 값이 겹쳐질 확률이 적어져서 성능이 좋아지는 건가요? -> 키 값이 겹치면 빈 공간을 찾아 가야하니
-> 그것도 그렇고, 핵심은 '바로' 찾을 수 있는 것에 있습니다.
가령 상자를 1000개 마련하고, 어떤 숫자를 주더라도 1000으로 나눈 나머지를 해시값으로 사용한다 가정하면,
23123411 라는 숫자도 411번 상자에 있을거라 예상할 수 있겠죠. (물론 이때 값이 겹치면 조금 상황이 복잡해지고, 이를 해쉬 충돌이라 합니다)
문제집은 없나요 수업을 어떻게 들어야 할지 모르겠어요
0
114
2
동적배열 Vector의 push_back 함수에서 조건문 질문
0
76
1
디버깅할때 메모리보는법 단축키가 뭐죠??
0
93
1
113-충돌처리 강의에서 22:26 부근의 SetPos()를 적용해도 충돌되지 않고 뚫고 지나가게 됩니다.
0
89
1
SaveFile에서 크래시 발생하는 분들 체크해보세요
1
70
1
수업자료 확인 부탁드립니다.
0
106
3
explicit을 붙였을 때 빨간줄이 뜨는 이유가 맞는지 궁금합니다.
0
100
0
22강에서 구조체와 포인터로 설명해주셨는데 패딩의 경우는 어떻게 되나요?
0
89
2
리소스 매니저 강의 18분 부근
0
89
1
[Service강의] owner -> shared_ptr
0
80
2
C#에서 생성자 관련 질문
0
84
2
특정 조건에서만 함수를 반환할 때
0
91
2
스택 empty
0
105
2
섹션4 배열실습 질문입니다.
0
133
1
섹션3 '파일분할' 강의 질문입니다.
0
99
1
Defines.h의 DECLARE_SINGLE관련 질문입니다.
0
110
1
세션8 우선순위 큐 pop함수의 Predicate 적용 관련 질문이 있습니다.
0
182
3
섹션9 함수 포인터 관련 질문입니다.
0
137
1
exercise_A 번 문제 해결방법에 대한 질문.
0
150
1
[강의명: virtual 소멸자] 자식 클래스의 소멸자에도 virtual 을 붙이시는 이유가 궁금합니다
0
200
2
Scene과 SceneManager 강의 수강 중 키보드 입력 오류
0
149
1
Window API 강의 수강 중 LARGE_INTEGER 타입 변환 오류
0
198
3
섹션15 스마트 포인터 20:00 질문이요!
0
128
1
55강 수업자료 빌드를 하면 이상합니다.
0
133
1