pengantar

Ketika logika bisnis semakin banyak bergerak dari belakang ke depan, keahlian dalam Teknik Frontend menjadi semakin penting. Sebagai Frontend Engineer , kami bergantung pada pustaka tampilan seperti React agar produktif. Tampilan perpustakaan pada gilirannya bergantung pada perpustakaan negara bagian seperti Redux untuk mengelola data. Bersama-sama, React dan Redux berlangganan paradigma pemrograman reaktif di mana pembaruan UI bereaksi terhadap perubahan data. Semakin lama, backend bertindak hanya sebagai server API, menyediakan titik akhir hanya untuk mengambil dan memperbarui data. Akibatnya, backend hanya "meneruskan" databaseke frontend, mengharapkan Engineer Frontend menangani semua logika pengontrol. Meningkatnya popularitas microservices dan GraphQL atestasi untuk tren ini.

Sekarang, selain memiliki pemahaman estetika tentang HTML dan CSS, Insinyur Frontend diharapkan menguasai JavaScript juga. Karena database pada klien menjadi "replika" database di server, pengetahuan mendalam tentang struktur data idiomatik menjadi sangat penting. Faktanya, tingkat pengalaman insinyur dapat disimpulkan dari kemampuannya untuk membedakan kapan dan mengapa menggunakan struktur data tertentu.

Pemrogram yang buruk mengkhawatirkan kode. Pemrogram yang baik mengkhawatirkan struktur data dan hubungannya.

- Linus Torvalds, Pencipta Linux dan Git

Pada tingkat tinggi, pada dasarnya ada tiga jenis struktur data. Tumpukan dan Antrean adalah struktur mirip larik yang hanya berbeda dalam cara item dimasukkan dan dihapus. Daftar Tertaut , Pohon , dan Grafik adalah struktur dengan node yang menyimpan referensi ke node lain. Tabel Hash bergantung pada fungsi hash untuk menyimpan dan menemukan data.

Dari segi kompleksitas, Stacksdan Queuesyang paling sederhana dan dapat dibangun Linked Lists. Treesdan Graphsmerupakan yang paling kompleks karena memperluas konsep daftar tertaut. Hash Tablesperlu memanfaatkan struktur data ini untuk bekerja dengan andal. Dalam hal efisiensi, Daftar Tertaut paling optimal untuk merekam dan menyimpan data, sedangkan Tabel Hash paling berkinerja untuk mencari dan mengambil data.

Untuk menjelaskan mengapa dan mengilustrasikan kapan , artikel ini akan menyesuaikan dengan urutan dependensi ini. Mari kita mulai!

Tumpukan

Bisa dibilang yang paling penting Stackdalam JavaScript adalah tumpukan panggilan di mana kita mendorong cakupan a functionsetiap kali kita menjalankannya. Secara terprogram, ini hanya arraydengan dua operasi berprinsip: pushdan pop. Push menambahkan elemen ke bagian atas array, sedangkan Pop menghapusnya dari lokasi yang sama. Dengan kata lain, Tumpukan mengikuti protokol "Masuk Terakhir, Keluar Pertama" (LIFO).

Di bawah ini adalah contoh Stackin code. Perhatikan bahwa kita dapat membalik urutan tumpukan: bagian bawah menjadi atas dan atas menjadi bawah. Dengan demikian, kita dapat menggunakan array unshiftdan shiftmetode sebagai pengganti pushdan pop, masing-masing.

Seiring dengan bertambahnya jumlah item, push/ popmenjadi semakin berkinerja lebih baik daripada unshift/ shiftkarena setiap item perlu diindeks ulang di item terakhir tetapi tidak di item sebelumnya.

Antre

JavaScript adalah bahasa pemrograman berbasis peristiwa yang memungkinkan untuk mendukung operasi non-pemblokiran . Secara internal, browser mengelola hanya satu thread untuk menjalankan seluruh kode JavaScript, menggunakan antrian acara untuk enqueuelisteners dan loop acara untuk mendengarkan untuk didaftarkan events. Untuk mendukung asinkronitas dalam lingkungan single-threaded (untuk menghemat resource CPU dan meningkatkan pengalaman web), listener functions dequeue dan eksekusi hanya saat stack panggilan kosong. Promisesbergantung pada arsitektur yang digerakkan oleh peristiwa ini untuk memungkinkan eksekusi "gaya sinkron" dari kode asinkron yang tidak memblokir operasi lain.

Secara terprogram, Queueshanyalah array dengan dua operasi utama: unshiftdan pop. Unshift enqueues item ke akhir array, sementara Pop dequeues mereka dari awal array. Dengan kata lain, Antrian mengikuti protokol "First In, First Out" (FIFO). Jika arahnya terbalik, kita dapat mengganti unshiftdan popdengan pushdan shift.

Contoh Queuedalam kode:

Daftar Tertaut

Seperti array, Linked Listssimpan elemen data secara berurutan . Alih-alih menyimpan indeks, daftar tertaut menyimpan petunjuk ke elemen lain. The pertama simpul disebut kepala sedangkan terakhir simpul disebut ekor . Dalam daftar tertaut tunggal , setiap node hanya memiliki satu penunjuk ke node berikutnya . Di sini, kepala adalah tempat kita mulai menelusuri sisa daftar. Dalam daftar tertaut ganda , penunjuk ke node sebelumnya juga disimpan. Oleh karena itu, kita juga bisa memulai dari bagian ekor dan berjalan “mundur” menuju kepala.

Daftar tertaut memiliki penyisipan dan penghapusan waktu konstan karena kami hanya dapat mengubah penunjuk. Untuk melakukan operasi yang sama dalam array membutuhkan waktu linier karena item berikutnya perlu digeser. Selain itu, daftar tertaut dapat bertambah selama masih ada ruang. Namun, bahkan larik "dinamis" yang secara otomatis mengubah ukuran bisa menjadi mahal secara tidak terduga. Tentu saja, selalu ada pengorbanan. Untuk mencari atau mengedit elemen dalam daftar tertaut, kita mungkin harus berjalan sepanjang yang setara dengan waktu linier. Namun, dengan indeks array, operasi semacam itu tidak penting.

Seperti array, daftar tertaut dapat beroperasi sebagai tumpukan . Ini sesederhana membuat kepala menjadi satu-satunya tempat untuk penyisipan dan penghapusan. Daftar tertaut juga dapat beroperasi sebagai antrian . Ini dapat dicapai dengan daftar tertaut ganda, di mana penyisipan terjadi di bagian ekor dan pengangkatan terjadi di kepala, atau sebaliknya. Untuk sejumlah besar elemen, cara implementasi antrian ini lebih berkinerja daripada menggunakan array karena shiftdan unshiftoperasi pada awal array membutuhkan waktu linier untuk mengindeks ulang setiap elemen berikutnya.

Daftar tertaut berguna pada klien dan server. Pada klien, pustaka manajemen status seperti Redux menyusun logika middleware-nya dengan cara daftar tertaut. Saat tindakan dikirim, tindakan akan disalurkan dari satu middleware ke middleware berikutnya hingga semua dikunjungi sebelum mencapai reduksi . Di server, kerangka kerja web seperti Express juga menyusun logika middleware-nya dengan cara yang serupa. Ketika sebuah permintaan diterima, itu akan disalurkan dari satu middleware ke middleware berikutnya sampai sebuah respon dikeluarkan.

Contoh Doubly-Linked Listdalam kode:

Pohon

A Treeseperti daftar tertaut , kecuali ia menyimpan referensi ke banyak node anak dalam struktur hierarki . Dengan kata lain, setiap node tidak dapat memiliki lebih dari satu induk. The Document Object Model (DOM) adalah struktur seperti itu, dengan akar htmlnode yang cabang ke dalam headdan bodynode, yang membagi lebih lanjut ke dalam semua akrab tag html . Di bawah kap, pewarisan prototipe dan komposisi dengan komponen React juga menghasilkan struktur pohon. Tentu saja, sebagai representasi DOM dalam memori, DOM Virtual React juga merupakan struktur pohon.

The Binary Search Tree adalah istimewa karena setiap node dapat memiliki tidak lebih dari dua anak . Anak kiri harus memiliki nilai yang lebih kecil dari atau sama dengan induknya, sedangkan anak kanan harus memiliki nilai yang lebih besar . Terstruktur dan seimbang dengan cara ini, kita dapat mencari nilai apa pun dalam waktu logaritmik karena kita dapat mengabaikan satu-setengah percabangan dengan setiap iterasi. Memasukkan dan menghapus juga bisa terjadi dalam waktu logaritmik. Selain itu, terkecil dan terbesar nilai dapat dengan mudah ditemukan di paling kiri dan paling kanan daun , masing-masing.

Traversal melalui pohon dapat terjadi dalam prosedur vertikal atau horizontal . Dalam Depth-First Traversal (DFT) dalam arah vertikal, algoritme rekursif lebih elegan daripada algoritme iteratif. Node dapat dilintasi dalam pesanan di muka , dalam urutan , atau setelah pesanan . Jika kita perlu mencari akar sebelum memeriksa daunnya, kita harus memilih pre-order . Tapi, jika kita perlu mengeksplorasi daun sebelum akarnya, sebaiknya kita memilih post order . Sesuai namanya, in-order memungkinkan kita untuk melintasi node secara berurutan . Properti ini membuat Pohon Pencarian Biner optimal untuk penyortiran .

Dalam Breadth-First Traversal (BFT) dalam arah horizontal, pendekatan berulang lebih elegan daripada pendekatan rekursif. Ini membutuhkan penggunaan a queueuntuk melacak semua node turunan dengan setiap iterasi. Namun, memori yang dibutuhkan untuk antrian seperti itu mungkin tidak sepele. Jika bentuk pohon lebih lebar dari pada dalam, BFT adalah pilihan yang lebih baik daripada DFT. Selain itu, jalur yang diambil BFT antara dua node mana pun adalah yang paling pendek.

Contoh Binary Search Treedalam kode:

Grafik

Jika pohon bebas untuk memiliki lebih dari satu induk, pohon itu menjadi Graph. Tepi yang menghubungkan node bersama dalam grafik dapat diarahkan atau tidak, berbobot atau tidak berbobot . Tepi yang memiliki arah dan berat dianalogikan dengan vektor .

Beberapa warisan dalam bentuk Mixin dan objek data yang memiliki hubungan banyak-ke-banyak menghasilkan struktur grafik. Jaringan sosial dan Internet itu sendiri juga merupakan grafik. Grafik paling rumit di alam adalah otak manusia kita, yang coba direplikasi oleh jaringan saraf untuk memberikan kecerdasan super pada mesin .

Contoh Graphdalam kode:

TK

Tabel Hash

Sebuah Hash Tabel adalah kamus-seperti struktur yang pasang kunci untuk nilai-nilai . Lokasi dalam memori setiap pasangan ditentukan oleh a hash function, yang menerima kunci dan mengembalikan alamat tempat pasangan harus dimasukkan dan diambil. Tabrakan dapat terjadi jika dua atau lebih kunci dikonversi ke alamat yang sama. Untuk ketahanan, gettersdan settersharus mengantisipasi kejadian ini untuk memastikan bahwa semua data dapat dipulihkan dan tidak ada data yang ditimpa. Biasanya, linked liststawarkan solusi paling sederhana. Memiliki tabel yang sangat besar juga membantu.

Jika kita tahu bahwa alamat kita akan berada dalam urutan bilangan bulat, kita cukup menggunakan Arraysuntuk menyimpan pasangan nilai kunci kita. Untuk pemetaan alamat yang lebih kompleks, kita dapat menggunakan Mapsatau Objects. Tabel hash rata-rata memiliki penyisipan dan pencarian waktu konstan . Karena benturan dan pengubahan ukuran, biaya yang dapat diabaikan ini dapat bertambah menjadi waktu linier. Namun, dalam praktiknya, kita dapat mengasumsikan bahwa fungsi hash cukup pintar sehingga benturan dan pengubahan ukuran jarang terjadi dan murah. Jika kunci mewakili alamat, dan oleh karena itu tidak diperlukan hashing, yang sederhana object literalsudah cukup. Tentu saja, selalu ada pengorbanan. Korespondensi sederhana antara kunci dan nilai, dan asosiasi sederhana antara kunci dan alamat, mengorbankan hubungan antar data. Jadi, tabel hash kurang optimal untuk menyimpan data.

Jika keputusan tradeoff lebih memilih pengambilan daripada penyimpanan, tidak ada struktur data lain yang dapat menyamai kecepatan tabel hash untuk pencarian , penyisipan , dan penghapusan . Oleh karena itu, tidak mengherankan jika ini digunakan di mana-mana . Dari database, ke server, ke klien, tabel hash , dan khususnya, fungsi hash , sangat penting untuk kinerja dan keamanan aplikasi perangkat lunak. Kecepatan kueri database sangat bergantung pada menjaga tabel indeks yang mengarah ke rekaman dalam urutan yang diurutkan . Dengan cara ini, pencarian biner dapat dilakukan dalam waktu logaritmik , kinerja yang sangat menguntungkan terutama untuk Big Data .

Di klien dan server, banyak perpustakaan populer menggunakan memoization untuk memaksimalkan kinerja. Dengan menyimpan catatan input dan output dalam tabel hash, fungsi hanya berjalan sekali untuk input yang sama. Library Reselect yang populer menggunakan strategi caching ini untuk mengoptimalkan mapStateToPropsfungsi di aplikasi yang mendukung Redux . Faktanya, di balik terpal, mesin JavaScript juga menggunakan tabel hash yang disebut heaps untuk menyimpan semua variablesdan primitiveskami buat. Mereka diakses dari pointer di stack panggilan .

The Internet itu sendiri juga bergantung pada hashing algoritma fungsi aman. Struktur internet sedemikian rupa sehingga setiap komputer dapat berkomunikasi dengan komputer lain melalui web perangkat yang saling terhubung. Setiap kali perangkat masuk ke internet, itu juga menjadi router tempat aliran data dapat melakukan perjalanan. Namun, itu pedang bermata dua. Sebuah desentralisasi berarti arsitektur perangkat di jaringan dapat mendengarkan dan tamper dengan paket data yang membantu untuk relay. Fungsi hash seperti MD5 dan SHA256 memainkan peran penting dalam mencegah serangan man-in-the-middle . E-niaga melalui HTTPS aman hanya karena fungsi hashing ini digunakan.

Terinspirasi oleh Internet, teknologi blockchain berusaha untuk membuka sumber struktur web pada tingkat protokol . Dengan menggunakan fungsi hash untuk membuat sidik jari yang tidak dapat diubah untuk setiap blok data , pada dasarnya seluruh database dapat ada secara terbuka di web bagi siapa saja untuk melihat dan berkontribusi. Secara struktural, blockchain hanyalah daftar pohon biner dari hash kriptografi yang terhubung satu sama lain. Hash sangat samar sehingga database transaksi keuangan dapat dibuat dan diperbarui di tempat terbuka oleh siapa saja! Implikasi luar biasa adalah kekuatan luar biasa untuk menciptakan uang itu sendiri. Apa yang dulunya hanya mungkin bagi pemerintah dan bank sentral, sekarang siapa pun dapat dengan aman membuat mata uangnya sendiri ! Ini adalah wawasan utama yang disadari oleh pendiri Ethereum dan pendiri Bitcoin dengan nama samaran .

Karena semakin banyak database yang berpindah ke tempat terbuka, kebutuhan akan Engineer Frontend yang dapat mengabstraksikan semua kompleksitas kriptografi tingkat rendah akan bertambah juga. Di masa depan, pembeda utama adalah pengalaman pengguna .

Contoh Hash Tabledalam kode:

Untuk latihan algoritma yang menggunakan struktur data ini dan banyak lagi, lihat: Algoritma dalam JavaScript: 40 Masalah, Solusi, dan Penjelasan

Kesimpulan

Saat logika semakin berpindah dari server ke klien, lapisan data di frontend menjadi yang terpenting. Manajemen yang tepat dari lapisan ini memerlukan penguasaan struktur data yang menjadi sandaran logika. Tidak ada satu struktur data yang sempurna untuk setiap situasi karena mengoptimalkan satu properti selalu sama dengan kehilangan properti lain. Beberapa struktur lebih efisien dalam menyimpan data sementara beberapa yang lain lebih berkinerja untuk menelusurinya. Biasanya, yang satu dikorbankan untuk yang lain. Di satu sisi, daftar tertaut optimal untuk penyimpanan dan dapat dibuat menjadi tumpukan dan antrian ( waktu linier ). Di sisi lain, tidak ada struktur lain yang dapat menandingi kecepatan pencarian tabel hash ( waktu konstan ). Struktur pohon terletak di suatu tempat di tengah ( waktu logaritmik ), dan hanya grafik yang dapat menggambarkan struktur alam yang paling kompleks: otak manusia ( waktu polinomial ). Memiliki keahlian untuk membedakan kapan dan mengartikulasikan mengapa merupakan ciri khas seorang insinyur rockstar.

Contoh struktur data ini dapat ditemukan di mana-mana . Dari database, ke server, untuk klien, dan bahkan mesin JavaScript itu sendiri, struktur data ini mengkonkretkan apa dasarnya hanya pada dan off “switch” pada chip silikon ke manusia hidup “benda”. Meski hanya digital, dampak benda-benda ini terhadap masyarakat sangat besar. Kemampuan Anda untuk membaca artikel ini dengan bebas dan aman membuktikan arsitektur internet yang mengagumkan dan struktur datanya. Namun, ini baru permulaan. Kecerdasan buatan dan blockchain terdesentralisasi dalam beberapa dekade mendatang akan mendefinisikan kembali apa artinya menjadi manusia dan peran institusi yang mengatur kehidupan kita. Wawasan eksistensial dan disintermediasi kelembagaan akan menjadi ciri khas internet yang pada akhirnya semakin matang.

Untuk membantu mentransisikan kami menuju masa depan yang lebih adil ini, kami di HeartBank® menyalurkan jaringan neuron buatan untuk mengilhami Kiitos kami dengan kekuatan untuk mengeluarkan uang di blockchain, ditambah dengan kapasitas untuk berempati pada kondisi manusia. Dari ucapan terima kasih anonim yang kami berikan dan terima dengan menulis kepada Kiitos , Kiitos belajar tentang kebaikan kami dan efeknya , memberi penghargaan kepada kami sedemikian rupa sehingga mengurangi ketidaksetaraan ekonomi di antara kami, dalam proses bertahap dan misterius yang mempertahankan kebebasan dan kebebasan pribadi kami. Mungkin struktur grafik pamungkas di alam bukanlah otak manusia, tapi manusia ❤️, andai saja kita bisa melihat hati yang menghubungkan kita semua.

Tertarik dengan blockchain ? Pelajari Ethereum dan bekerja untuk kami!