Blogs

Tìm hiểu về hash table

Bạn đang quan tâm đến Tìm hiểu về hash table phải không? Nào hãy cùng ONLINEAZ đón xem bài viết này ngay sau đây nhé, vì nó vô cùng thú vị và hay đấy!

XEM VIDEO Tìm hiểu về hash table tại đây.

Hash table là gì

Giới thiệu

Thuật toán liên quan đến hash table được ứng dụng ở hầu hết các ngôn ngữ, 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 dùng để lưu theo các cặp key value, nó dùng hash function để tính toán tới một index, nơi lưu trữ một bucket các giá trị rồi từ đó sẽ retrieve ra value, mục tiêu là để độ phức tạp ở mức O(n)

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

Giải thích:

Có thể lấy một ví dụ đơn giản là việc lấy sách ở thư viện, mỗi cuốn sách trong thư viện đều có 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ẽ dựa 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 có thể được implement theo nhiều cách, cách cơ bản nhất dựa trên mã ascii của kí tự.

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

Có thể bạn quan tâm: Elly Trần tuổi 34 hạnh phúc bên 2 con, sống không màng vật chất

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

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

XEM THÊM:  20+ Hình Ảnh Ly Cà Phê Buổi Sáng Đẹp Nhất, Top 50 Hình Ảnh Ly Cafe Buổi Sáng Đẹp Tuyệt Vời

“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 các phần tử phía trên đều có cùng số kí tự và chỉ khác ở sự hoán vị. Thì index của phần tử đó sẽ bằng tổng (mã ascii của kí tự * vị trí của kí tự đó trong chuỗi)

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

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

Tìm hiểu về hash table

Giải quyết collision

Xem thêm: Bạc xi vàng tây là gì? trang sức bạc si có bền không?

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

XEM THÊM:  Kinh tế

Có thể 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 có phần tử chứa key thật của chúng ta, sau khi tới đó chúng ta sẽ dùng key thật để retrieve giá trị

Tìm hiểu về hash table

Tìm hiểu về hash table

Đâ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 { /** * @param {number} hashTableSize */ constructor(hashTableSize = defaultHashTableSize) { // Create hash table of certain size and fill each bucket with empty linked list. onlineaz.vnets = Array(hashTableSize).fill(null).map(() => new LinkedList()); // Just to keep track of all actual keys in a fast way. onlineaz.vn = {}; } /** * Converts key string to hash number. * * @param {string} key * @return {number} */ hash(key) { const hash = onlineaz.vn(key).reduce( (hashAccumulator, keySymbol) => (hashAccumulator + onlineaz.vnCodeAt(0)), 0, ); // Reduce hash number so it would fit hash table size. return hash % onlineaz.vnth; } /** * @param {string} key * @param {*} value */ set(key, value) { const keyHash = onlineaz.vn(key); onlineaz.vn[key] = keyHash; const bucketLinkedList = onlineaz.vnets[keyHash]; const node = onlineaz.vn({ callback: nodeValue => onlineaz.vn === key }); if (!node) { // Insert new node. onlineaz.vnnd({ key, value }); } else { // Update value of existing node. onlineaz.vn = value; } } /** * @param {string} key * @return {*} */ delete(key) { const keyHash = onlineaz.vn(key); delete onlineaz.vn[key]; const bucketLinkedList = onlineaz.vnets[keyHash]; const node = onlineaz.vn({ callback: nodeValue => onlineaz.vn === key }); if (node) { return onlineaz.vnte(node.value); } return null; } /** * @param {string} key * @return {*} */ get(key) { const bucketLinkedList = onlineaz.vnets[this.hash(key)]; const node = onlineaz.vn({ callback: nodeValue => onlineaz.vn === key }); return node ? onlineaz.vn : undefined; } /** * @param {string} key * @return {boolean} */ has(key) { return onlineaz.vn(this.keys, key); } /** * @return {string[]} */ getKeys() { return onlineaz.vn(this.keys); } }

XEM THÊM:  Đất rừng phòng hộ là gì? Chuyển đổi rừng phòng hộ sang rừng sản xuất?

Hy vọng các bạn hiểu hơn về hash map , hash table, thứ mà dân DEV chúng ta hầu như xài cả ngày (hoho)

Có thể bạn quan tâm: Quy định về tinh giản biên chế đối với giáo viên tiểu học mới nhất

Vậy là đến đây bài viết về Tìm hiểu về hash table đã dừng lại rồi. Hy vọng bạn luôn theo dõi và đọc những bài viết hay của chúng tôi trên website Onlineaz.vn

Chúc các bạn luôn gặt hái nhiều thành công trong cuộc sống!

Related Articles

Trả lời

Email của bạn sẽ không được hiển thị công khai.

Back to top button