Hàm băm() được tính như thế nào trong Java

Question

Giá trị nào là phương pháp hashCode() đang trả về trong java?

Tôi đọc rằng đó là tham chiếu bộ nhớ của một đối tượng ... Khi tôi in giá trị băm cho new Integer(1), nó là 1; cho String("a") là 97.

Tôi nhầm lẫn: ASCII hay loại giá trị nào?

Answer 1

Mã băm là giá trị số nguyên đại diện cho trạng thái của đối tượng mà nó được gọi. Đó là lý do tại sao một số Integer được đặt thành 1 sẽ trả lại mã băm là "1" vì mã băm Integer's và giá trị của nó là giống nhau. Mã băm của ký tự bằng mã ký tự ASCII. Nếu bạn viết một kiểu tùy chỉnh, bạn có trách nhiệm tạo ra một triển khai thực hiện tốt hashCode tốt nhất sẽ thể hiện trạng thái của cá thể hiện tại.

Answer 2

Giá trị trả về bởi hashCode() không được đảm bảo là địa chỉ bộ nhớ của đối tượng. Tôi không chắc chắn về việc thực hiện trong lớp Object, nhưng hãy nhớ rằng hầu hết các lớp sẽ ghi đè lên hashCode() sao cho hai trường hợp tương đương ngữ nghĩa (nhưng không phải là cùng một cá thể) sẽ băm với cùng một giá trị. Điều này đặc biệt quan trọng nếu các lớp có thể được sử dụng trong cấu trúc dữ liệu khác, chẳng hạn như Set, dựa trên số hashCode nhất quán với equals.

Không có hashCode() xác định duy nhất một thể hiện của đối tượng bất kể là gì. Nếu bạn muốn một hashcode dựa trên con trỏ bên dưới (ví dụ: trong triển khai của Sun), hãy sử dụng System.identityHashCode() - điều này sẽ ủy quyền cho phương thức mặc định là hashCode bất kể nó đã bị ghi đè hay chưa.

Tuy nhiên, ngay cả System.identityHashCode() cũng có thể trả về cùng một giá trị băm cho nhiều đối tượng. Xem các bình luận cho một lời giải thích, nhưng đây là một ví dụ chương trình liên tục tạo ra các đối tượng cho đến khi nó tìm thấy hai với cùng một System.identityHashCode(). Khi tôi chạy nó, nó nhanh chóng tìm thấy hai số System.identityHashCode() s phù hợp, trung bình sau khi thêm khoảng 86.000 đối tượng bao bọc dài (và trình bao bọc Integer cho khóa) vào bản đồ.

public static void main(String[] args) { 
    Map<Integer,Long> map = new HashMap<>(); 
    Random generator = new Random(); 
    Collection<Integer> counts = new LinkedList<>(); 

    Long object = generator.nextLong(); 
    // We use the identityHashCode as the key into the map 
    // This makes it easier to check if any other objects 
    // have the same key. 
    int hash = System.identityHashCode(object); 
    while (!map.containsKey(hash)) { 
     map.put(hash, object); 
     object = generator.nextLong(); 
     hash = System.identityHashCode(object); 
    } 
    System.out.println("Identical maps for size: " + map.size()); 
    System.out.println("First object value: " + object); 
    System.out.println("Second object value: " + map.get(hash)); 
    System.out.println("First object identityHash: " + System.identityHashCode(object)); 
    System.out.println("Second object identityHash: " + System.identityHashCode(map.get(hash))); 
} 

Ví dụ đầu ra:

Identical maps for size: 105822 
First object value: 7446391633043190962 
Second object value: -8143651927768852586 
First object identityHash: 2134400190 
Second object identityHash: 2134400190 

Answer 3

Phương pháp hashCode() thường được sử dụng để xác định một đối tượng. Tôi nghĩ rằng việc thực hiện Object trả về con trỏ (không phải là một con trỏ thực nhưng một id duy nhất hoặc một cái gì đó tương tự) của đối tượng. Nhưng hầu hết các lớp đều ghi đè lên phương thức. Giống như lớp học String. Hai đối tượng String có không phải là con trỏ tương tự, nhưng họ đều bình đẳng:

new String("a").hashCode() == new String("a").hashCode() 

Tôi nghĩ rằng việc sử dụng phổ biến nhất cho hashCode() là trong Hashtable, HashSet, vv ..

Java API Object hashCode()

Edit: (do một downvote gần đây và dựa trên một bài viết tôi đọc về các thông số JVM)

Với tham số JVM -XX:hashCode bạn có thể thay đổi cách tính hashCode (xem Issue 222 Bản tin Chuyên gia Java).

HashCode == 0: Đơn giản chỉ cần trả về các số ngẫu nhiên không liên quan đến nơi trong bộ nhớ tìm đối tượng. Theo như tôi có thể thực hiện, số đọc toàn bộ của hạt giống không được tối ưu cho các hệ thống có nhiều bộ xử lý .

HashCode == 1: Đếm các giá trị mã băm, không chắc chắn giá trị nào chúng bắt đầu, nhưng có vẻ như khá cao.

HashCode == 2: Luôn trả về mã băm nhận dạng giống hệt nhau 1. Điều này có thể được sử dụng để kiểm tra mã dựa trên nhận dạng đối tượng. Lý do tại sao JavaChampionTest trả về URL của Kirk trong ví dụ trên là tất cả các đối tượng đều trả lại mã băm giống nhau.

HashCode == 3: Đếm các giá trị mã băm, bắt đầu từ số không. Nó không phải là chủ đề an toàn, vì vậy nhiều luồng có thể tạo ra các đối tượng với cùng mã băm.

HashCode == 4: Điều này dường như có một số liên quan đến vị trí bộ nhớ mà tại đó đối tượng được tạo.

HashCode> = 5: Đây là thuật toán mặc định cho Java 8 và có hạt giống cho mỗi luồng một . Nó sử dụng kế hoạch xor-shift của Marsaglia để tạo ra các số giả ngẫu nhiên .

Answer 4

Object.hashCode(), nếu bộ nhớ phục vụ chính xác (hãy kiểm tra JavaDoc cho java.lang.Object), phụ thuộc vào triển khai thực hiện và sẽ thay đổi tùy thuộc vào đối tượng (Sun JVM có giá trị từ giá trị) của tham chiếu đến đối tượng).

Lưu ý rằng nếu bạn đang thực hiện bất kỳ đối tượng nontrivial, và muốn lưu trữ chúng một cách chính xác trong một HashMap hoặc HashSet, bạn PHẢI ghi đè hashCode() và equals(). Hàm hashCode() có thể làm bất cứ điều gì bạn thích (nó hoàn toàn hợp pháp, nhưng tối ưu để nó trả về 1.), nhưng quan trọng là nếu phương thức equals() của bạn trả về true, thì giá trị trả về bởi hashCode() cho cả hai đối tượng đều bằng nhau.

Lẫn lộn và thiếu hiểu biết về hashCode() và equals() là một nguồn lỗi lớn. Hãy chắc chắn rằng bạn hoàn toàn làm quen với JavaDocs cho Object.hashCode() và Object.equals(), và tôi đảm bảo rằng thời gian đã sử dụng sẽ tự chi trả.

Answer 5

tôi đọc rằng nó là một tài liệu tham khảo bộ nhớ của một đối tượng ..

số Object.hashCode() sử dụng để trả về một địa chỉ bộ nhớ khoảng 14 năm về trước. Không phải kể từ đó.

loại giá trị là

gì nó là phụ thuộc hoàn toàn vào những gì lớp bạn đang nói về và có hay không nó đã ghi đè 'Object.hashCode().

Answer 6

Nếu bạn muốn biết chúng được lồng ghép như thế nào, tôi khuyên bạn nên đọc nguồn. Nếu bạn đang sử dụng một IDE, bạn chỉ có thể + trên một phương thức mà bạn quan tâm và xem cách một phương thức được thực hiện. Nếu bạn không thể làm điều đó, bạn có thể google cho nguồn.

Ví dụ: Số nguyên.hashCode() được thực hiện như

public int hashCode() { 
     return value; 
    } 

và String.hashCode()

public int hashCode() { 
     int h = hash; 
     if (h == 0) { 
      int off = offset; 
      char val[] = value; 
      int len = count; 

      for (int i = 0; i < len; i++) { 
       h = 31*h + val[off++]; 
      } 
      hash = h; 
     } 
     return h; 
    } 

Answer 7

public static int murmur3_32(int paramInt1, char[] paramArrayOfChar, int paramInt2, int paramInt3) { 
/* 121 */  int i = paramInt1; 
/*  */  
/* 123 */  int j = paramInt2; 
/* 124 */  int k = paramInt3; 
/*  */  
/*  */  int m; 
/* 127 */  while (k >= 2) { 
/* 128 */  m = paramArrayOfChar[(j++)] & 0xFFFF | paramArrayOfChar[(j++)] << '\020'; 
/*  */  
/* 130 */  k -= 2; 
/*  */  
/* 132 */  m *= -862048943; 
/* 133 */  m = Integer.rotateLeft(m, 15); 
/* 134 */  m *= 461845907; 
/*  */  
/* 136 */  i ^= m; 
/* 137 */  i = Integer.rotateLeft(i, 13); 
/* 138 */  i = i * 5 + -430675100; 
/*  */  } 
/*  */  
/*  */ 
/*  */ 
/* 143 */  if (k > 0) { 
/* 144 */  m = paramArrayOfChar[j]; 
/*  */  
/* 146 */  m *= -862048943; 
/* 147 */  m = Integer.rotateLeft(m, 15); 
/* 148 */  m *= 461845907; 
/* 149 */  i ^= m; 
/*  */  } 
/*  */  
/*  */ 
/*  */ 
/* 154 */  i ^= paramInt3 * 2; 
/*  */  
/*  */ 
/* 157 */  i ^= i >>> 16; 
/* 158 */  i *= -2048144789; 
/* 159 */  i ^= i >>> 13; 
/* 160 */  i *= -1028477387; 
/* 161 */  i ^= i >>> 16; 
/*  */  
/* 163 */  return i; 
/*  */ } 

Nếu bạn thực sự tò mò muốn biết sau đó đi qua mã này có sẵn trong Hashing.class;

đây đầu tiên param HASHING_SEED được tính dựa trên mã dưới đây

{ 
    long nanos = System.nanoTime(); 
    long now = System.currentTimeMillis(); 
    int SEED_MATERIAL[] = { 
      System.identityHashCode(String.class), 
      System.identityHashCode(System.class), 
      (int) (nanos >>> 32), 
      (int) nanos, 
      (int) (now >>> 32), 
      (int) now, 
      (int) (System.nanoTime() >>> 2) 
    }; 

    // Use murmur3 to scramble the seeding material. 
    // Inline implementation to avoid loading classes 
    int h1 = 0; 

    // body 
    for (int k1 : SEED_MATERIAL) { 
     k1 *= 0xcc9e2d51; 
     k1 = (k1 << 15) | (k1 >>> 17); 
     k1 *= 0x1b873593; 

     h1 ^= k1; 
     h1 = (h1 << 13) | (h1 >>> 19); 
     h1 = h1 * 5 + 0xe6546b64; 
    } 

    // tail (always empty, as body is always 32-bit chunks) 

    // finalization 

    h1 ^= SEED_MATERIAL.length * 4; 

    // finalization mix force all bits of a hash block to avalanche 
    h1 ^= h1 >>> 16; 
    h1 *= 0x85ebca6b; 
    h1 ^= h1 >>> 13; 
    h1 *= 0xc2b2ae35; 
    h1 ^= h1 >>> 16; 

    HASHING_SEED = h1; 
} 

các param thứ hai là mảng char của String, thứ ba luôn là '0' và một phần tư là char chiều dài mảng.

Và phép tính ở trên chỉ dành cho mã băm chuỗi.

Đối với tất cả các số nguyên, mã băm của nó sẽ là giá trị số nguyên của nó. Đối với char (tối đa hai chữ cái) nó sẽ là mã ASCII.

Answer 8

Nhiều như là thực tế hợp lý, phương thức hashCode được xác định bởi lớp Object trả về các số nguyên riêng biệt cho các đối tượng riêng biệt. (Điều này thường được thực hiện bằng cách chuyển đổi địa chỉ nội bộ của đối tượng vào một số nguyên, nhưng kỹ thuật thực hiện điều này là không cần thiết bởi các ngôn ngữ lập trình Java ™.)

https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html#hashCode--