书签

底层的 Java HashMap

评论 0 浏览 0 2016-12-28

1.概述

在这篇文章中，我们将更详细地探讨Java集合框架中最流行的Map接口的实现，继续我们的intro文章中的内容。

在我们开始实现之前，有必要指出，主要的List和Set集合接口扩展了Collection，但Map并没有。

简单地说，HashMap按键存储数值，并提供API用于添加、检索和以各种方式操纵存储数据。这个实现是基于hashable的原则，乍听起来有点复杂，但实际上非常容易理解。

键值对被存储在所谓的桶中，这些桶共同构成了所谓的表，这实际上是一个内部数组。

一旦我们知道了一个对象被存储或将被存储的键，存储和检索操作就会在恒定的时间内发生，在一个尺寸适合的哈希图中为O(1)。

要了解哈希图是如何工作的，需要了解哈希图采用的存储和检索机制。我们将大量关注这些。

最后，HashMap相关的问题在面试中相当常见，所以这是准备面试或准备面试的一个可靠方法。

2. put() API

为了在哈希映射中存储一个值，我们调用put API，它需要两个参数；一个键和相应的值。

V put(K key, V value);

当一个值被添加到一个键下的映射时，键对象的hashCode() API被调用，以检索所谓的初始哈希值。

为了实际看到这一点，让我们创建一个对象将作为键的。我们将只创建一个单一的属性来作为哈希代码，以模拟哈希的第一阶段。

public class MyKey {
    private int id;
   
    @Override
    public int hashCode() {
        System.out.println("Calling hashCode()");
        return id;
    }

    // constructor, setters and getters 
}

现在我们可以使用这个对象来映射哈希图中的一个值。

@Test
public void whenHashCodeIsCalledOnPut_thenCorrect() {
    MyKey key = new MyKey(1);
    Map<MyKey, String> map = new HashMap<>();
    map.put(key, "val");
}

在上面的代码中没有发生什么，但要注意控制台的输出。的确，hashCode方法被调用了。

Calling hashCode()

接下来，哈希映射的hash() API在内部被调用，以使用初始哈希值计算最终的哈希值。

这个最终的哈希值最终会归结为内部数组中的一个索引，或者我们称之为桶的位置。

HashMap的hash函数看起来是这样的。

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

我们在这里应该注意的只是使用来自钥匙对象的哈希代码来计算最终的哈希值。

在 put 函数中，最终的哈希值是这样使用的：

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

请注意，调用内部 putVal 函数并将最终哈希值作为第一个参数。

人们可能会问，既然我们已经用它来计算哈希值了，为什么还要在这个函数中使用密钥呢？

原因是哈希映射将键和值都以Map.Entry对象的形式存储在桶的位置。

如前所述，所有的Java集合框架接口都扩展了Collection接口，但Map并没有。比较一下我们前面看到的Map接口的声明和Set接口的声明。

public interface Set<E> extends Collection<E>

原因是 ma​​p 并不像其他集合那样存储单个元素，而是键值对的集合。

因此，Collection接口的通用方法，如add、toArray，在涉及到Map时，并不具有意义。

我们在过去三段中所涉及的概念，使其成为最受欢迎的Java集合框架面试问题之一。所以，这是值得理解的。

哈希映射的一个特殊属性是它接受null值和null键。

@Test
public void givenNullKeyAndVal_whenAccepts_thenCorrect(){
    Map<String, String> map = new HashMap<>();
    map.put(null, null);
}

当在put操作中遇到一个空键时，它会被自动分配一个0的最终哈希值，这意味着它将成为底层数组的第一个元素。

这也意味着，当密钥为空时，没有散列操作，因此，密钥的hashCode API不被调用，最终避免了空指针异常。

在put操作中，当我们使用一个之前已经使用过的键来存储一个值时，它将返回与该键相关的前一个值。

@Test
public void givenExistingKey_whenPutReturnsPrevValue_thenCorrect() {
    Map<String, String> map = new HashMap<>();
    map.put("key1", "val1");

    String rtnVal = map.put("key1", "val2");

    assertEquals("val1", rtnVal);
}

否则，它就会返回null:。

@Test
public void givenNewKey_whenPutReturnsNull_thenCorrect() {
    Map<String, String> map = new HashMap<>();

    String rtnVal = map.put("key1", "val1");

    assertNull(rtnVal);
}

当put返回null时，也可能意味着与该键相关的前一个值为null，而不一定是新的键值映射。

@Test
public void givenNullVal_whenPutReturnsNull_thenCorrect() {
    Map<String, String> map = new HashMap<>();

    String rtnVal = map.put("key1", null);

    assertNull(rtnVal);
}

containsKey API可以用来区分这类情况，我们将在下一小节中看到。

3.get API

要检索一个已经存储在哈希映射中的对象，我们必须知道它被存储在哪个键下。我们调用get API，并向其传递Key对象。

@Test
public void whenGetWorks_thenCorrect() {
    Map<String, String> map = new HashMap<>();
    map.put("key", "val");

    String val = map.get("key");

    assertEquals("val", val);
}

在内部，使用相同的散列原则。Key对象的hashCode() API被调用以获得初始哈希值。

@Test
public void whenHashCodeIsCalledOnGet_thenCorrect() {
    MyKey key = new MyKey(1);
    Map<MyKey, String> map = new HashMap<>();
    map.put(key, "val");
    map.get(key);
}

这一次，hashCode的MyKey的API被调用了两次；一次是put，一次是get。

Calling hashCode()
Calling hashCode()

然后通过调用内部的hash() API来重构这个值，以获得最终的哈希值。

正如我们在上一节中所看到的，这个最终的哈希值最终归结为一个桶的位置或内部数组的索引。

然后，存储在该位置的值对象被检索并返回给调用的函数。

当返回值为null时，可能意味着键对象没有与哈希映射中的任何值相关联。

@Test
public void givenUnmappedKey_whenGetReturnsNull_thenCorrect() {
    Map<String, String> map = new HashMap<>();

    String rtnVal = map.get("key1");

    assertNull(rtnVal);
}

或者它可能只是意味着键被明确地映射到一个空的实例。

@Test
public void givenNullVal_whenRetrieves_thenCorrect() {
    Map<String, String> map = new HashMap<>();
    map.put("key", null);
        
    String val=map.get("key");
        
    assertNull(val);
}

为了区分这两种情况，我们可以使用containsKey API，我们向其传递Key，当且仅当为哈希映射中为指定的键创建了映射时，它才会返回true。

@Test
public void whenContainsDistinguishesNullValues_thenCorrect() {
    Map<String, String> map = new HashMap<>();

    String val1 = map.get("key");
    boolean valPresent = map.containsKey("key");

    assertNull(val1);
    assertFalse(valPresent);

    map.put("key", null);
    String val = map.get("key");
    valPresent = map.containsKey("key");

    assertNull(val);
    assertTrue(valPresent);
}

对于上述测试中的两种情况，get API调用的返回值都是空的，但我们能够区分哪一个是空的。

4.在HashMap中的集合视图

HashMap 提供了三个视图，使我们能够将其键和值视为另一个集合。我们可以获得一组所有map的键：

@Test
public void givenHashMap_whenRetrievesKeyset_thenCorrect() {
    Map<String, String> map = new HashMap<>();
    map.put("name", "baeldung");
    map.put("type", "blog");

    Set<String> keys = map.keySet();

    assertEquals(2, keys.size());
    assertTrue(keys.contains("name"));
    assertTrue(keys.contains("type"));
}

该集合是由map本身支持的。所以对集合的任何改变都会反映在map上。

@Test
public void givenKeySet_whenChangeReflectsInMap_thenCorrect() {
    Map<String, String> map = new HashMap<>();
    map.put("name", "baeldung");
    map.put("type", "blog");

    assertEquals(2, map.size());

    Set<String> keys = map.keySet();
    keys.remove("name");

    assertEquals(1, map.size());
}

我们还可以获得一个数值的集合视图。

@Test
public void givenHashMap_whenRetrievesValues_thenCorrect() {
    Map<String, String> map = new HashMap<>();
    map.put("name", "baeldung");
    map.put("type", "blog");

    Collection<String> values = map.values();

    assertEquals(2, values.size());
    assertTrue(values.contains("baeldung"));
    assertTrue(values.contains("blog"));
}

就像键集一样，在这个集合中的任何变化都会反映在底层映射中。

最后，我们可以获得映射中所有条目的集合视图。

@Test
public void givenHashMap_whenRetrievesEntries_thenCorrect() {
    Map<String, String> map = new HashMap<>();
    map.put("name", "baeldung");
    map.put("type", "blog");

    Set<Entry<String, String>> entries = map.entrySet();

    assertEquals(2, entries.size());
    for (Entry<String, String> e : entries) {
        String key = e.getKey();
        String val = e.getValue();
        assertTrue(key.equals("name") || key.equals("type"));
        assertTrue(val.equals("baeldung") || val.equals("blog"));
    }
}

请记住，哈希图专门包含无序的元素，因此我们在测试for each循环中的条目的键和值时，假定任何顺序。

很多时候，你会像上一个例子那样在一个循环中使用集合视图，更确切地说，是使用它们的迭代器。

只需记住，上述所有视图的迭代器都是fail-fast（快速失败）。

如果在迭代器创建后，在map上进行了任何结构性的修改，将抛出一个并发修改异常。

@Test(expected = ConcurrentModificationException.class)
public void givenIterator_whenFailsFastOnModification_thenCorrect() {
    Map<String, String> map = new HashMap<>();
    map.put("name", "baeldung");
    map.put("type", "blog");

    Set<String> keys = map.keySet();
    Iterator<String> it = keys.iterator();
    map.remove("type");
    while (it.hasNext()) {
        String key = it.next();
    }
}

唯一允许的结构性修改是通过迭代器本身执行的remove操作。

public void givenIterator_whenRemoveWorks_thenCorrect() {
    Map<String, String> map = new HashMap<>();
    map.put("name", "baeldung");
    map.put("type", "blog");

    Set<String> keys = map.keySet();
    Iterator<String> it = keys.iterator();

    while (it.hasNext()) {
        it.next();
        it.remove();
    }

    assertEquals(0, map.size());
}

关于这些集合视图，需要记住的最后一点是迭代的性能。这就是哈希图与它的同类链接哈希图和树形图相比表现相当差的地方。

散列图的迭代在最坏的情况下发生O(n)，其中n是其容量和条目数的总和。

5.HashMap性能

哈希图的性能受两个参数的影响。初始容量和负载因子。容量是指桶的数量或底层数组的长度，初始容量只是创建时的容量。

负载因子或LF，简而言之，是衡量在添加一些值之后，在调整大小之前，哈希图应该有多满的度量。

默认的初始容量是16，默认的负载系数是0.75。我们可以用初始容量和LF的自定义值创建一个哈希图。

Map<String,String> hashMapWithCapacity=new HashMap<>(32);
Map<String,String> hashMapWithCapacityAndLF=new HashMap<>(32, 0.5f);

Java团队设置的默认值在大多数情况下是很好的优化。然而，如果你需要使用你自己的值，这是非常可以的，你需要了解对性能的影响，以便你知道你在做什么。

当散列图条目的数量超过LF和容量的乘积时，就会发生rehashing，即创建另一个内部数组，其大小是初始数组的两倍，所有条目都被移到新数组中的新桶位置上。

低初始容量降低了空间成本，但增加了重新散列的频率。重新散列显然是一个非常昂贵的过程。因此，作为一项规则，如果你预计会有很多条目，你应该设置一个相当高的初始容量。

反过来说，如果你把初始容量设置得太高，你将在迭代时间上付出代价。正如我们在上一节看到的那样。

因此，高初始容量对大量条目加上很少或没有迭代的情况下是很好的。

一个低的初始容量适合于少量的条目，有大量的迭代。

6.在HashMap中的碰撞

碰撞，或者更具体地说，HashMap中的哈希代码碰撞，是指两个或更多的关键对象产生相同的最终哈希值，从而指向同一个桶的位置或数组索引的情况。

这种情况可能发生，因为根据equals和hashCode约定，Java中两个不相等的对象可以有相同的哈希代码。

由于底层数组的大小有限，即在调整大小之前。这个数组越小，碰撞的几率就越大。

也就是说，值得一提的是，Java实现了一种哈希码碰撞解决技术，我们将用一个例子来看看。

请记住，是键的哈希值决定了该对象将被存储在哪个桶里。因此，如果任何两个键的哈希代码发生冲突，它们的条目仍将被存储在同一个桶中。

而在默认情况下，该实现使用了一个链接列表作为桶的实现。

最初的恒定时间O(1) put和get操作，在发生碰撞的情况下，将以线性时间O(n)发生。这是因为在找到具有最终哈希值的桶的位置后，该位置的每个键将使用equals API与提供的键对象进行比较。

为了模拟这种碰撞解决技术，让我们稍稍修改一下我们先前的关键对象。

public class MyKey {
    private String name;
    private int id;

    public MyKey(int id, String name) {
        this.id = id;
        this.name = name;
    }
    
    // standard getters and setters
 
    @Override
    public int hashCode() {
        System.out.println("Calling hashCode()");
        return id;
    } 
 
    // toString override for pretty logging

    @Override
    public boolean equals(Object obj) {
        System.out.println("Calling equals() for key: " + obj);
        // generated implementation
    }

}

注意我们是如何简单地将id属性作为哈希代码返回的 – 从而迫使碰撞的发生。

另外，请注意，我们在equals和hashCode实现中添加了日志语句 – 这样我们就能准确地知道逻辑被调用的时间了。

现在让我们去存储和检索一些在某一点上发生碰撞的对象。

@Test
public void whenCallsEqualsOnCollision_thenCorrect() {
    HashMap<MyKey, String> map = new HashMap<>();
    MyKey k1 = new MyKey(1, "firstKey");
    MyKey k2 = new MyKey(2, "secondKey");
    MyKey k3 = new MyKey(2, "thirdKey");

    System.out.println("storing value for k1");
    map.put(k1, "firstValue");
    System.out.println("storing value for k2");
    map.put(k2, "secondValue");
    System.out.println("storing value for k3");
    map.put(k3, "thirdValue");

    System.out.println("retrieving value for k1");
    String v1 = map.get(k1);
    System.out.println("retrieving value for k2");
    String v2 = map.get(k2);
    System.out.println("retrieving value for k3");
    String v3 = map.get(k3);

    assertEquals("firstValue", v1);
    assertEquals("secondValue", v2);
    assertEquals("thirdValue", v3);
}

在上述测试中，我们创建了三个不同的键 – 其中一个有唯一的id，另外两个有相同的id。由于我们使用id作为初始哈希值，在用这些键存储和检索数据的过程中肯定会发生碰撞。

除此之外，由于我们前面看到的碰撞解决技术，我们期望我们的每一个存储值都能被正确地检索出来，因此在最后三行的断言。

当我们运行测试时，它应该通过，表明碰撞被解决了，我们将使用产生的日志来确认碰撞确实发生了。

storing value for k1
Calling hashCode()
storing value for k2
Calling hashCode()
storing value for k3
Calling hashCode()
Calling equals() for key: MyKey [name=secondKey, id=2]
retrieving value for k1
Calling hashCode()
retrieving value for k2
Calling hashCode()
retrieving value for k3
Calling hashCode()
Calling equals() for key: MyKey [name=secondKey, id=2]

请注意，在存储操作中，k1和k2被成功地映射到它们的值中，只使用了哈希代码。

然而，k3的存储并不那么简单，系统检测到其桶的位置已经包含了k2的映射。因此，equals的比较被用来区分它们，并创建了一个链接列表来包含这两个映射。

任何其他后续的映射，其键哈希到相同的桶的位置将遵循相同的路线，并最终取代链接列表中的一个节点，或者如果equals比较对所有现有的节点返回false，则被添加到列表的头部。

同样，在检索过程中，k3和k2被相等比较，以确定其值应被检索的正确的键。

最后，从Java 8开始，在碰撞解决中，当某个桶的位置的碰撞数量超过一定的阈值后，链接列表会被动态地替换为平衡的二进制搜索树。

这一变化带来了性能上的提升，因为在发生碰撞的情况下，存储和检索只需O(log n).即可完成。

这一部分在技术面试中非常常见，特别是在基本的存储和检索问题之后。

7.结语

在这篇文章中，我们探讨了JavaMap接口的HashMap实现。

本文所使用的所有示例的完整源代码可以在GitHub项目中找到。

最后更新2023-03-11
0 个评论
标签
Java Map