فرادرسساختمان های داده در جاوا اسکریپت — به زبان ساده
امروزه شاهد هستیم که منطق تجاری وب‌اپلیکیشن‌ها به مرور از بک‌اند به سمت فرانت‌اند در حال جابجایی است و از این رو خبرگی در زمینه «مهندسی فرانت‌اند» از هر زمان دیگری اهمیت بیشتری یافته است. مهندسان فرانت‌اند امروزه به کتابخانه‌های view از قبیل React وابسته هستند تا بهره‌وری را بالا ببرند. کتابخانه‌های view به نوبه خود به کتابخانه‌های «حالت» (State) مانند Redux وابسته هستند تا داده‌ها را مدیریت کنند. در مجموع ری‌اکت و ریداکس در پارادایم برنامه‌نویسی واکنشی مشارکت دارند که در آن UI در واکنش به تغییرهای داده اقدام به به‌روزرسانی ری‌اکت می‌کند. در این مطلب به بررسی ساختمان های داده در جاوا اسکریپت خواهیم پرداخت.
در عصر حاضر بک‌اند به طور فزاینده‌ای صرفاً به عنوان یک سرور API عمل کرده و نقاط انتهایی لازم برای بازیابی و به‌روزرسانی داده‌ها را عرضه می‌کند. در واقع، بک‌اند صرفاً پایگاه داده را به فرانت‌اند فوروارد می‌کند و انتظار دارد که مهندسان فرانت‌اند همه منطق کنترلر را مدیریت کنند. محبوبیت رو به تزاید میکروسرویس‌ها و GraphQL گواهی بر این روند رو به رشد است.
در حال حاضر انتظار می‌رود که مهندسان فرانت‌اند علاوه برداشتن درکی زیبایی‌شناسانه از HTML و CSS، بر جاوا اسکریپت نیز مسلط باشند. از آنجا که ذخیره داده‌ها در سمت کلاینت به عنوان نسخه‌هایی تکراری از پایگاه داده روی سرور تلقی می‌شود، کسب دانش دقیق از ساختمان‌های داده رایج به امری ضروری تبدیل شده است. درواقع، سطح خبرگی یک مهندس را می‌توان از توانایی وی برای تمییز زمان و چرایی استفاده از یک ساختمان داده، استنباط کرد.
برنامه نویسان بد از کد نگران هستند، اما برنامه نویسان خوب در مورد ساختمان داده و روابط آن دغدغه دارند.
- لینوس تروالدز، خالق لینوکس و گیت
در سطوح بالا اساساً سه نوع ساختمان داده وجود دارد: «پشته» (Stack)، «صف» (Queue) و ساختارهای شبیه آرایه که تنها تفاوتشان در شیوه درج و حذف آیتم‌ها است. لیست‌های پیوندی، درخت و گراف ساختمان‌هایی با گره هستند که به گره‌های دیگر ارجاع می‌دهند. جداول هَش برای ذخیره و مکان‌یابی داده‌ها به تابع‌های هش وابسته هستند.
برحسب پیچیدگی، پشته‌ها و صف‌ها ساده‌ترین ساختمان‌های داده هستند و می‌توانند از لیست‌های پیوندی ساخته شوند. درخت‌ها و گراف‌ها پیچیده‌ترین ساختمان‌های داده هستند که مفهوم لیست پیوندی را بسط داده‌اند. جداول هش نیاز دارند از این ساختمان‌های داده برای کارکرد پایدار بهره بگیرند. برحسب کارایی، لیست‌های پیوندی بهینه‌ترین ساختمان داده برای ثبت و ذخیره داده‌ها محسوب می‌شوند، در حالی که جداول هش برای جستجو و بازیابی داده‌ها بالاترین کارایی را دارند.
در این مقاله برای توضیح علت و روشن ساختن زمان استفاده از هر کدام از این ساختمان‌های داده از ترتیب این وابستگی‌ها تبعیت خواهیم کرد.
پشته
بدیهی است که مهم‌ترین پشته در جاوا اسکریپت «پشته فراخوانی» (call stack) است که هر زمان یک تابع را اجرا می‌کنیم آن را به دامنه تابع ارسال می‌کنیم. از نظر برنامه‌نویسی پشته فراخوانی صرفاً یک آرایه با دو عملیات اصلی یعنی push و pop است. عملیات push عناصری را به ابتدای آرایه اضافه می‌کند در حالی که عملیات pop عناصر را از همان مکان حذف می‌کند. به بیان دیگر پشته از پروتکل «ورودی اول، خروجی اول» به اختصار FIFO تبعیت می‌کند.
در ادامه مثالی از یک پشته را در کد جاوا اسکریپت می‌بینید. دقت کنید که می‌توانیم ترتیب پشته را معکوس کنیم و انتهای پشته به ابتدا بیاید و ابتدا به انتها برود. در چنین حالتی می‌توانیم از متدهای unshift و shift به ترتیب به جای عملیات push و pop استفاده کنیم.
1class Stack {
2 constructor(...items) {
3 this.reverse = false;
4 this.stack = [...items];
5 }
6
7 push(...items) {
8 return this.reverse
9 ? this.stack.unshift(...items)
10 : this.stack.push(...items);
11 }
12
13 pop() {
14 return this.reverse ? this.stack.shift() : this.stack.pop();
15 }
16}
17
18mocha.setup("bdd");
19const { assert } = chai;
20
21describe("Stacks", () => {
22 it("Should push items to top of stack", () => {
23 const stack = new Stack(4, 5);
24 assert.equal(stack.push(1, 2, 3), 5);
25 assert.deepEqual(stack.stack, [4, 5, 1, 2, 3]);
26 });
27
28 it("Should push items to bottom of stack", () => {
29 const stack = new Stack(4, 5);
30 stack.reverse = true;
31 assert.equal(stack.push(1, 2, 3), 5);
32 assert.deepEqual(stack.stack, [1, 2, 3, 4, 5]);
33 });
34
35 it("Should pop item from top of stack", () => {
36 const stack = new Stack(1, 2, 3);
37 assert.equal(stack.pop(), 3);
38 });
39
40 it("Should pop item from bottom of stack", () => {
41 const stack = new Stack(1, 2, 3);
42 stack.reverse = true;
43 assert.equal(stack.pop(), 1);
44 });
45});
46
47mocha.run();زمانی که تعداد آیتم‌ها افزایش پیدا می‌کند، push/pop به طور فزاینده‌ای کارایی بیشتری نسبت به unshift/shift پیدا می‌کنند، زیرا در حالت دوم هر آیتم باید مجدداً اندیس‌گذاری شود، اما در حالت اول چنین الزامی وجود ندارد.
صف
جاوا اسکریپت یک زبان برنامه‌نویسی «رویداد-محور» (event-driven) است که امکان پشتیبانی از عملیات غیر مسدودساز را فراهم می‌سازد. مرورگر به صورت داخلی تنها یک نخ دارد که کل کد جاوا اسکریپت را روی آن اجرا می‌کند و از «صف رویداد» (event queue) برای صف‌بندی شنونده‌ها و از «حلقه رویداد» (event loop) برای گوش دادن به رویدادهای ثبت شده استفاده می‌کند. برای پشتیبانی از ناهمگامی در یک محیط تک نخی (برای صرفه‌جویی در منابع پردازنده و بهبود تجربه وب) تابع‌های شنونده از صف خارج می‌شوند و تنها زمانی اجرا می‌شوند که پشته فراخوانی خالی شود. Promise-ها به این معماری رویداد-محور وابسته هستند که امکان اجرای کد ناهمگام به «سبک همگام» را فراهم می‌سازد و دیگر عملیات را مسدود نمی‌کند.
از نظر برنامه‌نویسی، صف‌ها صرفاً آرایه‌ای هستند که دو عملیات عمده یعنی unshift و pop دارند. unshift آیتم‌ها را در انتهای آرایه صف‌بندی می‌کند در حالی که pop آن‌ها را از ابتدای آرایه از صف خارج می‌کند. به بیان دیگر صف‌ها از پروتکل «ورودی اول، خروجی اول» یا FIFO تبعیت می‌کنند. اگر جهت عوض شود می‌توانیم unshift و pop را به ترتیب با push و shift عوض کنیم.
مثالی از کدنویسی صف در عمل به صورت زیر است:
1class Queue {
2 constructor(...items) {
3 this.reverse = false;
4 this.queue = [...items];
5 }
6
7 enqueue(...items) {
8 return this.reverse
9 ? this.queue.push(...items)
10 : this.queue.unshift(...items);
11 }
12
13 dequeue() {
14 return this.reverse ? this.queue.shift() : this.queue.pop();
15 }
16}
17
18mocha.setup("bdd");
19const { assert } = chai;
20
21describe("Queues", () => {
22 it("Should enqueue items to the left", () => {
23 const queue = new Queue(4, 5);
24 assert.equal(queue.enqueue(1, 2, 3), 5);
25 assert.deepEqual(queue.queue, [1, 2, 3, 4, 5]);
26 });
27
28 it("Should enqueue items to the right", () => {
29 const queue = new Queue(4, 5);
30 queue.reverse = true;
31 assert.equal(queue.enqueue(1, 2, 3), 5);
32 assert.deepEqual(queue.queue, [4, 5, 1, 2, 3]);
33 });
34
35 it("Should dequeue item from the right", () => {
36 const queue = new Queue(1, 2, 3);
37 assert.equal(queue.dequeue(), 3);
38 });
39
40 it("Should dequeue item from the left", () => {
41 const queue = new Queue(1, 2, 3);
42 queue.reverse = true;
43 assert.equal(queue.dequeue(), 1);
44 });
45});
46
47mocha.run();لیست‌های پیوندی
لیست‌های پیوندی نیز همانند آرایه‌ها به ذخیره‌سازی عناصر داده با ترتیب متوالی می‌پردازند. اما لیست‌های پیوندی به جای این که داده‌ها را اندیس‌گذاری کنند، از اشاره‌گر برای اشاره به عناصر دیگر بهره می‌گیرند. نخستین گره به نام head خوانده می‌شود در حالی که گره آخر tail نام دارد. در یک لیست پیوندی یک‌طرفه، هر گره تنها یک اشاره‌گر به گره بعدی دارد. در این وضعیت head جایی است که مسیر حرکت ما تا انتهای لیست از آنجا آغاز می‌شود. در لیست پیوندی دوطرفه، یک اشاره‌گر به گره قبلی نیز نگهداری می‌شود. از این رو می‌توانیم از tail نیز آغاز کنیم و در جهت معکوس به سمت head حرکت کنیم.
در لیست‌های پیوندی عملیات درج و حذف دارای زمان ثابتی است، زیرا می‌تواند صرفاً اشاره‌گرها را عوض کرد. اجرای عملیات مشابه در آرایه‌ها دارای پیچیدگی زمانی خطی است، زیرا آیتم‌های بعدی نیز باید جابجا شوند. ضمناً لیست‌های پیوندی می‌توانند تا جایی که فضا اجازه می‌دهد بسط یابند. با این وجود حتی آرایه‌های دینامیک که به طور خودکار تغییر اندازه می‌دهند نیز ممکن است به طور غیرمترقبه‌ای پرهزینه شوند. البته همواره تعادلی بین این مزایا و معایب وجود دارد. برای گشتن به دنبال یک عنصر و ویرایش کردن آن در لیست پیوندی ممکن است لازم باشد کل طول لیست را بپیماییم که از نظر زمانی دارای پیچیدگی خطی خواهد بود. در حالی که با وجود اندیس در آرایه‌ها چنین عملیاتی بسیار ساده‌تر است.
لیست‌های پیوندی نیز همچون آرایه‌ها می‌توانند به صورت پشته عمل کنند. این کار به سادگی اجرا می‌شود بدین ترتیب که head به عنوان تنها مکان برای درج و حذف عناصر استفاده می‌شود. لیست‌های پیوندی می‌توانند به صوت صف نیز مورد استفاده قرار گیرند. این وضعیت با استفاده از یک لیست پیوندی دوطرفه میسر می‌شود که در آن عملیات درج در tail رخ می‌دهد و عملیات حذف در head انجام می‌یابد و یا برعکس. در مورد تعداد بالای عناصر، این روش پیاده‌سازی صف بسیار کارآمدتر از استفاده از آرایه است، زیرا عملیات shift و unshift در ابتدای آرایه زمان خطی دارند و نیازمند اندیس‌گذاری مجدد همه عناصر بعدی هستند.
لیست‌های پیوندی در هر دو سمت کلاینت و سرور مفید هستند. در سمت کلاینت کتابخانه‌های مدیریت «حالت» (State) مانند ریداکس منطق میان‌افزاری خود را به روشی مانند لیست پیوندی سازماندهی می‌کنند. زمانی که اکشن ارسال می‌شود این کتابخانه آن را از یک میان‌افزار به دیگری pipe می‌کند و همین طور تا آخر می‌رود تا این که پیش از رسیدن به «کاهنده‌ها» (Reducers) همه میان‌افزارها را بازدید کرده باشد. در سمت سرور فریمورک‌های وب مانند Express نیز منطق میان‌افزاری خود را به روش مشابهی سازماندهی می‌کنند. زمانی که یک درخواست دریافت می‌شود، از یک میان‌افزار به دیگری pipe می‌شود تا این که یک پاسخ صادر شود.
نمونه‌ای از لیست پیوندی دوطرفه را در مثال زیر ملاحظه می‌کنید:
1class Node {
2 constructor(value, next, prev) {
3 this.value = value;
4 this.next = next;
5 this.prev = prev;
6 }
7}
8
9class LinkedList {
10 constructor() {
11 this.head = null;
12 this.tail = null;
13 }
14
15 addToHead(value) {
16 const node = new Node(value, null, this.head);
17 if (this.head) this.head.next = node;
18 else this.tail = node;
19 this.head = node;
20 }
21
22 addToTail(value) {
23 const node = new Node(value, this.tail, null);
24 if (this.tail) this.tail.prev = node;
25 else this.head = node;
26 this.tail = node;
27 }
28
29 removeHead() {
30 if (!this.head) return null;
31 const value = this.head.value;
32 this.head = this.head.prev;
33 if (this.head) this.head.next = null;
34 else this.tail = null;
35 return value;
36 }
37
38 removeTail() {
39 if (!this.tail) return null;
40 const value = this.tail.value;
41 this.tail = this.tail.next;
42 if (this.tail) this.tail.prev = null;
43 else this.head = null;
44 return value;
45 }
46
47 search(value) {
48 let current = this.head;
49 while (current) {
50 if (current.value === value) return value;
51 current = current.prev;
52 }
53 return null;
54 }
55
56 indexOf(value) {
57 const indexes = [];
58 let current = this.tail;
59 let index = 0;
60 while (current) {
61 if (current.value === value) indexes.push(index);
62 current = current.next;
63 index++;
64 }
65 return indexes;
66 }
67}
68
69mocha.setup("bdd");
70const { assert } = chai;
71
72describe("Linked List", () => {
73 it("Should add to head", () => {
74 const list = new LinkedList();
75 list.addToHead(1);
76 list.addToHead(2);
77 list.addToHead(3);
78 assert.equal(list.tail.prev, null);
79 assert.equal(list.tail.value, 1);
80 assert.equal(list.tail.next.value, 2);
81 assert.equal(list.head.prev.value, 2);
82 assert.equal(list.head.value, 3);
83 assert.equal(list.head.next, null);
84 assert.equal(list.head.prev.prev.value, 1);
85 assert.equal(list.tail.next.next.value, 3);
86 });
87
88 it("Should add to tail", () => {
89 const list = new LinkedList();
90 list.addToTail(1);
91 list.addToTail(2);
92 list.addToTail(3);
93 assert.equal(list.tail.prev, null);
94 assert.equal(list.tail.value, 3);
95 assert.equal(list.tail.next.value, 2);
96 assert.equal(list.head.prev.value, 2);
97 assert.equal(list.head.value, 1);
98 assert.equal(list.head.next, null);
99 assert.equal(list.head.prev.prev.value, 3);
100 assert.equal(list.tail.next.next.value, 1);
101 });
102
103 it("Should remove head", () => {
104 const list = new LinkedList();
105 list.addToHead(1);
106 list.addToHead(2);
107 list.addToHead(3);
108 assert.equal(list.removeHead(), 3);
109 assert.equal(list.head.value, 2);
110 assert.equal(list.tail.value, 1);
111 assert.equal(list.tail.next.value, 2);
112 assert.equal(list.head.prev.value, 1);
113 assert.equal(list.head.next, null);
114 assert.equal(list.removeHead(), 2);
115 assert.equal(list.head.value, 1);
116 assert.equal(list.tail.value, 1);
117 assert.equal(list.tail.next, null);
118 assert.equal(list.head.prev, null);
119 assert.equal(list.head.next, null);
120 assert.equal(list.removeHead(), 1);
121 assert.equal(list.head, null);
122 assert.equal(list.tail, null);
123 });
124
125 it("Should remove tail", () => {
126 const list = new LinkedList();
127 list.addToTail(1);
128 list.addToTail(2);
129 list.addToTail(3);
130 assert.equal(list.removeTail(), 3);
131 assert.equal(list.head.value, 1);
132 assert.equal(list.tail.value, 2);
133 assert.equal(list.tail.next.value, 1);
134 assert.equal(list.head.prev.value, 2);
135 assert.equal(list.tail.prev, null);
136 assert.equal(list.removeTail(), 2);
137 assert.equal(list.head.value, 1);
138 assert.equal(list.tail.value, 1);
139 assert.equal(list.tail.next, null);
140 assert.equal(list.head.prev, null);
141 assert.equal(list.tail.prev, null);
142 assert.equal(list.removeTail(), 1);
143 assert.equal(list.head, null);
144 assert.equal(list.tail, null);
145 });
146
147 it("Should search for value", () => {
148 const list = new LinkedList();
149 list.addToHead(1);
150 list.addToHead(2);
151 list.addToHead(3);
152 assert.equal(list.search(1), 1);
153 assert.equal(list.search(2), 2);
154 assert.equal(list.search(3), 3);
155 assert.equal(list.search(4), null);
156 });
157
158 it("Should search for indexes of value", () => {
159 const list = new LinkedList();
160 list.addToTail(1);
161 list.addToTail(2);
162 list.addToTail(3);
163 list.addToTail(3);
164 list.addToTail(1);
165 assert.deepEqual(list.indexOf(1), [0, 4]);
166 assert.deepEqual(list.indexOf(2), [3]);
167 assert.deepEqual(list.indexOf(3), [1, 2]);
168 assert.deepEqual(list.indexOf(4), []);
169 });
170});
171
172mocha.run();درخت
«درخت» (Tree) شبیه به لیست پیوندی است به جز این که هر آیتم در آن به گره‌های فرزند زیادی ارجاع می‌دهد و ساختاری سلسله مراتبی دارد. به بیان دیگر هر گره نمی‌تواند بیش از یک والد داشته باشد. «مدل شیء سند» (Document Object Model) یا به اختصار DOM چنین ساختاری است که ریشه آن گره html است که به گره‌های body و head تقسیم می‌شود و سپس به همه تگ‌های آشنای خانواده html انشعاب می‌یابد. وراثت پروتوتایپی و ترکیب‌بندی با استفاده از کامپوننت‌های ری‌اکت نیز در پس زمینه، ساختارهای درخت را بازتولید می‌کنند. البته DOM مجازی ری‌اکت به عنوان یک بازنمایی درون حافظه‌ای از DOM نیز ساختاری درختی دارد.
درخت جستجوی دودویی درخت خاصی است، زیرا در آن هر گره نمی‌تواند بیش از دو فرزند داشته باشد. فرزند چپ باید مقداری کمتر یا برابر با والد خود داشته باشد، در حالی که فرزند راست باید مقدار بزرگ‌تری داشته باشد. درخت جستجوی دودویی به این ترتیب سازماندهی یافته و متعادل شده است و بنابراین می‌توانیم در طی یک زمان لگاریتمی به دنبال هر آیتمی بگردیم، زیرا می‌توانیم در هر تکرار نیمی از انشعاب باقی‌مانده را نادیده بگیریم. درج و حذف نیز می‌تواند در زمان لگاریتمی اجرا شود. به علاوه کوچک‌ترین و بزرگ‌ترین مقدار می‌تواند به سادگی به ترتیب در برگ‌های انتهای سمت چپ و انتهای سمت راست مشاهده شود.
پیمایش درخت به دو شیوه افقی و عمودی اجرا می‌شود. «پیمایش عمق-اول» (Depth-First Traversal) یا به اختصار DFT در جهت عمودی صوت می‌گیرد و یک الگوریتم بازگشتی مناسب‌تر از نوع تکراری است. گره‌ها می‌توانند به روش‌های پیش‌ترتیبی، میان‌ترتیبی یا پس‌ترتیبی پیمایش شوند. اگر لازم باشد ریشه‌ها را پیش از بازرسی برگ‌ها بررسی کنیم، باید روش پیش‌ترتیبی را انتخاب کنیم. اما اگر نیاز باشد که برگ‌ها قبل از ریشه بررسی شوند، باید از روش پس‌ترتیبی استفاده کنیم. روش میان‌ترتیبی نیز چنان که از نامش مشخص است امکان پیمایش گره‌ها به روش متوالی را فراهم می‌سازد. این مشخصه موجب شده است که درخت جستجوی دودویی برای مرتب‌سازی بهینه باشد.
در روش «پیمایش سطح-اول» (Breadth-First Traversal) که به اختصار BFT نامیده می‌شود، از جهت‌گیری افقی استفاده می‌شود و رویکرد تکرار مناسب‌تر از رویکرد بازگشتی است. این پیمایش نیازمند استفاده از صف برای ردگیری همه گره‌های فرزند در هر تکرار است. با این حال، حافظه مورد نیاز برای چنین صفی ممکن است سنگین باشد. اگر شکل درخت بیشتر عریض است تا عمیق، BFT گزینه بهتری نسبت به DFT محسوب می‌شود. ضمناً مسیری که BFT بین هر دو گره طی می‌کند، کوتاه‌ترین مسیر ممکن است. نمونه‌ای از کد درخت جستجوی دودویی را در ادامه ملاحظه می‌کنید:
1class Tree {
2 constructor(value) {
3 this.value = value;
4 this.left = null;
5 this.right = null;
6 }
7
8 insert(value) {
9 if (value <= this.value) {
10 if (!this.left) this.left = new Tree(value);
11 else this.left.insert(value);
12 } else {
13 if (!this.right) this.right = new Tree(value);
14 else this.right.insert(value);
15 }
16 }
17
18 contains(value) {
19 if (value === this.value) return true;
20 if (value < this.value) {
21 if (!this.left) return false;
22 else return this.left.contains(value);
23 } else {
24 if (!this.right) return false;
25 else return this.right.contains(value);
26 }
27 }
28
29 depthFirstTraverse(order, callback) {
30 order === "pre" && callback(this.value);
31 this.left && this.left.depthFirstTraverse(order, callback);
32 order === "in" && callback(this.value);
33 this.right && this.right.depthFirstTraverse(order, callback);
34 order === "post" && callback(this.value);
35 }
36
37 breadthFirstTraverse(callback) {
38 const queue = [this];
39 while (queue.length) {
40 const root = queue.shift();
41 callback(root.value);
42 root.left && queue.push(root.left);
43 root.right && queue.push(root.right);
44 }
45 }
46
47 getMinValue() {
48 if (this.left) return this.left.getMinValue();
49 return this.value;
50 }
51
52 getMaxValue() {
53 if (this.right) return this.right.getMaxValue();
54 return this.value;
55 }
56}
57
58mocha.setup("bdd");
59const { assert } = chai;
60
61const tree = new Tree(5);
62for (const value of [3, 6, 1, 7, 8, 4, 10, 2, 9]) tree.insert(value);
63
64/*
65 5
66 3 6
671 4 7
68 2 8
69 10
70 9
71*/
72
73describe("Binary Search Tree", () => {
74 it("Should implement insert", () => {
75 assert.equal(tree.value, 5);
76 assert.equal(tree.left.value, 3);
77 assert.equal(tree.right.value, 6);
78 assert.equal(tree.left.left.value, 1);
79 assert.equal(tree.right.right.value, 7);
80 assert.equal(tree.right.right.right.value, 8);
81 assert.equal(tree.left.right.value, 4);
82 assert.equal(tree.right.right.right.right.value, 10);
83 assert.equal(tree.left.left.right.value, 2);
84 assert.equal(tree.right.right.right.right.left.value, 9);
85 });
86
87 it("Should implement contains", () => {
88 assert.equal(tree.contains(2), true);
89 assert.equal(tree.contains(9), true);
90 assert.equal(tree.contains(0), false);
91 assert.equal(tree.contains(11), false);
92 });
93
94 it("Should implement depthFirstTraverse", () => {
95 const _pre = [];
96 const _in = [];
97 const _post = [];
98 tree.depthFirstTraverse("pre", value => _pre.push(value));
99 tree.depthFirstTraverse("in", value => _in.push(value));
100 tree.depthFirstTraverse("post", value => _post.push(value));
101 assert.deepEqual(_pre, [5, 3, 1, 2, 4, 6, 7, 8, 10, 9]);
102 assert.deepEqual(_in, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
103 assert.deepEqual(_post, [2, 1, 4, 3, 9, 10, 8, 7, 6, 5]);
104 });
105
106 it("Should implement breadthDepthTraverse", () => {
107 const result = [];
108 tree.breadthFirstTraverse(value => result.push(value));
109 assert.deepEqual(result, [5, 3, 6, 1, 4, 7, 2, 8, 10, 9]);
110 });
111
112 it("Should implement getMinValue", () => {
113 assert.equal(tree.getMinValue(), 1);
114 });
115
116 it("Should implement getMaxValue", () => {
117 assert.equal(tree.getMaxValue(), 10);
118 });
119});
120
121mocha.run();گراف
اگر در یک درخت امکان این باشد که هر گره بیش از یک والد داشته باشد، آن را گراف می‌نامیم. یالی که گره‌ها را در گراف به هم وصل می‌کند، می‌تواند جهت‌دار یا غیر جهت‌دار، وزن‌دار یا بی‌وزن باشد. یال‌های دو جهته و وزن‌دار، شبیه بُردار هستند.
وراثت‌های چندگانه به شکل Mixin و اشیای داده که روابط چند به چند دارند ساختمان‌های داده گراف را ایجاد می‌کنند. یک شبکه اجتماعی و خود اینترنت نیز گراف محسوب می‌شوند. پیچیده‌ترین گراف برحسب ماهیت، مغز انسان است که الگوریتم‌های شبکه عصبی تلاش می‌کنند با شبیه‌سازی آن به ماشین‌ها نوعی فراهوشمندی بدهند.
نمونه‌ای از کد گراف به صورت زیر است:
1const fibonacci = element => {
2 return element < 3 ? 1 : fibonacci(element - 1) + fibonacci(element - 2);
3};
4
5mocha.setup("bdd");
6const { assert } = chai;
7
8describe("Graphs", () => {
9 it("todo", () => {
10 assert.equal(fibonacci(6), 8);
11 assert.equal(fibonacci(10), 55);
12 });
13});
14
15mocha.run();جداول هش
جداول هش ساختمان‌های شبه دیکشنری هستند که از جفت کلید/مقدار استفاده می‌کنند. مکان حافظه برای هر جفت بر اساس تابع هش تعیین می‌شود که یک کلید می‌پذیرد و آدرسی که جفت باید درج و بازیابی شود را بازمی‌گرداند. در صورتی که دو یا چند کلید به آدرس یکسانی تبدیل شوند، تصادم رخ می‌دهد. برای افزایش پایداری باید getter و setter، این رویدادها را پیش‌بینی کنند و اطمینان حاصل کنند که همه داده‌ها می‌توانند بازیابی شوند و هیچ داده‌ای بازنویسی نمی‌شوند. به طور معمول linked lists ساده‌ترین راه‌حل هستند. داشتن جداول بسیار بزرگ نیز در این زمینه کمک زیادی خواهد کرد.
اگر بدانیم که آدرس‌های ما توالی‌های عدد صحیح هستند، می‌توانیم صرفاً از Arrays برای ذخیره‌سازی جفت‌های کلید-مقدار استفاده کنیم. برای نگاشت‌های آدرس پیچیده‌تر می‌توانیم از Maps یا Objects استفاده کنیم. جداول هش به طور میانگین زمان ثابتی برای درج و جستجو دارند. به دلیل تصادم و تغییر اندازه، این هزینه ناچیز می‌تواند به صورت زمان خطی رشد کند. با این حال در عمل می‌توانیم تصور کنیم که تابع‌های هش به قدر کافی هوشمند هستند که تصادم و تغییر اندازه نادر و ارزان است. اگر کلیدها نماینده آدرس‌ها باشند و زمانی که به هیچ هش کردن نیاز نباشد، می‌توان از یک object literal استفاده کرد. البته همواره تعادلی بین مزیت‌ها و معایب وجود دارند. تناظر ساده بین کلید و مقدار و ارتباط ساده بین کلیدها و آدرس‌ها، روابط بین داده‌ها را قربانی می‌کند. از این رو جداول هش برای مرتب‌سازی داده‌ها اصلاً بهینه نیستند.
اگر کفه تصمیم شما به سمت بازیابی سنگین‌تر است تا ذخیره‌سازی، هیچ ساختمان داده دیگری نمی‌تواند سرعتی که جداول هش برای گشتن، درج، و حذف ارائه می‌کنند در اختیار شما قرار دهد. در نتیجه هیچ جای شگفتی نیست که از جداول هش تقریباً در همه جا استفاده می‌شود. از پایگاه داده تا سرور و کلاینت، جداول هش و به طور خاص تابع‌های هش برای عملکرد و امنیت اپلیکیشن‌های نرم‌افزاری حیاتی هستند. سرعت کوئری‌های پایگاه داده تا حدود زیادی به نگهداری اندیس‌های جدولی که به رکوردهای مرتب‌شده اشاره می‌کنند وابسته است. بدین ترتیب جستجوهای دودویی می‌توانند در زمان لگاریتمی اجرا شوند که ارتقای عملکرد عظیمی به خصوص در حوزه کلان‌داده محسوب می‌شود.
در هر دو سمت کلاینت و سرور کتابخانه‌های محبوب زیادی وجود دارند که از memorization برای بیشینه‌سازی عملکرد بهره می‌گیرند. با حفظ سوابق ورودی‌ها و خروجی‌ها در جدول هش، تابع‌ها برای ورودی‌های یکسان صرفاً یک بار اجرا می‌شوند. کتابخانه محبوب Reselect از این راهبرد کَش کردن برای بهینه‌سازی تابع‌ها در اپلیکیشن‌هایی که از ریداکس استفاده می‌کنند بهره می‌گیرد. در واقع موتور جاوا اسکریپت در پس زمینه از جداول هش به نام heap برای ذخیره‌سازی همه variables و primitives که ایجاد کردیم بهره می‌گیرد. این موارد از طریق اشاره‌گرها به پشته فراخوانی مورد دسترسی قرار می‌گیرند.
خود اینترنت برای عملکرد صحیحش بر مبنای الگوریتم‌های هش کردن بنا شده است. ساختار اینترنت به طوری است که هر رایانه‌ای می‌تواند با رایانه دیگر از طریق شبکه‌ای از دستگاه‌های به هم متصل ارتباط برقرار کند. هر زمان که یک دستگاه وارد اینترنت می‌شود خود به یک روتر تبدیل می‌شود که جریان داده‌ها می‌توانند از آن بگذرند. اما این یک شمشیر دو لبه است. معماری نامتمرکز به این معنی است که هر دستگاهی در شبکه می‌تواند بسته‌های داده را مورد شنود قرار دهد و آن‌ها را که رله می‌کند دستکاری نماید. تابع‌های هش مانند MD5 و SHA256 نقشی حیاتی در جلوگیری از چنین حمله‌های «مرد میانی» (Man-in-the-Middle) دارند. تجارت الکترونیک در بستر HTTPS تنها به این جهت امن است که این تابع‌های هش مورد استفاده قرار می‌گیرند.
فناوری بلاک چین که از اینترنت الهام گرفته به دنبال این است که ساختار وب را در سطح پروتکل، متن‌باز کند. بلاک چین با بهره‌گیری از تابع‌های هش برای ایجاد «اثرانگشت‌های تغییرناپذیر» (immutable fingerprints) برای هر بلوک داده کاری کرده است که اساساً کل پایگاه داده امکان حضور آزادانه روی وب برای همه افرادی که قصد مشارکت دارند پیدا کند. بلاک چین از نظر ساختاری صرفاً لیست‌های پیوندی یک‌طرفه‌ای از درخت‌های دودوییِ هش‌های رمزنگاری‌شده است.
هش کردن چنان جنبه رمزنگاری‌شده‌ای دارد که با استفاده از آن می‌توان یک پایگاه داده از تراکنش‌های مالی را طوری ایجاد و به‌روزرسانی کرد که هر کس به آن دسترسی آزاد داشته باشد. نتیجه ضمنی خارق‌العاده این وضعیت قدرت شگفت‌انگیز خلق پول بوده است. کاری که روزگاری صرفاً تحت سلطه دولت‌ها و بانک‌های مرکزی بود؛ اما امروزه هر کس می‌تواند پول خاص خود را خلق کند. این همان بینش کلیدی بود که بنیان‌گذار «اتریوم» (Ethereum) و مبدع ناشناس بیت‌کوین درک کرده‌اند.
همچنان که رفته‌رفته پایگاه‌های داده بیشتری باز می‌شوند، نیاز به مهندسان فرانت‌اند خبره که بتوانند همه سطوح پیچیدگی‌های رمزنگارانه سطح پایین را تجزیه کرده و همچنین ترکیب کنند، بیشتر حس می‌شود. در چنین آینده‌ای عامل تمایز اصلی تجربه کاربری خواهد بود.
در کد زیر می‌توانید نمونه‌ای از جدول هش را ملاحظه کنید:
1class Node {
2 constructor(key, value) {
3 this.key = key;
4 this.value = value;
5 this.next = null;
6 }
7}
8
9class Table {
10 constructor(size) {
11 this.cells = new Array(size);
12 }
13
14 hash(key) {
15 let total = 0;
16 for (let i = 0; i < key.length; i++) total += key.charCodeAt(i);
17 return total % this.cells.length;
18 }
19
20 insert(key, value) {
21 const hash = this.hash(key);
22 if (!this.cells[hash]) {
23 this.cells[hash] = new Node(key, value);
24 } else if (this.cells[hash].key === key) {
25 this.cells[hash].value = value;
26 } else {
27 let node = this.cells[hash];
28 while (node.next) {
29 if (node.next.key === key) {
30 node.next.value = value;
31 return;
32 }
33 node = node.next;
34 }
35 node.next = new Node(key, value);
36 }
37 }
38
39 get(key) {
40 const hash = this.hash(key);
41 if (!this.cells[hash]) return null;
42 else {
43 let node = this.cells[hash];
44 while (node) {
45 if (node.key === key) return node.value;
46 node = node.next;
47 }
48 return null;
49 }
50 }
51
52 getAll() {
53 const table = [];
54 for (let i = 0; i < this.cells.length; i++) {
55 const cell = [];
56 let node = this.cells[i];
57 while (node) {
58 cell.push(node.value);
59 node = node.next;
60 }
61 table.push(cell);
62 }
63 return table;
64 }
65}
66
67mocha.setup("bdd");
68const { assert } = chai;
69
70const table = new Table(5);
71table.insert("baa", 1);
72table.insert("aba", 2);
73table.insert("aba", 3);
74table.insert("aac", 4);
75table.insert("aac", 5);
76
77describe("Hash Table", () => {
78 it("Should implement hash", () => {
79 assert.equal(table.hash("abc"), 4);
80 });
81
82 it("Should implement insert", () => {
83 assert.equal(table.cells[table.hash("baa")].value, 1);
84 assert.equal(table.cells[table.hash("aba")].next.value, 3);
85 assert.equal(table.cells[table.hash("aac")].value, 5);
86 });
87
88 it("Should implement get", () => {
89 assert.equal(table.get("baa"), 1);
90 assert.equal(table.get("aba"), 3);
91 assert.equal(table.get("aac"), 5);
92 assert.equal(table.get("abc"), null);
93 });
94
95 it("Should implement getAll", () => {
96 assert.deepEqual(table.getAll(), [[], [], [1, 3], [5], []]);
97 });
98});
99
100mocha.run();سخن پایانی
همچنان که منطق تجاری به صورت فزاینده‌ای در حال جابجایی از سمت سرور به سمت کلاینت است، لایه داده در فرانت‌اند رواج بیشتری می‌یابد. مدیریت صحیح این لایه نیازمند چیرگی بر ساختمان‌های داده است که منطق تجاری بر مبنای آن شکل می‌گیرد. هیچ ساختمان داده‌ای برای همه موقعیت‌ها کامل محسوب نمی‌شود، چون بهینه‌سازی برای یک مشخصه عموماً موجب ضعف در مشخصه دیگر می‌شود. برخی ساختارها در ذخیره‌سازی داده‌ها کارآمدتر هستند، در حالی که برخی دیگر برای جستجوی داده‌ها کارایی بیشتری دارند. به طور معمول، یکی از این‌ها قربانی دیگری می‌شود.
در یک انتها، لیست‌های پیوندی برای ذخیره‌سازی بهینه هستند و می‌توان پشته و صف را با زمان خطی ساخت. در سمت دیگر هیچ ساختمان دیگری نمی‌تواند با سرعت جستجوی جدول هش (زمان ثابت) برابری کند. ساختمان‌های درخت در میانه این طیف (زمان لگاریتمی) قرار می‌گیرند و تنها یک گراف می‌تواند ماهیت پیچیده‌ترین ساختار طبیعی یعنی مغز انسان را (با زمان چندجمله‌ای) نمایش دهد. کسب مجموعه مهارت‌های مورد نیاز برای تمییز زمان و توضیح چرایی استفاده از یک ساختمان داده نشانه‌ای از توانایی‌های یک مهندس کاملاً خبره است.
نمونه‌هایی از این ساختمان‌های داده را می‌توانید هر کجا از پایگاه داده، تا سرور، تا کلاینت و حتی خود زبان جاوا اسکریپت ببینید. این ساختمان‌های داده سوییچ‌های روشن و خاموش روی تراشه‌های سیلیکونی را به اشیای شبه زنده‌ای تبدیل می‌کنند. گرچه این اشیا صرفاً دیجیتالی هستند اما تأثیری که روی جامعه دارند کاملاً شگرف است. این که شما امکان مطالعه این مقاله به صورت امن و رایگان را به دست آورده‌اید، مدیون معماری خارق‌العاده اینترنت و سازماندهی داده‌های آن است. با این حال این تنها یک شروع است. هوش مصنوعی و بلاک چین‌های نامتمرکز در دهه‌های آتی ماهیت انسان و نقش موسسه‌هایی که بر زندگی ما حکمرانی می‌کنند را بازتعریف خواهند کرد. بینش‌های وجودگرایانه و واسطه‌زدایی از نهادها جزء خصوصیات اینترنت هستند که نهایتاً در حال رسیدن به بلوغ هستند.
اگر این مطلب برای شما مفید بوده است، آموزشهای زیر نیز به شما پیشنهاد می‌شوند:
- مجموعه آموزشهای JavaScript (جاوا اسکریپت)
- آموزش پیشرفته ساختمان داده
- مجموعه آموزشهای ساختمان داده و طراحی الگوریتم
- آموزش ساختمان داده — مجموعه مقالات جامع وبلاگ فرادرس
- ساختار داده و الگوریتم ها — راهنمای مقدماتی
==
