Khi nào thích hợp để sử dụng Bản đồ Trie?

Question

Tôi đã đọc một số bài đăng và tự hỏi liệu có ai đó có thể trình bày tình huống khi một TrieMap thích hợp hơn khi sử dụng HashMap không.

Vì vậy, về cơ bản quyết định kiến ​​trúc nào sẽ thúc đẩy việc sử dụng TrieMap?

Answer 1

Theo tài liệu. Đó là bộ sưu tập có thể thay đổi có thể là an toàn được sử dụng trong đa luồng ứng dụng.

Đồng thời hash-trie hoặc TrieMap là concurrent thread-safe lock-free triển khai mảng băm được ánh xạ băm. Nó được sử dụng để triển khai bản đồ trừu tượng đồng thời. Nó có particularly scalable concurrent chèn và xóa hoạt động và là memory-efficient. Nó hỗ trợ O (1), nguyên tử, ảnh chụp nhanh không khóa được sử dụng để thực hiện kích thước không khóa được, trình lặp và thao tác rõ ràng. Chi phí đánh giá ảnh chụp nhanh (lazy) là được phân phối trên các bản cập nhật tiếp theo, do đó làm cho việc đánh giá ảnh chụp theo chiều ngang có thể mở rộng được.

Để biết chi tiết, xem: http://lampwww.epfl.ch/~prokopec/ctries-snapshot.pdf

Ngoài ra nó có thật sự tốt đẹp API cho caching. Vì vậy, ví dụ bạn phải tính giai thừa của các số khác nhau và đôi khi sử dụng lại kết quả này.

object o { 

    val factorialsCache = new TrieMap[Int, Int]() 

    def factorial(num: Int) = ??? // really heavy operations 
    def doWorkWithFuctorial(num: Int) = { 
     val factRes = factorialsCache.getOrElseUpdate(num, { 
     // we do not want to invoke it very often 
     factorial(num) 
      // this function will be executed only if there are no records in Map for such key 
     }) 
     // start do some work `withfactRes` 
     factRes 
    } 
    } 

Chú ý - chức năng trên sử dụng trạng thái toàn cầu (cache) cho các hoạt động ghi, nhưng nó hoàn toàn an toàn để sử dụng nó trong đề cùng lúc. Bạn sẽ không mất bất kỳ dữ liệu nào.