Java의 Dictionary ADT 및 Skip List에 대한 자세한 정보는 어디에서 얻을 수 있습니까?

Question

나는 Java의 Dictionary ADT에 깊이 들어가려고 노력하고 있습니다. 내 교과서는 이것에 대해 많이 다루지 않으며 그것이 다루는 것은 매우 복잡합니다. 이는 Java의 Dictionary ADT 및 Skip List에 대한 자세한 정보를 얻을 수있는 최고의 온라인 사이트입니다. 나는 시각적으로 이야기하고 많은 예를 제공하는 것을 찾고 있습니다.

Answer 1

알고리즘 클래스에있는 것처럼 들리므로 사전 구현과 Skip List를 Java API가 제공 한 것과 분리합니다. 이 시점에서 모든 언어로 구현할 수 있기 때문에 이러한 추상 데이터 유형의 개념을 이해하는 것이 더 중요합니다 (C#, PHP, Stand, Brainfuck 등).

강사는 아마도 다음을 원할 것입니다. 먼저, 사전 (또는 건너 뛰기 목록)의 인터페이스 또는 계약을 정의한 다음 구현을 알아냅니다. Java로 프로그래밍하는 경우 Junit을 사용하여 알고리즘의 정확성을 확인하십시오. 다른 언어로 프로그래밍하는 경우 Xunit API를 찾으십시오.

봐 NIST의 알고리즘 및 데이터 구조 사전 이런 것들이 무엇을 의미하는지 이해하기 위해 교과서에 대한 보조 리소스로서. 아마도 Java에서 가장 좋은 알고리즘 책은 Sedgewick 's이며, 주요 독특한 것은 애플릿의 교육적 사용입니다. 샘플 코드는 관용 Java로 작성되지 않았으므로 알고리즘의 산업 강도 구현을 찾지 못할 것입니다. 결국, 당신은 다른 사람의 컬렉션 API를 사용하지 않고 직접 일을해야합니다.

오, BTW, Java 6에는 두 가지 건너 뛰기 목록이 있습니다. ConcurrentSkipListSet 그리고 ConcurrentSkipListMap. 그리고 Java의 사전 데이터 구조의 인터페이스는 Map.

Answer 2

건너 뛰기 목록과 그 뒤에있는 이론을 설명하는 William Pugh의 원래 논문의 PDF를 다운로드 할 수 있습니다. 여기.

또한, 이것 건너 뛰기 목록의 작동을 시각화하기에 좋은 애플릿입니다. 내 데이터 구조 클래스에서 Skip Lists가 등장했을 때 많은 도움이되었습니다.

또한, 위키 백과 Entry는 다른 구현 및 Java 소스 코드에 대한 하단에 몇 가지 좋은 링크가 있습니다.