기본 해싱 개념

Question

저는 아주 기본적인 질문이 있습니다. 많은 책을 읽고, 비디오를 보았지만, 내 대답을 얻을 수 없다고 믿어주십시오. HashMap이 있다고 가정 해 보겠습니다. 동일한 해시에 매핑되는 3 개의 (a, b, c) 개의 값이 있지만 a와 b는 같지만 c가 다릅니다. a와 b만을 hastable에 추가하면 hashMap은 충돌이 아니라는 것을 어떻게 알 수 있습니까?

우리가 해시 맵을 가지고 있다고 가정 해 봅시다. 이제 put (obj1, "Test")을 호출 한 다음 obj1과 obj2를 동일한 키에 매핑합니다. 지도가이 두 건의 통화를 위해 저장됩니다.

실제 개체를 저장합니까? 두 번째 호출에서 obj1과 obj2가 같으면 충돌이 발생하지 않는 방법을 결정하지 않습니다.

감사

Answer 1

대부분의 해시 테이블은 저장 개체에서 지원의 두 비트를 필요로 - GetHashCode()와 같음을(). 두 객체가 같은 GetHashCode()하지만, 같음과의 비교()가 true를 돌려을 반환하는 경우

, 그들은 같은 데이터를 나타내고, 따라서 단지 항목을 중복, 충돌하지 않습니다.

두 개체가 동일한 GetHashCode()를 반환하고 비교 결과가 false를 반환하면 Hashtable은 개체가 다른 것을 나타내므로 충돌로 처리합니다.

많은 OOP 언어로는 C#과 같은, 당신이 당신의 저장 개체에서 GetHashCode()와 같음()을/설정을 무시하고 구현해야하는 이유입니다. Equals()와 비교할 때 두 객체가 true를 반환하지만 GetHashCode()에서 다른 값을 반환하도록 이러한 메소드를 구현하면 버그가 발생합니다.

Answer 2

위키에 따르면, 컴퓨터 과학

해시 테이블 또는 해시 맵 키라고도 식별 값에 매핑하는 해시 함수를 사용하는 데이터 구조 (예를하는 사람의 이름) 인 (예 : 전화 번호 ). 따라서 해시 테이블은 연관 배열을 구현합니다.

위키는 연관 배열을 "(키, 값) 쌍의 모음으로 구성된 추상 데이터 유형"이라고 말했습니다.

그래서 네, 해시 테이블은 "임차인"을 알고 있습니다.