배열을 사용하여 해시 테이블을 구현해야합니까?

배열을 사용하여 해시 테이블을 구현해야합니까? 대체 데이터 구조가 동일한 효율성을 달성합니까? 그렇다면 왜? 그렇지 않다면 배열이 제공하는 것과 동일한 효율성을 보장하기 위해 데이터 구조가 만족해야하는 조건은 무엇입니까?배열을 사용하여 해시 테이블을 구현해야합니까?

출처

2012-09-03 psyko666

배열을 사용하여 해시 테이블을 구현해야합니까?

아니요. 인터페이스는 arrray와 다른 다른 데이터 구조와 함께 구현할 수 있습니다. 예 : 레드 - 블랙 트리 (자바의 TreeMap).
이것은 액세스 시간이 O(logN)입니다.
그러나 Hash Table은 액세스 시간이 O(1) (가장 좋은 경우 - 충돌 없음) 일 것으로 예상됩니다.
이것은 일정한 시간에 임의 접근의 가능성을 제공하는 배열을 통해서만 달성 될 수 있습니다.

어레이가 제공하는 효율성을 보장하기 위해 데이터 구조가 만족해야하는 조건은 무엇입니까?

배열과 비교할 때 성능이 비슷해야합니다 (O(N)). treemap은 O(logN)입니다. 에 대한 최악의 액세스 시간은 모두입니다.

출처

2012-09-03 15:54:40 Cratylus

해시 테이블은 비교 기반 매핑과 완전히 다른 주장입니다. 이러한 차이점은 이론적으로나 후드 에서뿐만 아니라 키 요구 사항과 관련이 있습니다. 해시 테이블에는 해시 함수와 평등이 필요하며 다른 해시 테이블에는 전체 순서가 필요합니다. – delnan

@delnan : OP.My 관점을 해석하는 방법에 따라 'HashTable'은'Dictionary' 데이터 구조의 구현/확장입니다. 그것은'Dictionary'의 인터페이스를 제공합니다. 추상 데이터 구조는 다양한 구현 예를 가질 수있다. 배열이나 TreeMap에 의해 뒷받침되는'HashTable'을 의미합니다. * 당신이 * yes *를 제안 할만큼 엄격한 정의를 취한다면, * 해시 함수를 의미하는'HashTable'은 배열에 의해서만 지원 될 수 있습니다 – Cratylus

답장을 보내 주셔서 감사 드리며 늦게 답변을 드려 죄송합니다. 언제든지 stackoverflow에서 다시 확인하는 것을 잊어 버렸습니다. 다시 한 번 감사드립니다. – psyko666

배열을 사용하여 해시 테이블을 구현해야합니까?

답변

관련 문제