Memilih struktur data
Di antara 1023 kunci, pencarian linear untuk kunci yang tidak ada melakukan 1023 perbandingan, pencarian biner melakukan 10, dan tabel hash dengan 1023 bucket paling banyak melakukan 6 di laboratorium.
Mulai dari pertanyaan yang akan kamu ajukan
Tidak ada struktur yang terbaik dalam segala hal. Setiap struktur membuat sebagian operasi murah dengan membuat yang lain mahal, jadi cara memilihnya adalah mendaftar apa yang paling sering dilakukan programmu. MIT 6.006 membagi kemungkinannya menjadi dua antarmuka. Barisan (sequence) menyimpan butir dalam urutan yang kamu tentukan (pertama, kedua, ketiga), dan kamu meminta butir berdasarkan posisi. Set (himpunan) menyimpan butir berdasarkan kunci, dan kamu bertanya apakah sebuah kunci ada, atau meminta kunci terkecil, atau kunci berikutnya sesudah kunci tertentu. Set tanpa pertanyaan urutan disebut dictionary (kamus).
Beberapa situasi umum dan jawaban yang biasa:
- Membaca butir berdasarkan posisi, menambah di ujung: array dinamis (array JavaScript).
- Riwayat urungkan, pencocokan kurung, pencarian mendalam: tumpukan, yaitu array yang hanya dipakai di ujungnya.
- Pekerjaan yang ditangani sesuai urutan kedatangan, pencarian melebar: antrean, dengan indeks head atau ring buffer, bukan shift pada array yang panjang.
- Mencari sesuatu berdasarkan nama atau id: tabel hash, yang di JavaScript berarti Map atau Set.
- Menjaga kunci tetap terurut sambil menyisipkan dan menghapus, meminta kunci berikutnya: pohon pencarian biner seimbang.
- Banyak penyisipan dan penghapusan di tempat yang sudah kamu pegang: linked list.
Pencarian yang sama pada lima struktur
Laboratorium di bawah menyimpan kunci yang sama dengan lima cara dan menghitung perbandingan yang dibutuhkan untuk menemukan salah satunya. Kuncinya berupa 15, 127, atau 1023 bilangan cacah acak. Array tidak terurut memakai pencarian linear. Array terurut memakai pencarian biner. Pohon seimbang dibangun dengan menyisipkan kunci tengah lebih dulu, sehingga sependek mungkin. Pohon yang lain dibangun dari kunci dalam urutan terurut, sehingga berupa rantai. Tabel hash punya bucket sebanyak kuncinya dan menghitung 1 untuk menghitung h(k).
Seret untuk memutar. Gulir atau cubit untuk memperbesar.
Dengan 15 kunci, perbedaannya kecil: pencarian linear rata-rata butuh 8 perbandingan dan pencarian biner sekitar 3.3. Dengan 1023 kunci, perbedaannya besar. Pencarian linear rata-rata 512 dan butuh 1023 untuk kunci yang tidak ada, sedangkan pencarian biner dan pohon seimbang tidak pernah butuh lebih dari 10. Pohon rantai sama buruknya dengan pencarian linear. Tabel hash tetap di antara 2.3 dan 2.5 rata-rata pada setiap ukuran karena rantainya tetap pendek, dan di laboratorium ini kasus terburuknya untuk 1023 kunci adalah 6. Karena itulah Map menjadi pilihan bawaan untuk pencarian, dan struktur terurut hanya sepadan kalau kamu juga butuh urutan.
| Berdasarkan posisi | Ambil butir i | Sisipkan atau hapus di depan |
|---|---|---|
| Array dinamis | 1 | n |
| Linked list | n | 1 |
| Array terurut | 1 | n |
| Berdasarkan kunci | Cari | Sisipkan | Kunci berikutnya |
|---|---|---|---|
| Array atau list | n | n | n |
| Array terurut | log n | n | log n |
| Tabel hash | 1 rata-rata | 1 rata-rata | n |
| BST seimbang | log n | log n | log n |
Setiap sel dalam kedua tabel ini adalah laju pertumbuhan biaya untuk n butir, mengikuti tabel dalam catatan kuliah 2, 4, dan 7 MIT. Tabel hash dan pohon pencarian hanya muncul di tabel kedua karena keduanya bekerja berdasarkan kunci, bukan posisi. Pada array tidak terurut atau list, menyisipkan kunci memakan n karena kamu harus lebih dulu memeriksa bahwa kunci itu belum ada. Array terurut mencari dengan cepat tetapi harus menggeser nilai untuk memberi ruang bagi kunci baru.
Map atau objek?
Program JavaScript sering memakai objek biasa sebagai kamus, dengan menulis prices["apple"]. MDN mencantumkan alasan untuk memilih Map kalau kuncinya berasal dari data: objek punya prototipe, jadi berisi kunci bawaan yang bisa bertabrakan dengan kuncimu; Map bisa memakai nilai apa pun sebagai kunci, tidak hanya string dan simbol; ukurannya cukup satu properti, map.size; dan Map ditelusuri sesuai urutan penyisipan. Objek tetap pilihan alami untuk data catatan dengan sekumpulan bagian bernama yang tetap.
- 1953: Memorandum IBM dari H. P. Luhn mengusulkan hashing ke dalam bucket dengan chaining.
- Sekitar 1956: IPL karya Newell, Shaw, dan Simon menghadirkan linked list.
- 1957: Bauer dan Samelson mengajukan paten untuk metode tumpukan; Fortran dirilis dengan array.
- 1962: Adelson-Velsky dan Landis menerbitkan pohon AVL, pohon pencarian seimbang yang pertama.
- 2015: ECMAScript 2015 menambahkan Map dan Set ke JavaScript.
- Pencarian linear untuk kunci yang tidak ada di antara 1023 kunci melakukan berapa perbandingan?
- Pencarian biner di antara 1023 kunci terurut melakukan paling banyak berapa perbandingan?
- Pencarian linear pada 15 kunci: berapa rata-rata banyaknya perbandingan untuk semua 15 kunci?
- BST yang dibangun dari 127 kunci yang disisipkan dalam urutan terurut: berapa perbandingan untuk kunci terbesar?
- Sebuah penyunting teks butuh Urungkan (Undo). Struktur mana yang cocok?
- Antrean
- Tumpukan
- Tabel hash
- Array terurut
- Server cetak harus menangani pekerjaan sesuai urutan kedatangannya. Struktur mana yang cocok?
- Antrean
- Tumpukan
- BST
- Linked list yang dipakai sebagai tumpukan
- Kamu harus mencari data catatan pengguna berdasarkan id-nya berkali-kali per detik. Mana pilihan yang biasa di JavaScript?
- Array yang ditelusuri dengan perulangan
- Map dengan kunci id
- Tumpukan
- Linked list
- Kamu butuh kunci tetap terurut sambil menyisipkan dan menghapus, dan sering meminta kunci berikutnya yang lebih besar. Mana yang paling cocok?
- Tabel hash
- BST seimbang
- Antrean
- Array tidak terurut
- Dalam istilah MIT 6.006, set tanpa operasi urutan disebut
- barisan (sequence)
- dictionary (kamus)
- tumpukan (stack)
- antrean (queue)
- Menurut MDN, mengapa objek biasa bisa berisiko sebagai kamus untuk kunci yang berasal dari data?
- Objek tidak bisa menyimpan string
- Prototipenya membawa kunci bawaan yang bisa bertabrakan dengan kuncimu
- Objek selalu lebih lambat daripada array
- Objek melupakan nilai setelah satu detik
- Pilih berdasarkan operasi yang paling sering kamu lakukan.
- Barisan: array, linked list, tumpukan, antrean. Set: tabel hash, BST.
- Untuk 1023 kunci: pencarian linear sampai 1023 perbandingan, pencarian biner dan pohon seimbang sampai 10.
- Map adalah kamus yang biasa di JavaScript; pakai pohon seimbang kalau kamu juga butuh urutan.
Sumber kursus ini (11)
- MIT OpenCourseWare 6.006 Introduction to Algorithms, Spring 2020 (Demaine, Ku, Solomon)
- lecture notes 2 Data Structures (interface vs data structure, Sequence and Set interfaces, stack = insert_last/delete_last, queue = insert_last/delete_first, array, linked list, dynamic array, amortized Θ(1) append)
- 4 Hashing (chaining, pigeonhole collisions, chain length n/m)
- 6 Binary Trees Part 1 (height, traversal order, O(h) operations) and 7 Binary Trees Part 2: AVL (Adelson-Velsky and Landis, 1962) at ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/pages/lecture-notes
- MDN Web Docs, Array.prototype.shift (shifts all values left by 1)
- Array.prototype.unshift, Map (insertion order, Map vs Object, spec requires sublinear average access) and Set (developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects)
- ECMAScript 2025 Language Specification (tc39.es/ecma262)
- 24.1 Map Objects and 24.2 Set Objects ("must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements")
- Array.prototype.shift steps (Repeat, while k < len: move element k to k - 1)
- D. E. Knuth, The Art of Computer Programming vol. 3 (2nd ed. 1998) section 6.4 History (H. P. Luhn, IBM internal memorandum January 1953, hashing with chaining; digit pairs added mod 10, 31415926 -> 4548) via gwern.net copy, and IEEE Spectrum, "Hans Peter Luhn and the Birth of the Hashing Algorithm" (2018)
- "A brief history of the stack", SIGCIS (sigcis.org/files/A brief history.pdf: Bauer and Samelson applied for the patent in 1957, US 3,047,228 granted July 31, 1962; IPL list processing by Newell, Simon and Shaw at RAND 1956) and Wikipedia, Information Processing Language (Newell, Shaw, Simon, RAND and Carnegie Institute of Technology, about 1956).
Diperiksa: 2026-10-18