해시 맵에서 목록 또는 배열을 키로 사용하는 런타임은 무엇입니까

Question

해시 맵은 O (1) 시간의 값을 반환합니다. 그것이 우리가 사용하는 이유입니다.

그러나 두 개의 배열 또는 목록을 O (N) 시간 동안 비교해야합니다. 여기서 N은 비교를 위해 N 요소를 조회해야하므로 N은 해당 목록의 길이입니다.

그래서 목록/배열을 해시 맵의 키로 사용하면 어떻게됩니까? 해시 맵 색인은 목록 비교에서의 비효율을 보완합니까? 또는 해시 코드 함수가 이제 O (M) 시간 (M은 키로 사용 된 목록의 길이 임)으로 실행됩니다.

의심되는 O (M)에서 실행되는 경우 단일 키가 아닌 키 목록으로 값을 매핑해야 할 때 더 나은 방법은 무엇입니까?

입력 해 주셔서 감사합니다.

Answer 1

글쎄, 모든 객체는 자체 서명을 가지고 있기 때문에 맵핑은 그것에 기반을두고 키가 실제로리스트 또는 배열 인면은 중요하지 않습니다. 시간은 대략 O (1)이됩니다. 그럼, 실제로 목록을 쉽게 (그리고 빨리) 검색 할 수 있다면 좋은 방법이라고 제안했습니다.

일부 추가 사항 : 해시지도의 작동 방식은 개체 ID (키)를 기반으로 자동 또는 수동으로 생성 할 수있는 몇 가지 기능 - 해시 기능이 있으며 모든 다른 개체에 대해 너에게 전화 번호를 알려줘. 이 숫자는 귀하의 가치로 결정됩니다. 이와 같이 특정 키를 사용하여 O (1) 검색을 통해 가치를 찾을 수 있습니다.

Answer 2

HashMap<ArrayList<K>,V>과 같은 것을 사용한다고 가정하면 다음과 같습니다. 작동 원리는 다음과 같습니다.

(키, 값) 쌍을 목록에 추가하면 키의 해시 코드가 계산됩니다. ArrayList의 해시 코드는 목록의 모든 요소의 해시 코드를 확인하는 수식을 사용하여 계산됩니다. 따라서 요소가 동일한 두 개의 ArrayList이있는 경우 (즉 요소의 equals() 메서드가 true를 반환하면 hashCode() 메서드가 동일한 값을 반환해야 함을 의미 함) ArrayList은 hashCode을 반환합니다. 이 해시 코드는 해시 배열의 인덱스로 변환되어 하나의 해시 버킷을 식별하고 키가 버킷의 키 목록에 추가됩니다. 일반적으로 해시 테이블은 키 길이가 1보다 길지 않도록 충분히 커야합니다.

키를 검색하면 HashMap은 키의 해시 코드를 계산합니다. 위에서 언급했듯이 이것은 목록의 모든 요소를 ​​조사하므로 O (N)입니다. 여기서 N은 목록의 길이입니다. 이것은 다시 하나의 해시 버킷을 식별하는 인덱스로 변환됩니다. 이 버킷에는 키 목록이 있습니다. 그런 다음 키는 equals()을 사용하여 "버킷 목록"의 각 키와 비교됩니다 (더 나은 용어를 생각해 야합니다). equals()은 두 키의 각 요소를 조사해야하며, 다른 O (N)입니다. 찾고있는 키를 찾으면 값을 검색 할 수 있습니다. 같지 않은 두 개의 목록이 동일한 해시 코드를 가질 수 있기 때문에 equals()을 사용하는 키를 비교하지 않고서는 얻을 수 없습니다.

따라서 해시 검색은 키가 동일한지 확인하기 위해 ArrayList의 모든 요소를 ​​통과해야합니다. 실행중인 해시 코드를 유지하는 래퍼 클래스를 설정하여 해시 코드 계산을 상수로 만들 수도 있지만 일반적으로 모든 요소의 동등성을 검사하지 않는 것은 불가능합니다. 동일한 해시 코드가 같은 목록을 의미하도록 일대일 대응 인 해시 함수를 만들 수 있다면 해당 O (N)을 제거 할 수 있습니다.그러나 일반적으로 어떤 종류의 데이터가 목록에 포함될 것인가에 대한 심각한 제약이 없으면이 작업을 수행 할 수 없습니다. 이 경우 equals()을 간단한 해시 코드 비교 방법으로 만들 수 있습니다. 그러나 그럴만 한 가치는 없을 것입니다. 목록이 짧으면 O (N)은 아무 것도 걱정할 필요가 없습니다. 길면 길 같은 기능을 생각해내는 것이 불가능해질 것입니다.