HashMap trong môi trường đa luồng khi thực hiện thay đổi kích thước

Question

tôi đang theo một hướng dẫn và về cơ bản giải thích về nguyên nhân của tình trạng chủng tộc mà xảy ra khi thay đổi kích thước HashMap trong một môi trường đa luồng:

Trong Java, nếu hai chủ đề đồng Thời gian tìm thấy rằng bây giờ HashMap cần thay đổi kích thước và cả hai đều cố gắng thay đổi kích thước. về quá trình thay đổi kích thước của HashMap trong Java, phần tử trong nhóm được lưu trữ trong danh sách được liên kết sẽ được đảo ngược theo thứ tự trong quá trình di chuyển sang nhóm mới vì java HashMap không thêm phần tử mới vào đuôi thay vì nó thêm phần tử mới vào đầu tránh đi qua đuôi. Nếu tình trạng chủng tộc xảy ra sau đó bạn sẽ kết thúc với một vòng lặp vô hạn

Tôi có hai câu hỏi sau khi đọc bài viết này:

1. Tại sao danh sách liên kết cho mỗi xô bị đảo ngược theo thứ tự?
2. Tôi có thể thấy có thể có điều kiện chủng tộc, nhưng không thể thấy vòng lặp vô hạn đến như thế nào? Có phải vì một sợi có thể nối đầu phần tử vào đuôi trong khi một chuỗi khác làm theo thứ tự ngược lại không?

Hãy giúp tôi làm rõ điều này, được đánh giá cao!

Answer 1

Thực tế có ít nhất một điều kiện chủng tộc liên quan đến rehashing. Nhìn vào đoạn mã này (nó là của Sun JDK7):

boolean oldAltHashing = this.useAltHashing; 
this.useAltHashing |= sun.misc.VM.isBooted() && (this.newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD); 
boolean rehash = oldAltHashing^this.useAltHashing; 
transfer(newTable, rehash); 
this.table = newTable; 

đây Có thể là chủ đề T1 kết thúc với rehash = true và sợi T2 kết thúc với rehash = false (giả sử T1 đã thay đổi giá trị của this.useAltHashing) .

Bây giờ, hãy đoán chuỗi nào sẽ viết this.table - bạn không có ý tưởng, có thể. Vì vậy, đó là một câu hỏi may mắn cho dù bạn nhận được một trạng thái nội bộ phù hợp hay không.

Dù sao, như tôi đã đề cập trong nhận xét của tôi theo thiết kế, nó không được phép sử dụng HashMap trong môi trường đa luồng. Nó sẽ không làm việc. Hoặc là vì điều này, hoặc vì lý do khác. Ở trên chỉ là một ví dụ tại sao bạn không nên cố gắng chống lại các hợp đồng.

Answer 2

Tôi không biết ví dụ này có hợp lệ hay không. Điều rõ ràng là nó được thực hiện cụ thể. Tôi nghĩ nó cũng bỏ lỡ bức tranh lớn hơn.

HashMap 's contract bang rõ ràng (nhấn mạnh của họ):

Nếu nhiều đề truy cập vào một bản đồ băm đồng thời, và ít nhất một trong những chủ đề sẽ thay đổi bản đồ cấu trúc, nó phải được đồng bộ từ bên ngoài. (Sửa đổi cấu trúc là bất kỳ hoạt động nào thêm hoặc xóa một hoặc nhiều ánh xạ; chỉ thay đổi giá trị liên quan đến khóa mà một cá thể đã chứa không phải là một sửa đổi cấu trúc.)

Nếu bạn vi phạm hợp đồng, tất cả các cược đang tắt. Bản đồ là miễn phí để thổi lên trong tùy ý, không xác định, cách.

Answer 3

Câu trả lời cho câu hỏi đầu tiên của bạn là trong văn bản trích dẫn:

"vì java HashMap không nối thêm các yếu tố mới ở đuôi thay vào đó nó thêm yếu tố mới vào đầu để tránh đuôi traversing"

Nếu HashMap lưu trữ chúng theo thứ tự chèn, nó phải duyệt qua danh sách tại mỗi lần chèn hoặc lưu con trỏ thêm vào cuối danh sách (và duy trì nó). Dù sao lưu trữ các phần tử trong xô theo thứ tự chèn sẽ không đưa ra bất kỳ lợi ích nào (ít nhất là tôi không thể nghĩ ra được).

Câu trả lời cho câu hỏi thứ hai của bạn dựa ở đây:

http://mailinator.blogspot.hu/2009/06/beautiful-race-condition.html