은 연결된 목록처럼 구현 된 NSMutableSet입니까?

NSMutableSet의 요소에 무작위로 액세스 할 수 없으므로 링크 된 목록처럼 구현됩니까?은 연결된 목록처럼 구현 된 NSMutableSet입니까?

e.e. NSMutableArray보다 삽입/삭제 속도가 빠릅니까?

2010-12-11 Robert

이 질문은 다음과 같습니다. http://stackoverflow.com/questions/4422141/objective-c-what-structure-should-i -use-to-store-these-objects – Robert

소스 코드를 사용할 수 있으므로 다음을 볼 수 있습니다. CFSet.c. (이것은 NSSet의 핵심 파운데이션과 동일하지만 기본적으로 동일합니다.) 해시 테이블입니다.

그러나 사실 NSArray은 배열로 구현되어 있지 않습니다. 여기 구현 내용을 볼 수 있습니다 : CFArray.c. 어쩌면 this blog article은 약간 날짜가 있지만 (~ 5 년) 이해하기 쉽습니다.

2010-12-11 16:46:14 Yuji

세트는 일반적으로 밸런스 이진 검색 트리 (예 : 빨강 검정 나무, avl 나무)로 구현됩니다.

2010-12-11 15:26:52 swegi

Hashtables는 삽입, 삭제 및 조회를 위해 O (1)을 제공합니다. 나무들은 그것들 중 적어도 O (log (N))를 필요로합니다. 내 대답을 보라. – back2dos

@ back2dos : 주문할 필요가없는 경우에만 해시가 사용됩니다. 이 제한으로 인해 java에는 HashMap 및 TreeMap이 있고 C++에는 map 및 unordered_map이 있습니다. java에는 TreeSet과 HashSet도있다. – swegi

동의 함, 정의 집합에는 "특정 순서 없음"이 있음에도 불구하고 http://en.wikipedia.org/wiki/Set_(computer_science) – back2dos

아니요. 해시를 사용하므로 검색 시간이 빨라집니다.

2010-12-11 15:29:31 vakio

나는 Objective-C progammer가 아니지만 일반적으로 세트는 해시 테이블을 통해 구현되며, 적절하게 수행되면 삽입, 삭제 및 조회를 위해 O (1)을 생성합니다.

기술적으로 해시는 일반적으로 O (M)을 제공합니다. 여기서 M은 키의 크기이지만 집합의 경우 키 객체의 ID (상수)를 사용하기 때문에 O (1).

2010-12-11 15:31:46 back2dos

답변