هر اندازه‌ای که در لایه منطق تجاری از سمت بک اند (backend) به سمت فرانت اند (frontend) سوق پیدا کنیم، اهمیت تخصص در مهندسی فرانت اند یا سمت کاربر (Frontend Engineering) خود را بیشتر نمایان می‌کند. به عنوان مهندسین فرانت اند یا سمت کاربر (Frontend Engineers)، وابستگی ما بر کارآیی کتابخانه‌های دیداری (view libraries) همچون React بیشتر و بیشتر می‌شود.
کتابخانه‌های دیداری نیز به نوبه خود بر کتابخانه‌های وضعیتی (state libraries) همچون Redux وابستگی دارند تا داده‌ها را مدیریت کنند. روی هم رفته، کتابخانه‌های React و Redux نیز تحت پارادایم برنامه‌نویسی واکنش‌گرا هستند تا رابط کاربری را بر طبق تغییرات صورت گرفته در داده‌ها، بروز رسانی کنند.
بک اندها بطور فزآینده‌ای صرفاً به عنوان سرورهای API (رابط برنامه‌نویسی کاربردی) عمل می‌کنند تا نقاطی پایانی (endpoints) برای بازیابی و بروز رسانی داده‌ها فراهم کنند. در عمل، بک اند صرفاً پایگاه‌داده را به سمت فرانت اند می‌فرستد و وظیفه اداره کردن تمامی کنترل‌گر منطقی بر عهده مهندس فرانت اند است. محبوبیت روز افزون میکروسرویس‌ها و GraphQL نیز گواه بر این روند و شیوه در حال رشد است.
امروزه مهندسین فرانت اند نه تنها باید درکی کلی از HTML و CSS داشته باشند، بلکه مجاب هستند تا تسلط کاملی بر JavaScript نیز داشته باشند. از آنجایی که ذخیره‌داده‌های (datastores) کلاینت در حال تبدیل به نسخه‌های روبرداشتی از پایگاه‌داده‌های بر روی سرور هستند، نقش دانش اساسی از ساختمان‌داده‌های اصطلاحی پر رنگ‌تر می‌شود. در حقیقت، میزان تجربه یک مهندس را می‌توان از توانایی وی در زمان استفاده و دلیل استفاده از یک ساختمان‌داده خاص استنتاج کرد.
در سطوح بالای برنامه‌نویسی، اساساً سه نوع ساختمان‌داده وجود دارد. Stack ها و Queue ها ساختارهایی آرایه مانند هستند که تنها تفاوت‌شان در نحوه وارد کردن و پاک کردن آیتم‌ها است. Linked List ها، Tree ها و Graph ها نیز ساختارهایی گره‌داری هستند که مرجع گره‌های دیگر را در خود دارند. Hash Table ها نیز وابسته توابع درهم‌ساز (hash functions) هستند تا داده‌ها را ذخیره‌کرده و مکان‌یابی کنند.
اگر از لحاظ پیچیدگی این انواع را دسته‌بندی کنیم، Stack ها و Queue ها ساده‌ترین سطح پیچیدگی را دارند و آنها را می‌توان به کمک Linked List ها ایجاد کرد. Tree ها و Graph ها نیز پیچیده‌ترین نوع هستند زیرا بسط‌یافته مفهوم Linked List هستند. جداول هش (Hash Tables) برای عملکرد قابل اعتماد خود نیازمند بکارگیری این ساختمان‌داده‌ها هستند. در دیدگاه کارآیی، بهینه‌ترین نوع ساختارها برای ثبت و ذخیره‌سازی داده‌ها، Linked List ها هستند؛ در حالی که Hash Table ها کارآمدترین ساختارها برای جستجو و بازیابی داده‌ها خواهند بود.
برای اینکه درک بهتری از دلیل استفاده و زمان استفاده داشته باشید، طبق ترتیب این وابستگی‌ها پیش خواهیم رفت.
بدون شک مهم‌ترین Stack در جاوا اسکریپت، call stack است که در آن دامنه (scope) یک تابع (function) را زمانی که آن را اجرا می‌کنیم، می‌توانیم وارد کنیم. از لحاظ برنامه‌نویسی، این صرفاً یک آرایه (array) با دو عملیات اصلی است: Push و Pop. Push المان‌ها را به بالای آرایه می‌افزاید، در حالی که Pop آنها را از همان محل پاک می‌کند. به عبارت دیگر، Stack ها از پروتکل “آخرین ورودی، اولین خروجی” یا همان پروتکل LIFO) Last In, First Out) استفاده می‌کنند. در زیر مثالی از کدنویسی Stack را آورده‌ایم. دقت کنید که می‌توانیم ترتیب Stack را معکوس کنیم: انتهای استک تبدیل به ابتدای آن شود و بالعکس. بدین طریق می‌توانیم به ترتیب از روش‌های Unshift و Shift آرایه به جای Push و Pop استفاده کنیم.
class Stack {
constructor(...items) {
this.reverse = false;
this.stack = [...items];
}
push(...items) {
return this.reverse
? this.stack.unshift(...items)
: this.stack.push(...items);
}
pop() {
return this.reverse ? this.stack.shift() : this.stack.pop();
}
}
mocha.setup("bdd");
const { assert } = chai;
describe("Stacks", () => {
it("Should push items to top of stack", () => {
const stack = new Stack(4, 5);
assert.equal(stack.push(1, 2, 3), 5);
assert.deepEqual(stack.stack, [4, 5, 1, 2, 3]);
});
it("Should push items to bottom of stack", () => {
const stack = new Stack(4, 5);
stack.reverse = true;
assert.equal(stack.push(1, 2, 3), 5);
assert.deepEqual(stack.stack, [1, 2, 3, 4, 5]);
});
it("Should pop item from top of stack", () => {
const stack = new Stack(1, 2, 3);
assert.equal(stack.pop(), 3);
});
it("Should pop item from bottom of stack", () => {
const stack = new Stack(1, 2, 3);
stack.reverse = true;
assert.equal(stack.pop(), 1);
});
});
mocha.run();
جاوااسکریپت یک زبان برنامه‌نویسی رویدادگرا (event-driven) است که پشتیبانی از عملیات‌های non-blocking را میسر می‌سازد. به صورت درونی، جستجوگر قادر به مدیریت تنها یک ریسه (thread) برای راه‌اندازی تمامی کد جاوااسکریپت است که از event queue برای به صف کردن (enqueue) گوش فراخوان‌ها (listeners) و از event loop برای گوش فراخوانی رخدادهای ثبت‌شده (registered events) بهره می‌برد.
برای پشتیبانی از ناهمگامی (asynchronicity) در یک محیط تک‌ریسگی (single-threaded environment) که به منظور صرفه‌جویی در منابع CPU و بهبود تجربه کاربری وب انجام می‌شود، توابع گوش فراخوان (listener functions) تنها زمانی صف‌زدایی (dequeue) و اجرا می‌شوند که call stack خالی باشد. Promise ها وابسته این معماری رویدادگرا هستند تا اجازه اجرای شیوه هم‌زمان (synchronous-style) کد ناهمگامی (asynchronous) را دهند که دیگر عملیات‌ها را بلوکه نکند.
از لحاظ برنامه‌نویسی، Queue ها صرفاً آرایه‌هایی هستند با دو عملیات اصلی: Unshift، آیتم‌ها را در انتهای آرایه به صف می‌کند، در حالی که Pop این آیتم‌ها را از اول آرایه از صف خارج می‌کند. به عبارت دیگر، Queue ها از پروتکل “اولین ورودی، اولین خروجی” یا همان پروتکل FIFO) First In, First Out) بهره می‌برند. اگر جهت معکوس شود، می‌توانیم unshift و pop را به ترتیب با push و shift جایگزین کنیم. در ادامه مثالی از یک کد Queue آمده است:
class Queue {
constructor(...items) {
this.reverse = false;
this.queue = [...items];
}
enqueue(...items) {
return this.reverse
? this.queue.push(...items)
: this.queue.unshift(...items);
}
dequeue() {
return this.reverse ? this.queue.shift() : this.queue.pop();
}
}
mocha.setup("bdd");
const { assert } = chai;
describe("Queues", () => {
it("Should enqueue items to the left", () => {
const queue = new Queue(4, 5);
assert.equal(queue.enqueue(1, 2, 3), 5);
assert.deepEqual(queue.queue, [1, 2, 3, 4, 5]);
});
it("Should enqueue items to the right", () => {
const queue = new Queue(4, 5);
queue.reverse = true;
assert.equal(queue.enqueue(1, 2, 3), 5);
assert.deepEqual(queue.queue, [4, 5, 1, 2, 3]);
});
it("Should dequeue item from the right", () => {
const queue = new Queue(1, 2, 3);
assert.equal(queue.dequeue(), 3);
});
it("Should dequeue item from the left", () => {
const queue = new Queue(1, 2, 3);
queue.reverse = true;
assert.equal(queue.dequeue(), 1);
});
});
mocha.run();
همانند آرایه‌ها، لیست‌های پیوندی (Linked Lists) المان‌های داده را در ترتیب اصلی (sequential order) ذخیره می‌کنند. به جای نگهداری ایندکس‌ها، Linked List ها از پوینترها (pointers) یا اشاره‌گرها به دیگر المان‌ها نگهداری می‌کنند. اولین گره، head نامیده می‌شود در حالی که آخرین گره tail است.
در یک لیست پیوندی یک‌طرفه (Singly-Linked List)، هر گره تنها یک پوینتر یا اشاره‌گر به گره بعدی دارد. بدین معنی که head نقطه شروعی برای دسترسی به مابقی لیست است. در یک لیست پیوندی دوطرفه (Doubly-Linked List)، پوینتر یا اشاره‌گر به گره قبلی نیز نگهداری می‌شود. بنابراین می‌توانیم از tail شروع کرده و به در جهت عکس به head برسیم.
Linked List ها دارای افزودن (insertion) و حذف (deletion) با زمان ثابتی (constant time) هستند زیرا تنها می‌توانیم پوینترها را تغییر دهیم. همین عملیات در آرایه‌ها دارای زمان خطی (linear time) هستند زیرا آیتم‌های متوالی باید به نوبت تغییر یابند. هم‌چنین Linked List ها می‌توانند تا جایی که فضا وجود دارند گسترش یابند. با این حال، حتی آرایه‌های پویایی (dynamic arrays) که قادر به تغییر انداره به صورت خودکار هستند، می‌توانند به طور غیرقابل‌پیش‌بینی بسیار پرهزینه شوند.
البته همواره موازنه و پایاپایی وجود دارد. برای جستجو و ادیت کردن یک المان در یک Linked List، شاید مجبور باشیم کل طول المان‌ها را طی کنیم که معادل با زمان خطی (linear time) است. این در حالی است که به کمک ایندکس‌های آرایه‌ها، چنین عملیات‌هایی بسیار ناچیز و سریع هستند.
همانند آرایه‌ها، Linked List ها می‌توانند به عنوان Stack عمل کنند. این کار خیلی ساده است: کافی است head را به عنوان تنها محل افزودن و حذف تعیین نماییم. Linked List ها هم‌چنین می‌توانند به عنوان Queue عمل کنند. این را می‌توان به کمک لیست پیوندی دو طرفه انجام داد که در آن باید افزودن در tail و حذف در head انجام پذیرد یا بالعکس.
برای تعداد بالای المان‌ها، این روش پیاده‌سازی Queue ها نسبت به استفاده از آرایه‌ها بسیار کارآمدتر است زیرا عملیات‌های shift و unshift در ابتدای آرایه‌ها نیاز به زمان خطی دارد تا هر المان بعدی را ایندکس‌گذاری مجدد نماید.
Linked List ها برای هر دو سمت سرور و کلاینت مفید و کاربردی هستند. در سمت کلاینت، کتابخانه‌های مدیریت وضعیتی (state management libraries) همچون Redux، منطق میان‌افزار (middleware logic) خود را به روش Linked List ساختاربندی می‌کنند. زمانی که action ها ارسال شوند، از یک میان‌افزار (middleware) به میان‌افزار بعدی مسیردهی می‌شوند تا همه آنها قبل از رسیدن به reducer ها، بازبینی شده و ملاقات شوند.
در سمت سرور، فریم‌ورک‌های وب همانند Express نیز منطق میان‌افزار خود را به روشی مشابه ساختاربندی می‌کند. زمانی که یک request دریافت شود، از یک میان‌افزار به میان‌افزار بعدی مسیردهی می‌شود تا response صادر شود.
در ادامه مثالی از یک کد لیست پیوندی دوطرفه آمده است:
class Node {
constructor(value, next, prev) {
this.value = value;
this.next = next;
this.prev = prev;
}
}
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
}
addToHead(value) {
const node = new Node(value, null, this.head);
if (this.head) this.head.next = node;
else this.tail = node;
this.head = node;
}
addToTail(value) {
const node = new Node(value, this.tail, null);
if (this.tail) this.tail.prev = node;
else this.head = node;
this.tail = node;
}
removeHead() {
if (!this.head) return null;
const value = this.head.value;
this.head = this.head.prev;
if (this.head) this.head.next = null;
else this.tail = null;
return value;
}
removeTail() {
if (!this.tail) return null;
const value = this.tail.value;
this.tail = this.tail.next;
if (this.tail) this.tail.prev = null;
else this.head = null;
return value;
}
search(value) {
let current = this.head;
while (current) {
if (current.value === value) return value;
current = current.prev;
}
return null;
}
indexOf(value) {
const indexes = [];
let current = this.tail;
let index = 0;
while (current) {
if (current.value === value) indexes.push(index);
current = current.next;
index++;
}
return indexes;
}
}
mocha.setup("bdd");
const { assert } = chai;
describe("Linked List", () => {
it("Should add to head", () => {
const list = new LinkedList();
list.addToHead(1);
list.addToHead(2);
list.addToHead(3);
assert.equal(list.tail.prev, null);
assert.equal(list.tail.value, 1);
assert.equal(list.tail.next.value, 2);
assert.equal(list.head.prev.value, 2);
assert.equal(list.head.value, 3);
assert.equal(list.head.next, null);
assert.equal(list.head.prev.prev.value, 1);
assert.equal(list.tail.next.next.value, 3);
});
it("Should add to tail", () => {
const list = new LinkedList();
list.addToTail(1);
list.addToTail(2);
list.addToTail(3);
assert.equal(list.tail.prev, null);
assert.equal(list.tail.value, 3);
assert.equal(list.tail.next.value, 2);
assert.equal(list.head.prev.value, 2);
assert.equal(list.head.value, 1);
assert.equal(list.head.next, null);
assert.equal(list.head.prev.prev.value, 3);
assert.equal(list.tail.next.next.value, 1);
});
it("Should remove head", () => {
const list = new LinkedList();
list.addToHead(1);
list.addToHead(2);
list.addToHead(3);
assert.equal(list.removeHead(), 3);
assert.equal(list.head.value, 2);
assert.equal(list.tail.value, 1);
assert.equal(list.tail.next.value, 2);
assert.equal(list.head.prev.value, 1);
assert.equal(list.head.next, null);
assert.equal(list.removeHead(), 2);
assert.equal(list.head.value, 1);
assert.equal(list.tail.value, 1);
assert.equal(list.tail.next, null);
assert.equal(list.head.prev, null);
assert.equal(list.head.next, null);
assert.equal(list.removeHead(), 1);
assert.equal(list.head, null);
assert.equal(list.tail, null);
});
it("Should remove tail", () => {
const list = new LinkedList();
list.addToTail(1);
list.addToTail(2);
list.addToTail(3);
assert.equal(list.removeTail(), 3);
assert.equal(list.head.value, 1);
assert.equal(list.tail.value, 2);
assert.equal(list.tail.next.value, 1);
assert.equal(list.head.prev.value, 2);
assert.equal(list.tail.prev, null);
assert.equal(list.removeTail(), 2);
assert.equal(list.head.value, 1);
assert.equal(list.tail.value, 1);
assert.equal(list.tail.next, null);
assert.equal(list.head.prev, null);
assert.equal(list.tail.prev, null);
assert.equal(list.removeTail(), 1);
assert.equal(list.head, null);
assert.equal(list.tail, null);
});
it("Should search for value", () => {
const list = new LinkedList();
list.addToHead(1);
list.addToHead(2);
list.addToHead(3);
assert.equal(list.search(1), 1);
assert.equal(list.search(2), 2);
assert.equal(list.search(3), 3);
assert.equal(list.search(4), null);
});
it("Should search for indexes of value", () => {
const list = new LinkedList();
list.addToTail(1);
list.addToTail(2);
list.addToTail(3);
list.addToTail(3);
list.addToTail(1);
assert.deepEqual(list.indexOf(1), [0, 4]);
assert.deepEqual(list.indexOf(2), [3]);
assert.deepEqual(list.indexOf(3), [1, 2]);
assert.deepEqual(list.indexOf(4), []);
});
});
mocha.run();
Tree نیز همانند یک Linked List است با این تفاوت که مرجع‌ها (references) به چندین گره فرزندی (child nodes) را در یک ساختار سلسله‌مراتبی (hierarchical structure) حفظ می‌کند. به عبارت دیگر، هر گره نمی‌تواند بیش از یک والد (parent) داشته باشد. مدل شی‌گرای سند (DOM یا Document Object Model) چنین ساختاری است با یک گره HTML ریشه که به گره‌های head و body شاخه‌بندی می‌شود که در ادامه مجدداً به تمامی html تگ‌های (html tags) آشنا تقسیم‌بندی شده است.
درون این ساختار، ارث‌بری پروتوتایپی (prototypal inheritence) و ترکیب‌بندی (composition) با اجزای React نیز ساختارهای درختی (tree structures) تولید می‌کند. البته به عنوان یک بازنمایی درون‌حافظه‌ای (in-memory representation) از DOM، DOM مجازی React نیز یک ساختار درختی است.
درخت جستجوی دودویی (Binary Search Tree) بسیار خاص است زیرا هر گره نمی‌تواند بیش از دو فرزند داشته باشد. فرزند چپی باید ارزشی کمتر یا برابر با والد خود داشته باشد در حالی که فرزند راستی باید ارزش بزرگ‌تری داشته باشد. به وسیله ساختاربندی و توازن این چنینی می‌توانیم هر ارزشی را در زمان لگاریتمی (logarithmic time) جستجو کنیم زیرا در هر مرجله (iteration) قادر به حذف نصف شاخه‌بندی خواهیم بود.
افزودن و حذف نیز می‌توانند در زمان لگاریتمی انجام شوند. علاوه بر این می‌توان به آسانی کوچک‌ترین و بزرگ‌ترین ارزش را به ترتیب در چپ‌ترین و راست‌ترین برگ بافت.
پیمایش درختی می‌تواند به صورت پروسه‌ای عمودی یا افقی انجام شود. در پیمایش اول‌عمق (DFT یا Depth-First Traversal) در جهت عمودی، یک الگوریتم بازگشتی (recursive algorithm) بسیار هوشمندانه‌تر از یک الگوریتم تکراری (iterative algorithm) است. گره‌ها را می‌توان به صورت پیش‌ترتیب (pre-order)، میان‌ترتیب (in-order) و پس‌ترتیب (post-order) پیمایش کرد.
اگر بخواهیم ریشه‌ها (roots) را قبل از بازرسی برگ‌ها (leaf) جستجو کنیم، باید روش پیش‌ترتیب را برگزینیم. اما اگر بخواهیم برگ‌ها را قبل از ریشه‌ها جستجو کنیم، باید روش پس‌ترتیب را انتخاب نماییم. همان‌طور که از اسم این روش پیدا است، روش میان‌ترتیب ما را قادر می‌سازد تا گره‌ها را در ترتیب اصلی (sequential order) پیمایش کنیم. این ویژگی باعث می‌شود تا درخت‌های جستجوی دودویی برای ترتیب‌دهی (sorting) بهترین و بهینه‌ترین باشند.
پیمایش اول‌سطح (BFT یا Breadth-First Traversal) در جهت افقی، رویکرد تکراری (iterative approach) بسیار هوشمندانه‌تر از رویکرد بازگشتی (recursive approach) خواهد بود. برای یان کار لازم است تا از یک Queue برای ردیابی تمامی گره‌های فرزند در هر تکرار استفاده کنیم.
البته حافظه مورد نیاز برای چنینی صفی (queue) ناچیز نخواهد بود. اگر شکل درخت عریض‌تر از عمق آن باشد، BFT انتخاب بهتری نسبت به DFT خواهد بود. هم‌چنین مسیری که BFT برای پیمایش بین دو گره انتخاب می‌کند، کوتاه‌ترین مسیر ممکن خواهد بود.
در ادامه مثالی از یک کد درخت جستجوی دودویی (Binary Search Tree) آورده شده است:
class Tree {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
insert(value) {
if (value <= this.value) {
if (!this.left) this.left = new Tree(value);
else this.left.insert(value);
} else {
if (!this.right) this.right = new Tree(value);
else this.right.insert(value);
}
}
contains(value) {
if (value === this.value) return true;
if (value < this.value) {
if (!this.left) return false;
else return this.left.contains(value);
} else {
if (!this.right) return false;
else return this.right.contains(value);
}
}
depthFirstTraverse(order, callback) {
order === "pre" && callback(this.value);
this.left && this.left.depthFirstTraverse(order, callback);
order === "in" && callback(this.value);
this.right && this.right.depthFirstTraverse(order, callback);
order === "post" && callback(this.value);
}
breadthFirstTraverse(callback) {
const queue = [this];
while (queue.length) {
const root = queue.shift();
callback(root.value);
root.left && queue.push(root.left);
root.right && queue.push(root.right);
}
}
getMinValue() {
if (this.left) return this.left.getMinValue();
return this.value;
}
getMaxValue() {
if (this.right) return this.right.getMaxValue();
return this.value;
}
}
mocha.setup("bdd");
const { assert } = chai;
const tree = new Tree(5);
for (const value of [3, 6, 1, 7, 8, 4, 10, 2, 9]) tree.insert(value);
/*
۵
۳ ۶
۱ ۴ ۷
۲ ۸
۱۰
۹
*/
describe("Binary Search Tree", () => {
it("Should implement insert", () => {
assert.equal(tree.value, 5);
assert.equal(tree.left.value, 3);
assert.equal(tree.right.value, 6);
assert.equal(tree.left.left.value, 1);
assert.equal(tree.right.right.value, 7);
assert.equal(tree.right.right.right.value, 8);
assert.equal(tree.left.right.value, 4);
assert.equal(tree.right.right.right.right.value, 10);
assert.equal(tree.left.left.right.value, 2);
assert.equal(tree.right.right.right.right.left.value, 9);
});
it("Should implement contains", () => {
assert.equal(tree.contains(2), true);
assert.equal(tree.contains(9), true);
assert.equal(tree.contains(0), false);
assert.equal(tree.contains(11), false);
});
it("Should implement depthFirstTraverse", () => {
const _pre = [];
const _in = [];
const _post = [];
tree.depthFirstTraverse("pre", value => _pre.push(value));
tree.depthFirstTraverse("in", value => _in.push(value));
tree.depthFirstTraverse("post", value => _post.push(value));
assert.deepEqual(_pre, [5, 3, 1, 2, 4, 6, 7, 8, 10, 9]);
assert.deepEqual(_in, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
assert.deepEqual(_post, [2, 1, 4, 3, 9, 10, 8, 7, 6, 5]);
});
it("Should implement breadthDepthTraverse", () => {
const result = [];
tree.breadthFirstTraverse(value => result.push(value));
assert.deepEqual(result, [5, 3, 6, 1, 4, 7, 2, 8, 10, 9]);
});
it("Should implement getMinValue", () => {
assert.equal(tree.getMinValue(), 1);
});
it("Should implement getMaxValue", () => {
assert.equal(tree.getMaxValue(), 10);
});
});
mocha.run();
اگر یک درخت اجازه داشتن بیش از یک والد (parent) را داشته باشد، تبدیل به یک Graph می‌شود. لبه‌هایی (Edges) که گره‌ها را در یک Graph به هم وصل می‌کنند می‌توانند جهت‌دار (directed) یا بی‌جهت (undirected) و وزن‌دار (weighted) یا بی‌وزن (unweighted) باشند. لبه‌هایی که هم دارای جهت و هم دارای وزن باشند مشابه با بردارها (vectors) هستند.
ارث‌بری‌های چندگانه (multiple inheritances) در شکل و قالب Mixin ها و data object هایی که روابط چند به چند (many-to-many relationships) دارند، ساختارهای گراف (Graph) را تولید می‌کنند. یک شبکه اجتماعی و حتی خود اینترنت، گراف (Graph) هستند. پیچیده‌ترین گراف موجود در طبیعت، مغز انسان است که شبکه‌های عصبی (neural networks) سعی در تقلید از آن دارند تا به ماشین‌ها فراهوش (superintelligence) ارائه کنند.
جدول درهم‌سازی (Hash Table) یک ساختار دیکشنری مانند است که key ها را با value ها جفت می‌کند. محل موجود در حافظه هر جفت با یک تابع درهم‌ساز (hash function) تعیین می‌شود که یک key را قبول کرده و یک address را بازگشت می‌دهد که جفت باید در آن افزوده شده و بازیابی شود. در صورتی که دو یا چند key به یک address تبدیل شوند، تصادم (collision) ایجاد خواهد شد.
برای استحکام ساختاری بیشتر، getter ها و setter ها باید این نوع رویدادها را پیش‌بینی کنند تا اطمینان حاصل شود که تمامی داده‌ها را می‌توان بازیابی کرد و هیچ داده‌ای جانویسی (overwrite) نخواهد شد. معمولاً Linked List ها ساده‌ترین راه حل را ارائه می‌کنند. داشتن جداول بسیار بزرگ نیز می‌تواند به این امر کمک کند.
اگر بدانیم که address ها در دنباله‌های صحیح خواهند بود، می‌توانیم به سادگی از آرایه‌ها برای ذخیره‌سازی جفت‌های key-value استفاده کنیم. برای نگاشت‌آدرس‌های (address mappings) پیچیده‌تر می‌توانیم از Map ها و Object ها استفاده کنیم. Hash Table ها به طور میانگین دارای افزودن و جستجوی زمان ثابت هستند. به دلیل تصادم‌ها (collisions) و تغییر ابعاد (resizing)، این هزینه قابل‌چشم‌پوشی می‌تواند به صورت زمان خطی درآید.
البته در عمل می‌توانیم فرض کنیم که توابع درهم‌ساز به اندازه‌ای هوشمندانه هستند که تصادم‌ها و تغییر ابعاد، ارزان و نادر باشند. اگر key ها بازنمایی address ها باشند و در نتیجه درهم‌سازی (hashing) نیاز نباشد، یک object literal ساده می‌تواند کافی باشد. البته همواره پایاپایی و مصالحه وجود خواهد داشت.
یک مطابقت ساده بین key ها و value ها و یک شرکت‌پذیری (associativity) ساده بین key ها و address ها، به معنای قربانی کردن روابط میان داده‌ها خواهد بود. بنابراین hash table ها برای ذخیره‌سازی داده‌ها، زیربهینه (suboptimal) خواهند بود.
اگر مصالحه‌ای بدین ترتیب باشد که بازیابی را بر ذخیره‌سازی ترجیح دهد، هیچ ساختار داده دیگری وجود ندارد که در جستجو، افزودن و حذف، یارای رقابت با hash table ها باشد. پس جای تعجب نیست که می‌بینیم در همه جا استفاده می‌شود. از پایگاه‌داده‌ها گرفته تا سرور و کلاینت، hash table ها به خصوص hash function ها برای عملکرد و امنیت نرم‌افزارها حیاتی هستند.
سرعت databasequery ها شدیداً وابسته نگهداری جداول ایندکس‌هایی هستند که به سوابق در ترتیب چینشی (sorted order) اشاره کنند. بدین طریق، جستجوهای دودویی می‌توانند در زمان لگاریتمی انجام پذیرند؛ این یک دستاورد و یک عملکرد بی‌نظیر، به خصوص برای داده‌های حجیم است.
هم در کلاینت و هم در سرور، بسیاری از کتابخانه‌های مشهور برای ماکزیمم کردن عملکرد، از memorization بهره می‌برند. با نگهداری بایگانی input ها و Output ها در یک hash table، توابع برای همان input ها تنها یک بار اجرا می‌شوند. کتابخانه مشهور Reselect از این استراتژی عالی بهره می‌برد تا توابع mapStateToProps در نرم‌افزارهای دارای قابلیت Redux را بهینه کند.
در حقیقت موتور جاوا اسکریپت نیز از hash table هایی با نام heaps بهره می‌برد تا تمامی variable ها و primitive هایی که ایجاد می‌کنیم را ذخیره‌سازی کند. اینها از طریق اشاره‌گرهای (پوینترها) داخل call stack قابل دسترسی هستند.
خود اینترنت نیز به الگوریتم‌های درهم‌ساز وابستگی شدیدی دارد تا امنیت عملکرد خود را تامین کند. ساختار اینترنت به گونه‌ای است که هر کامپیوتر می‌تواند از طریق شبکه‌ای از تجهیزات متصل به هم با هر کامپیوتر دیگری ارتباط برقرار کند. هر زمان که دستگاهی به اینترنت وصل شود، تبدیل به روتری می‌شود که بوسیله آن جریان داده‌ها می‌توانند انتقال یابند. البته این یک شمشیر دو لبه است. یک معماری تمرکز زدایی شده به این معنی است که هر دستگاه داخل شبکه می‌تواند به بسته‌های داده‌ای که از طریق آن دستگاه رله می‌شوند گوش فرا داده و آنها را دستکاری کند.
توابع درهم‌سازی همچون MD5 و SHA256 نقشی کلیدی و حیاتی در جلوگیری از چنین حملات استراق سمع فعال (به اصطلاح حملات مرد میانی یا man-in-the-middle attacks) دارند. تجارت الکترونیک تحت HTTPS تنها به این دلیل امن است که از این توابع درهم‌ساز استفاده می‌شود.
فناوری بلاک چین از این ایده الهام گرفته شده است و در جستجوی این است تا تمامی ساختارهای وب را در سطح پروتکلی، متن‌باز (اپن سورس یا open source) نماید. با استفاده از توابع درهم‌ساز برای ایجاد اثر انگشت‌های تغییر ناپذیر برای هر بلوک داده، در نهایت می‌توان پایگاه داده‌ای داشت که به صورت باز و آزاد در وب قرار داده شده است تا هر شخصی بتواند آن را دیده و به بهبود آن کمک کند.
از لحاظ ساختاری، بلاک چین‌ها صرفاً لیست‌های تک پیوندی (singly-linked lists) از درخت‌های دودویی درهم‌سازهای کریپتوگرافی شده هستند. درهم‌سازی چنان مرموز و سربسته است که هر کسی در بیرون از گود می‌تواند پایگاه داده تراکنش‌های مالی را ایجاد کند و آن را بروز رسانی کند! نتیجه شگفت‌انگیز آن، داشتن قدرتی بی‌نظیر برای ایجاد خود پول است. چیزی که زمانی تنها برای دولت‌ها و بانک‌های مرکزی میسر بود، اکنون هر کسی می‌تواند واحد پولی امن خود را ایجاد کند! این همان ادراک کلیدی است که توسط مؤسس Ethereum و مؤسس Bitcoin درک شده است!
هر چقدر پایگاه داده‌ها بیشتر و بیشتر به سمت فضای باز سوق پیدا کنند، نیاز به مهندسین فرانت اندی که بتوانند پیچیدگی‌های کریپتوگرافی سطح پایین را حل نمایند، بیشتر و بیشتر می‌شود. در آینده‌ای که پیش رو داریم، تنها وجه تمایز اصلی، تجربه کاربری (user experience) خواهد بود.
در ادامه مثالی از یک کد hash table آمده است:
class Node {
constructor(key, value) {
this.key = key;
this.value = value;
this.next = null;
}
}
class Table {
constructor(size) {
this.cells = new Array(size);
}
hash(key) {
let total = 0;
for (let i = 0; i < key.length; i++) total += key.charCodeAt(i);
return total % this.cells.length;
}
insert(key, value) {
const hash = this.hash(key);
if (!this.cells[hash]) {
this.cells[hash] = new Node(key, value);
} else if (this.cells[hash].key === key) {
this.cells[hash].value = value;
} else {
let node = this.cells[hash];
while (node.next) {
if (node.next.key === key) {
node.next.value = value;
return;
}
node = node.next;
}
node.next = new Node(key, value);
}
}
get(key) {
const hash = this.hash(key);
if (!this.cells[hash]) return null;
else {
let node = this.cells[hash];
while (node) {
if (node.key === key) return node.value;
node = node.next;
}
return null;
}
}
getAll() {
const table = [];
for (let i = 0; i < this.cells.length; i++) {
const cell = [];
let node = this.cells[i];
while (node) {
cell.push(node.value);
node = node.next;
}
table.push(cell);
}
return table;
}
}
mocha.setup("bdd");
const { assert } = chai;
const table = new Table(5);
table.insert("baa", 1);
table.insert("aba", 2);
table.insert("aba", 3);
table.insert("aac", 4);
table.insert("aac", 5);
describe("Hash Table", () => {
it("Should implement hash", () => {
assert.equal(table.hash("abc"), 4);
});
it("Should implement insert", () => {
assert.equal(table.cells[table.hash("baa")].value, 1);
assert.equal(table.cells[table.hash("aba")].next.value, 3);
assert.equal(table.cells[table.hash("aac")].value, 5);
});
it("Should implement get", () => {
assert.equal(table.get("baa"), 1);
assert.equal(table.get("aba"), 3);
assert.equal(table.get("aac"), 5);
assert.equal(table.get("abc"), null);
});
it("Should implement getAll", () => {
assert.deepEqual(table.getAll(), [[], [], [1, 3], [5], []]);
});
});
mocha.run();
با گذر روز افزون منطق (logic) از سمت سرور به سمت کلاینت، لایه داده‌ها (data layer) در بخش فرانت اند برجسته‌تر می‌شود. مدیریت صحیح این لایه شامل تسلط بر ساختارهای داده‌ای می‌شود که زیربنا و شالوده منطق (logic) هستند. هیچ ساختار داده‌ای وجود ندارد که برای تمامی موقعیت‌ها عالی باشد زیرا همواره بهینه‌سازی یک ویژگی منجر به ضعف ویژگی دیگری خواهد شد.
برخی ساختارها برای ذخیره‌سازی داده‌ها کارامدتر هستند در حالی که برخی دیگر برای جستجو در میان آنها موثرتر خواهند بود. معمولاً چنین است که یک ساختار قربانی ساختار دیگری می‌شود. در یک حالت، Linked List ها برای ذخیره‌سازی بهینه هستند و می‌توانند به stack ها و queue ها تبدیل شوند (زمان خطی). در حالتی دیگر نیز هیچ ساختاری وجود ندارد که در سرعت به گرد پای hash table ها برسد.
ساختارهای درختی نیز جایی مابین این دو قرار دارند (زمان لگاریتمی) و این تنها Graph است که قادر به ایجاد و تقلید از پیچیده‌ترین ساختار طبیعت است: یعنی مغز انسان (زمان چند جمله‌ای یا polynomial time). داشتن مجموعه مهارت‌هایی برای اینکه تشخیص دهیم چه زمان و در چه محلی از یک ساختار استفاده کنیم، وجه تمایز میان مهندسین است و آنها را یک مهندس قدر و بی‌همتا می‌کند.
مثال‌هایی از این ساختارهای داده را می‌توان در همه جا یافت. از پایگاه‌داده‌ها گرفته تا سرور و کلاینت و حتی خود موتور جاوااسکریپت، این ساختارهای داده هستند که تعیین می‌کنند که سوئیچ‌هایی بر روی چیپ الکترونیکی فعال یا خاموش باشند و این چیپ‌ها را مبدل به اشیایی دارای حیات می‌کنند. با اینکه مباحثی صرفاً دیجیتال هستند، اما این اشیاء تاثیر بزرگ و عظیمی بر روی جوامع دارند.
اینکه اکنون می‌توانید این متن را آزادانه و ایمن بخوانید، گواهی بر معماری بی‌نظیر اینترنت و ساختار موجود در داده‌های آن است. اما این تنها شروع راه است. هوش مصنوعی و بلاک چین تمرکز زدایی شده در دهه‌های آتی که پیش رو داریم، تعریف انسانیت را از نو خواهند نوشت و نقش مؤسسات حاکم بر زندگی ما را دگرگون خواهند کرد. فراست هستی‌گرایانه و واسطه‌زدایی بنیادین، خصوصیات و ویژگی‌‌هایی هستند که اینترنت در بلوغ خود بدان‌ها دست خواهد یافت.
منبع: medium.com
۵۰ درصد تخفیف ویژه زمستان فرانت کست تا ۱۴ دی
کد تخفیف: wnt
دیدگاه‌ها:
سعید
بهمن 27, 1397 در 1:38 ب.ظ
ممنون از مقاله خوبتون . خیلی مفید بود خسته نباشید .
حتما از دید کاربردی، مثال های متنوعی برای بهینه سازی و پرفرمنس و سرعت کار با داده هایی که از سمت سرور میاد ، تو مقاله های بعدی داشته باشید .
مسعود صدری
بهمن 27, 1397 در 10:34 ب.ظ
ممنون از شما، بله حتما.