Tìm kiếm, xóa, cập nhật giá trị trong mảng (Array) và bảng băm (Hash Table)

Array và Hash Table là hai trong số những kiểu dữ liệu được sử dụng khá thường xuyên trong lập trình. Trên thực tế thì cả hai kiểu dữ liệu này được sử dụng theo cách tương tự nhau và thường thực hiện các tác vụ phổ biến như thêm dữ liệu, tìm kiếm, sửa và xoá dữ liệu. Đối với các lập trình viên ít kinh nghiệm thì hai kiểu dữ liệu này không có gì khác biệt. Điều này cũng không phải là lạ bởi sự khác biệt giữa Array và Hash Table chỉ được thể hiện rõ nét khi chúng được đánh giá trên góc độ performance.

Bạn muốn biết Array và Hash Table khác nhau như thế nào? Hãy cùng tôi tìm hiểu ngay trong những phần tiếp theo đây của bài viết này. Nhưng trước tiên chúng ta hãy cùng nhau ôn lại hai khái niệm Array và Hash Table.

Array (mảng) là kiểu dữ liệu dùng để lưu trữ nhiều giá trị khác nhau. Mỗi giá trị sẽ được lưu trữ bởi một phần tử của mảng, các phần tử được gắn một số khoá duy nhất. Khoá của phần tử trong mảng là các số tự nhiên liên tiếp và phần tử đầu tiên bắt đầu của mảng thường được đánh số là 0.

Ví dụ một mảng gồm 6 phần tử sẽ có thể được biểu diễn bởi hình minh hoạc như dưới đây:

Để lưu trữ các giá trị của phần tử trong mảng máy tính sẽ sử dụng các địa chỉ còn trống nằm cạnh nhau trên bộ nhớ tương tự như hình mà bạn thấy ở trên. Tuỳ vào kiểu dữ liệu của phần tử trong mảng mà máy tính sẽ đăng ký số lượng bộ nhớ cần thiết cho từng phần tử. Ví dụ với mảng chứa phần tử thuộc kiểu dữ liệu là kiểu ký tự VARCHAR thì mỗi phần tử thông thường sẽ cần sử dụng tới 1 byte để lưu trữ.

Lưu ý: Trong một số ngôn ngữ lập trình bậc cao thì cách định nghĩa array như trên sẽ tương đương với kiểu dữ liệu mảng đánh số hay numeric array.

Hash Table là kiểu dữ liệu cho phép lưu trữ nhiều giá trị trong đó mỗi giá trị được lưu trữ bởi một phần tử và mỗi phần tử được đánh khoá khác nhau. Tuy nhiên khác với mảng thì phần tử trong kiểu dữ liệu hash table được đánh khoá với giá trị tuỳ ý (có thể là một chuỗi, một object hay thậm chí một hash table khác) và không nhất thiết phải là các số nguyên liên tiếp. Chính vì điều này nên hash table cần sử dụng một hàm mã hoá hash function để mã hoá giá trị các khoá của từng phần tử.

Ví dụ để lưu trữ danh bạn điện thoại của các cư dân trong thành phố chúng ta có thể sử dụng một hash table được minh hoạ bởi hình dưới đây:

Hash table ở trên sử dụng tên của môi cư dân là giá trị đặt cho khoá. Mỗi khoá sẽ được kết nối tới một phần tử mà ở đó lưu trữ số điện thoại của người đó. Tuy nhiên như bạn đã biết máy tính lưu trữ giá trị trên các địa chỉ bộ nhớ và do đó bạn cần chuyển đổi giá tri khoá này về một giá trị mà máy tính có thể xử lý được.

Việc này được thông qua sử dụng hash function. Hash function đơn giản là một hàm mã hoá với mục đích mã hoá một giá trị về giá trị với kiểu dữ liệu cho trước (thường là đơn giản hơn kiểu dữ liệu trước đó). Thường thì sẽ là 1 địa chỉ của phần tử trong mảng hoặc địa chỉ bộ nhớ của máy tính.

Trở lại ví dụ về mảng gồm 6 phần tử mà chúng ta đã tìm hiểu ở phần trước. Bây giờ hãy thử phân tích điều gì xảy ra nếu chúng ta yêu cầu máy tính tìm kiếm phần tử thứ 3 trong mảng. Bạn nhớ lại rằng giá trị của các phần tử trong mảng (hay bất cứ kiểu dữ liệu nào khác trong chương trình) thông thường sẽ được máy tính lưu trữ trên bộ nhớ. Để tìm ra phần tử thứ 3 trong mảng máy tính cần tính toán đúng địa chỉ bộ nhớ lưu trữ phần tử này. Để làm điều này máy tính bắt đầu bằng cách tìm ra địa chỉ bộ nhớ để lưu trữ giá trị phần tử đầu tiên. Tiếp theo nó sẽ chuyển sang địa chỉ nằm kế tiếp địa chỉ vừa tìm thấy trên bộ nhớ. Đây sẽ là phần tử thứ 2 vẫn chưa phải là giá trị cần tìm kiếm. Máy tính lúc này sẽ tiếp tục di chuyển tới địa chỉ tiếp theo và do đây là giá trị cần tìm nó sẽ trả về kết quả.

Bây giờ nếu chúng ta tìm kiếm cho số điện thoại của John Smith sử dụng hash table thì lúc này máy tính đầu tiên sẽ sử dụng hàm hash function để mã hoá giá trị John Smith (giá trị này thường là chỉ số của mảng hay là địa chỉ của ô nhớ lưu trữ giá trị) sau đó giá trị trả về sẽ được sử dụng để tìm kiếm ra giá trị của địa chỉ bộ nhớ được dùng để lưu trữ số điện thoại của người này. Việc tìm kiếm kết thúc tại đây.

Như vậy bạn có thể thấy rằng sử dụng hash table việc tìm kiếm trở lên đơn giản hơn rất nhiều so với array. Trên thực tế nếu bạn đã từng tìm hiểu về cấu trúc dữ liệu và giải thuật thì bạn biết rằng mức độ phức tạp của việc tìm kiếm trong array là O(n) hoặc là O(nlogn) với mảng đã được sắp xếp. Ngược lại với hash table thì sẽ là O(1).

Tương tự với tìm kiếm phần tử, việc cập nhật giá trị phần tử và xoá phần tử trên hash table diễn ra nhanh hơn so với array.