Bảng băm v/s Cây

Các thẻ bắt đầu bằng # có luôn nhanh hơn cây không? Mặc dù Hashtables có O (1) phức tạp tìm kiếm nhưng giả sử nếu do hàm băm được thiết kế xấu xảy ra và nếu chúng ta xử lý các va chạm bằng cách sử dụng cấu trúc chuỗi (nói một cây cân bằng) thì thời gian chạy xấu nhất cho tìm kiếm sẽ là O (log n). Vì vậy, tôi có thể kết luận cho các tập dữ liệu lớn hay nhỏ ngay cả trong trường hợp kịch bản trường hợp xấu nhất bảng băm sẽ luôn luôn nhanh hơn cây? Ngoài ra Nếu tôi có bộ nhớ phong phú và tôi không muốn phạm vi tìm kiếm tôi có thể luôn luôn đi cho một bảng băm?Bảng băm v/s Cây

Nguồn

2012-04-05 avinash shah

Tôi không có chuyên gia, nhưng tôi muốn nói đó là tình huống. Rất nhiều hàm băm rất đắt, và đối với một số kiểu truy cập nhất định, cây là tốt. –

"Luôn luôn" là một từ bao gồm tất cả. Bất kỳ cơ hội nào bạn có thể chỉnh sửa câu hỏi này để giảm câu hỏi thành một cái gì đó cụ thể hơn một chút, giống như các tình huống cụ thể (chỉ)? Nếu không, nó gần như chắc chắn sẽ bị đóng cửa không mang tính xây dựng. –

Rất nhiều người ở đây đã đề cập rằng trường hợp xấu nhất sẽ là O (N). Làm thế nào nó có thể là O (n) nếu các va chạm được xử lý bằng cách sử dụng một cấu trúc cây cân bằng thay vì một danh sách liên kết. Trường hợp xấu nhất để tìm kiếm trên một cây cân bằng như AVL sẽ là O (log n) –

Thẻ bắt đầu bằng # có luôn nhanh hơn cây không?

Không, không luôn là. Điều này phụ thuộc vào nhiều thứ, chẳng hạn như kích thước của bộ sưu tập, hàm băm, và đối với một số triển khai bảng băm - cũng là số lượng các lệnh xóa.

bảng băm là O(1) trên mỗi op trên mức trung bình - nhưng điều này không phải luôn luôn như vậy. Chúng có thể là O(n) trong trường hợp xấu nhất.

Một số lý do tôi có thể nghĩ ra lúc này để thích cây:

Thứ tự là rất quan trọng. [bảng băm không duy trì trật tự, BST được sắp xếp theo định nghĩa]
Latency là một vấn đề - và bạn không thể gặp phải O(n) có thể xảy ra. [Điều này có thể rất quan trọng đối với các hệ thống thời gian thực]
Dữ liệu có thể "tương tự" có liên quan đến hàm băm của bạn và nhiều phần tử được băm vào cùng một vị trí [va chạm] không thể giải quyết được. [điều này đôi khi có thể được giải quyết bằng cách sử dụng hàm băm khác nhau]
Đối với các bộ sưu tập tương đối nhỏ - nhiều lần hằng số ẩn giữa số O(1) của hashtable cao hơn nhiều so với cây - và sử dụng cây có thể nhanh hơn cho các bộ sưu tập nhỏ.

Tuy nhiên - nếu dữ liệu lớn, độ trễ không phải là vấn đề và các xung đột không thể thực hiện được - bảng băm là tiệm cận tốt hơn sau đó sử dụng cây.

Nguồn

2012-04-05 17:56:30 amit

Thường thì trường hợp cây được đóng gói cẩn thận có thể thực hiện một bảng băm do sự kết hợp bộ nhớ cache (có thể là từ bộ nhớ chính hoặc đĩa). Không quan trọng bạn có bao nhiêu dữ liệu trong trường hợp này - bảng băm có thể không phải là lựa chọn tốt nhất của bạn tùy thuộc vào cách bạn đang sử dụng cấu trúc từ điển. – Kaganar

Bảng băm nào? Mở địa chỉ bảng băm hoặc bảng băm "Xô"? Có hoặc không có thay đổi kích thước gia tăng? Hoặc tuyến tính băm dựa? Có * rất nhiều * triển khai các bảng băm xung quanh! Câu trả lời của bạn là sai đối với một số người trong số họ, vì vậy xin vui lòng, được chính xác. –

@MatthieuM: Đây là những hạn chế truyền thống cho khá nhiều bảng băm, ngay cả khi sử dụng địa chỉ mở hoặc chuỗi với một mảng đơn giản là "xô". Đặt hàng là hạn chế vì băm không đảm bảo trật tự sẽ được giữ nguyên. Độ trễ là một vấn đề do trường hợp xấu nhất (nếu bạn không thể chịu bất kỳ lệnh 'O (n)' nào do một số ràng buộc - đó là một vấn đề), giá trị băm tương tự không thực sự rút lại vì nó có thể dễ dàng được giải quyết bằng cách chọn Hàm băm khác nhau và vấn đề về kích thước thường là do hàm băm trên đầu nếu tôi nhớ chính xác. Những gì cụ thể bạn có vấn đề với? – amit

Sử dụng thẻ bắt đầu bằng # và bắt đầu bằng thứ nguyên phù hợp. Ví dụ, nếu bạn chỉ sử dụng một nửa không gian thì các va chạm rất ít.

Nguồn

2012-04-05 17:55:28 dash1e

Trong trường hợp xấu nhất, bạn sẽ có O (n) thời gian trong bảng nhanh. Nhưng đây là một tỷ ít có thể xảy ra sau đó mặt trời nổ viết bây giờ, vì vậy khi sử dụng một hàm băm tốt, bạn có thể an toàn giả sử nó hoạt động trong O (1) trừ khi mặt trời phát nổ. Mặt khác, hiệu suất của cả Hash-Tables và Trees có thể khác nhau trên thực thi, ngôn ngữ và giai đoạn của mặt trăng, do đó, câu trả lời duy nhất cho câu hỏi này là "Hãy thử cả hai, nghĩ và chọn tốt hơn".

Nguồn

2012-04-05 17:55:39 kilotaras

Nếu do hàm băm được thiết kế xấu xảy ra va chạm và nếu chúng ta xử lý các va chạm bằng cấu trúc xích (nói một cây cân bằng) thì trường hợp xấu nhất chạy để tìm kiếm sẽ là O (n) (not O (log) n)). Do đó bạn không thể kết luận cho các tập dữ liệu lớn hay nhỏ ngay cả trong trường hợp các kịch bản trường hợp xấu nhất, các bảng băm sẽ luôn nhanh hơn các cây.

Nguồn

2012-04-05 17:56:38

Trả lời

Các vấn đề liên quan