Posted by on | Featured

大多数JAVA开发人员都在使用Maps，特别是HashMaps。HashMap是一种简单而强大的存储和获取数据的方式。但有多少开发人员知道HashMap如何在内部工作？几天前，我已经阅读了java.util.HashMap的源代码（在Java 7和Java 8中）的大部分内容，以深入了解这种基本的数据结构。在这篇文章中，我将解释java.util.HashMap的实现，介绍JAVA 8实现中的新特性，并讨论使用HashMaps时的性能，内存和已知问题。

内部存储器

JAVA HashMap类实现了接口Map <K，V>。这个接口的主要方法是：

V放（K键，V值）

V get（Object key）

V remove（Object key）

Boolean containsKey（Object key）

HashMaps使用内部类来存储数据：Entry <K，V>。这个条目是一个简单的键值对与两个额外的数据：

对另一个Entry的引用，以便HashMap可以存储单个链接列表等条目

表示密钥的哈希值的哈希值。这个散列值被存储来避免每次HashMap需要散列的计算。

以下是JAVA 7中的Entry实现的一部分：

static class Entry<K,V> implements Map.Entry<K,V> {

final K key;

V value;

Entry<K,V> next;

int hash;

…

}

一个HashMap将数据存储到项的多个单链表（也称为桶或桶）。所有列表都在Entry（Entry <K，V> []数组）中进行注册，此内部数组的默认容量为16。

 

下图显示了具有可为空条目的数组的HashMap实例的内部存储。每个条目可链接到另一个条目以形成链接列表。

 

所有具有相同散列值的密钥都放在同一个链表（存储区）中。具有不同散列值的密钥可以在同一个桶中结束。

当用户调用put（K key，V value）或get（Object key）时，该函数会计算Entry所在的存储桶的索引。然后，函数遍历列表来查找具有相同键的Entry（使用键的equals（）函数）。

在get（）的情况下，函数返回与条目关联的值（如果条目存在）。

在put（K键，V值）的情况下，如果条目存在，函数会用新值替换它，否则它会在单向链表的头部创建一个新条目（从参数中的键和值）。

 

存储区的索引（链接列表）由地图以3个步骤生成：

它首先获取密钥的哈希码。

它重新编码哈希码以防止来自将所有数据放在内部数组的相同索引（桶）中的密钥的散列函数

它需要重新哈希散列码，并用数组的长度（减1）对它进行位掩码。此操作确保索引不能大于数组的大小。你可以把它看作一个非常计算优化的模函数。

这是处理索引的JAVA 7和8源代码：

// the “rehash” function in JAVA 7 that takes the hashcode of the key

static int hash(int h) {

h ^= (h >>> 20) ^ (h >>> 12);

return h ^ (h >>> 7) ^ (h >>> 4);

}

// the “rehash” function in JAVA 8 that directly takes the key

static final int hash(Object key) {

int h;

return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

}

// the function that returns the index from the rehashed hash

static int indexFor(int h, int length) {

return h & (length-1);

}

为了有效地工作，内部数组的大小需要是2的幂，让我们看看为什么。

想象一下，数组大小是17，掩码值将是16（大小-1）。16的二进制表示为0 … 010000，因此对于任何散列值H，使用按位公式“H AND 16”生成的索引将为16或0.这意味着大小为17的数组将仅用于2个桶：索引0和索引16的一个，效率不高

但是，如果您现在采用的是16的2的幂的大小，则按位索引公式为“H AND 15”。15的二进制表示是0 … 001111，因此索引公式可以输出0到15的值，并且大小为16的数组可以被完全使用。例如：

如果H = 952，则其二进制表示是0..0111011 1000，相关联的索引是0 … 0 1000  = 8

如果H = 1576，其二进制表示是0..01100010 1000，则相关的索引是0 … 0 1000  = 8

如果H = 12356146，则其二进制表示是0..010111100100010100011 0010，关联的索引是0 … 0 0010 = 2

如果H = 59843，它的二进制表示是0..0111010011100 0011，相关联的索引是0 … 0 0011  = 3

 

这就是为什么数组大小是2的幂。这个机制对于开发者来说是透明的：如果他选择了一个大小为37的HashMap，那么Map会自动选择内部数组大小为37（64）后的下一个2的幂。

 

自动调整大小

获取索引后，函数（get，put或remove）访问/迭代关联的链表以查看给定键是否存在现有的Entry。如果没有修改，这个机制可能会导致性能问题，因为函数需要迭代整个列表来查看条目是否存在。想象一下，内部数组的大小是默认值（16），您需要存储2百万个值。在最好的情况下，每个链表将有125 000个条目（2/16百万）的大小。因此，每个get（），remove（）和put（）将导致125 000次迭代/操作。为了避免这种情况，HashMap有能力增加其内部数组，以保持非常短的链表。

在创建HashMap时，可以使用以下构造函数指定初始大小和loadFactor：

public HashMap(int initialCapacity, float loadFactor)

如果不指定参数，则默认的initialCapacity为16，默认的loadFactor为0.75。initialCapacity表示链接列表的内部数组的大小。

每次使用put（…）在Map中添加新的键/值时，函数会检查是否需要增加内部数组的容量。为了做到这一点，地图存储2个数据：

地图的大小：它表示HashMap中条目的数量。每次添加或删除条目时，此值都会更新。

阈值：它等于（内部数组的容量）* loadFactor，并在内部数组的每个调整大小后刷新

在添加新的Entry之前，put（…）检查size是否大于阈值，并且如果它重新创建一个具有加倍大小的新数组。由于新数组的大小已更改，索引函数（它返回按位操作“hash（key）AND（sizeOfArray-1）”）会更改。因此，调整数组的大小会创建两倍以上的存储桶（即链接列表），并将  所有现有条目重新分配到存储桶（旧存储条目和新创建的存储条目）中。

这个调整大小操作的目的是减少链表的大小，以便put（），remove（）和get（）方法的时间成本保持在低水平。所有其键具有相同散列的条目将在调整大小后保留在同一个存储桶中。但是，具有不同散列键的2个条目之前位于同一个存储桶中的条目在转换后可能不在同一个存储桶中。

 

图片显示了内部数组的大小调整之前和之后的表示。在增加之前，为了获得条目E，地图必须迭代5个元素的列表。调整大小后，同样的get（）只是遍历2个元素的链表，get（）在调整大小后快2倍！

 

注意：HashMap只会增加内部数组的大小，并不能提供减少它的方法。

 

线程安全

如果你已经知道HashMaps，你知道这不是线程安全的，但为什么？例如，假设您有一个只将新数据放入Map中的Writer线程和一个从Map中读取数据的Reader线程，为什么它不工作？

因为在自动调整大小的机制中，如果线程尝试放置或获取对象，地图可能会使用旧的索引值，并且不会找到条目所在的新存储桶。

最糟糕的情况是，2个线程同时放置数据，2个put（）调用同时调整Map的大小。由于两个线程同时修改链接列表，因此Map可能最终在其链接列表中有一个内部循环。如果您尝试使用内部循环获取列表中的数据，get（）将永远不会结束。

该哈希表的实现是线程安全的实现，从这种情况可以防止。但是，由于所有的CRUD方法都是同步的，所以这个实现非常缓慢。例如，如果线程1调用get（key1），线程2调用get（key2），线程3调用get（key3），则一次只有一个线程将能够获取其值，而其中的3个线程可以访问数据与此同时。

自JAVA 5以来，存在一个线程安全的HashMap的更智能的实现：ConcurrentHashMap。只有桶同步，因此多个线程可以同时获取（），remove（）或put（）数据（如果它不暗示访问同一个桶或调整内部数组的大小）。在多线程应用程序中使用此实现更好。

 

关键不变性

为什么字符串和整数是HashMap的关键字的一个很好的实现？主要是因为它们是不可改变的！如果您选择创建自己的Key类并且不使其不可变，那么您可能会丢失HashMap中的数据。

看看下面的用例：

你有一个内部值为“1”的密钥

你用这个键把一个对象放在HashMap中

HashMap根据Key的哈希码生成一个哈希（所以从“1”开始）

Map  将这个散列存储  在新创建的Entry中

您将该键的内部值修改为“2”

密钥的散列值被修改，但HashMap不知道它（因为旧的散列值被存储）

您尝试使用修改后的密钥来获取对象

该映射计算您的密钥的新散列（从“2”开始）以查找条目在哪个链接列表（存储区）中

 

案例1：由于您修改了密钥，因此地图会尝试在错误的存储区中找到条目，但找不到它

情况2：幸运的是，修改后的密钥会生成与旧密钥相同的存储桶。然后，映射遍历链表来查找具有相同键的条目。但要找到密钥，映射首先比较哈希值，然后调用equals（）比较。由于修改的密钥与旧的散列值（存储在条目中）没有相同的散列，因此映射将无法在链接列表中找到该条目。

这是Java中的一个具体示例。我在Map中放置了两个键值对，我修改了第一个键，然后尝试获取2个值。只有第二个值从地图返回，第一个值在HashMap中为“lost”：

public class MutableKeyTest {

 

public static void main(String[] args) {

 

class MyKey {

Integer i;

 

public void setI(Integer i) {

this.i = i;

}

 

public MyKey(Integer i) {

this.i = i;

}

 

@Override

public int hashCode() {

return i;

}

 

@Override

public boolean equals(Object obj) {

if (obj instanceof MyKey) {

return i.equals(((MyKey) obj).i);

} else

return false;

}

 

}

 

Map<MyKey, String> myMap = new HashMap<>();

MyKey key1 = new MyKey(1);

MyKey key2 = new MyKey(2);

 

myMap.put(key1, “test ” + 1);

myMap.put(key2, “test ” + 2);

 

// modifying key1

key1.setI(3);

 

String test1 = myMap.get(key1);

String test2 = myMap.get(key2);

 

System.out.println(“test1= ” + test1 + ” test2=” + test2);

 

}

 

}

输出是：“test1 = null test2 = test 2”。正如预期的那样，Map无法使用修改的键1检索字符串1。

 

JAVA 8的改进

在JAVA 8中，HashMap的内部表示已经发生了很大变化。事实上，JAVA 7中的实现需要1k行代码，而JAVA 8中的实现需要2k行。除了链接的条目列表之外，我之前说过的大部分内容都是真实的。在JAVA8中，您仍然拥有一个数组，但它现在存储的节点包含与条目完全相同的信息，因此也是链接列表：

以下是JAVA 8中的Node实现的一部分：

static class Node<K,V> implements Map.Entry<K,V> {

final int hash;

final K key;

V value;

Node<K,V> next;

那么，与JAVA 7有什么不同呢？那么，节点可以扩展到TreeNodes。TreeNode是一个红黑树结构，存储更多信息，以便它可以添加，删除或获取O（log（n））中的元素。

仅供参考，这里是存储在TreeNode中的数据的详尽清单

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {

final int hash; // inherited from Node<K,V>

final K key; // inherited from Node<K,V>

V value; // inherited from Node<K,V>

Node<K,V> next; // inherited from Node<K,V>

Entry<K,V> before, after;// inherited from LinkedHashMap.Entry<K,V>

TreeNode<K,V> parent;

TreeNode<K,V> left;

TreeNode<K,V> right;

TreeNode<K,V> prev;

boolean red;

红黑树是自平衡的二元搜索树。尽管新增或删除了节点，但它们的内部机制确保它们的长度总是在log（n）中。使用这些树的主要优点是，在许多数据位于内部表的相同索引（桶）中的情况下，树中的搜索将花费  O（log（n）），而花费O（n）与一个链表。

正如你所看到的，树比链表需要更多的空间（我们将在下一部分讨论它）。

通过继承，内部表可以包含节点（链接列表）和 TreeNode（红黑树）。Oracle决定使用两种数据结构，并使用以下规则：
– 如果对于内部表中的给定索引（存储区），存在多于8个节点，则将链接列表转换为红色黑色树
– 如果对于给定索引）在内部表中少于6个节点时，树被转换成链接列表

此图显示了具有树（在存储区0）和链接列表（在存储区1,2和3）的JAVA 8 HashMap的内部数组。存储桶0是一个树，因为它有8个以上的节点。

 

内存开销

JAVA 7

在内存方面，使用HashMap会带来成本。在JAVA 7中，HashMap将键值对封装在Entries中。一个条目有：

对下一个条目的引用

预先计算的散列（整数）

对密钥的引用

对价值的引用

而且，JAVA 7 HashMap使用Entry的内部数组。假设JAVA 7 HashMap包含N个元素，并且其内部数组具有容量CAPACITY，则额外的内存成本大约为：

sizeOf（integer）* N + sizeOf（reference）*（3 * N + C）

哪里：

整数的大小取决于等于4个字节

引用的大小取决于JVM / OS / Processor，但通常是4个字节。

这意味着开销通常是16 * N + 4 * CAPACITY字节

提醒：在Map自动调整大小之后，内部数组的容量等于N之后的下一个二次幂。

注意：由于JAVA 7，HashMap类具有惰性初始化。这意味着即使您分配了一个HashMap，在第一次使用put（）方法之前，内部条目数组（将花费4 * CAPACITY字节）也不会分配到内存中。

JAVA 8

使用JAVA 8实现时，获取内存使用情况会变得有点复杂，因为Node可以包含与Entry相同的数据或相同的数据以及6个引用和布尔值（如果它是TreeNode）。

如果所有节点都只有节点，则JAVA 8 HashMap的内存消耗与JAVA 7 HashMap相同。

如果所有节点都是TreeNode，则JAVA 8 HashMap的内存消耗将变为：

N * sizeOf（integer）+ N * sizeOf（boolean）+ sizeOf（reference）*（9 * N + CAPACITY）

在大多数标准JVM中，它等于44 * N + 4 * CAPACITY个字节

 

性能问题

偏斜的HashMap vs良好平衡的HashMap

在最好的情况下，get（）和put（）方法的时间复杂度为O（1）。但是，如果你不关心密钥的散列函数，你可能会以非常缓慢的put（）和get（）调用结束。put（）和get的良好性能取决于将数据重新分配到内部数组（bucket）的不同索引中。如果密钥的哈希函数设计不合适，则会产生偏移重新分区（无论内部数组的容量有多大）。所有使用最大链接列表的put（）和get（）将会很慢，因为它们需要迭代整个列表。在最坏的情况下（如果大多数数据在同一个桶中），最终可能会导致O（n）时间复杂度。
这是一个视觉例子。第一张图片显示了一个偏斜的HashMap，第二张图片是一个很平衡的图片。

 

在这种偏斜的HashMap的情况下，bucket 0上的get（）/ put（）操作代价很高。获得Entry K将花费6次迭代

在这个平衡好的HashMap的情况下，获得Entry K将花费3次迭代。两个HashMaps都存储相同数量的数据并具有相同的内部数组大小。唯一的区别是散列（关键字）函数分发了桶中的条目。

这里是JAVA中的一个极端例子，我创建了一个哈希函数，将所有数据放在同一个桶中，然后添加200万个元素。

public class Test {

 

public static void main(String[] args) {

 

class MyKey {

Integer i;

public MyKey(Integer i){

this.i =i;

}

 

@Override

public int hashCode() {

return 1;

}

 

@Override

public boolean equals(Object obj) {

…

}

 

}

Date begin = new Date();

Map <MyKey,String> myMap= new HashMap<>(2_500_000,1);

for (int i=0;i<2_000_000;i++){

myMap.put( new MyKey(i), “test “+i);

}

 

Date end = new Date();

System.out.println(“Duration (ms) “+ (end.getTime()-begin.getTime()));

}

}

在我的核心i5-2500k @ 3.6Ghz上，java 8u40 需要45分钟以上（我在45分钟后停止了这个过程）。

现在，如果我运行相同的代码，但是这次我使用下面的散列函数

    @Override

public int hashCode() {

int key = 2097152-1;

return key+2097152*i;

}

它需要46秒，这是更好的方式！这个散列函数比以前的散列函数有更好的重新分区，所以put（）调用更快。

如 果我用下面的哈希函数运行相同的代码，它可以提供更好的哈希重新分区

@Override

public int hashCode() {

return i;

}

现在需要2秒钟。

我希望你明白散列函数有多重要。如果在JAVA 7上运行相同的测试，结果对于第一种和第二种情况会更糟（因为在JAVA 8中，put的时间复杂度是O（n）vs O（log（n）））

在使用HashMap时，您需要为您的密钥找到一个散列函数，以将密钥分散到最可能的桶中。为此，您需要避免散列冲突。字符串对象是一个很好的关键，因为它具有良好的散列函数。整数也很好，因为它们的哈希码是他们自己的价值。

 

调整开销

如果你需要存储大量数据，你应该创建一个初始容量接近预期容量的HashMap。

如果您不这样做，则地图将采用默认大小16，因子负荷为0.75。11的第一个put（）将会非常快，但是第12（16 * 0.75）会重新创建一个新的内部数组（具有相关联的链表/树），新的容量为32.第13到第23将会很快，但是第24 （32 * 0.75）会重新创建一个昂贵的新表示，使内部数组的大小加倍。内部大小调整操作将出现在put（）的第48,96,192 ……个调用中。在低音量情况下，内阵列的全面娱乐速度很快，但在高音量时可能需要几秒到几分钟的时间。通过最初设置您的预期尺寸，您可以避免这些  昂贵的操作。

但是有一个缺点：如果你设置了一个非常高的数组大小，如2 ^ 28，而你只在数组中使用2 ^ 26个存储桶，那么你会浪费大量内存（在这种情况下大概是2 ^ 30字节）。

 

结论

对于简单的用例，您不需要知道HashMaps的工作方式，因为您不会看到O（1）和O（n）或O（log（n））操作之间的区别。但最好理解最常用的数据结构之一的底层机制。而且，对于Java开发人员而言，这是一个典型的面试问题。

在高容量下，了解它的工作原理和理解密钥散列函数的重要性就显得非常重要。

我希望这篇文章能帮助你深入理解HashMap的实现。

 

Tags: , , ,
Comments are closed.