Thắc mắc về bảng băm hash?

Xemsix · February 4, 2019, 8:04am

em vừa học đến chổ này có thắc mắc

trong sách có viết dùng bảng băm hash giúp giảm độ phức tạp của việc tìm kiếm giá trị đi so với cách dùng mảng
em có xem bài viết này
https://www.codehub.vn/Khac-Biet-Giua-Array-va-Hash-Table

có đoạn nó giải thích nếu cùng tìm kiếm 1 phần tử :

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 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) . Ngược lại với hash table thì sẽ là O(1) .

ở đây em muốn hỏi :

vì sao đối với 1 mảng để lấy được giá trị tại phần tử n thì phải duyệt qua hết từ phần tử 0 đến phần tử n-1 ? vì em học thì các phần tử của 1 mảng đặt trên vùng nhớ liên tiếp nhau nên nếu biết được địa chỉ phần tử đầu tiên thì cứ thế mà cộng lên thôi cần gì phải duyệt qua từng phần tử ?
chỗ đoạn tìm số điện thoại của John Smith thì em thấy hàm băm cũng trả về 1 hash code và hash code đó tương ứng với 1 index , và lúc này sẽ trở về lại việc tìm 1 phần tử thông qua index ? ( thì cũng phải duyệt từ phần tử đầu tiên đến phần tử cần tìm đúng không ?) vậy thì nhanh hơn ở chổ nào ?

rogp10 · February 4, 2019, 8:59am

Đúng vậy Thớt bển giống như đầu nghĩ 1 kiểu mà tay gõ một kiểu khác rồi không đọc lại vậy.

Như trên

Thực ra O(1) của hash table cũng chỉ là lấy index như mảng thôi còn tính ra hash code là O(len(key)). Vậy độ phức tạp của hash table là O(len(key))

Xemsix · February 4, 2019, 8:59am

vâng cảm ơn anh em hiểu rồi , tại cái thớt đó viết chỗ truy xuất qua index mà lên tới O(n) nên em không hiểu thôi , chứ nếu đưa về hash table thì độ phức tạp sẽ nhỏ hơn O(n)

rogp10 · February 5, 2019, 2:59am

Hai cấu trúc này phải đặt chung một bài toán thì mới so được. VD như truy cập theo tên.

Nếu chỉ là mảng thường mà tìm tên trong đó thì O(n) thật đấy. Mảng sắp xếp trước thì O(logn).
Còn hash table thì phải tính hết cái key (tên), sau đó vào đúng slot. Có thể bị trùng hash nữa nên vẫn không phải là O(1) chỗ này. O(1) chỉ là tính địa chỉ thôi. Đó là chưa tính chuyện phải rehash O(n) tính tổng cộng là O(k).

Mảng thường: thêm O(1) (sau), tìm/sửa O(n), xóa O(1)
Mảng sắp xếp: thêm/sửa O(n), tìm O(logn), xóa O(n)
Hash: Khá phức tạp. Sẽ cần một bài viết riêng.

Tóm lại hash không phải là O(1) mà phụ thuộc vào độ dài của khóa.

Phong_Ky_Vo · February 5, 2019, 1:38am

Hi Xemsix.
Cái gì cũng có hai mặt tốt và sấu. Với bảng băm bạn mất chi phí cho việc tính giá trị băm nên thường dùng khi bạn có một mảng mà chủ yếu là tìm kiếm như bảng các mặt hàng trong siêu thị. Còn với các mảng thay đổi liên tục như danh sách xe gửi trong bến thì không nên.