해싱은 진정한

Question

샘플 코드를 고려 돌려줍니다 :

class EmployeeClass { 
    int id; 
    public EmployeeClass(int eid) { 
     this.id=eid; 
    } 

    @Override 
    public int hashCode(){ 
     return this.id; 
    } 
    @Override 
    public boolean equals(Object o){ 
     return true; 
    } 
} 

public class HashcodeAndEquals { 

    public static void main(String[] args) { 
     Map map=new HashMap(); 
     EmployeeClass e1=new EmployeeClass(1); 
     map.put(e1, "Employee 1");    // line 1 
     EmployeeClass e2=new EmployeeClass(2); 
     map.put(e2, "Employee 2"); 
     EmployeeClass e3=new EmployeeClass(3); 
     EmployeeClass e4=new EmployeeClass(1); // line 2 
     EmployeeClass e5=new EmployeeClass(1); 
     map.put(e5, "Employee 5");    // line 3 
     System.out.println("e1 -> "+map.get(e1)); 
     System.out.println("e2 -> "+map.get(e2)); 
     System.out.println("e3 -> "+map.get(e3)); 
     System.out.println("e4 -> "+map.get(e4)); // line 4 
     System.out.println("e5 -> "+map.get(e5)); 
    } 
} 

출력 : 사실

e1 -> Employee 5 
e2 -> Employee 2 
e3 -> null 
e4 -> Employee 5 

e5 -> Employee 5 

라인 (1) 실행 후, 다음 3 호선 대체 e1의 값하지만 내 동등한 방법 반환 만. 심지어 라인 4에서 equals 메소드가 true를 리턴하더라도 e4의 값을 얻습니다. equals 메서드는 비교가 없기 때문에 true를 반환하고 put 및 get은 여기서 어떻게 작동하는지 알 수 있습니다. 무엇이 뒤에서 일어나고 있습니까?

Answer 1

나는 모두가 직원 5가 아니라는 사실에 놀랐 을까? Equals는 항상 true를 반환하므로 e5가 모든 내용을 덮어 써야합니다. 맞습니까?

HashMap은 백그라운드에서 "버킷"을 사용합니다. 간단하게 만드는 데 2 ​​개 밖에 없다고 가정 해 봅시다. 진짜 HashMap은 훨씬 더 많습니다.

개체를 HashMap에 넣으면 먼저 hashCode를 찾습니다. hashCode에 기반하여 해시 코드를 저장하기 위해 버킷을 선택합니다. e1의 경우 hashCode는 1이므로 버킷 1을 선택합니다. e2의 경우 2이므로 버켓 2로 이동합니다. . e3의 해시 코드는 3이지만, 거기에 단지 2 버킷은, 그래서이 버킷 3 1. e4이 같은 이유로 버킷 2로 전환입니다 모듈 2로 이동되며, e5 1.

주에 돌아 나는 여기서 매우 단순화하고있다. 현실적으로 프로세스는 좀 더 복잡하지만, 이것은 사물을 설명하기에 충분해야합니다.

그래서 우리는 다음과 같은 버킷이 있습니다

bucket 1 | bucket 2 
e5  | e4 
e3  | e2 
e1  | 

을 그래서 지금은 값을 검색하는 시간이다. e1을 검색하면 hashCode는 여전히 1이므로 버킷 1에서 찾습니다. equalse1 인 e5 인 첫 번째 객체를 선택합니다. 마지막으로 입력 한 객체가 첫 번째 객체입니다. e2은 버킷 2로 지정되므로이 예의 경우 결과적으로 e4이 표시됩니다.

실제로는 e3과 e4을 HashMap에 넣지 않았습니다. 그러나 e3의 hashCode가 버킷 1로 지정되고 e5과 같기 때문에 e3을 조회하면 실제로는 존재하지 않지만 여전히 e5이됩니다.

내가 말했듯이 이것은 사물을 극단적으로 단순화 한 것입니다. 실제 HashMap에는 2 개 이상의 버킷이 있습니다. 따라서 귀하의 경우 e3에는 빈 버킷으로 연결되는 해시 코드가 있고 e1, e4 및 e5에 대한 hashCodes는 분명히 모두 동일한 버킷으로 연결됩니다.

해시 코드를 작성할 때 좋은 "배포"를 제공하는 것이 중요합니다. 항상 42를 반환하면 모든 객체가 항상 동일한 버킷으로 이동하므로 HashMap이 본질적으로 매우 어색한 ArrayList가됩니다. HashMap이 제공하는 성능상의 이점을 모두 잃게됩니다.