hash 맵과 일반 어레이의 차이점은 무엇인가요?

computetime의 이미지

요즘 많이들 해시 테이블을 사용하고 계신데

해시 테이블과 일반 array의 차이점을 알고 싶어서요

저는 해시 알고리즘이 해시펑션에 많이 의존적이어서 동일한 해시 펑션을 사용했을때

일반 어레이나 해시 테이블을 썻을경우에 성능차이가 별로 없을거라고 생각했는데요

요즘에 찾다보니까 동일한 해시 펑션을 써도 해시 테이블과 vector 에서의 성능차이가 있다고 해서요

정확하게 알고 싶어서 질문드려요

예를들어서

데이터 - 해시 펑션 - 인덱스 펑션 - 해시 테이블 의 구조하고
데이터 - 해시 펑션과 비슷한 펑션 - 어레이 순서에 맞춰주는 인덱스 펑션 - vector 하고 비교해 봤을때

두개의 차이가 크게 나나요?

요약하자면 해시 알고리즘에서 해시 펑션을 제외한 알고리즘하고 vector 하고 성능차이가 나는지 알고 싶어요.

jick의 이미지

Array는 데이터를 0에서부터 *순서대로 번호에 맞춰서* 집어넣는 용도이고 hash table은 key값에 따라 해당하는 데이터를 기억하는 용도이니 완전히 쓰임새가 다르죠.

예를 들면 해시테이블에서 "key 3에 해당하는 값이 있는가?"는 O(1) 연산이지만 array나 벡터에서는 아예 키값의 개념이 없으니 처음부터 끝까지 다 비교해 봐야 하는데 그러면 O(N)이 되겠죠.

혹은 벡터에서 "3번째 원소의 값은?"은 (당연히) O(1) 연산이지만 hash table은 원소를 순서대로 넣는 게 아니니 "3번째 원소"라는 질문 자체가 성립하지 않습니다.

stypr의 이미지

.

Necromancer의 이미지

해쉬테이블은 데이터를 저장소에 저장할 때 키가 되는 정보를 해쉬해서 저장할곳의 위치를 정합니다.
만일 해쉬 충돌나서(키는 다른데 해쉬값이 같음) 한곳에 2개 이상 데이터가 들어가야 된다면 그 위치에 array로 저장.

근데 해쉬 충돌은 고의로 그러지 않는 이상은 매우 드뭅니다. 해쉬만 한번하면 대부분 찾고, 만일 2개 이상 있으면 array 2~3번이면 끝.

디스크에서는 엄청나죠.

Written By the Black Knight of Destruction

gosuchoi의 이미지

hash table은 키를 이용하여 빠른 접근은 O(1)으로 vector에 비하면 빠릅니다. 물론 hash function이 잘 디자인되어서 충돌이 0에 가깝다는 가정에서 하는 얘깁니다. 하지만 모든 데이타를 순차적으로 접근하는 것은 array에 비하면 훨씬 느립니다.
array 나 vector는 인덱스를 이용해서 접근하는 것은 이론적으로는 O(1)으로 hash나 같지만, hash fcuntion을 거치지 않으므로 훨씬 빠릅니다. 또 순차적인 접근도 빠릅니다. 하지만 키 값을 찾는 것은 소팅이 되어 있지 않으면 순차적으로 해야 하므로 아주 느립니다.
학급의 학생들을 번호를 이용하면 접근하는 것은 array가 좋겠지만, 이름으로 정보에 접근하는 것은 hashing이 빠르겠지요.

shint의 이미지

기억으로는 결과가 엉터리 일 수 있습니다.
확실한건.
배열이 가장 빠릅니다.
vector는 빠르지만. 중간 삽입삭제가 안되서. deque를 사용하면 편합니다.
그렇지만. 빠르려면. map을 사용하는데
Visual Studio 6.0 에서는 STL Port 5.2 가 가장 빠릅니다.
Visual Studio 2008 이후? 부터. ATLMAP이 가장 빠릅니다.

중간에 삽입 삭제. 사용을 하지 않는 경우.
배열 > vector > ATL MAP > STL Port 5.2 > map. deque. list

중간에 삽입 삭제가 가능한 경우.
ATL MAP > STL Port 5.2 > map. deque

테스트 안해본 경우
- 이중 링크드 리스트 : 제가 만든건 오히려 더 느렸습니다.
- boost map

----------------------------------------------------------------------------
젊음'은 모든것을 가능하게 만든다.

매일 1억명이 사용하는 프로그램을 함께 만들어보고 싶습니다.
정규 근로 시간을 지키는. 야근 없는 회사와 거래합니다.

각 분야별. 좋은 책'이나 사이트' 블로그' 링크 소개 받습니다. shintx@naver.com