인프런 커뮤니티 질문&답변
작성한 질문수
hash_map, map 질문 드립니다.
해결된 질문
작성
·
243
0
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
2
Rookiss
지식공유자
그럼 map도 키 값을 알면 O(1) 즉 빠르게 찾을 수 있게 되는 건가요?
-> NO. 맵은 바로 접근이 되는게 아니라 이진트리 기반이라 한참을 타고 가야 합니다.
hash 기법을 이용해서 key값을 추출하는 이유가 보안 때문인건가요?
-> NO. 여기선 그런 용도의 hash의 의미가 아닙니다. 해쉬 자체는 어떤 값을 변형해 일종의 '지문'을 추출하는 셈인데요. 그것을 이용해 빠르게 어떤 버킷(상자)에 있는지를 찾는 것이 핵심입니다.
메모리를 늘릴 수 록 성능이 좋아지는 의미가 키 값이 겹쳐질 확률이 적어져서 성능이 좋아지는 건가요? -> 키 값이 겹치면 빈 공간을 찾아 가야하니
-> 그것도 그렇고, 핵심은 '바로' 찾을 수 있는 것에 있습니다.
가령 상자를 1000개 마련하고, 어떤 숫자를 주더라도 1000으로 나눈 나머지를 해시값으로 사용한다 가정하면,
23123411 라는 숫자도 411번 상자에 있을거라 예상할 수 있겠죠. (물론 이때 값이 겹치면 조금 상황이 복잡해지고, 이를 해쉬 충돌이라 합니다)