Là unordered_map thực sự không có thứ tự?

Question

Tôi rất bối rối với cái tên 'unordered_map'. Tên cho thấy rằng các phím không được đặt hàng cả. Nhưng tôi luôn nghĩ rằng chúng được sắp xếp theo giá trị băm của chúng. Hoặc là sai (vì tên ngụ ý rằng họ không được đặt hàng)?

Hoặc để đặt nó khác nhau: Đây có phải là

typedef map<K, V, HashComp<K> > HashMap; 

với

template<typename T> 
struct HashComp { 
    bool operator<(const T& v1, const T& v2) const { 
     return hash<T>()(v1) < hash<T>()(v2); 
    } 
}; 

giống như

typedef unordered_map<K, V> HashMap; 

? (OK, không chính xác, STL sẽ phàn nàn ở đây vì có thể có chìa khóa k1, k2 và không k1 < k2 cũng không k2 < k1 Bạn sẽ cần phải sử dụng multimap và ghi đè lên bằng kiểm tra..)

Hoặc một lần nữa cách khác nhau: Khi tôi lặp qua chúng, tôi có thể giả định rằng danh sách khóa được sắp xếp theo giá trị băm của chúng?

Answer 1

Trong câu trả lời cho câu hỏi đã chỉnh sửa của bạn, không có hai đoạn mã nào không tương đương chút nào. std::map lưu trữ các nút trong cấu trúc cây, unordered_map lưu trữ chúng trong một hashtable *.

Khóa không được lưu trữ theo thứ tự "giá trị băm" của chúng vì chúng không được lưu trữ trong bất kỳ đơn đặt hàng nào tại tất cả. Thay vào đó, chúng được lưu trữ trong "nhóm", trong đó mỗi nhóm tương ứng với một loạt các giá trị băm. Về cơ bản, việc thực hiện đi như thế này:

function add_value(object key, object value) { 
    int hash = key.getHash(); 

    int bucket_index = hash % NUM_BUCKETS; 
    if (buckets[bucket_index] == null) { 
     buckets[bucket_index] = new linked_list(); 
    } 
    buckets[bucket_index].add(new key_value(key, value)); 
} 

function get_value(object key) { 
    int hash = key.getHash(); 

    int bucket_index = hash % NUM_BUCKETS; 
    if (buckets[bucket_index] == null) { 
     return null; 
    } 

    foreach(key_value kv in buckets[bucket_index]) { 
     if (kv.key == key) { 
      return kv.value; 
     } 
    } 
} 

Rõ ràng đó là một việc đơn giản hóa nghiêm trọng và thực hiện thực sẽ là tiên tiến hơn nhiều (ví dụ, hỗ trợ thay đổi kích thước mảng buckets, có thể sử dụng một cấu trúc cây thay vì danh sách liên kết cho các xô , vv), nhưng điều đó sẽ đưa ra ý tưởng về cách bạn không thể lấy lại các giá trị theo bất kỳ thứ tự cụ thể nào. Xem wikipedia để biết thêm thông tin.

* Về mặt kỹ thuật, việc thực hiện nội bộ của std::map và unordered_map đang thực hiện xác định, nhưng tiêu chuẩn đòi hỏi nhất định Big-O phức tạp cho các hoạt động mà ngụ ý những triển khai nội

Answer 2

Nếu bạn muốn có sự tương tự, hãy xem RDBMS bạn chọn.

Nếu bạn không chỉ định mệnh đề ORDER BY khi thực hiện truy vấn, kết quả sẽ được trả về "không có thứ tự" - tức là, theo thứ tự nào mà cơ sở dữ liệu cảm thấy như thế nào. Thứ tự không được chỉ định và hệ thống được tự do "đặt hàng" chúng nhưng nó thích để có được hiệu suất tốt nhất.

Answer 3

Bạn nói đúng, unordered_map thực sự là lệnh băm. Lưu ý rằng hầu hết các triển khai hiện tại (trước TR1) gọi nó là hash_map.

IBM C/C++ documentation nhận xét rằng nếu bạn có một hàm băm tối ưu, số lượng các hoạt động thực hiện trong tra cứu, chèn và loại bỏ các yếu tố độc đoán không phụ thuộc vào số lượng của các nguyên tố trong dãy , do đó, điều này có nghĩa là đơn đặt hàng không phải là không có thứ tự ...

Bây giờ, nó có nghĩa là gì là băm đặt hàng? Như một băm nên không thể đoán trước, theo định nghĩa bạn không thể lấy bất kỳ giả định nào về thứ tự của các phần tử trong bản đồ. Đây là lý do tại sao nó được đổi tên thành TR1: tên cũ đã đề xuất một đơn đặt hàng. Bây giờ chúng ta biết rằng một đơn đặt hàng thực sự được sử dụng, nhưng bạn có thể bỏ qua nó vì nó là không thể đoán trước.

Answer 4

"Không theo thứ tự" không có nghĩa là không có chuỗi tuyến tính nào đó trong quá trình triển khai. Nó có nghĩa là "bạn không thể giả định bất cứ điều gì về thứ tự của các yếu tố này". Ví dụ, mọi người thường giả định rằng các mục nhập sẽ xuất phát từ một bản đồ băm theo cùng thứ tự mà chúng được đưa vào. Nhưng chúng không, bởi vì các mục nhập không được sắp xếp thứ tự.

Đối với "được đặt hàng theo giá trị băm của chúng": giá trị băm thường được lấy từ toàn bộ các số nguyên, nhưng bản đồ băm không có 2 ** 32 vị trí trong chúng. Phạm vi của giá trị băm sẽ được giảm xuống số lượng các khe bằng cách lấy nó modulo số khe. Hơn nữa, khi bạn thêm các mục vào một bản đồ băm, nó có thể thay đổi kích thước để chứa các giá trị mới. Điều này có thể khiến tất cả các mục trước được đặt lại, thay đổi thứ tự của chúng.

Trong cấu trúc dữ liệu không có thứ tự, bạn không thể giả định bất cứ điều gì về thứ tự của các mục nhập.

Answer 5

Như tên unordered_map gợi ý, không có thứ tự nào được chỉ định theo chuẩn C++ 0x. Thứ tự rõ ràng của unordered_map sẽ phụ thuộc vào bất cứ thứ gì thuận tiện cho việc thực thi thực tế.