Hashtable Là Gì

Bài viết gốc:https://medium.freecodecamp.org/how-to-implement-a-simple-hash-table-in-javascript-cb3b9c1f2997

Tác giả: Alex Nadalin.

Bạn đang xem: Hashtable là gì

Dịch giả: Togahepi a.k.a Hà Hiệp.

*

quý khách gồm thấy vệt đẹp lung linh vời không?

Nó cho phép bạn lưu dữ liệu khớp ứng cùng với khóa, và truy nã xuất lại cực kỳ thuận tiện (O(1), họ đã bàn cho tới nghỉ ngơi sau).

Trong nội dung bài viết này tôi sẽ khuyên bảo giải pháp thực thi một hash table đơn giản dễ dàng, bọn họ vẫn mổ sẻ giải pháp nó chuyển động nhằm phát âm sâu rộng về một Một trong những ý tưởng phát minh hết sức phàm vào khoa học laptop.

Vấn đề

Tưởng tượng rằng nhiều người đang xây cất một ngữ điệu lập trình mới: các bạn sẽ ban đầu bằng phần lớn đẳng cấp tài liệu dễ dàng (chuỗi, số nguyên, số thập phân, ...) và rồi sẽ xây dựng phần lớn kết cấu tài liệu đơn giản và dễ dàng. trước hết các bạn gồm mảng array (< >), rồi sẽ cho tới hash table (xuất xắc được nghe biết nlỗi trường đoản cú điển, mảng link, hashmaps, bản đồ cùng ... còn dài lắm).

Có lúc nào các bạn từ hỏi chúng chuyển động ra sao? Nlỗi nuốm như thế nào màchúng lại hoạt động nkhô hanh nhỏng giảm vậy?

Ta đang đưa sử như JavaScript không tồn tại hoặc new Map (), và ta vẫn trường đoản cú xây đắp phiên bạn dạng từ bỏ chế DumbMap - NguNgơMap!

Ghi chú về độ phức hợp của thuật toán

Trước lúc họ thực hiện, chúng ta đề nghị phát âm độ phức tạp thuật toán của một hàm là gì: Wikipedia có định nghĩa ví dụ trên đây độ phức tạp thuật tân oán, cơ mà tôi đã lý giải một phương pháp vắn tắt đến mấy thiếu phụ lười luôn.

Độ phức tạp tính toán bao nhiêu bước rất cần phải tiến hành trong hàm - càng ít bước thì đã càng chạy nhanh hao (tên thường gọi không giống là "running time" càng ngắn thêm càng ngon).

Bây tiếng hãy quan sát vào hàm này:

function fn(n, m) return n * mĐộ tinh vi thuật toán thù (Gọi tắt luôn là "độ phức tạp") của hàm fn là O(1), nghĩanó là hằng số(chúng ta có thể Điện thoại tư vấn O(1) là "tốn tất cả một"): bất cứ tmê mẩn số đầu vào của doanh nghiệp bự ra sao thì hàm này vẫn chỉ chạy một phxay tính (nhân n cùng với m). Do nó chỉ tốn một phnghiền tính buộc phải độ phức hợp chỉ với O(1).

Độ phức tạp được đo lường và thống kê vì chưng đầu vào của hàm rất có thể không hề nhỏ. Hãy quan sát vào ví dụ bên dưới dây:

function fn(n, m) { let s = 0 for (i = 0; i quý khách hàng sẽ cho là độ tinh vi vẫn là O(3)?

Do trong một trong những trường thích hợp độ phức tạp hết sức lớn, bởi vì vậy họ vẫn "quăng quật qua" hồ hết hằng số cùng coi O(3) cũng bằng O(1). Vì núm, vào trường thích hợp này thì độ phức hợp của hàm fn cũng chính là O(1). Bất đề cập n, m ra làm sao thì bạn cũng chỉ tính toán thù bao gồm 3 phxay tính - là 1 trong hằng số (chính vì như vậy vẫn chỉ là O(1)).

Bây giờ đồng hồ hãy xem một ví dụ khác hoàn toàn chút ít xíu:

function fn(n, m) { let s = <> for (i = 0; i quý khách hàng thấy đó, họ đã tái diễn n lần, chính vì vậy n rất có thể lên đến mức hàng tỷ lần. Trong ngôi trường thích hợp này, chúng ta khái niệm độ tinh vi của hàm này là O(n), vì bạn sẽ nên thực hiện số phnghiền tính bằng với giá trị của tmê mẩn sốnhập vào.

lấy ví dụ không giống nè?

function fn(n, m) { let s = <> for (i = 0; i Trong ví dụ này họ đã lặp 2*n lần, tức là độ phức hợp sẽ là O(2n). Tuy nhiên nhỏng ta đã nói từ bỏ trước số đông hằng số sẽ tiến hành "quăng quật qua" Lúc tính toán độ phức tạp của hàm, vì thế trong ví dụ này độ phức hợp chỉ nên O(n).

Thêm ví dụ nữa cho đọc kĩ nè!

function fn(n, m) { let s = <> for (i = 0; i Tại phía trên bọn họ tái diễn n lần rồi trong những lần họ lại lặp n lần tiếp nữa như thế độ phức tạp đang là "bình phương" n*n: nếu n là 2 thì chạy 4 lần, nếu như là 3 thì chạy 9 lần, v.v.

Trong ngôi trường hợp này thì độ phức tạp sẽ được tính là O(n2) .

Chốt quả cuối đến Chắn chắn nè! :))

function fn(n, m) { let s = <> for (i = 0; i Trong ví dụ này họ không lồng những vòng lặp, mà chỉ lặp 2 vòng cùng với 2 tđam mê số: độ phức hợp đã là O(n+m). Rõ nlỗi buổi ngày rùi.

Vậy là họ đang bao gồm một màn ra mắt nho bé dại về độ phức hợp, nhờ đó ta gọi một hàm cùng với độ phức tạp O(1) vẫn chạy nhanh hao hơn những so với hàm tất cả độ tinh vi O(n).

Hash table tất cả độ tinh vi là O(1): xem qua thì bọn chúng sẽcực kì nhanh.Hãy gọi tiếp nhé.

(Tôi hơi gồm chém nhẹm Lúc nói hash table luôn luôn luôn gồm độ tinh vi là O(1), tuy thế hãy cđọng phát âm tiếp nhé ;))

Hãy gây ra một hash table (phiên bạn dạng ngây ngô ngơ)

Hash table của họ sẽ có được 2 cách tiến hành - set(x, y) và get(x). Hãy bắt đầu nào:

class DumbMap get(x) console.log(`get $x`) set(x, y) console.log(`set $x to lớn $y`) let m = new DumbMap()m.set("a", 1) // "set a khổng lồ 1"m.get("a") // "get a"Chúng ta sẽ xây dựng một cách khôn cùng đơn giản nhưng kết quả nhằm tàng trữ cặp chìa khóa-giá trị (key-value) với tất cả thểtruy nã xuất cho tới chúng trong tương lai. Trước tiên ta sẽ lưu lại chúng nó vào một mảng (lưu giữ nhé, họ không thể dùng do chúng ta đang xây dựng nhé - quyết liệt chưa! :v):

class DumbMap constructor() this.các mục = <> ... set(x, y) this.list.push() Và để đưa bộ phận ta mong muốn tự list này thì giải pháp dễ dàng là:

get(x) let result this.các mục.forEach(pairs => if (pairs<0> === x) result = pairs<1> ) return resultví dụ như đầy đủ:

class DumbMap constructor() this.menu = <> get(x) let result this.danh mục.forEach(pairs => if (pairs<0> === x) result = pairs<1> ) return result set(x, y) this.menu.push() let m = new DumbMap()m.set("a", 1)console.log(m.get("a")) // 1console.log(m.get("I_DONT_EXIST")) // undefinedHàm DumbMap của bọn họ giỏi nhỉ! Làm câu hỏi chuẩn chỉ luôn luôn, tuy vậy vẫn như thế nào trường hợp ta bắt buộc thêm vào một lượng béo cặp key-value?

Hãy benchmark một ít. trước hết chúng ta đã demo kiếm tìm kiếm một trong những phần tử ko có mặt trong một hash table bé dại với vài thành phần, tiếp đến đang demo với loại có lượng phệ bộ phận sau:

let m = new DumbMap()m.set("x", 1)m.set("y", 2)console.time("với cùng 1 vài ba bản ghi trong map")m.get("I_DONT_EXIST")console.timeEnd("với cùng 1 vài ba bạn dạng ghi vào map")m = new DumbMap()for (x = 0; x Kết quả? Không ngon nghẻ gì:

với cùng 1 vài ba phiên bản ghi vào map: 0.118msvới tương đối nhiều những phiên bản ghi trong map: 14.412msVới phương pháp thực hiện của chúng ta, ta đề nghị lặp qua tất cả những thành phần trong this.các mục để tìm một phần tử trùng với key. Độ phức tạp vẫn là O(n), tương đối là tệ rò rỉ.

Làm nó nhanh hao rộng làm sao.

Chúng ta bắt buộc tìm ra phương pháp tránh bắt buộc lặp qua cả danh sách: đã tới khi xàihashtronghash tablenhư thế nào.

Bạn tất cả vướng mắc tại vì sao lại call kết cấu dữ liệu này làhashtable không? Đó là vì chưng một hàm hashing được áp dụng với những khóa nhưng mà bạn mix và get. Chúng ta sẽ sử dụng hàm này nhằm biến hóa key của bọn họ thành một số ít nguyên i, và lưu giữ value vào chỉ mục i của danh sách. Do vậy Lúc truy vấn xuất một trong những phần tử, bằng chỉ mục của chính nó xuất phát điểm từ một danh sách thì chỉ tốn có O(1) thôi vì vậy ta nói hash table gồm độ tinh vi O(1).

Xem thêm: Ý Kiến Về Mỹ Phẩm M White Có Tốt Không ? Mỹ Phẩm M White Có Tốt Không

Hãy nấu thử luôn nào:

let hash = require("string-hash")class DumbMap constructor() this.các mục = <> get(x) return this.list set(x, y) this.list = y Tại phía trên họ sử dụng một string-hash module, sẽ biến hóa một chuỗi thành 1 mã hash dạng số. Chúng ta đang tàng trữ cùng truy tìm xuất phần tử tại chỉ mục index hash(key) của list. Và hiệu quả benchmark lại:

với rất nhiều những bản ghi vào map: 0.013msW --- O --- W. Đây đó là điều tôi ước ao nói!

Chúng ta đang không phải lặp đi lặp lại qua toàn bộ những bộ phận trong list, vì thế tróc nã xuất tới một phần tử bất kỳ trong DumpMap sẽ cực kì nkhô nóng luôn!

Tóm gọn gàng lại luôn nè: hashing làm hash table trsinh hoạt đề xuất vô đối. Không gồm phép màu làm sao luôn. Một ý tưởng phát minh hết sức dễ dàng, logic với sáng suốt.

Chọn hàm hashing cũng quan trọng đó.

Đương nhiên, chọn hàm hashing cũng đặc biệt quan trọng lắm.Nếu hàm hash(key) chạy tốn vài ba giây thì hàm của chúng ta đã lờ đờ đi kha khá và tăng cả độ phức tạp.

điều đặc biệt quan trọng nữa là hàm hashing ko được tạo ra những quý giá trùng nhau - collision,bởi nó đang có tác dụng hư hash table luôn.

Rối trí phải hem? Hãy tò mò kĩ rộng về collision như thế nào.

Collisions

Quý khách hàng rất có thể tưởng rằng "Ui giời, một hàm hashing tốt thì chẳng tạo ra mã lặp collision nào đâu!":thôi như thế nào quay trở về mặt đất đê. Google sẽ rất có thể tạo ra collision đến thuật toán hashing SHA-1,chỉ là sự việc thời gian thôi, với sức khỏe rất máy tính xách tay thì một hàm hashing bị craông xã với mang lại thuộc 1 mã hash mang đến 2 cực hiếm đầu vào là tất cả thực. Luôn luôn đề nghị sẵn sàng chuẩn bị rằng hàm hashing của bạn có thể tạo ra những collision và buộc phải tạo thành các lớp phòng vệ trước mọi trường thích hợp kia.

function divide(int) int = Math.round(int / 2) if (int > 10) return divide(int) return intfunction hash(key) let h = require("string-hash")(key) return divide(h)Hàm này dùng mảng 10 bộ phận để giữ quý giá, có nghĩa là các bộ phận có khả năng sẽ bị sửa chữa - một bug to lớn oành khi áp vào DumbMap:

function divide(int) int = Math.round(int / 2) if (int > 10) return divide(int) return intfunction hash(key) let h = require("string-hash")(key) return divide(h)Để xử lý vấn đề này, chúng ta dễ dàng và đơn giản làlưu trữ nhiều cặp key-value vào thuộc 1 chỉ mục index. Hãy sửa đổi lại hash table:

class DumbMap { constructor() this.các mục = <> get(x) let i = hash(x) if (!this.list) return undefined let result this.list.forEach(pairs => if (pairs<0> === x) result = pairs<1> ) return result set(x, y) { let i = hash(x) if (!this.list) this.list = <> this.list.push()quý khách hàng nhận ra đúng không nhỉ, chúng ta lại trở lại cách xúc tiến ban đầu: lưu 1 danh sách các cặp key-value và lặp qua từng thành phần. Nó sẽ trở bắt buộc cực kì lờ lững Khi có nhiều collision trong cùng 1 chỉ mục vào list.

Thử benchmark cùng với hàm hash() của chúng ta chỉ tạo thành chỉ mục từ là một mang đến 10:

với rất nhiều nhiều bạn dạng ghi vào map: 11.919mscòn với hàm hash trường đoản cú string-hash, tạo nên chỉ mục random:

với nhiều các phiên bản ghi vào map: 0.014msVậy là ví dụ rồi nhé, bài toán chọn hàm hash cũng hết sức đặc biệt - buộc phải đầy đủ nhanh nhằm không làm lờ đờ cả quá trình, và cũng cần đầy đủ tốt để ko tạo nên những collision.

Thông thường O(1)

Nhớ lời tôi chém gió thuở đầu chứ?

Hashtable luôn luôn gồm độ tinh vi O(1)

Thực ra tôi chém nhẹm đó: độ tinh vi của một hash table phụ thuộc vào hàm hashing nhưng các bạn chọn. Càng các collision thì độ tinh vi càng tiệm cận O(n).

Một hàm hashing ví dụ:

function hash(key) return 0sẽ nghĩa là hash table này sẽ có được độ tinh vi O(n).

Vì vậy vào độ tinh vi chia làm 3 nấc độ: rất tốt, mức độ vừa phải và ngôi trường đúng theo tệ nhất. Hashtable bao gồm độ tinh vi O(1) là rất tốt tuy nhiên sẽ tiệm cận dần dần O(n) làm việc trường hợp tệ độc nhất vô nhị.

Luôn nhớ:Một hàm hashing xuất sắc là khóa xe để sở hữu một hash table công dụng ---ko hơn cũng không kém.

Tìm phát âm thêm về collision...

Kĩ thuật nhưng mà bọn họ áp dụng nhằm sửa DumbMap trong trường hợp có tương đối nhiều collision được điện thoại tư vấn là separate chaining:bọn họ sẽ giữ toàn cục các key cơ mà tạo ra collision và một danh sách và lặp qua bọn chúng.

Một kỹ năng thông dụng khác là open addressing - can hệ mở:

Tại từng chỉ mục index của danh sách bọn họ chỉ lưu giữ trữ1 và chỉ còn 1 cặp key-valuekhi cố gắng giữ một cặp sinh sống chỉ mục x, nếu như sống đó đã lưu một cặp không giống rồi thì sẽ demo lưu cặp new đó vào x + 1Nếu x + 1 đã bị chiếm phần chỗ thì lại khiêu vũ sang x + 2 cùng cứ rứa...lúc truy xuất lại một phần tử, hash key kia cùng khám nghiệm nếu thành phần trên địa chỉ (x) có trùng key kia ko.Nếu ko thì lại thử truy vấn thành phần trên địa điểm x + 1Cứ đọng tái diễn cho đến cuối list hoặc khi bạn tìm kiếm thấy một chỉ mục trống rỗng - Có nghĩa là thành phần đó không tồn tại trong hash table

Thông minc, đơn giản dễ dàng, thanh hao kế hoạch cùng hay thì cực kì hiệu quả!

FAQs (hỏi chuyển phiên đáp xoáy)

Có cần hash table hash value mà họ đã lưu?

Không đúng, chỉ gồm key được hash nhằm trở thành một số ngulặng i, và cả key lẫn value sẽ tiến hành giữ trên địa chỉ i vào list.

Những hàm hashing được sử dụng vào hash table tạo thành những giá trị lặp collision?

Chuẩn kia - chính vì như thế hash table sẽ đề nghị thực thi thêm các giải pháp phòng vệ để tránh gặp bug.

Có cần hash table thực hiện mảng danh mục hay 1 linked các mục có sẵn?

Nó còn tùy, cả 2 phần lớn rất có thể thực hiện. Trong ví dụ của họ, mảng trong JavaScript ( <> ) rất có thể đổi khác kích thước động:

> a = <>> a<3> = 1> a< , 1 >

Vậy tại vì sao ta lại chọn JavaScript làm ví dụ? Mảng vào JS là hash table!

Ví dụ:

> a = <><>> a<"some"> = "thing""thing"> a< some: "thing" >> typeof a"object"Đùa chứ đọng, kiên cố chỉ bao gồm mỗi JavaScript là vậy.

JavaScript có lẽ rằng là ngữ điệu dễ nắm bắt nhất lúc làm cho code chủng loại. JS có lẽ rằng không hẳn là ngôn từ xuất xắc độc nhất tuy vậy đa số ví dụ này mong rằng đủ ví dụ.

Đây có đề xuất là một trong cách thực hiện hash table tốt? Nó bao gồm đơn giản nhỏng vậy?

Không, Chưa hẳn là vậy.

Hãy xem thêm bài viết này "thực hiện hash table vào JavaScript". Sẽ có rất nhiều ngôi trường đúng theo rộng, và còn những tư liệu tham khảo không giống tại:

Kết bài:

Hash table là 1 trong phát minh cực kì lý tưởng được sử dụng rộng rãi: bất cứ đâu khi nhưng mà các bạn chế tác tự điển cùng với Pythanh mảnh, một mảng liên kết vào PHPhoặc Map vào JavaScript. Chúng phần đông dựa vào và một ý tưởng tuyệt vời góp họ lưu trữ với truy nã xuất phần tử chỉ bởi key, với gần như là chỉ tốn O(1).