안녕하세요 ArrayList 또는 HashMap을 사용할 지 여부에 대한 질문이 있습니다.ArrayList 또는 HashMap 사용
그림판 프로그램을 만들려고합니다. 그려진 각 객체에는 고유 한 객체 ID이 할당됩니다.
개체를 클릭 할 때 빠른 검색 속도를 원한다면 arraylist 또는 hashmap을 사용해야합니까?
일반적으로 해시 맵에는 O (1)이 있고 arraylist에는 O (n) 검색 속도가 있습니다.
그러나 개체를 클릭하면 배열의 인덱스와 ID를 얻을 것이므로 ArraylistObject.get (iithElement)와 같은 작업을 수행 할 수 있습니다. ,이 경우 O (1) 검색 프로세스가 될 것입니다.
입력 사항이 있습니까?
감사합니다.
객체가 O (1) 액세스가 될 것보다 배열에 일대일로 매핑 될 수있는 ID를 가지고 있고 실제로는 해시 맵 조회보다 약간 빠르다. 해시 계산).
그러나 개체를 삭제할 때 문제가 발생합니다. 목록에 구멍이 생깁니다. 새 객체를 만들 때 목록에 계속 추가하고 천천히 조각 나게하거나 예비 슬롯을 찾으면 여분의 공간을 O (n) 검색 할 수 있습니다.
요약하면 해시 맵이 더 적합합니다.
Java Collections의 ArrayList 인 경우 객체를 삭제 한 후에도 배열이 인접해야합니다 (구현 세부 정보는 잊어 버림).그러나 객체 ID가 배열 색인과 같으면 특정 객체를 삭제 한 후에 동작이 더 이상할 수 없으므로 ID가 모든 새 객체를 가리 키기 시작할 수 있습니다. 간격을 메우기 위해 모든 것이 위로 이동합니다. 그래서 확실히 HashMap입니다. – Anurag
죄송합니다. 요소가 제거 될 때 ArrayList가 기본 배열을 재편성한다는 점을 잊어 버렸습니다 (Java를 수행 한 지 오래되었지만). 그렇지만 요점이 매우 유효하여 참조가 엉망이 될 것입니다. – Paolo
ID를 색인으로 사용하는 요점은 항목을 삭제하지 않고 null로 설정한다는 것입니다. –
플러스 측면에서는 ArrayLists를 올바르게 수행하여 약간의 성능을 줄일 수 있습니다. 그러나 개체를 삭제하면 왕실의 고통이 될 것입니다. Paolo와 Anurag가 말했듯이 빈 자리 표시 자 (null?)를 넣거나 간격을 메우기 위해 다른 다른 개체의 번호를 다시 지정해야합니다. 이로 인해 성능 버그와 일반적인 오래된 버그가 발생할 수 있습니다.
해시 맵 (HashMaps). 사용하기 쉽고 괜찮은 성능을 보장합니다 (실제로 ID를 잘못 할당하지 않는 한).
그리고 id로 객체를 검색하면 응용 프로그램의 병목 현상이 전혀 아닐 수도 있습니다. 속담이 말하듯이, 조기 최적화는 모든 악의 뿌리입니다.
만약 당신은 당신이 오히려 ArrayList보다 (최대 ID로 preinitialized 크기에) 일반 배열을 사용해야의 ID를 비교적 작은 수치 범위에있을 것이라는 점을 보장 할 수있다. 이렇게하면 실수로 항목을 제거하지 않고 모든 항목을 잘못된 색인으로 끝내면서 간격을 메우기 위해 다른 모든 항목을 이동하지 않도록 할 수 있습니다. 일반 배열은 ArrayList보다 약간 빠릅니다.
보장 할 수 없다면 HashMap을 사용하십시오. 속도 차이가 눈에 띄지 않을 것 같으며 유지 관리가 더 쉬울 것입니다.
ID가 배열의 색인과 동일합니까? –