Bảng băm so với cây nhị phân cân bằng

Question

Tôi nên tính đến các yếu tố nào khi cần chọn giữa bảng băm hoặc cây nhị phân cân bằng để thực hiện một bộ hoặc một mảng kết hợp?

Answer 1

Câu hỏi này không thể trả lời được, nói chung, tôi lo sợ.

Vấn đề là có nhiều loại bảng băm và cây nhị phân cân bằng, và hiệu suất của chúng thay đổi rất nhiều.

Vì vậy, câu trả lời ngây thơ là: nó phụ thuộc vào chức năng bạn cần.Sử dụng một bảng băm nếu bạn không cần đặt hàng và một cây nhị phân cân bằng khác.

Để có câu trả lời phức tạp hơn, hãy cân nhắc một số giải pháp thay thế.

Hash Table (xem mục Wikipedia đối với một số vấn đề cơ bản)

• Không phải tất cả các bảng băm sử dụng một danh sách liên kết như một cái xô. Cách thay thế phổ biến là sử dụng nhóm "tốt hơn", ví dụ: cây nhị phân hoặc bảng băm khác (với hàm băm khác), ...
• Một số bảng băm không sử dụng nhóm nào cả: xem Mở địa chỉ (chúng đi kèm với các vấn đề khác, rõ ràng)
• Có một cái gì đó gọi là Tái băm tuyến tính (đó là chất lượng chi tiết thực hiện), giúp ngăn chặn sự cố "dừng lại-thế giới-và-rehash". Về cơ bản trong giai đoạn di chuyển bạn chỉ chèn vào bảng "mới", và cũng di chuyển một mục "cũ" vào bảng "mới". Tất nhiên, giai đoạn di cư có nghĩa là đôi nhìn lên vv ...

Binary Tree

• Tái cân bằng là tốn kém, bạn có thể xem xét một Skip-List (còn tốt hơn cho các truy cập đa luồng) hoặc cây Splay.
• Trình phân bổ tốt có thể "đóng gói" các nút cùng nhau trong bộ nhớ (hành vi lưu vào bộ nhớ cache tốt hơn), mặc dù điều này không làm giảm bớt vấn đề tìm kiếm con trỏ.
• B-Tree và các biến thể cũng cung cấp "đóng gói"

Đừng quên rằng O (1) là một phức tạp tiệm cận. Đối với một số yếu tố, hệ số thường quan trọng hơn (hiệu suất khôn ngoan). Điều này đặc biệt đúng nếu hàm băm của bạn chậm ...

Cuối cùng, đối với các bộ, bạn cũng có thể xem xét các cấu trúc dữ liệu xác suất, như Bloom Filters.

Answer 2

Bảng băm thường tốt hơn nếu không cần lưu giữ dữ liệu theo bất kỳ loại chuỗi nào. Cây nhị phân sẽ tốt hơn nếu dữ liệu phải được sắp xếp.

Answer 3

bảng Hash là tra cứu nhanh hơn:

• Bạn cần một chìa khóa mà tạo ra một phân bố (nếu không bạn sẽ bỏ lỡ rất nhiều và phải dựa vào một cái gì đó khác hơn là băm; giống như một tìm kiếm tuyến tính).
• Hash's có thể sử dụng nhiều không gian trống. Bạn có thể dự trữ 256 mục nhưng chỉ cần 8 (cho đến nay).

cây nhị phân:

• xác định. O (log n) Tôi nghĩ ...
• Không cần thêm không gian như bảng băm có thể
• Phải được sắp xếp. Thêm một phần tử ở giữa có nghĩa là di chuyển phần còn lại xung quanh.

Answer 4

Nếu bạn chỉ cần truy cập vào các phần tử đơn lẻ, thì thẻ bắt đầu bằng # thì tốt hơn. Nếu bạn cần một loạt các phần tử, bạn chỉ đơn giản là không có tùy chọn nào khác ngoài cây nhị phân.

Answer 5

Điểm đáng giá trên kiến ​​trúc hiện đại: Một bảng băm thường sẽ, nếu hệ số tải thấp, có ít bộ nhớ hơn so với cây nhị phân. Vì truy cập bộ nhớ có xu hướng khá tốn kém so với các chu kỳ CPU đang cháy, bảng băm thường nhanh hơn.

Trong cây nhị phân sau đây được giả định là tự cân bằng, như một cây đen đỏ, cây AVL hoặc giống như một quả bóng.

Mặt khác, nếu bạn cần phải rehash mọi thứ trong bảng băm khi bạn quyết định mở rộng nó, đây có thể là một hoạt động tốn kém xảy ra (khấu hao). Cây nhị phân không có giới hạn này.

Cây nhị phân dễ thực hiện hơn bằng các ngôn ngữ thuần túy.

Cây nhị phân có thứ tự sắp xếp tự nhiên và cách tự nhiên để đi bộ cây cho tất cả các yếu tố.

Khi hệ số tải trong bảng băm thấp, bạn có thể lãng phí nhiều không gian bộ nhớ, nhưng với hai con trỏ, cây nhị phân có xu hướng chiếm nhiều không gian hơn.

Bảng băm gần bằng O (1) (tùy thuộc vào cách bạn xử lý hệ số tải) so với cây Bin O (lg n).

Cây có xu hướng là "biểu diễn trung bình". Không có gì họ làm đặc biệt tốt, nhưng sau đó không có gì họ làm đặc biệt xấu.

Answer 6

Để thêm vào các câu trả lời tuyệt vời khác ở trên, tôi muốn nói:

Sử dụng một bảng băm nếu số lượng dữ liệu sẽ không thay đổi (ví dụ lưu trữ hằng); nhưng, nếu lượng dữ liệu sẽ thay đổi, hãy sử dụng một cây. Điều này là do thực tế rằng, trong một bảng băm, một khi các yếu tố tải đã đạt được, bảng băm phải thay đổi kích cỡ. Hoạt động thay đổi kích thước có thể rất chậm.

Answer 7

Cây tìm kiếm nhị phân yêu cầu tổng quan hệ thứ tự giữa các phím. Bảng băm chỉ yêu cầu mối quan hệ tương đương hoặc nhận dạng với hàm băm nhất quán.

Nếu mối quan hệ đặt hàng có sẵn, thì mảng được sắp xếp có hiệu suất tra cứu so sánh với cây nhị phân, hiệu suất chèn trường hợp xấu nhất theo thứ tự bảng băm và độ phức tạp và sử dụng bộ nhớ ít hơn cả hai.

Sự phức tạp chèn trường hợp xấu nhất cho bảng băm có thể được để ở O (1)/O (log K) (với K số phần tử có cùng giá trị băm) nếu được chấp nhận để tăng tra cứu trường hợp xấu nhất phức tạp đến O (K) hoặc O (log K) nếu các yếu tố có thể được sắp xếp.

Các bất biến cho cả cây và bảng băm là tốn kém để khôi phục nếu các phím thay đổi, nhưng nhỏ hơn O (n log N) cho các mảng được sắp xếp.

Đây là những yếu tố để đưa vào tài khoản trong việc quyết định thực hiện để sử dụng:

1. sẵn có của một mối quan hệ để tổng.
2. Tính khả dụng của hàm băm tốt cho mối quan hệ tương đương.
3. Kiến thức linh mục về số lượng phần tử.
4. Hiểu biết về tỷ lệ chèn, xóa và tra cứu.
5. Độ phức tạp tương đối của hàm so sánh và băm.

Answer 8

Nếu bạn sẽ có nhiều tập hợp hơi khác nhau, có thể bạn sẽ muốn chúng chia sẻ cấu trúc. Điều này rất dễ dàng với cây (nếu chúng không thay đổi hoặc copy-on-write). Tôi không chắc bạn có thể làm tốt như thế nào với hashtables; ít nhất là ít rõ ràng hơn.

Answer 9

Theo kinh nghiệm của tôi, các hastables luôn nhanh hơn vì cây bị quá nhiều hiệu ứng bộ nhớ cache.

Để xem một số dữ liệu thực tế, bạn có thể kiểm tra trang điểm chuẩn của thư viện TommyDS tôi http://tommyds.sourceforge.net/

đây bạn có thể thấy so với việc thực hiện các Hashtable phổ biến nhất, cây và Trie thư viện có sẵn.

Answer 10

Một điểm mà tôi không nghĩ là đã được giải quyết là cây tốt hơn cho các cấu trúc dữ liệu liên tục. Đó là, cấu trúc bất biến. Bảng băm tiêu chuẩn (nghĩa là bảng băm sử dụng một danh sách liên kết duy nhất) không thể sửa đổi mà không sửa đổi toàn bộ bảng. Một tình huống trong đó điều này có liên quan là nếu hai hàm đồng thời đều có bản sao của bảng băm và một trong số chúng thay đổi bảng (nếu bảng có thể thay đổi được, thay đổi đó cũng sẽ hiển thị với bảng khác). tình huống khác sẽ là một cái gì đó như sau:

def bar(table): 
    # some intern stuck this line of code in 
    table["hello"] = "world" 
    return table["the answer"] 

def foo(x, y, table): 
    z = bar(table) 
    if "hello" in table: 
     raise Exception("failed catastrophically!") 
    return x + y + z 

important_result = foo(1, 2, { 
    "the answer": 5, 
    "this table": "doesn't contain hello", 
    "so it should": "be ok" 
}) 
# catastrophic failure occurs 

Với một bảng có thể thay đổi, chúng tôi không thể đảm bảo rằng bảng một cuộc gọi chức năng nhận sẽ vẫn là bảng suốt thực hiện của nó, bởi vì các cuộc gọi chức năng khác có thể sửa đổi nó.

Vì vậy, tính đột biến đôi khi không phải là điều dễ chịu. Bây giờ, một cách xung quanh điều này sẽ là giữ cho bàn không thay đổi và có bản cập nhật trả về bảng mới mà không sửa đổi bảng cũ. Nhưng với một bảng băm này thường sẽ là một hoạt động tốn kém O (n), vì toàn bộ mảng cơ bản sẽ cần được sao chép. Mặt khác, với một cây cân bằng, cây mới có thể được tạo ra chỉ với các nút O (log n) cần được tạo (phần còn lại của cây giống hệt nhau).

Điều này có nghĩa là một cây hiệu quả có thể rất thuận tiện khi bản đồ bất biến được mong muốn.

Answer 11

Một điểm cần lưu ý là về mục ngang, tối thiểu và tối đa. Bảng băm không hỗ trợ bất kỳ loại truyền tải có thứ tự nào hoặc truy cập vào các mục tối thiểu hoặc tối đa. Nếu những khả năng này là quan trọng, cây nhị phân là một lựa chọn tốt hơn.