Hash와 Dictionary의 차이점은 무엇입니까?
스크립팅 배경에서 왔기 때문에 비슷하다고 생각하지만 정확한 차이점을 알고 싶었습니다. 인터넷 검색은 저에게별로 도움이되지 않았습니다.
답변
Hash 는 프로그래머가 인터페이스를 구현과 혼동 한 ( 너무 게으 르기 때문에 전체 이름을 쓸 수없는) 이름이 매우 낮은 데이터 구조입니다. 즉 HashTable 대신 약어 인 Hash)를 사용합니다.
Dictionary 는 인터페이스의 “올바른”이름 입니다 (= ADT ), 즉 (일반적으로 고유 한) 키를 고유하지 않은 값에 매핑하는 연관 컨테이너입니다.
해시 테이블은 다음과 같습니다. (런타임 측면에서) 상당히 우수한 액세스 특성을 제공하고 따라서 종종 기본 구현이되는 그러한 사전의 가능한 구현 하나 입니다.
이러한 구현에는 두 가지 중요한 속성이 있습니다.
- 키는 ha 여야합니다. shable 및 동등 비교 .
- 항목이 사전에 특정 순서로 나타나지 않습니다.
( be hashable은 배열에서 인덱스로 사용되는 키에서 숫자 값을 계산할 수 있음을 의미합니다.)
순서 를 부과하는 사전 데이터 구조의 대체 구현이 있습니다. em> on the keys – 이것은 종종 sorted 딕셔너리라고합니다 (그리고 다른 효율적인 구현이 존재하지만 일반적으로 검색 트리 관점에서 구현됩니다).
To 요약 : 사전 은 키를 값에 매핑하는 ADT입니다. 이 ADT의 가능한 구현은 여러 가지가 있으며 그 중 해시 테이블 이 하나입니다. Hash는 잘못된 이름이지만 문맥 상 해시 테이블 측면에서 구현 된 사전과 동일합니다.
댓글
- C ++로 예제를 제공하기 위해 표준 연관 컨테이너 템플릿은 해시로 구현할 수 없었습니다. ' 다음 표준에는 효과적인 해시 테이블이 포함될 것입니다. '
unordered_map라고 불리며 자신이 무엇을하는지 보여줍니다. - 무슨 권위? Ruby 및 Perl과 같은 일부 언어에서 공식 ( “올바른”이라고 읽음)은 이러한 구조의 이름이 “hash”입니다.
- @nohat : 따옴표를 사용했습니다. 게다가 왜 이름이 잘못 뽑혔는지 설명을 했어요. 그렇지 않나요? 따라서 권한이 필요한 경우 이론적 컴퓨터 과학 경찰의 권한이라고 말씀 드리겠습니다.
- 흥미롭게도 Ruby 1.9에서는 실제로 클래스는 해시 테이블을 사용합니다. Ruby 1.9
Hash는 삽입 순서를 유지하지만 해시 테이블은 유지하지 않습니다. 따라서 Ruby 1.9에서Hash라는 이름은 ' 더 이상 구현을 반영하지 않습니다. - @hippietrail 당신은 틀 렸습니다. 첫째, 그것들은 객관적인 설명입니다. 결국, 나는 이름이 형편없고 잘못된 이름 인 이유를 인정합니다 (아래 참조). “너무 게으르다”는 것은 예술적 라이선스이지만 이름을 줄여야하는 이유는 본질적인 것입니다. 즉, 이름을 줄이는 것 외에는 닉네임을 사용할 이유가 없습니다. 그리고 “사전”에 대해 잘못 알고 있습니다. 이는 단순히 데이터 구조의 공식 이름 입니다. 컴퓨터 과학의 맥락에서 “사전”에 대한 정의는 잘못되었으며 이름은 Python보다 수십 년 이전입니다.
Answer
“사전”은 개념의 이름입니다. 해시 테이블은 가능한 구현입니다.
댓글
- 해시는 ADT이기도합니다. HashTable은 Hash의 구현입니다.
- @Sairam ' hash '가 의미하는 것이 훨씬 더 일반적이라고 생각합니다. 해시 테이블이 아닌 해시 함수입니다.
- @jk 실제로 " 해시 "는 일부 입력에 대한 " 해시 함수 / 알고리즘 ". " 해시 테이블 " 또는 " 해시 맵 " omehoe는 일부 개체 (OOP에 국한되지 않는 일반 형식의 개체)와 관련되고 해시 가능한 개체를 연결합니다.
- ' 해시 '는 해시 함수 연산이 아닌 사전 유형 구조를 참조합니다. 예 : Ruby .
Answer
사전은 빠른 조회 / 삽입에 사용되는 모든 데이터 구조 구현에 대해 주어지는 총칭입니다. 이것은 해시 테이블, 스킵 목록, rb 트리 등과 같은 다양한 데이터 구조를 사용하여 달성 / 구현 될 수 있습니다. 해시 테이블은 사전 구현을 포함하여 여러 목적에 유용한 특정 데이터 구조입니다.
코멘트
코멘트
- 해시는 ADT이기도합니다. Hash와 Dictionary ADT간에 특별한 차이가 있습니까?
- @Sairam : 아니요, 해시는 특정 알고리즘 (해시 함수)의 출력입니다.
답변
사전 는 키를 사용하여 연관 배열 내부의 값을 직접 참조합니다.
즉 (KEY => VALUE)
해시 는 종종 해시 테이블 : 해시 함수 를 사용하여 계산 값이있을 메모리 (또는 더 쉽게 배열)의 위치. 해시는 KEY를 입력으로 사용하고 값을 출력으로 제공합니다. 그런 다음 해당 값을 메모리 또는 배열 인덱스에 연결합니다.
ie KEY => HASH FUNCTION => VALUE
하나는 직접적이고 다른 하나는 그렇지 않습니다. 해시 함수도 완벽하지 않을 수 있으며 때로는 잘못된 값을 참조하는 색인을 제공 할 수 있습니다.하지만 수정 될 수 있습니다.
가장 좋은 위치 : Wikipedia ( 연관 배열 및 해시 테이블 )