java - type - 사전을 구현하는 방법(Trie vs HashTable 및 중요한 문제)?




java return dict (2)

Java로 사전 구현, 해시 콜렉션이 가장 좋습니다.

HashMap 또는 HashTable 관련 : 주로 HashTable 을 사용해야하는 것보다 클래스가 다중 스레드 방식으로 사용되는 경우, 그렇지 않으면 HashMap 이 가장 좋습니다.

HashMapTreeMap : 컬렉션에 삽입 순서가 필요한 경우 TreeMap 을 사용해야합니다.

HashMap vs LinkedHashMap : LinkedHashMap 구현은 HashMap 과 달리 모든 항목을 통해 실행되는 이중 링크 목록을 유지합니다. 이 링크 된 목록은 일반적으로 키가 맵에 삽입 된 순서 (삽입 순서) 인 반복 순서를 정의합니다. 키가 맵에 다시 삽입되면 삽입 순서가 영향을받지 않습니다. m.put(k, v) 가 호출 직전에 true를 돌려 m.containsKey(k) 경우에 m.put(k, v) 가 불려 m.put(k, v) , 맵 mk 가 재 삽입됩니다.

여러 질문과 기사를 통해 Java에서 사전 구현이 시도를 사용하여 가장 잘 수행되었다고 말했습니다. 그러나 그들 대부분은 중요한 문제를 언급하지 않았다. 그럼, 다음은 현실 세계의 과제입니다.

사전을 구현할 필요가 있다고 가정 해 봅시다 (Lingvo와 비슷하지만 더 간단합니다) java를 사용합니다. 내 특정 작업을 위해서는 단어 정의를 저장하고 빠른 사전 검색을 수행해야합니다.

다음 질문에 답해주십시오 :

  • 그런 다음 어떤 데이터 구조 (Trie 또는 HashTable)를 사용해야합니까?
  • 사전에 대소 문자를 구분해야하는 경우 어떻게해야합니까 (검색, 데이터 구조)?
  • 대 / 소문자를 구분 (검색, 사전)하고 싶다면 어떻게해야합니까?

추신 : 코드 예제를 높이 평가합니다. :)

미리 답변 해 주셔서 감사합니다.

업데이트 : 만약 우리가 자바에서 표준 DS 구현에 대해 이야기하고 있다면, HashTable이이 특정 작업에 가장 적합한 것인가? 왜 HashMap, TreeMap 또는 LinkedHashMap을 사용하지 않을까요?


귀하의 질문에 단 한 점을 지적하고 싶습니다 :

trie 는 범용 사전 데이터 구조가 아닙니다 . 그 이유는 trie가 (하위) 문자열 검색을위한 특수 검색 트리이기 때문입니다. 일반적으로 이진 검색 트리 또는 B-trees 트리와 같은 일반적인 검색 트리에 더 많은 관심을 갖 B-trees .

이러한 모든 구현은 사전 요소의 순서 에 의존하며 모든 요소는 일반적인 작업에 대해 로그 평균 평균 및 최악의 런타임을 갖습니다.

반대로 해시 테이블 은 요소의 상대적 순서를 요구하지 않습니다. 대신 요소가 해시 가능 하고 동등한 비교가 가능해야 합니다. 공통 해시 테이블 특성의 최악의 경우 특성은 트리보다 훨씬 나쁩니다. 즉 요소 수는 선형입니다.

그러나 약간의주의를 기울이면 해시 테이블 작업의 평균적인 경우를 일정하게 만들 수 있습니다 (즉, 컨테이너 크기와 무관). 게다가 느린 작업이 매우 드물다는 것이 입증 될 수 있습니다.

실제로 이것은 매우 특수화 된 사용 사례를 제외하고는 해시 테이블이 트리 기반 사전을 손상시키는 것을 의미합니다.

단점은 해시 테이블이 요소에 임의의 순서를 적용한다는 것입니다. 사전에서 항목을 정렬 된 순서로 가져 오는 데 관심이있는 경우 해시 테이블은 사용할 수 없습니다.

(검색 트리에 필적하는 목록 건너 뛰기Bloom 필터 와 같은 확률 론적 구현과 같은 사전의 다른 흥미로운 구현이 있습니다.)

트라이 기반 구현은 문자열 값 사전을 처리하는 경우에만 사용할 수 있습니다.이 경우 실제로는 종종 좋은 선택입니다. 특히 사전의 많은 문자열이 공통 접두사를 공유하고 다소 짧은 경우에 사용합니다.





lookup