TAILIEUCHUNG - Cấu trúc dữ liệu : BẢNG BĂM (HASH TABLE) part 1

Bài 3: BẢNG BĂM (HASH TABLE) Phép băm được đề xuất và hiện thực trên máy tính từ những năm 50 của thế kỷ 20. Nó dựa trên ý tưởng: biến đổi giá trị khóa thành một số (xử lý băm) và sử dụng số này để đánh chỉ cho bảng dữ liệu. Các phép toán trên các cấu trúc dữ liệu như danh sách, cây nhị phân, phần lớn được thực hiện bằng cách so sánh các phần tử của cấu trúc, do vậy thời gian truy xuất không nhanh và phụ thuộc vào kích thước của cấu trúc. Trong. | Bài 3 BẢNG BĂM HASH TABLE Phép băm được đề xuất và hiện thực trên máy tính từ những năm 50 của thế kỷ 20. Nó dựa trên ý tưởng biến đổi giá trị khóa thành một số xử lý băm và sử dụng số này để đánh chỉ cho bảng dữ liệu. Các phép toán trên các cấu trúc dữ liệu như danh sách cây nhị phân . phần lớn được thực hiện bằng cách so sánh các phần tử của cấu trúc do vậy thời gian truy xuất không nhanh và phụ thuộc vào kích thước của cấu trúc. Trong bài này chúng ta sẽ khảo sát một cấu trúc dữ liệu mới được gọi là bảng băm hash table . Các phép toán trên bảng băm sẽ giúp hạn chế số lần so sánh và vì vậy sẽ cố gắng giảm thiểu được thời gian truy xuất. Độ phức tạp của các phép toán trên bảng băm thường có bậc là 0 1 và không phụ thuộc vào kích thước của bảng băm. Các khái niệm chính trên cấu trúc bảng băm Phép băm hay hàm băm hash function Tập khoá của các phần tử trên bảng băm Tập địa chỉ trên bảng băm Phép toán thêm phần tử vào bảng băm Phép toán xoá một phần tử trên bảng băm Phép toán tìm kiếm trên bảng băm Thông thường bảng băm được sử dụng khi cần xử lý các bài toán có dữ liệu lớn và được lưu trữ ở bộ nhớ ngoài. 1 1. PHÉP BĂM Hash Function Định nghĩa Trong hầu hết các ứng dụng khoá được dùng như một phương thức để truy xuất dữ liệu. Hàm băm được dùng để ánh xạ giá trị khóa khoá vào một dãy các địa chỉ của bảng băm hình 1 . K -------h I---------------- h K Hình 1 Khóa có thể là dạng số hay số dạng chuỗi. Giả sử có 2 khóa phân biệt ki và kj nếu h ki h kj thì hàm băm bị đụng độ. Một hàm băm tốt phải thỏa mãn các điều kiện sau Tính toán nhanh. Các khoá được phân bố đều trong bảng. Ít xảy ra đụng độ. Xử lý được các loại khóa có kiểu dữ liệu khác nhau Hàm Băm sử dụng Phương pháp chia Dùng số dư h k k mod m k là khoá m là kích thước của bảng. Như vậy h k sẽ nhận 0 1 2 . m-1. Việc chọn m sẽ ảnh hưởng đến h k . Nếu chọn m 2p thì giá trị của h k sẽ là p bit cuối cùng của k trong biểu diễn nhị phân. Nếu chọn m 10p thì giá trị của h k sẽ là p chữ số cuối cùng trong biểu diễn thập phân

• Cơ sở dữ liệu
• Cấu trúc dữ liệu
• tài liệu Cấu trúc dữ liệu
• đề cương Cấu trúc dữ liệu
• giáo trình Cấu trúc dữ liệu
• bài giảng Cấu trúc dữ liệu
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình cấu trúc dữ liệu và giải thuât
• bài tập cấu trúc dữ liệu và giải thuât
• Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu cây AVL
• Cấu trúc dữ liệu cây
• Thuật toán DSW
• Cây nhị phân tìm kiếm
• Cấu trúc dữ liệu cây đỏ đen
• Cấu trúc dữ liệu cho nút cây đỏ đen
• Phép biến đổi cây đỏ đen cân bằng
• bài tập cấu trúc dữ liệu
• lập trình dữ liệu
• Vị trí cấu trúc dữ liệu
• Áp dụng tin học
• Cơ sở dữ liệu
• Quan hệ giải thuật
• Cấu trúc dữ liệu cơ bản
• Đánh giá cấu trúc dữ liệu
• Định nghĩa kiểu dữ liệu
• Kiểu dữ liệu có cấu trúc
• Đánh giá thuật toán
• Thiết kế cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Kiểu dữ liệu trừu tượng
• Kiểu dữ liệu cây
• Phân loại cây
• Cấu trúc dữ liệu giải thuật
• Bài giảng Cấu trúc dữ liệu giải thuật
• Ngôn ngữ lập trình
• Cấu trúc chương trình
• Cấu trúc điều khiển
• Cấu trúc dữ liệu căn bản
• Khái niệm cấu trúc dữ liệu
• Độ phức tạp thuật toán
• tiếp cận lập trình
• thuật toán
• thuật toán trong cấu trúc dữ liệu
• cấu trúc dữ liệu động
• kỹ thuật sắp xếp