해시 맵이 할 수있는 일이 있습니까?

해시 맵과 맵의 차이점은 hashmap이 해시 함수로 구현되지만 맵은 트리로 구현된다는 점만 알고 있습니다. 어떤 몸이라도 더 추가 할 수 있을까요?해시 맵이 할 수있는 일이 있습니까?

이것을 바탕으로 hashmap이 할 수있는 일이 있습니까?

2010-03-30 skydoor

비슷한 종류 일 수도 있지만 속지는 아닐 수도 있습니다. http://stackoverflow.com/questions/2196995/is-there-any-advantage-of-using-map-over-unordered-map-in-case-of -treevial-keys/ – GManNickG

용어에 약간주의하십시오. 일부 서클에서 "지도"는 키/값 저장 및 조회를 수행하는 객체를 가리키며 "해시 맵"은지도의 구현 중 하나입니다. (트리 맵이 다른 트리 맵일 수 있습니다.) IOW, "map"은 인터페이스이고, "hash map"은 구체적인 구현 중 하나입니다. (질문은 특정 라이브러리로 태그 지정되거나 참조하지 않기 때문에이 점에 유의할 것입니다.) –

@Ben : C++의'map'에서 거의 모호하지 않게 트리를 참조합니다. – GManNickG

해시 맵은 평균 액세스 성능 (O (1))이 좋지만 최악의 성능 (O (n))이 있습니다. 지도는 항상 O (lg (n))입니다.
지도는 키순으로 정렬되며, 해시 맵은 순서가 지정되지 않습니다.
해시 맵은 일반적으로 맵보다 많은 메모리를 사용합니다.
지도는 일반적으로 더 빠른 반복을 허용합니다.
좋은 해시 함수는 좋은 순서 기능보다 작성하기가 어렵습니다 (분석하기가 더 어렵습니다).

지도가 할 수없는 해시 맵이 할 수있는 일은 없다고 생각합니다.

출처

2010-03-30 00:24:28

해시 맵은 일반적으로 더 많은 메모리도 사용합니다. – GManNickG

IMO 해시 테이블에 대한 O (1) 클레임은 약간의 속임수입니다. 충돌 처리없이 별개로 인식되는 키 수에는 고정 된 경계가 있으며, 충돌이 발생하면 성능은 충돌 처리 (종종 O (n))의 성능으로 저하됩니다. 좋습니다. 해시는 전통적으로 메모리에 저장할 수있는 많은 고유 키를 지원합니다.하지만 많은 사람들이 32 비트에서 64 비트로 사용자 지정 해시 계산을 업그레이드하는 것을 소홀히하고 매우 큰 해시 테이블로 성능 저하를 일으키는 지 궁금합니다. 해시 자체가 너무 좁은 경우에는 크기 해시 테이블로 해결할 수 없습니다. – Steve314

@ 스티브 - 나는 O (1)이 평균적인 경우이고 O (n)이 최악의 경우라고 언급했다. @GMan - 고마워요, 제가 추가하겠습니다. –

지도에는 키가 약한 주문이 필요하며 이는 아마도 존재하지 않을 수도 있습니다. 해시 맵은 해시 함수 만 필요합니다. 따라서 이러한 방식으로 엄격한 약한 순서가없는 키와 함께 해시 맵을 사용할 수 있습니다.

출처

2010-03-30 01:09:37 rlbond

솔직히 나무와 해시 맵은 동일한 문제가 있습니다. 최근 필자는 finite automata를 키로 사용하여 해결해야만했던 문제입니다. 동등한 오토마타가 다른 표현을 가질 수 있기 때문에 메모리 내 표시의 해시 (또는 비교)를 수행 할 수 없습니다. 해결책은 정식 양식을 유도하는 것입니다. 정식 양식을 사용하면 비교 중이거나 해시 여부에 관계없이 메모리 내 표현에서 동일하게 작업 할 수 있습니다. 이는 모든 종류의 데이터에 적용됩니다. 해시 할 수 있다면 임의로 일관된 순서를 쉽게 정의 할 수 있습니다. – Steve314

해시 맵이 트리에 갖는 이점 중 하나는 멀티 스레딩 환경에서 단일 키를 추가하거나 제거하기 위해 전체 컨테이너를 잠글 필요가 없다는 것입니다. 해시 테이블에서 관련 항목 하나를 잠그면 거의) 충분히.

거의 업데이트하기 위해 메타 데이터 (예 : 해시 테이블에있는 항목 수)가있을 수 있기 때문입니다. 물론 전체 테이블을 잠 그거나 늘리려면 테이블을 잠글 필요가 있습니다.

출처

2010-03-30 01:14:23 Steve314

해시 맵이 할 수있는 일이 있습니까?

답변

관련 문제