BST tra cứu O(log n)? Chỉ khi cây cân bằng. Tôi đo thử: chèn dữ liệu ĐÃ sắp xếp vào một BST thường làm cây lệch thành chuỗi cao đúng bằng N (50.000), tra cứu chậm hơn std::map 461 lần và xây cây chậm 594 lần. Dữ liệu sắp xếp — thứ trông đẹp nhất — hóa ra là worst case, không phải best.
std::unordered_map dùng chaining nên chaining là cách nhanh nhất xử lý va chạm? Đo ra: open addressing (dò trong một mảng liền) tra cứu nhanh hơn ở hệ số tải vừa (10,4 vs 15,1 ns ở tải 0,5) và gọn hơn 3,4 lần bộ nhớ. Nhưng ở tải 0,9, dò dồn cụm trung bình 5,45 lần khiến open chậm hẳn và chaining vượt lên — một điểm giao rõ ràng.
Immutable chậm vì cứ phải copy mỗi lần đổi? Đo ra: đúng một nửa — cập nhật một trường nhiều lần thì immutable naive chậm hơn mutable 101 lần (142,7 vs 1,4 ns) vì mỗi lần đổi phải copy cả đối tượng. Nhưng chia sẻ để đọc thì ngược lại: immutable chia sẻ tự do không tốn gì, còn mutable phải copy phòng thủ mỗi lần trao đi — chậm hơn immutable 97 lần.
Đọc lại bit của một int như float bằng ép kiểu con trỏ nghe vô hại. Tôi đo: cùng hàm trả về 1 với -O2 nhưng 1073741824 với -fno-strict-aliasing — một cờ đổi kết quả là bằng chứng chắc chắn của hành vi không xác định. Strict aliasing cho tốc độ ~9%, nhưng type-punning ép kiểu vi phạm nó; memcpy mới đúng, mà vẫn nhanh.
Hash map O(1) nên luôn nhanh nhất cho tra cứu? Đo ra: với khóa chuỗi (băm phải đọc cả 24 ký tự ~10ns), quét tuyến tính một mảng nhỏ thắng hash map tới n≈16 — vì hằng số nhỏ hơn nhiều: cache liền, so sánh thoát sớm, không băm, không con trỏ. Big-O là tiệm cận n→vô cùng; ở n nhỏ chính hằng số quyết định, và điểm giao tùy giá của khóa.
Bài kết sê-ri: cùng một bài toán 'x có trong tập không', kẻ thắng đổi theo quy mô — quét tuyến tính nhanh nhất ở n=8, hash ở n lớn, bitset đè bẹp cả nếu biết miền khóa; và nhị phân O(log n) luôn kẹt giữa, không bao giờ nhanh nhất. Không có cấu trúc tốt nhất phổ quát — đo, đừng đoán.