Tại sao initialCapacity của Hashtable là 11 trong khi DEFAULT_INITIAL_CAPACITY trong HashMap là 16 và đòi hỏi một sức mạnh của 2

Question

So sánh HashMap và Hashtable mã nguồn trong jdk 1.6, tôi thấy bên dưới mã bên trong HashMap

/** 
* The default initial capacity - MUST be a power of two. 
*/ 
static final int DEFAULT_INITIAL_CAPACITY = 16; 

    int capacity = 1; 
    while (capacity < initialCapacity) 
     capacity <<= 1; 

tuy nhiên, trong Hashtable , tôi thấy mã dưới đây?

table = new Entry[initialCapacity]; 

public Hashtable() { 
    this(11, 0.75f); 
} 

vì vậy câu hỏi của tôi là: tại sao hashMap yêu cầu công suất 2 là dung lượng ban đầu? và trong khi hashtable chọn 11 làm dung lượng ban đầu mặc định? tôi giả định điều này không có gì để làm với điều mà hashtable là thread an toàn và không cho phép null key hoặc giá trị.

thx.

Answer 1

Bài viết sau đề cập đến câu hỏi này một cách chi tiết: HashMap requires a better hashCode() - JDK 1.4 Part II.

Theo bài viết đó, lý do chính để chuyển sang kích cỡ hai nguồn là mặt nạ bit nhanh hơn phân chia số nguyên. Đây không phải là không có hậu quả bất lợi, được giải thích bởi một trong các tác giả gốc:

Joshua Bloch: Nhược điểm của việc sử dụng sức mạnh của hai là bảng băm rất nhạy cảm với chất lượng của băm Hàm (hashCode). Điều bắt buộc là bất kỳ thay đổi nào trong đầu vào phải ảnh hưởng đến các bit thứ tự thấp của giá trị băm. (Lý tưởng nhất, nó sẽ ảnh hưởng đến tất cả các bit của giá trị băm với khả năng tương đương.) Bởi vì chúng tôi không đảm bảo rằng điều này là đúng, chúng tôi đặt một hàm băm thứ cấp (hoặc "phòng thủ") khi chúng tôi chuyển sang power-of-two bảng băm. Hàm băm này được áp dụng cho các kết quả của hashCode trước khi loại bỏ các bit thứ tự thấp. Công việc của nó là phân tán thông tin trên tất cả các bit, và đặc biệt, vào các bit thứ tự thấp. Tất nhiên, nó phải chạy nhanh rất nhanh hoặc bạn mất lợi ích khi chuyển sang bảng có kích thước 2 bảng. Hàm băm thứ cấp ban đầu trong 1.4 hóa ra là không đủ. Chúng tôi biết rằng đây là một khả năng lý thuyết, nhưng chúng tôi nghĩ rằng nó không ảnh hưởng đến bất kỳ bộ dữ liệu thực tế nào. Chúng tôi đã sai. Hàm băm thứ hai thay thế (mà tôi đã phát triển với sự trợ giúp của một máy tính) có các thuộc tính thống kê mạnh mẽ mà khá nhiều đảm bảo phân phối thùng tốt.

Answer 2

này có thể giúp:

http://www.concentric.net/~Ttwang/tech/primehash.htm

Về cơ bản, nếu tôi nhớ không lầm, khi bạn có một bảng băm với kích thước đó là sức mạnh của 2, thật dễ dàng để có được một hàm băm dựa trên các bit ít liên quan hơn của khóa.

Sử dụng số nguyên tố (như trong 11) làm kích thước của bảng, làm cho va chạm trên các hàng trong bảng ít có khả năng hơn, vì vậy việc chèn là "rẻ hơn".

Answer 3

Yêu cầu về kích thước bảng là sức mạnh của hai là chi tiết triển khai, không được biết đến với người dùng của lớp - đó là lý do tại sao c'tor âm thầm điều chỉnh giá trị thành lũy thừa lớn hơn kế tiếp của hai gắn cờ một lỗi.

Việc triển khai Hashtable giả định rằng băm có thể không được phân phối đồng đều, do đó, nó cố gắng sử dụng một số thùng là nguyên tố với hy vọng tránh các đỉnh trong phân phối tần số của hàm băm.

Sự kết hợp của hai chi tiết triển khai này dẫn đến hiệu suất kém.

(ví dụ một hàm băm nguyên thủy sẽ

int hash(String s, int nBins) { 
    return s[0] % nBins; 
} 

Nếu nBins là 32, e và E kết thúc trong thùng như nhau, do sự phân bố của các giá trị băm tương quan với sự phân bố của sự xuất hiện của chữ cái, mà có các đỉnh khác nhau - vì vậy phân bố tần số sẽ có một đỉnh ở 32.)

Answer 4

Hashtable sử dụng kích thước bảng số nguyên tố giả và tăng kích thước của bảng tương đối chậm hơn. HashMap sử dụng sức mạnh của 2 như bit khôn ngoan và nhanh hơn sử dụng modulus. Trớ trêu thay, một mô đun có công suất 2 có nghĩa là một hashCode tốt() là cần thiết vì các bit trên sẽ bị bỏ qua để HashMap có phương pháp sắp xếp lại hashCode bạn có thể tránh được vấn đề này có nghĩa là nó thực sự có thể chậm hơn. : Z