Giới thiệu

Khi logic kinh doanh di chuyển từ phía sau ra phía trước ngày càng nhiều, kiến ​​thức chuyên môn về Frontend Engineering càng trở nên quan trọng hơn bao giờ hết. Với tư cách là Frontend Engineers , chúng tôi phụ thuộc vào các thư viện view như React để hoạt động hiệu quả. Xem các thư viện lần lượt phụ thuộc vào các thư viện trạng thái như Redux để quản lý dữ liệu. Cùng nhau, React và Redux đăng ký mô hình lập trình phản ứng trong đó các bản cập nhật giao diện người dùng phản ứng với các thay đổi dữ liệu. Càng ngày, các chương trình phụ trợ hoạt động đơn giản như các máy chủ API, chỉ cung cấp các điểm cuối để truy xuất và cập nhật dữ liệu. Trên thực tế, chương trình phụ trợ chỉ "chuyển tiếp" cơ sở dữ liệuđến giao diện người dùng, mong đợi Kỹ sư giao diện người dùng xử lý tất cả logic của bộ điều khiển. Sự phổ biến ngày càng tăng của các microservices và GraphQL chứng thực cho xu hướng ngày càng tăng này.

Giờ đây, ngoài việc có hiểu biết thẩm mỹ về HTML và CSS, các kỹ sư Frontend cũng phải thông thạo JavaScript. Khi các cơ sở dữ liệu trên máy khách trở thành "bản sao" của cơ sở dữ liệu trên máy chủ, kiến ​​thức sâu sắc về cấu trúc dữ liệu thành ngữ trở thành then chốt. Trên thực tế, mức độ kinh nghiệm của một kỹ sư có thể được suy ra từ khả năng của họ để phân biệt khi nào và tại sao sử dụng một cấu trúc dữ liệu cụ thể.

Lập trình viên tồi lo lắng về mã. Các lập trình viên giỏi lo lắng về cấu trúc dữ liệu và các mối quan hệ của chúng.

- Linus Torvalds, Người tạo ra Linux và Git

Ở cấp độ cao, về cơ bản có ba loại cấu trúc dữ liệu. Ngăn xếp và Hàng đợi là các cấu trúc giống như mảng chỉ khác nhau về cách các mục được chèn và loại bỏ. Danh sách liên kết , cây , và đồ thị là các cấu trúc với các nút mà giữ tài liệu tham khảo để các nút khác. Bảng băm phụ thuộc vào các hàm băm để lưu và định vị dữ liệu.

Về độ phức tạp, Stacksvà Queueslà đơn giản nhất và có thể được xây dựng từ Linked Lists. Treesvà Graphsphức tạp nhất vì chúng mở rộng khái niệm danh sách liên kết. Hash Tablescần sử dụng các cấu trúc dữ liệu này để hoạt động đáng tin cậy. Về mặt hiệu quả, Danh sách liên kết là tối ưu nhất cho việc ghi và lưu trữ dữ liệu, trong khi Bảng băm là hiệu quả nhất cho việc tìm kiếm và truy xuất dữ liệu.

Để giải thích tại sao và minh họa khi nào , bài viết này sẽ tuân theo thứ tự của các phần phụ thuộc này. Hãy bắt đầu nào!

Cây rơm

Có thể cho rằng điều quan trọng nhất Stacktrong JavaScript là ngăn xếp cuộc gọi nơi chúng ta đẩy trong phạm vi a functionbất cứ khi nào chúng ta thực thi nó. Về mặt lập trình, nó chỉ là một arrayvới hai hoạt động chính: pushvà pop. Push thêm các phần tử lên đầu mảng, trong khi Pop xóa chúng khỏi cùng một vị trí. Nói cách khác, Stacks tuân theo giao thức “Last In, First Out” (LIFO).

Dưới đây là một ví dụ về Stackmã trong. Chú ý rằng chúng ta có thể đảo ngược thứ tự của ngăn xếp: đáy trở thành đỉnh và đỉnh trở thành đáy. Như vậy, chúng ta có thể sử dụng các phương thức unshiftvà của mảng shiftthay cho pushvà pop, tương ứng.

Khi số lượng mục tăng lên, push/ popngày càng trở nên hiệu quả hơn unshift/ shiftbởi vì mọi mục cần được lập chỉ mục lại trong mục sau chứ không phải mục trước.

Xếp hàng

JavaScript là một ngôn ngữ lập trình hướng sự kiện giúp nó có thể hỗ trợ các hoạt động không chặn . Bên trong, trình duyệt quản lý chỉ một thread để chạy toàn bộ mã Javascript, sử dụng hàng đợi sự kiện để enqueuelisteners và vòng lặp sự kiện để lắng nghe cho đăng ký events. Để hỗ trợ asynchronicity trong một môi trường đơn ren (để tiết kiệm tài nguyên CPU và nâng cao trải nghiệm web), listener functions dequeue và chỉ thực hiện khi gọi stack rỗng. Promisesphụ thuộc vào kiến trúc hướng sự kiện này để cho phép thực thi “kiểu đồng bộ” của mã không đồng bộ không chặn các hoạt động khác.

Về mặt lập trình, Queueschỉ là các mảng với hai phép toán chính: unshiftvà pop. Unshift enqueues mục vào cuối của mảng, trong khi Pop dequeues chúng ra khỏi đầu của mảng. Nói cách khác, Hàng đợi tuân theo giao thức “Nhập trước, Xuất trước” (FIFO). Nếu hướng bị đảo ngược, chúng ta có thể thay thế unshiftvà popbằng pushvà shift, tương ứng.

Ví dụ về Queuemã trong:

Danh sách liên kết

Giống như mảng, Linked Listslưu trữ các phần tử dữ liệu theo thứ tự tuần tự. Thay vì giữ các chỉ mục, danh sách được liên kết giữ các con trỏ đến các phần tử khác. Các đầu nút được gọi là người đứng đầu trong khi cuối cùng nút được gọi là đuôi . Trong danh sách được liên kết đơn , mỗi nút chỉ có một con trỏ đến nút tiếp theo . Ở đây, phần đầu là nơi chúng ta bắt đầu bước xuống phần còn lại của danh sách. Trong danh sách được liên kết kép , một con trỏ đến nút trước đó cũng được giữ. Do đó, chúng ta cũng có thể bắt đầu từ đuôi và đi “lùi” về phía đầu.

Danh sách được liên kết có các thao tác chèn và xóa liên tục vì chúng tôi chỉ có thể thay đổi con trỏ. Để thực hiện các thao tác tương tự trong mảng đòi hỏi thời gian tuyến tính vì các mục tiếp theo cần được chuyển qua. Ngoài ra, danh sách được liên kết có thể phát triển miễn là có không gian. Tuy nhiên, ngay cả các mảng "động" tự động thay đổi kích thước có thể trở nên đắt tiền một cách bất ngờ. Tất nhiên, luôn có sự đánh đổi. Để tra cứu hoặc chỉnh sửa một phần tử trong danh sách được liên kết, chúng ta có thể phải đi bộ toàn bộ chiều dài tương đương với thời gian tuyến tính. Tuy nhiên, với chỉ mục mảng, các hoạt động như vậy là không đáng kể.

Giống như mảng, danh sách được liên kết có thể hoạt động dưới dạng ngăn xếp . Nó đơn giản như để đầu là nơi duy nhất để chèn và tháo. Danh sách được liên kết cũng có thể hoạt động như hàng đợi . Điều này có thể đạt được với một danh sách được liên kết kép, trong đó việc chèn diễn ra ở phần đuôi và việc loại bỏ xảy ra ở phần đầu hoặc ngược lại. Đối với số lượng lớn các phần tử, cách triển khai hàng đợi này hiệu quả hơn so với việc sử dụng mảng vì shiftvà các unshifthoạt động ở đầu mảng yêu cầu thời gian tuyến tính để lập chỉ mục lại mọi phần tử tiếp theo.

Danh sách được liên kết hữu ích trên cả máy khách và máy chủ. Trên máy khách, các thư viện quản lý trạng thái như Redux cấu trúc logic phần mềm trung gian của nó theo kiểu danh sách liên kết. Khi các hành động được gửi đi, chúng được chuyển từ phần mềm trung gian này sang phần mềm trung gian tiếp theo cho đến khi tất cả được truy cập trước khi đến các bộ giảm . Trên máy chủ, các khung công tác web như Express cũng cấu trúc logic phần mềm trung gian của nó theo cách tương tự. Khi một yêu cầu được nhận, nó được chuyển từ phần mềm trung gian này sang phần mềm trung gian tiếp theo cho đến khi phản hồi được đưa ra.

Ví dụ về Doubly-Linked Listmã trong:

Cây

A Treegiống như một danh sách được liên kết , ngoại trừ nó giữ các tham chiếu đến nhiều nút con trong một cấu trúc phân cấp . Nói cách khác, mỗi nút không thể có nhiều hơn một nút cha. Các Document Object Model (DOM) là một cấu trúc như vậy, với một gốc htmlnút đó chi nhánh vào headvà bodynút, trong đó tiếp tục chia nhỏ thành tất cả quen thuộc thẻ html . Về cơ bản, kế thừa nguyên mẫu và thành phần với các thành phần React cũng tạo ra cấu trúc cây. Tất nhiên, như một đại diện trong bộ nhớ của DOM, Virtual DOM của React cũng là một cấu trúc cây.

Các Binary Search Tree là đặc biệt vì mỗi nút có thể có không quá hai trẻ em . Con bên trái phải có giá trị nhỏ hơn hoặc bằng giá trị cha của nó, trong khi con bên phải phải có giá trị lớn hơn . Được cấu trúc và cân bằng theo cách này, chúng ta có thể tìm kiếm bất kỳ giá trị nào theo thời gian logarit vì chúng ta có thể bỏ qua một nửa số lần phân nhánh với mỗi lần lặp. Việc chèn và xóa cũng có thể xảy ra theo thời gian logarit. Hơn nữa, giá trị nhỏ nhất và lớn nhất có thể dễ dàng tìm thấy lần lượt ở lá ngoài cùng bên trái và ngoài cùng bên phải .

Việc truyền qua cây có thể xảy ra theo quy trình dọc hoặc ngang . Trong Truyền theo chiều sâu-đầu tiên (DFT) theo hướng dọc, thuật toán đệ quy thanh lịch hơn thuật toán lặp lại. Các nút có thể được duyệt theo thứ tự trước , theo thứ tự hoặc đặt hàng sau . Nếu cần thăm dò rễ trước khi tra lá, chúng ta nên chọn đặt hàng trước . Nhưng, nếu chúng ta cần thăm dò lá trước rễ thì nên chọn thứ tự sau . Như tên gọi của nó, theo thứ tự cho phép chúng ta duyệt các nút theo thứ tự tuần tự. Thuộc tính này làm cho Cây tìm kiếm nhị phân tối ưu cho việc sắp xếp .

Trong Breadth-First Traversal (BFT) theo hướng ngang, cách tiếp cận lặp lại thanh lịch hơn cách tiếp cận đệ quy. Điều này yêu cầu sử dụng a queueđể theo dõi tất cả các nút con với mỗi lần lặp. Tuy nhiên, bộ nhớ cần thiết cho một hàng đợi như vậy có thể không nhỏ. Nếu hình dạng của cây rộng hơn sâu, BFT là lựa chọn tốt hơn DFT. Ngoài ra, đường dẫn mà BFT đi giữa hai nút bất kỳ là đường ngắn nhất có thể.

Ví dụ về Binary Search Treemã trong:

Đồ thị

Nếu một cây tự do có nhiều hơn một cây bố mẹ, nó sẽ trở thành một cây Graph. Các cạnh kết nối các nút với nhau trong một biểu đồ có thể được định hướng hoặc vô hướng, có trọng số hoặc không có trọng số . Các cạnh có cả hướng và trọng lượng tương tự như vectơ .

Nhiều kế thừa dưới dạng Mixin và các đối tượng dữ liệu có mối quan hệ nhiều-nhiều tạo ra cấu trúc đồ thị. Mạng xã hội và bản thân Internet cũng là đồ thị. Biểu đồ phức tạp nhất trong tự nhiên là bộ não con người của chúng ta, mà mạng lưới thần kinh cố gắng tái tạo để cung cấp cho máy móc siêu trí tuệ .

Ví dụ về Graphmã trong:

TK

Bảng băm

Một Hash Table là một cuốn từ điển giống như cấu trúc mà cặp chìa khóa để các giá trị . Vị trí trong bộ nhớ của mỗi cặp được xác định bởi a hash function, nó chấp nhận một khóa và trả về địa chỉ nơi cặp cần được chèn và truy xuất. Có thể xảy ra va chạm nếu hai hoặc nhiều khóa chuyển đổi thành cùng một địa chỉ. Để có tính mạnh mẽ, gettersvà settersnên lường trước các sự kiện này để đảm bảo rằng tất cả dữ liệu có thể được phục hồi và không có dữ liệu nào bị ghi đè. Thông thường, hãy linked listsđưa ra giải pháp đơn giản nhất. Có bàn rất lớn cũng giúp ích.

Nếu chúng ta biết địa chỉ của mình sẽ nằm trong chuỗi số nguyên, chúng ta có thể chỉ cần sử dụng Arraysđể lưu trữ các cặp khóa-giá trị của mình. Đối với các ánh xạ địa chỉ phức tạp hơn, chúng ta có thể sử dụng Mapshoặc Objects. Bảng băm trung bình có chèn và tra cứu thời gian không đổi . Do va chạm và thay đổi kích thước, chi phí không đáng kể này có thể tăng lên theo thời gian tuyến tính. Tuy nhiên, trên thực tế, chúng ta có thể giả định rằng các hàm băm đủ thông minh để việc va chạm và thay đổi kích thước là rất hiếm và rẻ. Nếu các khóa đại diện cho địa chỉ và do đó không cần băm, thì một đơn giản là object literalđủ. Tất nhiên, luôn có sự đánh đổi. Sự tương ứng đơn giản giữa các khóa và giá trị cũng như sự liên kết đơn giản giữa các khóa và địa chỉ, hy sinh mối quan hệ giữa các dữ liệu. Do đó, bảng băm là không tối ưu để lưu trữ dữ liệu.

Nếu một quyết định đánh đổi ủng hộ việc truy xuất qua bộ nhớ, không có cấu trúc dữ liệu nào khác có thể phù hợp với tốc độ của bảng băm để tra cứu , chèn và xóa . Do đó, không có gì ngạc nhiên khi nó được sử dụng ở mọi nơi . Từ cơ sở dữ liệu, đến máy chủ, đến máy khách, các bảng băm và đặc biệt là các hàm băm , rất quan trọng đối với hiệu suất và tính bảo mật của các ứng dụng phần mềm. Tốc độ của các truy vấn cơ sở dữ liệu chủ yếu dựa vào việc giữ các bảng chỉ mục trỏ đến các bản ghi theo thứ tự được sắp xếp . Bằng cách này, các tìm kiếm nhị phân có thể được thực hiện theo thời gian logarit , một chiến thắng hiệu suất rất lớn, đặc biệt là đối với Dữ liệu lớn .

Trên cả máy khách và máy chủ, nhiều thư viện phổ biến sử dụng tính năng ghi nhớ để tối đa hóa hiệu suất. Bằng cách ghi lại các đầu vào và đầu ra trong bảng băm, các hàm chỉ chạy một lần cho các đầu vào giống nhau. Thư viện Reselect phổ biến sử dụng chiến lược bộ nhớ đệm này để tối ưu hóa các mapStateToPropschức năng trong các ứng dụng bật Redux . Trên thực tế, công cụ JavaScript cũng sử dụng các bảng băm được gọi là đống để lưu trữ tất cả variablesvà primitiveschúng tôi tạo ra. Chúng được truy cập từ các con trỏ trên ngăn xếp cuộc gọi .

Bản thân Internet cũng dựa vào các thuật toán băm để hoạt động một cách an toàn. Cấu trúc của Internet sao cho bất kỳ máy tính nào cũng có thể giao tiếp với bất kỳ máy tính nào khác thông qua một mạng lưới các thiết bị được kết nối với nhau. Bất cứ khi nào một thiết bị đăng nhập vào internet, nó cũng sẽ trở thành một bộ định tuyến mà qua đó các luồng dữ liệu có thể di chuyển. Tuy nhiên, đó là một con dao hai lưỡi. Một phân cấp phương tiện kiến trúc bất kỳ thiết bị trong mạng có thể nghe và làm xáo trộn với các gói dữ liệu mà nó giúp để chuyển tiếp. Các hàm băm như MD5 và SHA256 đóng một vai trò quan trọng trong việc ngăn chặn các cuộc tấn công trung gian như vậy . Thương mại điện tử qua HTTPS chỉ an toàn vì các hàm băm này được sử dụng.

Lấy cảm hứng từ Internet, các công nghệ blockchain tìm cách mã nguồn mở chính cấu trúc của web ở cấp độ giao thức . Bằng cách sử dụng các hàm băm để tạo ra các dấu vân tay bất biến cho mọi khối dữ liệu , về cơ bản toàn bộ cơ sở dữ liệu có thể tồn tại công khai trên web cho bất kỳ ai cũng có thể xem và đóng góp. Về mặt cấu trúc, các blockchains chỉ là danh sách được liên kết đơn lẻ của các cây nhị phân của các băm mật mã. Các băm là quá khó hiểu rằng một cơ sở dữ liệu của các giao dịch tài chính có thể được tạo ra và được cập nhật ở ngoài trời bởi bất cứ ai! Hàm ý đáng kinh ngạc là sức mạnh tuyệt vời để tự tạo ra tiền . Điều mà trước đây chỉ có thể có đối với các chính phủ và ngân hàng trung ương, giờ đây, bất kỳ ai cũng có thể tạo tiền tệ của riêng mình một cách an toàn ! Đây là cái nhìn sâu sắc chính được nhận ra bởi người sáng lập Ethereum và người sáng lập biệt danh của Bitcoin .

Khi ngày càng có nhiều cơ sở dữ liệu mở ra, nhu cầu về Frontend Engineers, những người có thể loại bỏ tất cả các phức tạp mật mã cấp thấp cũng sẽ tăng lên. Trong tương lai, điểm khác biệt chính sẽ là trải nghiệm người dùng .

Ví dụ về Hash Tablemã trong:

Đối với các bài tập thuật toán sử dụng các cấu trúc dữ liệu này và hơn thế nữa, hãy xem: Các thuật toán trong JavaScript: 40 Vấn đề, Giải pháp và Giải thích

Phần kết luận

Khi logic ngày càng di chuyển từ máy chủ sang máy khách, lớp dữ liệu trên giao diện người dùng trở nên tối quan trọng. Việc quản lý thích hợp lớp này đòi hỏi sự thành thạo của các cấu trúc dữ liệu mà logic nằm trên đó. Không có cấu trúc dữ liệu nào là hoàn hảo cho mọi tình huống bởi vì tối ưu hóa cho một thuộc tính luôn đồng nghĩa với việc mất một thuộc tính khác. Một số cấu trúc lưu trữ dữ liệu hiệu quả hơn trong khi một số cấu trúc khác hoạt động hiệu quả hơn khi tìm kiếm thông qua chúng. Thông thường, một người được hy sinh cho người kia. Ở một góc độ nào đó, danh sách được liên kết là tối ưu cho việc lưu trữ và có thể được tạo thành các ngăn xếp và hàng đợi ( thời gian tuyến tính ). Mặt khác, không có cấu trúc nào khác có thể phù hợp với tốc độ tìm kiếm của bảng băm ( thời gian không đổi ). Cấu trúc cây nằm ở đâu đó ở giữa ( thời gian logarit ), và chỉ một biểu đồ mới có thể miêu tả cấu trúc phức tạp nhất của tự nhiên: bộ não con người ( thời gian đa thức ). Có bộ kỹ năng để phân biệt khi nào và nói rõ tại sao lại là dấu hiệu của một kỹ sư nhạc rock.

Ví dụ về các cấu trúc dữ liệu này có thể được tìm thấy ở khắp mọi nơi . Từ cơ sở dữ liệu, máy chủ, cho khách hàng, và thậm chí cả động cơ Javascript chính nó, những cấu trúc dữ liệu cụ thể gì về cơ bản chỉ là trên và tắt “công tắc” trên chip silicon vào thật “đối tượng”. Mặc dù chỉ là kỹ thuật số nhưng tác động của những vật thể này đối với xã hội là rất lớn. Khả năng của bạn để đọc bài viết này một cách tự do và an toàn chứng thực cho kiến ​​trúc tuyệt vời của Internet và cấu trúc dữ liệu của nó. Tuy nhiên, đây chỉ là sự khởi đầu. Trí tuệ nhân tạo và các chuỗi khối phi tập trung trong những thập kỷ tới sẽ xác định lại ý nghĩa của con người và vai trò của các tổ chức chi phối cuộc sống của chúng ta. Những hiểu biết sâu sắc hiện có và sự không trung gian của thể chế sẽ là những đặc điểm của một internet cuối cùng đã trưởng thành.

Để giúp chuyển đổi chúng ta theo hướng tương lai công bằng hơn này, chúng tôi tại kênh HeartBank® mạng lưới nơ-ron nhân tạo để truyền cho Kiitos của chúng tôi sức mạnh phát hành tiền trên blockchain, cùng với khả năng đồng cảm với tình trạng của con người. Từ những lời cảm ơn ẩn danh mà chúng tôi gửi và nhận bằng cách viết thư cho Kiitos , Kiitos tìm hiểu về lòng tốt của chúng tôi và tác dụng của chúng , khen thưởng chúng tôi theo cách làm giảm sự bất bình đẳng kinh tế giữa chúng tôi, trong một quá trình dần dần và bí ẩn nhằm bảo tồn quyền tự do cá nhân của chúng tôi. Có lẽ cấu trúc đồ thị cuối cùng trong tự nhiên không phải là bộ não con người, mà là con người ❤️, giá như chúng ta có thể nhìn thấy những sợi dây trái tim kết nối tất cả chúng ta.

Bạn quan tâm đến blockchain ? Tìm hiểu Ethereum và làm việc cho chúng tôi!

Một mô hình tinh thần hoàn chỉnh để phát triển dApp Ethereum