nextlint-logo
Đăng nhập

[DataStructure] HashTable

Tiny
Tiny

10:37 10/07/2021đăng trongCông nghệ

HashTable là cấu trúc dữ liệu dạng [key:value]. HashTable được ứng dụng rất nhiều để implement các cấu trúc dữ liệu như  Set, Map, Object, HashMap trong các ngôn ngữ cấp cao như Javascript, Python, Ruby.
Khi bạn biết giá trị ở trong Array nằm ở vị trí thứ bao nhiêu, bạn có thể truy xuất đến vị trí đó với độ phức tạp O(1)
HashTable
Giả sử muốn lấy thông tin của studentB trong mảng students, nhìn vào ảnh trên mình biết index của nó bằng 1, lúc này mình chỉ đơn giản là students[1] là lấy được thông tin của studentB
Với mắt thường thì có thể thấy được, nhưng máy tính thì đâu có mắt mà thấy được index của studentB = 1 mà lấy ra . Tất cả những gì máy tính biết được chỉ là một bộ nhớ liên tục có độ dài 3*sizeof(students[0]).
Vậy thì làm sao khi mà mình thêm một giá trị vào Array, mình có thể biết được index của giá trị đó để phục vụ cho việc truy xuất nhanh chóng sau này ?

Yah đây là lúc bạn cần đến HashTable

Mình có một cấu trúc dữ liệu HashTable như sau:
class HashTable:
    def __init__(self,size):
        self.size=size
        self.array=[None]*size
HashTable là một Array có size cố định dựa vào số lượng các phần tử bạn muốn chứa.
Vì là cấu trúc giữ liệu [key:value] nên mỗi giá trị trong HashTable phải thuộc về một key nào đó.

Thêm một giá trị vào HashTable

Giả sử mình muốn thêm mới:
[key:value] => ['studentA':{ student: "studentA", age: 12, class: "10A"}]
Điều đầu tiên cần làm là mình dựa vào key studentA thông qua một hàm hash (hàm băm) để return về giá trị là số nguyên X. Sau khi có được số nguyên trả về từ hàm hash, mình sẽ thêm data vào vị trí self.array[X]
Hàm băm: ý tưởng là mình sẽ băm chuỗi ra thành các kí tự đơn lẻ, sau đó mình sẽ tính tổng của tất cả các kí tự ở hệ thập phân trong bảng mã ASCII. Sau đó Mod với size của HashTable.
class HashTable:
#.....
    def hash(self,v):
        sum=0
        for i in range(len(v)):
            sum += ord(v[i])
        return sum%self.size
Ví dụ: HashTable với size=4. Với mỗi [key:value] được thêm vào HashTable sẽ đi theo flow sau:
studentA:
hashA = 115(s) + 116(t)+117(u)+100(d)+101(e)+110(n)+116(t)+65(A) = 840 % 4 = 0
=> self.array[hashA]= { student: "studentA", age: 12, class: "10A"}
studentB:
hashB=115(s) + 116(t)+117(u)+100(d)+101(e)+110(n)+116(t)+66(A) = 841 % 4 = 1
=>self.array[hashB]= { student: "studentB", age: 12, class: "10A"}
studentC:
hashC=115(s) + 116(t)+117(u)+100(d)+101(e)+110(n)+116(t)+67(A) = 842 % 4 = 2
=>self.array[hashC]= { student: "studentC", age: 12, class: "10A"}
studentD:
hashD = 115(s) + 116(t)+117(u)+100(d)+101(e)+110(n)+116(t)+68(A) = 843 % 4 = 3
=>self.array[hashD]= { student: "studentD", age: 12, class: "10A"}
Code:
class HashTable:
    def hash(self,v):
        sum=0
        for i in range(len(v)):
            sum += ord(v[i])
        return sum%self.size

    def add(self,k,v):
        key=self.hash(k)
        self.array[key]=v
Khi bạn tìm kiếm một key nào đó, điều đầu tiên cũng là hash key đó ra hashIndex và truy xuất tới kết quả thông qua hashIndex. Lúc này độ phức tạp khi tìm kiếm chỉ là O(1)
Để đảm bảo tính đúng đắn của cấu trúc dữ liệu, thì hàm băm key lúc thêm data và hàm băm key lúc tìm kiếm dữ liệu phải là một.

Trường hợp đụng độ key

Mỗi key thông qua hàm băm sẽ return về hashKey tương ứng, với công thức generate key như ở trên sẽ fail ở case sau: hashKey= abc = acb = bac =bca = 298 %4 = 2
Như vậy khi thêm vào HashTable thì những giá trị ở key trước đó sẽ bị replace bởi những giá bị thêm vào sau => mất dữ liệu.
Ok. Chúng ta có thể resolve chỗ này bằng cách optimize hàm hash để có thể băm ra key với tỉ lệ đụng độ thấp nhất có thể:
abc = a(97)*indexA(1) + b(98)*indexB(2)+c(99)*indexC(3)=590%4 = 2
=> array[2]=abc
acb=a(97)*indexA(1)+c(99)*indexC(2)+b(98)*indexB(3)=589%4 = 1
=> array[1]=abc
Trông có vẻ ổn đó, nhưng các bạn nên nhớ băm ra tổng khác nhau thì chưa chắc % size sẽ khác nhau 8%4 = 16%4 = 24%4 = 0
Chúng ta cần một phương án bao quát hơn. Nếu các bạn đã đọc bài blog trước của mình về Linklist thì mình có để cập đến việc sử dụng DSLK để xử lý đụng độ trong HashTable.
Lúc này mỗi phần tử cơ bản trong HashTable sẽ là một DSLK đơn. Khi xảy ra đụng độ, thì DSLK tại key đó sẽ tạo một Node mới và thêm vào DSLK đơn. Lúc này vẫn đề đụng độ được giải quyết nhưng trong trường hợp xấu nhất. Tất cả các phần tử được thêm vào tại một key ( do hàm băm quá chuối) thì độ phức tạp tìm kiếm lúc này là  O(n) với n là số phần tử được thêm vào.

Okay như vậy ở hàm add mình cần sửa lại chút xíu:
class HashTable:
    def __init__(self,size):
        self.size=size
        self.array=[None]*size

    def add(self,k,v):
        key=self.hash(k)
        if self.array[key]!=None:
            self.array[key].addHead(v)
            return
        ll=LinkList()
        ll.addHead(v)
        self.array[key]=ll
✧ ✧ ✧

Tìm kiếm trên HashTable

Lúc này HashTable của mình là một Array với các phần tử trong mảng là DSLK. Việc tìm kiếm mình sẽ uỷ thác cho class LinkList.
class LinkList:
    def __init__(self):
        self.head = None
        self.tail = None

    def find(self, cb):
        node = self.head
        result = None
        while node is not None:
            if cb(node):
                result = node
                break
            else:
                node = node.next
        return result
Chi phí tìm kiếm trên DSLK trong trường hợp tốt nhất là O(1) và xấu nhất là O(n).
Hàm get setup trong class HashTable như sau:
class HashTable:
    def __init__(self,size):
        self.size=size
        self.array=[None]*size

    def get(self,v):
        key=self.hash(v)
        def cb(node):
            return node.value == v
        r= self.array[key].find(cb)
        if r != None:
            return r.value
        return None
Ưu điểm HashTable: Tốc độ tìm kiếm
Nhược điểm:
  • Hiệu năng của  HashTable phụ thuộc nhiều vào hàm băm
  • Tốn chi phí lưu trữ
  • Lãng phí bộ nhớ nếu xảy ra nhiều trường hợp đụng độ => bộ nhớ đã fix sẵn không sử dụng hết
  • Không hiệu quả khi đụng độ key quá nhiều

Tính ứng dụng

Associative array (là các mảng mà index có thể được đặt theo tên) HashTable được sử dụng để implement nhiều loại in-memory tables. Với những ngôn ngữ hỗ trợ chỉ mục index là string như Ruby, Python, PHP sử dụng HashTable để lưu trữ những giá trị này.
Javascript  Associative array không được support, nếu bạn xài Associative syntax thì javascript sẽ tự động chuyển Associative array thành kiểu Object
Database indexing HashTable được sử dụng để lưu trữ indexing database (ngoài ra còn có B-tree)
Caches vì có tốc độ tìm kiếm tốt nên thường được sử dụng để caching.
Sets implement từ HashTable
Object representation những ngôn ngữ cấp cao như Ruby, Python, Javascript sử dụng HashTable để implement Objects.
Unique data representation là singleton của datastructure. Sử dụng để lưu trữ unique data.