Hash table O(1): phép màu tra cứu — và ba cách nó sụp đổ về O(n)
Map/dict cho tra cứu O(1) — nhanh bất kể dữ liệu lớn cỡ nào. Bài này đo thật trong go-lab: hashtable và map Go giữ ~1-21 ns dù N tăng 256 lần, trong khi quét slice tăng tuyến tính tới 32 µs. Nhưng O(1) chỉ là trung bình: hàm băm tệ (mọi key về một bucket) làm tra cứu chậm gấp 11.874 lần, và quên pre-size map khiến chèn chậm gấp đôi vì rehash.