ساختمان داده map (یا dictionary) از ابزارهای مهم و کاربردی هر زبان برنامه‌نویسی است که برای برقراری نگاشت بین هر نوع کلید و مقدار متناظر استفاده می‌شود. آرایههای معمولی یک عدد صحیح را به عنوان کلید به یک مقدار از هر نوع کلاس یا نوع داده نگاشت می‌کنند. اما وقتی از map استفاده می‌کنیم، این امکان را داریم که از اشیاء کلاس‌ها و انواع داده‌های پیش‌فرض هر زبان برنامه‌نویسی به عنوان کلید استفاده کنیم. در نتیجه پیاده‌سازی بسیاری از عملیات‌ها ساده‌تر می‌شود که کمک بزرگی به حساب می‌آید.
با توجه به نوع نگاشت، طبیعتا محاسبات map برای ذخیره کردن و بازیابی اطلاعات پیچیده‌تر از آرایههای معمولی است. برای مثال برنامه‌ای به زبان ++C را در نظر بگیرید که مقدار هفتصد هزار جمله اول دنباله فیبوناچی را به روش برنامه‌نویسی پویا داخل یک آرایه و همینطور یک map ذخیره می‌کند و مدت زمان اجرای این فرآیندها را به عنوان خروجی چاپ می‌کند:
int main(){
const int size = 700000;
int a[size];
map<int, int> b;
clock_t tStart;
double cps = CLOCKS_PER_SEC;
a[0] = b[0] = 0;
a[1] = b[1] = 1;
tStart = clock();
for(int i = 2 ; i < size ; i++)
a[i] = a[i - 1] + a[i - 2];
cout << "Time for array: " << (clock() - tStart) / cps << "s" << endl;
tStart = clock();
for(int i = 2 ; i < size ; i++)
b[i] = b[i - 1] + b[i - 2];
cout << "Time for map: " << (clock() - tStart) / cps << "s" << endl;
return 0;
}
خروجی هر اجرای برنامه متناسب با مشخصات سیستم حوالی اعداد مشخصی هستند. روی یک سیستم معمولی شاید پر کردن آرایه در حدود چند میلی ثانیه و map بیشتر از دو ثانیه طول بکشد. پس اگر بخواهیم اینجا از map برای حل یک سوال مسابقه ACM استفاده کنیم، عملا اکثر زمان در اختیار را به محاسبه‌ای اختصاص می‌دهیم که می‌شد در عرض چند میلی‌ثانیه انجام داد.
این برنامه ساده نشان می‌دهد زمانی که کلید ما اعداد صحیح هستند، تا حد ممکن باید از آرایه استفاده کنیم. ممکن است محدوده اعداد صحیح مورد نظر ما از صفر شروع نشود یا حتی شامل اعداد منفی هم باشد. این موارد را می‌توان با یک جابجایی ساده به صفر در نظر گرفت. مثلا اگه اعداد کلید در بازه [10,10-] هستند، می‌توان آن را با آرایه به طول 21 پیاده‌سازی کرد که مقدار متناظر کلید i در اندیس i + 10 از آرایه ذخیره می‌شود. حتی اگر صرفا از احتمال توزیع کلید در یک بازه اطلاع داشته باشیم و کل عناصر بازه استفاده نشوند، خیلی از اوقات استفاده از آرایه با اندازه max - min + 1 و وجود حافظه بلااستفاده، نسبت به استفاده از map مقرون به صرفه‌تر است. در واقع هزینه زمانی را به هزینه حافظه تبدیل می‌کنیم.