Tạo một bản đồ băm bằng một khóa kép

Question

Tôi đang tìm một cấu trúc dữ liệu thích hợp cho vấn đề của mình. Tôi muốn có thể chọn các đối tượng nút hiệu quả nhất có thể bằng hai phím. Chèn và xóa cũng cần phải hiệu quả. Về cơ bản, mỗi đối tượng nút có một cặp hai khóa. Các cặp là duy nhất nhưng các khóa riêng lẻ thì không. Tôi cần để có thể chọn một nhóm các nút có giá trị cụ thể cho một trong hai khóa.

Ví dụ:

node1 có các phím a1 và b1

node2 có các phím a1 và b2

Node3 có các phím a2 và b2

Tôi muốn ví dụ có thể để chọn nút có khóa a1, b1 nhưng cũng tất cả các nút có b2 là key2.

Tất nhiên tôi có thể tạo hai HashMaps (một cho mỗi khóa) nhưng đây là một giải pháp tồi tệ vì khi tôi thêm hoặc xóa thứ gì đó tôi sẽ phải làm trong cả hai bản đồ. Vì sẽ có rất nhiều việc thêm và xóa đi, tôi muốn làm điều này trong một lần nữa. Có ai có bất kỳ ý tưởng về làm thế nào để làm điều này? Rõ ràng là có một khóa duy nhất kết hợp hai khóa lại với nhau không giải quyết được vấn đề vì tôi cũng cần có khả năng tìm kiếm một khóa duy nhất mà không phải tìm kiếm thông qua toàn bộ bản đồ. Điều đó sẽ không hiệu quả lắm. Vấn đề là một vấn đề hiệu quả. Tôi chỉ có thể tìm kiếm mọi mục nhập trong bản đồ cho một khóa cụ thể nhưng thay vào đó tôi muốn sử dụng một hàm băm để tôi có thể chọn nhiều đối tượng nút bằng cách sử dụng một trong hai khóa ngay lập tức.

Tôi không tìm kiếm thứ gì giống như MultiKeyMap vì trong cấu trúc dữ liệu này, khóa đầu tiên luôn giữ nguyên, bạn chỉ có thể thêm khóa thay vì thay thế khóa đầu tiên bằng một khóa khác. Tôi muốn có thể chuyển đổi giữa khóa đầu tiên và khóa thứ hai.

Tôi thực hiện và không muốn lưu trữ nhiều đối tượng bằng cùng một khóa. Nếu bạn nhìn vào ví dụ bạn có thể thấy rằng hai khóa với nhau luôn là duy nhất. Điều này có thể được xem như là một khóa duy nhất do đó tôi sẽ không lưu trữ nhiều đối tượng dưới cùng một khóa. Nhưng nếu bạn nhìn vào các khóa riêng lẻ, chúng không phải là duy nhất do đó tôi muốn lưu trữ nhiều đối tượng được tham chiếu bởi các khóa riêng lẻ.

Answer 1

Nếu bạn có thể sử dụng thư viện, hãy nhìn vào giao diện Table của ổi. Nó liên kết một hàng và một cột với một giá trị. Hàng và cột có thể là khóa đầu tiên và thứ hai của bạn. Ngoài ra, bạn có thể tìm kiếm theo hàng hoặc theo cột.

Một trong những triển khai của giao diện này là hash based.

Answer 2

Viết một lớp đơn giản có thể chứa hai giá trị (khóa) và ghi đè bằng (..) và hashCode() để kiểm tra bình đẳng được sử dụng bởi bản đồ. Sử dụng lớp đơn giản này làm khóa cho bản đồ.

Ở đây bạn có thể tìm thấy một hashmap tương thích lớp cặp (câu trả lời thứ 2):

What is the equivalent of the C++ Pair<L,R> in Java?

Answer 3

Vì điều này khá cụ thể đối với vấn đề của bạn, bạn rất có thể sẽ cần phát triển bộ sưu tập của riêng mình. Tôi sẽ kết hợp hai số MultiMaps từ Apache Commons vào lớp bộ sưu tập của riêng tôi để cập nhật cả hai bản đồ cùng một lúc và sử dụng lớp của tôi để thực hiện chèn và truy vấn.

Answer 4

Vì HashMap chỉ có thể sắp xếp trên một giá trị băm cho mỗi đối tượng, bạn sẽ không bao giờ có thể chọn các danh sách riêng biệt 'ra khỏi hộp'. Những gì tôi sẽ đề nghị là sử dụng một Tuple với hai phím, và sau đó lặp qua HashMap và chọn chỉ những yếu tố có tuple.key1 = X.

Answer 5

HashMaps có thể có bất kỳ đối tượng nào làm Khóa, vậy tại sao không tạo một lớp với 2 trường và xem lớp này là khóa của bạn. bạn cũng có thể Override phương thức Equals nói với nó như thế nào các phím là bằng

Answer 6

Bạn cần phải tạo ra một lớp chủ chốt (bình đẳng được coi là Point):

public class Key { 

    int field1; 
    int field2; 

    public boolean equals(Object o) { 
     if (o == null || !(o instanceof Key)) return false; 
     Key other = (Key) o; 
     return field1 == other.field1 && field2 == other.field2; 
    } 

    public int hashCode() { 
     return field1*field2; // doesn't matter if some keys have same hash code 
    } 

} 

Đối với việc lựa chọn các phím với một giá trị cụ thể trong trường đầu tiên:

public List<Key> getKeysWithField1EqualsTo(int value) { 
    List<Key> result = new ArrayList<>(); 
    for (Key k: map.keySet()) { 
     if (k.field1 == value) result.add(k); 
    } 
    return result; 
} 

Answer 7

Tôi nghĩ chúng tôi có thể thực hiện theo cách này: Đối với mỗi khóa, chúng tôi có thể tính toán mã băm tương ứng.

key1 -> hashcode1 
key2 -> hashcode2 

Sau đó, chúng tôi có mảng 2-d, với N cột và N hàng.

key1 -> rowIndex: hashcode1 MOD N 
key2 -> columnIndex: hashcode2 MOD N 

Sau đó, chúng tôi lưu trữ hàng trong array[rowIndex][columnIndex].

Trong triển khai này, bạn có thể nhận tất cả các mục nhập bằng khóa đích1 và bất kỳ khóa 2 nào. Bạn cũng có thể nhận tất cả các mục nhập bằng khóa đích2 và bất kỳ khóa nào1.

Mảng này có thể mở rộng khi có nhiều xung đột, giống như những gì bạn làm với băm băm thông thường.