HashMap에서 키와 값이 같은 객체 사용

Question

나는이 검색에서 내가 할 수 있다고 생각하는만큼 여러 번 다시 말 했으므로 아무 것도 생각 나지 않았다. , 또는 나는 묻는 방법을 모른다.

저는 시작 상태에서 완료 상태까지 최단 경로를 찾기 위해 노력하는 개인 프로젝트를 진행하고 있습니다.

너무 많은 (2^64 이상) 상태가 있으므로 전체 그래프를 생성 할 수 없습니다. 그러나 각 상태에는 인접한 모든 상태를 결정할 수있는 충분한 정보가 들어 있습니다. 국가마다 다른 경로가 (무한정) 많으며, 나는 최단 거리에만 관심이 있습니다. 이것은 제가 전에 국가에 다녔는지와 내가 처음 거기에 도착한 방법을 알게합니다.

내 상태 개체에는 모든 상태 정보와 거기에서 나를 안내하는 경로의 깊이 및 해당 경로의 이전 상태에서 얻은 이동이 포함됩니다. 다른 경로를 따라 같은 상태가되면 상태 정보도 같지만 깊이와 이전 이동 필드는 달라집니다.

이전에 해당 상태를 방문했는지 여부를 알려주는 데이터 구조가 필요하며, 그럴 경우 깊이 및 이전 상태 정보를 검색합니다. myHashMap.put(myState, myState)

:

내가 지금까지 함께 온 가장 좋은 방법은 같이 상태로 상태를 매핑는 HashMap을 사용하고, 키와 값 모두 같은 상태 개체를 사용하는 것입니다 hashCode()와 equals()를 구현했는데 어떻게 상태에 관계없이 같은 상태 정보 (예 : 우리가이 방에 있었는지)가 같으면 두 상태가 "같음"으로 간주됩니다. 방에 들어가기 위해 사용됨).

이것은 다소 어리석은 것처럼 보이지만 내가 상태에 있었는지 여부와 어떻게 도착했는지에 대한 정보를 저장하는 다른 방법 (빠른 저장/액세스 사용)은 생각할 수 없습니다.

내 계획이 의미가 있습니까? 아니면 더 좋은 방법이 있습니까?

Answer 1

키와 값을 동일한 값으로 저장하는 것을 본다면 실제로 필요한 것은 Set입니다.

Set<State> set = new HashSet<>(); 
set.put(stat1); 

그리고 HashSet가 HashSet의이 HashMap의 것과 같은 성능 특성을 가지고 있으며, equals 및 hashCode 방법에 의존 의미 장면 뒤에 HashMap에 의해 백업됩니다 귀하의 솔루션은 아주 멀리 것과없는 그런데

.

Answer 2

당신은 "내가 이전에 그 상태를 방문했는지 여부를 알려주는 데이터 구조가 필요하다면, 그 상태에서 깊이와 이전 상태 정보를 검색 할 수 있습니다."라고 말합니다.

Set (HashSet이 설명한 것에 대한 TreeSet보다 가능성이 높음)는 첫 번째 부분을 수행합니다. 이제, 정보를 검색하는 후반 작업을 수행하기 위해 Map을 사용하려고합니다. 그러나 이미 상태를 방문했는지 여부를 확인할 수 있다면 상태에 대한 참조가 있음을 의미합니다. 그래서지도가 전혀 필요 없습니다.

/* Marking a state as visited */ 
Set<State> visited = new HashSet<>(); 
visited.put(currentState); 

/* Checking if visited/retrieving */ 
if (visited.contains(currentState)) { 
    // already visited 
} else { 
    // do something with 'currentState' 
}