混亂的Hashmap內部工作

Question

我無法理解我寫的下面的代碼中發生了什麼。

我所做的是，我有一個外部類Employee一些領域：id, panNo ,名and地址. Then I have an inner class(it was not actually necessary to have it as an inner class) with ID and panNo`字段和它們的值是相同的外部類的成員。

根據我所知道的關於HashMaps，我們使用它們來存儲鍵值對。 該鍵值具有hashcode值，並且取決於此值hashcode值被散列。當我們藉助密鑰檢索一個值時，再次對其值hashcode進行評估，然後獲取適當的值。

所以，hashmap一定是有什麼樣子的：

重點----->其哈希碼|引用字段-------->引用值對象。

因此，當我嘗試插入具有相同鍵的對象時，插入最後一個的元素纔可用。這是因爲必須有唯一的鍵，這意味着hashcode值應該只引用一個對象。

現在，我在我的代碼做的是，我在插入地圖中Employee對象，並使用EmployeeKey類作爲返回每次都在同hashcode值即1的關鍵。所以根據我的理解，地圖中應該只有一個元素。但是，這並沒有發生......我錯過了解一些事情。

我已經寫了下面的類：

package package1; 
public class Employee { 
    int id; 
    int panNo; 
    String name; 
    String address; 

    public Employee(int id, int panNo, String name, String address) { 
     this.id = id; 
     this.panNo = panNo; 
     this.name = name; 
     this.address = address; 
} 

@Override 
public String toString() { 
     return "Employee [id=" + id + ", panNo=" + panNo + ", name=" + name + ", address=" + address + "]"; 
} 

public class EmployeeKey { 
    int id = Employee.this.id; 
    int panNo = Employee.this.panNo; 

    @Override 
    public int hashCode() { 
     return 1; 
    } 

    @Override 
    public boolean equals(Object obj) { 
     if (this == obj) 
      return true; 
     if (obj == null) 
      return false; 
     if (getClass() != obj.getClass()) 
      return false; 
     EmployeeKey other = (EmployeeKey) obj; 
     if (!getOuterType().equals(other.getOuterType())) 
      return false; 
     if (id != other.id) 
      return false; 
     if (panNo != other.panNo) 
      return false; 
     return true; 
    } 

    private Employee getOuterType() { 
     return Employee.this; 
    } 

    } 
} 

，並有一個測試類，如下所示：

public class Test { 
    public static void main(String[] args) { 

     Employee e1 = new Employee(1, 123, "neeraj", "pune"); 
     Employee e2 = new Employee(2, 456, "viraaj", "pune"); 

     System.out.println(e1.new EmployeeKey().id); 

     Map<Employee.EmployeeKey, Employee> myMap = new  HashMap<Employee.EmployeeKey, Employee>(); 
     myMap.put(e1.new EmployeeKey(), e1); 
     myMap.put(e2.new EmployeeKey(), e2); 

     System.out.println("Size:" + myMap.size()); 
     System.out.println("Hashcode of inner class e1: " 
      + e1.new EmployeeKey().hashCode()); 
     System.out.println("Hashcode of inner class e2: " 
      + e2.new EmployeeKey().hashCode()); 

     System.out.println(myMap.get(e1.new EmployeeKey())); 
     System.out.println(myMap.get(e2.new EmployeeKey())); 
    } 
} 

Answer 1

不，哈希表使用哈希碼來決定哪個「哈希桶」用於密鑰。但是哈希碼不一定是唯一的。總是有碰撞的可能性，而且這實際上經常發生。

因此，正確的散列表只使用散列代碼作爲決定存儲元素的位置的第一步，但它必須具有某種衝突解決方法 - 一種使用相同散列代碼存儲不同密鑰的方法。這通常意味着在散列表的每個元素中都有一個鏈表或實際鍵的樹。

當您將密鑰放入散列表中時，它首先計算散列代碼以作出第一個決定。但之後它使用equals()方法來決定是否將相同的密鑰作爲該位置上的現有密鑰。如果是，那麼新條目將替換舊條目，並且鍵將保持唯一。但是，如果它不是相同的密鑰 - equals()返回false - 然後，儘管有相同的哈希碼，新的密鑰將被單獨保存（添加到鏈接列表或樹）。

當您想要通過密鑰檢索值時，則會再次計算散列碼作爲第一步，但使用equals()方法將該密鑰與表中該位置的所有密鑰進行比較（鏈表或樹）。只有當密鑰等於存儲的密鑰時纔會返回值。如果沒有相等的密鑰，那麼雖然哈希碼是相同的，但不認爲密鑰是相同的。

這就是爲什麼總是重寫hashCode()和equals()方法總是很重要的，並確保它們是基於對象中相同的字段進行計算的。

爲所有對象返回相同的哈希碼不會違反哈希表的唯一性，但會惡化它的性能，因爲有效地，而不是哈希表，它基於一個計算hashCode()和有限數量的equals()調用，您在哈希表中有一個有效單元，並且您的數據結構已成爲鏈接列表或樹 - 使用線性搜索。

Answer 2

這裏有階段在HashMap的鍵查找。

1. 使用key.hashCode()獲取鑰匙的hash。
2. 使用散列找到桶這一關鍵應該已經擺在。
3. 通過檢查使用equals比較關鍵的是桶每個鍵搜索的是桶的關鍵。

你已經做了hashCode回1總是那麼所有的項目將被放置在同一個桶，但你仍然equals將返回false兩個鍵。

Employee e1 = new Employee(1, 123, "neeraj", "pune"); 
    Employee e2 = new Employee(2, 456, "viraaj", "pune"); 

    System.out.println(e1.new EmployeeKey().id); 

    Map<Employee.EmployeeKey, Employee> myMap = new HashMap<Employee.EmployeeKey, Employee>(); 
    Employee.EmployeeKey k1 = e1.new EmployeeKey(); 
    myMap.put(k1, e1); 
    Employee.EmployeeKey k2 = e2.new EmployeeKey(); 
    myMap.put(k2, e2); 

    System.out.println("Size:" + myMap.size()); 
    System.out.println("Hashcode of inner class e1: " 
      + e1.new EmployeeKey().hashCode()); 
    System.out.println("Hashcode of inner class e2: " 
      + e2.new EmployeeKey().hashCode()); 
    System.out.println("Equals of keys: " 
      + k1.equals(k2)); 

    System.out.println(myMap.get(e1.new EmployeeKey()));