tầm quan trọng của "sức mạnh của 2" trong việc thực hiện java.util.HashMap

Question

thể trùng lặp:
Java HashMap Default Initial Capacity

Tôi đã đọc thi hành HashMap trong java.util.HashMap. Công suất ban đầu, công suất tối đa, vv, là quyền hạn của hai.

Các bộ phận của tuyên bố sao chép từ java.util.HashMap

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


/** 
* The maximum capacity, used if a higher value is implicitly specified 
* by either of the constructors with arguments. 
* MUST be a power of two <= 1<<30. 
*/ 
static final int MAXIMUM_CAPACITY = 1 << 30; 


/** 
* The table, resized as necessary. Length MUST Always be a power of two. 
*/ 
transient Entry[] table; 

Các ý kiến ​​đề nghị các kích thước PHẢI là một sức mạnh của hai. Tại sao sức mạnh của hai được cho là rất quan trọng?

Answer 1

Sử dụng quyền hạn của hai đơn giản hóa việc triển khai và cải thiện hiệu suất của nó.

Ví dụ: để tìm một cái xô từ một mã băm nó có thể sử dụng hash & (SIZE -1) thay vì abs(hash) % SIZE

Answer 2

nói lý thuyết, chúng ta có thể khấu hao chi phí mở rộng danh sách các chỉ khi hoạt động trở nên không đáng kể như số lượng các yếu tố trong việc tăng đồ. Tăng gấp đôi kích thước mỗi khi hệ số tải đạt được là một cách để đảm bảo việc mở rộng và tải lại các mục được khấu hao.

Lý do tại sao nó đặc biệt là sức mạnh của hai ban đầu là khi chúng ta băm một phần tử, số nguyên kết quả (32 bit) có thể được cắt ngắn thành k-bit đầu tiên, trong đó k là log (N) trong đó N là công suất hiện tại.