Sự khác nhau giữa các bản triển khai Bản đồ khác nhau trong Dart là gì?

Question

Phi tiêu có loại Bản đồ, với các triển khai như HashMap, LinkedHashMap và SplayTreeMap. Sự khác nhau giữa các bản triển khai Bản đồ khác nhau là gì?

Answer 1

Dart có hỗ trợ tích hợp cho các bộ sưu tập như Danh sách, Tập hợp và Bản đồ. Dart có các bản triển khai Bản đồ khác nhau. Hiểu được ưu và nhược điểm giữa việc triển khai có thể giúp bạn đưa ra quyết định sáng suốt.

(Lưu ý:. Này được viết trong khoảng thời gian của Dart M3, vì vậy những gì sau có thể không phù hợp với các tài liệu tại thời điểm này)

một bản đồ là gì?

Bản đồ là vùng chứa liên kết, ánh xạ khóa tới giá trị. Các khóa là duy nhất và có thể trỏ đến một và chỉ một giá trị. Một khóa không thể là null, nhưng một giá trị có thể là null.

Bản đồ Literals

Dart hỗ trợ literals Bản đồ, như thế này:

var accounts = {'323525': 'John Smith', '588982': 'Alice Jones'}; 

Các spec nói rằng literals bản đồ phải duy trì trật tự chèn. Điều này có nghĩa là accounts là một phiên bản của LinkedHashMap.

Thông số cũng cho biết rằng Khóa chữ bản đồ phải là Chuỗi. Điều này có thể được thay đổi trong tương lai.

Bản đồ mới()

Dart hỗ trợ nhà xây dựng nhà máy, vì vậy bạn có thể tạo một đối tượng mới của Map như thế này:

var accounts = new Map(); 

Lớp Map là trừu tượng, có nghĩa là các nhà xây dựng nhà máy thực sự tạo ra một thể hiện của một lớp con của Map. Vì vậy, loại thực tế của accounts là gì?

Phiên bản trước của Dart đã tạo phiên bản mới HashMap từ hàm tạo new Map(). Tuy nhiên, Dart bug 5803 nói rằng để thực hiện {} và new Map trả về cùng một loại, new Map sẽ sớm trả lại phiên bản LinkedHashMap.

LinkedHashMap (hoặc, InsertionOrderedMap)

Một LinkedHashMap lặp thông qua các phím và các giá trị theo thứ tự chúng được chèn vào.

Lưu ý: LinkedHashMap có thể sẽ được đổi tên thành InsertionOrderedMap. Theo dõi Dart bug 2349 để biết tiến trình.

Dưới đây là một ví dụ:

import 'dart:collection'; 
main() { 
    var ordered = new LinkedHashMap(); 
    ordered['32352'] = 'Alice'; 
    ordered['95594'] = 'Bob'; 

    for (var key in ordered.keys) { 
    print(key); 
    } 

    // guaranteed to print 32352, then 95594 
} 

Đây là source code for LinkedHashMap. (Nếu liên kết này ngừng hoạt động, nó có thể là bởi vì lớp được đổi tên)

HashMap

Một HashMap có gì bảo đảm giữ gìn trật tự chèn.Khi bạn lặp qua các khóa hoặc giá trị của HashMap, bạn không thể mong đợi một thứ tự nhất định.

HashMap được triển khai bằng cách sử dụng hash table.

Dưới đây là một ví dụ về việc tạo ra một new HashMap:

import 'dart:collection'; 
main() { 
    var accounts = new HashMap(); 
} 

Nếu bạn không quan tâm đến việc duy trì trật tự chèn, sử dụng HashMap.

Đây là source code of HashMap.

SplayTreeMap

Một cây splay là một cây tìm kiếm nhị phân tự cân đối với tài sản bổ sung các yếu tố mới truy cập nhanh chóng để truy cập một lần nữa. Nó thực hiện các thao tác cơ bản như chèn, tra cứu và loại bỏ trong thời gian phân bổ O (log (n)).

import 'dart:collection'; 
main() { 
    var accounts = new SplayTreeMap(); 
} 

Một SplayTreeMap yêu cầu tất cả các khóa đều cùng loại.

Cây splay là lựa chọn tốt cho dữ liệu được lưu trữ và truy cập thường xuyên, như bộ nhớ cache. Lý do là họ sử dụng phép quay cây để đưa một phần tử vào thư mục gốc để truy cập thường xuyên hơn. Hiệu suất xuất phát từ việc tự tối ưu hóa cây. Đó là, các yếu tố thường xuyên truy cập được di chuyển gần hơn đến đỉnh. Tuy nhiên, nếu cây thường được truy cập bình thường, thì có rất ít điểm sử dụng bản đồ cây splay.

Trường hợp ví dụ là bộ định tuyến modem nhận gói mạng ở mức rất cao. Modem phải quyết định gói nào đi theo dây nào. Nó có thể sử dụng một bản đồ thực hiện trong đó khóa là IP và giá trị là đích. Bản đồ cây splay là một lựa chọn tốt cho kịch bản này, bởi vì hầu hết các địa chỉ IP sẽ được sử dụng nhiều lần và do đó chúng có thể được tìm thấy từ thư mục gốc của cây.