Java: Phím tổng hợp trong hashmaps

Question

Tôi muốn lưu trữ một nhóm đối tượng trong một băm, trong đó khóa sẽ là một tổng hợp của hai giá trị chuỗi. Có cách nào để đạt được điều này?

tôi có thể chỉ cần nối hai chuỗi, nhưng chắc chắn có cách tốt hơn để thực hiện việc này.

Answer 1

Bạn có thể có một đối tượng tùy chỉnh chứa hai chuỗi:

class StringKey { 
    private String str1; 
    private String str2; 
} 

Vấn đề là, bạn cần phải xác định kiểm tra bình đẳng và mã băm cho hai đối tượng như vậy.

bình đẳng có thể là trận đấu trên cả hai dây và hashcode có thể là hashcode của các thành viên nối (điều này là gây tranh cãi):

class StringKey { 
    private String str1; 
    private String str2; 

    @Override 
    public boolean equals(Object obj) { 
     if(obj != null && obj instanceof StringKey) { 
      StringKey s = (StringKey)obj; 
      return str1.equals(s.str1) && str2.equals(s.str2); 
     } 
     return false; 
    } 

    @Override 
    public int hashCode() { 
     return (str1 + str2).hashCode(); 
    } 
} 

Answer 2

Tại sao không tạo đối tượng (nói) Pair, trong đó có hai chuỗi là thành viên, sau đó sử dụng làm khóa?

ví dụ:

public class Pair { 
    private final String str1; 
    private final String str2; 

    // this object should be immutable to reliably perform subsequent lookups 
} 

Đừng quên về equals() và hashCode(). Xem this blog entry để biết thêm về HashMaps và các khóa, bao gồm một nền tảng về các yêu cầu bất biến. Nếu khóa của bạn không thay đổi, thì bạn có thể thay đổi thành phần của nó và tìm kiếm tiếp theo sẽ không định vị được nó (đây là lý do tại sao các đối tượng bất biến như String là ứng cử viên tốt cho khóa)

Bạn đang ghép nối đó là đúng không lý tưởng. Đối với một số trường hợp, nó sẽ hoạt động, nhưng thường là giải pháp không đáng tin cậy và dễ vỡ (ví dụ: AB/C một khóa khác từ A/BC?).

Answer 3

Tôi có một trường hợp tương tự. Tất cả những gì tôi làm là nối hai chuỗi được phân tách bằng dấu ngã (~).

Vì vậy, khi khách hàng gọi hàm dịch vụ để có được những đối tượng từ bản đồ, nó trông như thế này:

MyObject getMyObject(String key1, String key2) { 
    String cacheKey = key1 + "~" + key2; 
    return map.get(cachekey); 
} 

Nó là đơn giản, nhưng nó hoạt động.

Answer 4

public static String fakeMapKey(final String... arrayKey) { 
    String[] keys = arrayKey; 

    if (keys == null || keys.length == 0) 
     return null; 

    if (keys.length == 1) 
     return keys[0]; 

    String key = ""; 
    for (int i = 0; i < keys.length; i++) 
     key += "{" + i + "}" + (i == keys.length - 1 ? "" : "{" + keys.length + "}"); 

    keys = Arrays.copyOf(keys, keys.length + 1); 

    keys[keys.length - 1] = FAKE_KEY_SEPARATOR; 

    return MessageFormat.format(key, (Object[]) keys);} 

public static string FAKE_KEY_SEPARATOR = "~"; 

 
INPUT: 
fakeMapKey("keyPart1","keyPart2","keyPart3"); 

 
OUTPUT: keyPart1~keyPart2~keyPart3

Answer 5

public int hashCode() { 
    return (str1 + str2).hashCode(); 
} 

Điều này dường như là một cách khủng khiếp để tạo ra hashCode: Tạo một trường hợp chuỗi mới mỗi lần mã băm được tính là khủng khiếp! (Thậm chí tạo ra các ví dụ chuỗi một lần và bộ nhớ đệm kết quả là thực hành kém.)

Có rất nhiều gợi ý ở đây:

How do I calculate a good hash code for a list of strings?

public int hashCode() { 
    final int prime = 31; 
    int result = 1; 
    for (String s : strings) { 
     result = result * prime + s.hashCode(); 
    } 
    return result; 
} 

Đối với một cặp chuỗi, mà trở thành:

return string1.hashCode() * 31 + string2.hashCode(); 

Đó là triển khai rất cơ bản. Rất nhiều lời khuyên thông qua liên kết để đề xuất các chiến lược được điều chỉnh tốt hơn.

Answer 6

Tôi thấy nhiều người sử dụng bản đồ lồng nhau. Tức là, để lập bản đồ Key1 -> Key2 -> Value (Tôi sử dụng ký pháp ghi dòng haskell/khoa học máy tính để lập bản đồ (Key1 x Key2) -> Value có hai đối số và tạo giá trị), trước tiên bạn cung cấp khóa đầu tiên - số này trả về cho bạn (partial) mapKey2 -> Value. bước tiếp theo.

Ví dụ,

Map<File, Map<Integer, String>> table = new HashMap(); // maps (File, Int) -> Distance 

add(k1, k2, value) { 
    table2 = table1.get(k1); 
    if (table2 == null) table2 = table1.add(k1, new HashMap()) 
    table2.add(k2, value) 
} 

get(k1, k2) { 
    table2 = table1.get(k1); 
    return table2.get(k2) 
} 

Tôi không chắc chắn rằng nó là tốt hơn hay không hơn so với đồng bằng xây dựng trọng điểm composite. Bạn có thể bình luận về điều đó.

Answer 7

Đọc về ngăn xếp spaguetti/xương rồng Tôi đã đưa ra một biến thể có thể phục vụ cho mục đích này, bao gồm khả năng ánh xạ khóa của bạn theo thứ tự bất kỳ để map.lookup ("a", "b") và bản đồ .lookup ("b", "a") trả về cùng một phần tử. Nó cũng làm việc với bất kỳ số lượng các phím không chỉ là hai.

Tôi sử dụng nó như một ngăn xếp để thử nghiệm với lập trình dataflow nhưng đây là một phiên bản nhanh và bẩn hoạt động như một bản đồ đa khóa (cần được cải thiện: Bộ thay vì mảng nên được sử dụng để tránh tìm kiếm các ocurrences trùng lặp a key)

public class MultiKeyMap <K,E> { 
    class Mapping { 
     E element; 
     int numKeys; 
     public Mapping(E element,int numKeys){ 
      this.element = element; 
      this.numKeys = numKeys; 
     } 
    } 
    class KeySlot{ 
     Mapping parent; 
     public KeySlot(Mapping mapping) { 
      parent = mapping; 
     } 
    } 
    class KeySlotList extends LinkedList<KeySlot>{} 
    class MultiMap extends HashMap<K,KeySlotList>{} 
    class MappingTrackMap extends HashMap<Mapping,Integer>{} 

    MultiMap map = new MultiMap(); 

    public void put(E element, K ...keys){ 
     Mapping mapping = new Mapping(element,keys.length); 
     for(int i=0;i<keys.length;i++){ 
      KeySlot k = new KeySlot(mapping); 
      KeySlotList l = map.get(keys[i]); 
      if(l==null){ 
       l = new KeySlotList(); 
       map.put(keys[i], l); 
      } 
      l.add(k); 
     } 
    } 
    public E lookup(K ...keys){ 
     MappingTrackMap tmp = new MappingTrackMap(); 
     for(K key:keys){ 
      KeySlotList l = map.get(key); 
      if(l==null)return null; 
      for(KeySlot keySlot:l){ 
       Mapping parent = keySlot.parent; 
       Integer count = tmp.get(parent); 
       if(parent.numKeys!=keys.length)continue; 
       if(count == null){ 
        count = parent.numKeys-1; 
       }else{ 
        count--; 
       } 
       if(count == 0){ 
        return parent.element; 
       }else{ 
        tmp.put(parent, count); 
       }    
      } 
     } 
     return null; 
    } 
    public static void main(String[] args) { 
     MultiKeyMap<String,String> m = new MultiKeyMap<String,String>(); 
     m.put("brazil", "yellow", "green"); 
     m.put("canada", "red", "white"); 
     m.put("USA", "red" ,"white" ,"blue"); 
     m.put("argentina", "white","blue"); 

     System.out.println(m.lookup("red","white")); // canada 
     System.out.println(m.lookup("white","red")); // canada 
     System.out.println(m.lookup("white","red","blue")); // USA 
    } 
} 

Answer 8

Bạn không cần phải tái tạo lại bánh xe. Đơn giản chỉ cần sử dụng Guava 's HashBasedTable<R,C,V> thực hiện của giao diện Table<R,C,V>, cho nhu cầu của bạn. Dưới đây là ví dụ

Table<String, String, Integer> table = HashBasedTable.create(); 

table.put("key-1", "lock-1", 50); 
table.put("lock-1", "key-1", 100); 

System.out.println(table.get("key-1", "lock-1")); //prints 50 
System.out.println(table.get("lock-1", "key-1")); //prints 100 

table.put("key-1", "lock-1", 150); //replaces 50 with 150 

Mã hóa hạnh phúc!