Hỏi đáp

Hashtable Là Gì – Bảng Băm (Hash Table) – viettingame

Trình làng

Thuật toán liên quan tới hash table được ứng dụng ở hầu hết những ngôn từ, là một trong những nền tảng về thuật toán và cấu trúc dữ liệu.

Trong computing, hash table là một cấu trúc dữ liệu sử dụng để lưu theo những cặp key value, nó sử dụng hash function để tính toán tới một index, nơi lưu trữ một bucket những giá trị rồi từ đó sẽ retrieve ra value, tiềm năng là để độ phức tạp ở mức O(n)

Lý luận:

Mà thậm chí lấy một ví dụ giản dị và đơn giản là việc lấy sách ở thư viện, mỗi cuốn sách trong thư viện đều sở hữu môt unique number, những cuốn sách này sẽ sắp xếp trong cùng một địa chỉ (call number) toạ lạc bên trong thư viện, chúng ta sẽ nhờ vào call number và unique number để tìm ra được cuốn sách đang cất ở đâu

Id của sách sẽ được sinh ra dựa trên một function gọi là hash function,

*

Hash function thậm chí được implement theo nhiều cách thức, cách cơ bạn dạng nhất dựa trên mã ascii của kí tự.

Ví dụ như dựa trên công thức

s.charAt(0) * 31n-1 + s.charAt(1) * 31n-2 + … + s.charAt(n-1)

Ở phía trên s là string cần chuyển, n là độ dài của nó, ví dụ:

“ABC” = “A” * 312 + “B” * 31 + “C” = 65 * 312 + 66 * 31 + 67 = 64578

Giả sử chúng ta lưu một bảng string {“abcdef”, “bcdefa”, “cdefab” , “defabc” }.Mã ASCII a, b, c, d, e, và f là 97, 98, 99, 100, 101, 102 , như ta thấy những thực thể phía trên đều sở hữu cùng số kí tự và chỉ khác ở sự hoán vị.Thì index của thực thể đó sẽ bằng tổng (mã ascii của kí tự * vị trí của kí tự đó trong chuỗi)

Chúng ta sẽ sử dụng mã ASCII để sinh ra những đoạn hash code cho một thực thể, tổng tất những mã ascii thậm chí xác định được kí tự là 2069, nên chúng chia lại cho số lượng đó để tạo index

String Hash function Index abcdef (971 + 982 + 993 + 1004 + 1015 + 1026)%2069 38bcdefa (981 + 992 + 1003 + 1014 + 1025 + 976)%2069 23cdefab (991 + 1002 + 1013 + 1024 + 975 + 986)%2069 14defabc (1001 + 1012 + 1023 + 974 + 985 + 996)%2069 11

*

Xử lý collision

Vấn phát sinh những trường hợp trùng vị trí (index) nếu thuật toán hash ko được tốt và hâù như không tồn tại thuật toán hash nào thực sự tuyệt vời nhất để sinh ra unique key nếu lưu trữ một lượng to dữ liệu , để xử lý vấn đề này chúng ta sử dụng linked list để lưu trữ thêm một tầng nữa những thực thể cho index đó.

Mà thậm chí coi việc sinh hash là để tạo keyHash và lưu vào trong mảng giá trị nơi chứa một linked list sở hữu thực thể chứa key thật của con người, sau lúc tới đó chúng ta sẽ sử dụng key thật để retrieve giá trị

*

*

Trên đây là đoạn code mình thấy khá hay và dễ hiểu về implement hastable:

import LinkedList from “../linked-list/LinkedList”;// Hash table size directly affects on the number of collisions.// The bigger the hash table size the less collisions you”ll get.// For demonstrating purposes hash table size is small to show how collisions// are being handled.const defaultHashTableSize = 32;export default class HashTable { /** *

Đang xem: Hashtable là gì

param {number} hashTableSize */ constructor(hashTableSize = defaultHashTableSize) { // Create hash table of certain size and fill each bucket with empty linked list. this.buckets = Array(hashTableSize).fill(null).map(() => new LinkedList()); // Just to keep track of all actual keys in a fast way. this.keys = {}; } /** * Converts key string to hash number. * *
return {number} */ hash(key) { const hash = Array.from(key).reduce( (hashAccumulator, keySymbol) => (hashAccumulator + keySymbol.charCodeAt(0)), 0, ); // Reduce hash number so it would fit hash table size. return hash % this.buckets.length; } /** *

Xem thêm: What Is The Meaning Of “I’M So Drained Là Gì, Drain Là Gì

param {*} value */ set(key, value) { const keyHash = this.hash(key); this.keys = keyHash; const bucketLinkedList = this.buckets; const node = bucketLinkedList.find({ callback: nodeValue => nodeValue.key === key }); if (!node) { // Insert new node. bucketLinkedList.append({ key, value }); } else { // Update value of existing node. node.value.value = value; } } /** *
return {*} */ delete(key) { const keyHash = this.hash(key); delete this.keys; const bucketLinkedList = this.buckets; const node = bucketLinkedList.find({ callback: nodeValue => nodeValue.key === key }); if (node) { return bucketLinkedList.delete(node.value); } return null; } /** *

Xem thêm: Cấp Bậc Junior, Internship Và Fresher Trong Doanh Nghiệp, Junior Là Gì

return {*} */ get(key) { const bucketLinkedList = this.buckets; const node = bucketLinkedList.find({ callback: nodeValue => nodeValue.key === key }); return node ? node.value.value : undefined; } /** *
return {string} */ getKeys() { return Object.keys(this.keys); }}Hy vọng chúng ta hiểu hơn về hash map , hash table, thứ mà dân DEV chúng ta hầu như xài một ngày dài (hoho)

Về Viettingame.com

Viettingame.com - Chuyên trang web tổng hợp những thông tin hữu ích trên internet như thông tin về game, tin tổng hợp
Xem tất cả các bài viết của Viettingame.com →

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *