Hash table là gì

Giới thiệu

Thuật toán liên quan mang lại hash table được áp dụng sống phần lớn những ngôn từ, là 1 trong trong những gốc rễ về thuật toán thù với kết cấu dữ liệu.

Trong computing, hash table là 1 trong cấu tạo tài liệu dùng làm lưu theo các cặp key value, nó sử dụng hash function để tính toán cho tới một index, nơi lưu trữ một bucket những cực hiếm rồi từ bỏ đó sẽ retrieve sầu ra value, mục tiêu là nhằm độ phức hợp ở tại mức O(n)

Giải thích:

cũng có thể đem một ví dụ dễ dàng là câu hỏi rước sách làm việc thỏng viện, mỗi cuốn sách trong tlỗi viện đều phải có môt chất lượng number, rất nhiều cuốn nắn sách này đã sắp xếp vào và một tương tác (Gọi number) toạ lạc bên trong thư viện, bọn họ vẫn phụ thuộc vào Hotline number với quality number nhằm tìm ra được cuốn nắn sách đang cất ở đâu

Id của sách sẽ được xuất hiện dựa trên một function Call là hash function,

*

Hash function rất có thể được implement theo rất nhiều cách, giải pháp cơ phiên bản độc nhất dựa trên mã ascii của kí từ bỏ.

lấy ví dụ nhỏng 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 đề xuất đưa, n là độ nhiều năm của nó, ví dụ:

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

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

Chúng ta sẽ dùng mã ASCII nhằm hiện ra các đoạn hash code đến một phần tử, tổng tất những mã ascii hoàn toàn có thể xác minh được kí từ là 2069, đề nghị chúng phân chia lại mang đến số lượng đó nhằm 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

*

Giải quyết collision

Vấn tạo ra những ngôi trường đúng theo trùng vị trí (index) nếu thuật toán thù hash không được giỏi và hâù nhỏng không có thuật toán hash như thế nào đích thực tuyệt đối để ra đời unique key nếu tàng trữ một lượng Khủng tài liệu , nhằm giải quyết và xử lý vấn đề này họ dùng linked list nhằm tàng trữ thêm 1 tầng nữa những bộ phận mang đến index đó.

cũng có thể coi vấn đề sinch hash là để tạo nên keyHash cùng lưu lại vào vào mảng cực hiếm vị trí cất một linked danh sách gồm bộ phận cất key thiệt của bọn họ, sau khi tới đó bọn họ đang dùng key thiệt nhằm retrieve sầu giá bán trị

*

*

Đây là đoạn code mình thấy khá hay và dễ dàng nắm bắt về implement hastable:

import LinkedList from "../linked-list/LinkedList";// Hash table kích cỡ directly affects on the number of collisions.// The bigger the hash table kích cỡ 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 mặc định class HashTable /** *


Bạn đang xem: Hash table là gì

param number hashTableSize */ constructor(hashTableSize = defaultHashTableSize) // Create hash table of certain form size và fill each bucket with empty linked danh sách. this.buckets = Array(hashTableSize).fill(null).map(() => new LinkedList()); // Just lớn keep trachồng of all actual keys in a fast way. this.keys = ; /** * Converts key string khổng lồ 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 form size. return hash % this.buckets.length; /** *


Xem thêm: Làm Thế Nào Để Sữa Mẹ Về Nhanh, Sữa Về Nhanh

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: Tải Phần Mềm Viết Chữ Thư Pháp ❤️ Tạo Chữ Ông Đồ Trên Máy Tính

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 các bạn gọi rộng về hash bản đồ , hash table, thứ nhưng mà dân DEV chúng ta phần lớn xài một ngày dài (hoho)


Chuyên mục: Hỏi Đáp