（Java）使用Maps时，键和值是否有相同的类型？

Question

举个简单的例子，考虑一个Place类：

public class Place { 

    //fields 
    private String name; 

    private String state; 

    private int population; 

    private int squareMileage; 

    private int elevation; 

    //constructors 
    public Place() {  
    } 

    public Place(String name, String state) { 
     this.name = name; 
     this.state = state; 
    } 

    public Place(String name, String state, int population, int squareMileage, 
        int elevation) { 
     this.name = name; 
     this.state = state; 
     this.population = population; 
     this.squareMileage = squareMileage; 
     this.elevation = elevation; 
    } 

    //getters and setters 
    public String getName() { 
     return this.name; 
    } 

    public String getState() { 
     return this.state; 
    } 
    //... (other getters and setters omitted) 

    //do stuff 
}

而一个Places类（Place的HashMap一个对象）：

import java.util.*; 

public class Places { 
    private Map searchablePlaces; 

    public Places() { 
     searchablePlaces = new HashMap(); 
    } 

    public void add(Place value) { 
     Place key = new Place(value.getName(), value.getState()); 
     searchablePlaces.put(key, value); 
    } 

    public Place find(Place key) { 
     return searchablePlaces.get(key); 
    } 

    //override hashCode, equals 

    //do stuff 
}

从本质上讲，我的问题是：

1. 会有效率吗？，而不是直接搜索value，比方说，排序的ArrayList？
2. 如果key类型String等于name + state（或String[2]类型）会怎么样？

Answer 1

它令人困惑，恕我直言。我将定义一个PlaceKey类，只保存一个名称和一个状态并定义hashCode和equals。一个地方可以容纳一个PlaceKey和其他属性。我会使用Map<PlaceKey, Place>。

请注意，在您的示例中，Place类需要equals和hashCode，而不是Places类。

现在回答你两个问题：

1. 哈希映射为O（1），和一个列表为O（n）。因此地图通常会更快（除非是非常小的n值）
2. 连接几乎总是一个坏主意。你可能有name1 = aa，state1 = a，name2 = a和state2 = aa，这会导致冲突。一个数组在内容方面不会覆盖equals和hashCode，并且不是一个合适的映射关键类。

Answer 2

会不会有在寻找关键的HashMap中获得的任何效率，直接而不是寻找价值，比方说，一个有序的ArrayList？

是的。比较字符串比比较整数要慢（而且比较字符串也很少）。

如果您使用自定义对象的键，您应该谨慎实施hashCode与最常用的可能值。您还应该精简一下equals。

自定义类对name + state的好处是您可以考虑可能的值。

Answer 3

通过ArrayList访问对象比通过HashMap的键访问对象要快得多，但指向该对象的指针必须存储在内存中的连续块中，这会使删除对象更慢并将其放入ArrayList 。因此，决定哪种类型更好取决于您在执行程序期间要执行的操作。

例如，如果您需要放置和/或删除地方很多次，使用HashMap会更好，因为ArrayList不够高效。如果你的位置或多或少是固定的，你必须很少移动它们，那么ArrayList会给你更多的性能。

如果您定义了使用HashMap，则使用唯一字符串作为键会更快。

Answer 4

使用另一个（未完全填充的）Place对象作为关键字至少会浪费内存。通常你用一个唯一的标识符搜索。有几种可能性获得一个：

1. 如果要使用它们进行搜索，请使用（名称+ SEPARATOR +状态）作为键。
2. 使用几个地图，每个（可搜索）属性 - 如果它不是唯一的，你会连接一个列表。
3. 使用对象的（cryptogrphic）哈希关键 ...

Answer 5

1. 这取决于你如何搜索HashMap。例如，如果使用containsKey()，那么地图的搜索速度将比搜索列表快一个数量级。在典型情况下，检查散列表中的密钥是在一定的时间内发生的（O(1)）。如果使用二进制搜索，则可以在O(log n)时间内为排序的数组搜索密钥。但是，如果您通过迭代密钥集（不保证按任何顺序排序）来搜索密钥，那么您将执行一个O(n)操作，这比搜索排序列表要慢。

   短版？使用containsKey()将提供最佳性能。

2. 你可以这样做，但为什么使用Map？为什么不是List或Set？ Map的要点是将密钥与值关联起来。如果你没有这样做（并且示例代码并非如此），那么你的任务使用了错误的数据结构。