mở Băm (Chaining riêng):Ý nghĩa của mở băm và Closed băm
Trong băm mở, khóa được lưu trong danh sách liên kết gắn liền với các tế bào của một bảng băm.
Closed Băm (Open Addressing):
Trong băm khép kín, tất cả các phím được lưu trữ trong bảng băm bản thân mà không cần dùng danh sách liên kết.
Tôi không thể hiểu tại sao chúng được gọi là mở, đóng và Riêng biệt. Có thể một số người giải thích nó?
Việc sử dụng "đóng" và "mở" phản ánh việc chúng tôi có bị khóa vào sử dụng vị trí hoặc cấu trúc dữ liệu nhất định hay không (đây là mô tả cực kỳ mơ hồ). Ví dụ, "mở" trong "mở địa chỉ" cho chúng ta biết chỉ mục (aka. Address) mà tại đó một đối tượng sẽ được lưu trữ trong bảng băm không hoàn toàn được xác định bởi mã băm của nó. Thay vào đó, chỉ mục có thể khác nhau tùy thuộc vào những gì đã có trong bảng băm.
"Đã đóng" trong "băm đóng" đề cập đến thực tế là chúng tôi không bao giờ rời khỏi bảng băm; mọi đối tượng được lưu trữ trực tiếp tại một chỉ mục trong mảng nội bộ của bảng băm. Lưu ý rằng điều này chỉ có thể bằng cách sử dụng một số loại chiến lược địa chỉ mở. Điều này giải thích tại sao "băm khép kín" và "mở địa chỉ" là từ đồng nghĩa.
Tương phản điều này với băm mở - trong chiến lược này, không có đối tượng nào thực sự được lưu trữ trong mảng bảng băm; thay vào đó một khi một đối tượng được băm, nó được lưu trữ trong một danh sách tách biệt với mảng nội bộ của bảng băm. "mở" đề cập đến sự tự do mà chúng tôi nhận được bằng cách rời khỏi bảng băm và sử dụng một danh sách riêng biệt. Bằng cách này, "danh sách riêng biệt" gợi ý tại sao băm mở còn được gọi là "chuỗi riêng biệt".
Trong ngắn hạn, "đóng" luôn đề cập đến một số loại bảo đảm nghiêm ngặt, như khi chúng tôi đảm bảo rằng các đối tượng luôn được lưu trữ trực tiếp trong bảng băm (đóng băm). Sau đó, đối diện của "đóng cửa" là "mở", vì vậy nếu bạn không có bảo lãnh như vậy, chiến lược được coi là "mở".
Vâng đây là đơn giản như vậy để hiểu được khái niệm về mở và đóng băm,
Trong mở băm, Nó lấy tài sản của danh sách liên kết mà nói nếu bất kỳ quan trọng của chỉ số allready có yếu tố dữ liệu hơn chúng ta có thể chèn một phần tử dữ liệu khác trong cùng một vị trí, rõ ràng nó được mở cho dữ liệu có cùng một vị trí sau khi nó bị allready chiếm giữ.
Và nhập Close, nếu dữ liệu có được vị trí trong bảng hơn là không có dữ liệu có thể sử dụng địa chỉ đó ..
Giải Quyết ........ dễ na
Tên mở giải quyết đề cập đến thực tế là vị trí ("địa chỉ") của phần tử không được xác định bởi giá trị băm của nó. (Phương pháp này còn được gọi là băm đóng).
Trong chuỗi riêng biệt, mỗi nhóm độc lập và có một số loại ADT (danh sách, cây tìm kiếm nhị phân, v.v) của các mục có cùng chỉ mục. Trong một bảng băm tốt, mỗi thùng có không hoặc một mục, bởi vì chúng ta cần hoạt động trật tự O (1) cho chèn, tìm kiếm, vv
Đây là một example của riêng chaining bằng C++ với một đơn giản hàm băm sử dụng toán tử mod (clearly, a bad hash function)
Bạn có một mảng là "bảng băm".
Trong Mở Hashing mỗi ô trong mảng trỏ đến danh sách tiếp giáp với các va chạm. Hàm băm đã tạo ra cùng một chỉ mục cho tất cả các mục trong danh sách liên kết.
Trong Hashing bị đóng, bạn chỉ sử dụng một mảng cho mọi thứ. Bạn lưu trữ các va chạm trong cùng một mảng. Bí quyết là sử dụng một số cách thông minh để nhảy từ va chạm đến unit va chạm bạn tìm thấy những gì bạn muốn. Và làm điều này theo cách tái tạo/xác định.
Chúng ta nên thêm rằng Mở Hashing (Chaining riêng biệt) không bị giới hạn trong danh sách liên kết, mà không phải là bộ nhớ cache thân thiện và denegerate vào cuộc tấn công va chạm với hành vi O (n/2). Bạn cũng có thể sử dụng cây hoặc các mảng được sắp xếp cho các nhóm xung đột. – rurban