Bảng ánh xạ

Khái niệm

Bảng ánh xạ lưu dữ liệu theo cặp khóa và giá trị. Thay vì truy cập bằng vị trí số nguyên, chương trình dùng một khóa có ý nghĩa để tìm đúng giá trị cần thiết.

Ví dụ tra cứu theo khóa

student = {"name": "Lan", "age": 18}
print(student["name"])

using System;
using System.Collections.Generic;

Dictionary<string, object> student = new Dictionary<string, object>
{
		["name"] = "Lan",
		["age"] = 18
};

Console.WriteLine(student["name"]);

const student = new Map([
		["name", "Lan"],
		["age", 18]
]);

console.log(student.get("name"));

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int main() {
    unordered_map<string, string> student = {
        {"name", "Lan"}
    };
    cout << student["name"] << endl;
    return 0;
}

const student = new Map<string, string | number>([
    ["name", "Lan"],
    ["age", 18]
]);

console.log(student.get("name"));

package main

import "fmt"

func main() {
    student := map[string]interface{}{
        "name": "Lan",
        "age":  18,
    }
    fmt.Println(student["name"])
}

use std::collections::HashMap;

fn main() {
    let mut student = HashMap::new();
    student.insert("name", "Lan");

    println!("{}", student["name"]);
}

Ứng dụng điển hình

Lưu cấu hình theo tên thuộc tính.
Tra cứu thông tin theo mã, khóa hoặc định danh.
Biểu diễn dữ liệu bán cấu trúc dưới dạng cặp khóa và giá trị.

Ghi chú theo ngôn ngữ

Thông tin</div>

Pascal truyền thống không có bảng ánh xạ tổng quát trong lõi ngôn ngữ. Nếu cần cơ chế tra cứu theo khóa, người viết thường dùng record, mảng song song hoặc thư viện chuyên biệt.

C cũng không có cấu trúc map trong thư viện chuẩn. Các bảng băm hoặc từ điển thường phải tự cài đặt hoặc dùng thư viện bên ngoài.

C++ có std::map (cây nhị phân) và std::unordered_map (bảng băm). unordered_map có hiệu suất tra cứu nhanh hơn trong đa số trường hợp.

TypeScript có Map<K, V> generic và object literal. Map giữ thứ tự chèn và hỗ trợ khóa khiểu bất kỳ, còn object chỉ dùng chuỗi làm khóa.

Go có map[K]V là kiểu nội tại, không cần import. Truy cập khóa không tồn tại trả về giá trị zero; kiểm tra sự tồn tại cần dùng value, ok := m[key].

Rust có HashMap<K, V> và BTreeMap<K, V>. HashMap nhanh hơn, BTreeMap giữ khóa được sắp xếp. Cả hai thuộc std::collections.

Kết luận

Từ điển (map/hash map) là cấu trúc không thể thiếu khi cần tra cứu nhanh theo khoá. Trong mục Thuật toán, từ điển thường được dùng cho đếm tần suất, tìm kiếm O(1) và memoization trong quy hoạch động.

Trong series này: