HashTable hay bảng băm (CTDL)

Diễn đàn Cấu trúc dữ liệu và giải thuật HashTable hay bảng băm (CTDL)

Thành viên	Nội dung
coder lap trinh khong bien gioi 142 bài	03-03-2010 11:44:53 Là một loại cấu trúc dữ liệu (CTDL) mà thay vì truy cập các phần tử bằng chỉ số, chúng ta truy cập nó bằng các key với tốc độ truy cập phần tử là rất nhanh. Đối với bảng băm, mỗi khóa sẽ được trỏ đến một ô trống (slot) trong bộ nhớ để lưu trữ dữ liệu. Có 1 ví dụ như sau : Bạn lưu trữ một danh sách các ông bạn trong yahoo friend list có tên : nam, tung, hung, long, tuan, anh, truong, viet, thuy, nguyen ... giờ muốn truy cập vào phần tử hung để xem ông bạn này nói gì ? nếu duyệt như arraylist (danh sách tìm kiếm theo chỉ số) thì thời gian là rất lâu. Bạn sẽ phải duyệt cả n phần tử (n bạn) trong danh sách của mình. Bảng băm sẽ giúp bạn tìm nhanh bằng lệnh : hash ["hung"] là ra phần tử hung, với tất cả các cuộc nói chuyện giữa bạn và hung. Không phải máy tính lúc nào cũng truy cập bằng chỉ số. Lẽ dĩ nhiên máy tính sẽ "băm" (hash) giúp bạn từ tên (name) thành chỉ số của mảng từ đó máy tính chỉ ra cho bạn phần tử cần lấy. Tớ nghe loáng thoáng một ông anh chuyên nghiên cứu cấu trúc dữ liệu và giải thuật nói rằng, thuật toán băm đơn giản nhất là cứ (bé + lớn) /2 cuối cùng sẽ ra 1 con số mà chẳng cái key (name) nào giống cái nào cách nghĩ này cũng hay. --- http://coder.awas.vn http://mobile.awas.vn http://vtv.awas.vn http://baihatviet.awas.vn
meoconbinbin 1 bài	13-07-2010 09:41:09 bạn ơi! hè này mình đang phải làm bài tập về phần hàm băm đó nhưng mà khó quá! bài toán của mình là từ thông tin lưu trong 1 trang web mình phải tìm cách lưu trữ nó bằng b tree để việc tìm kiếm được dễ dàng hơn. theo mình nghĩ chắc là phải thiết kế được hàm băm để băm file đó ra thành từng b tree. nhưng quả thật không dễ. mình mong nhận được sự giúp đỡ của bạn và mấy anh chị trên diễn đàn. Em xin chân thành cám ơn

Chủ đề gần đây :

Cùng loại :