Compare map and mutableMap

Trong Kotlin, Map và MutableMap đều là các cấu trúc dữ liệu key-value tuy nhiên có sự khác biệt về tính không thay đổi (immutable) và có thể thay đổi (mutable):

1. Map:
   • Map là một interface trong Kotlin.
   • Map đại diện cho một bộ các cặp key-value, trong đó mỗi key là duy nhất và không thể thay đổi.
   • Map không có khả năng thêm hoặc xóa phần tử trực tiếp; bạn cần sử dụng các phương thức khác như put hoặc remove để thực hiện các thay đổi này.
   • Các implementors của Map có thể bao gồm HashMap, LinkedHashMap, TreeMap, vv.

Ví dụ sử dụng Map:

val map = mapOf("key1" to 1, "key2" to 2, "key3" to 3)
println(map["key1"]) // In ra 1

1. MutableMap:
   • MutableMap cũng là một interface trong Kotlin.
   • Tương tự như Map, MutableMap đại diện cho một bộ các cặp key-value, nhưng khác biệt là bạn có thể thay đổi nó.
   • MutableMap cho phép thêm, xóa và thay đổi các phần tử.
   • Implementors phổ biến của MutableMap bao gồm HashMap, LinkedHashMap, TreeMap, vv.

Ví dụ sử dụng MutableMap:

val mutableMap = mutableMapOf("key1" to 1, "key2" to 2, "key3" to 3)
mutableMap["key4"] = 4 // Thêm một phần tử mới
mutableMap.remove("key2") // Xóa phần tử có key là "key2"
println(mutableMap["key3"]) // In ra 3

Tóm lại, Map là một interface không thể thay đổi trong khi MutableMap là một interface có thể thay đổi, cho phép thêm, xóa và thay đổi các phần tử.

Advanced

1. HashMap
   • HashMap là một class cụ thể trong Kotlin và thực hiện giao diện Map.
   • Nó thực hiện bằng cách sử dụng bảng băm để lưu trữ các cặp key-value.
   • HashMap cho phép thêm, xóa và truy xuất các phần tử một cách hiệu quả.
   • Trong hầu hết các trường hợp, bạn sẽ sử dụng HashMap khi cần một cấu trúc dữ liệu key-value đơn giản và hiệu quả.
2. HashTable

Bảng băm (hash table) là một cấu trúc dữ liệu dùng để lưu trữ các cặp key-value, trong đó các key được sử dụng để tìm kiếm các giá trị tương ứng. Mục tiêu chính của bảng băm là cung cấp một cách hiệu quả để thêm, tìm kiếm và xóa các phần tử trong tập hợp dữ liệu lớn.

Cách thức hoạt động của bảng băm thường như sau:

1. Hashing: Một hàm băm (hash function) được sử dụng để ánh xạ mỗi key tới một vị trí duy nhất trong bảng băm. Mục đích của hàm băm là phân phối đều các key vào các vị trí trong bảng băm.
2. Buckets: Bảng băm thực sự là một mảng (array) của các "bucket" (hộp chứa). Mỗi bucket có thể chứa một hoặc nhiều cặp key-value. Khi một cặp key-value được thêm vào bảng băm, hàm băm được áp dụng cho key để xác định vị trí (index) của bucket tương ứng trong mảng.
3. Collision Handling: Collision xảy ra khi hai hoặc nhiều key được ánh xạ đến cùng một vị trí trong bảng băm. Kỹ thuật xử lý va chạm quan trọng để đảm bảo hiệu suất của bảng băm. Có nhiều cách để xử lý va chạm, bao gồm sử dụng chaining (mỗi bucket chứa một danh sách liên kết các cặp key-value) hoặc open addressing (thử các vị trí khác cho đến khi tìm thấy vị trí trống).
4. Retrieval and Modification: Khi tìm kiếm một giá trị cho một key, hàm băm được áp dụng lần nữa để xác định vị trí của bucket trong mảng. Sau đó, các giá trị trong bucket này được kiểm tra để tìm kiếm giá trị tương ứng với key đã cho. Khi thêm hoặc cập nhật một cặp key-value, quá trình tương tự được thực hiện để xác định vị trí và thêm giá trị vào bucket.

Bảng băm là một trong những cấu trúc dữ liệu quan trọng và được sử dụng rộng rãi trong nhiều ngôn ngữ lập trình và ứng dụng khác nhau do khả năng cung cấp thời gian truy cập đáng kể là O(1) trong trường hợp tốt nhất (nếu không có va chạm). Trong trường hợp tồi nhất, thời gian truy cập có thể là O(n), nơi n là số lượng phần tử trong bảng băm.