苏州Java培训
达内苏州java培训中心

0512-67873100

热门课程

苏州java培训学习HashMap工作原理

  • 时间:2016-06-15
  • 发布:苏州java培训
  • 来源:达内新闻

苏州java培训学习HashMap工作原理,大部分Java开发者都在使用Map,特别是HashMap。HashMap是一种简单但强大的方式去存储和获取数据。

内部存储

Java HashMap类实现了Map<K, V>接口。这个接口中的主要方法包括:

V put(K key, V value)

V get(Object key)

V remove(Object key)

Boolean containsKey(Object key)

HashMap使用了一个内部类Entry<K, V>来存储数据。这个内部类是一个简单的键值对,并带有额外两个数据:

一个指向其他入口(译者注:引用对象)的引用,这样HashMap可以存储类似链接列表这样的对象。

一个用来代表键的哈希值,存储这个值可以避免HashMap在每次需要时都重新生成键所对应的哈希值。

下面是Entry<K, V>在Java 7下的一部分代码:

1

2

3

4

5

6

7

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

final K key;

V value;

Entry<K,V> next;

int hash;



}

HashMap将数据存储到多个单向Entry链表中(有时也被称为桶bucket或者容器orbins)。所有的列表都被注册到一个Entry数组中(Entry<K, V>[]数组),这个内部数组的默认长度是16。

所有具有相同哈希值的键都会被放到同一个链表(桶)中。具有不同哈希值的键最终可能会在相同的桶中。

当用户调用 put(K key, V value) 或者 get(Object key) 时,程序会计算对象应该在的桶的索引。然后,程序会迭代遍历对应的列表,来寻找具有相同键的Entry对象(使用键的equals()方法)。

对于调用get()的情况,程序会返回值所对应的Entry对象(如果Entry对象存在)。

对于调用put(K key, V value)的情况,如果Entry对象已经存在,那么程序会将值替换为新值,否则,程序会在单向链表的表头创建一个新的Entry(从参数中的键和值)。

桶(链表)的索引,是通过map的3个步骤生成的:

首先获取键的散列码。

程序重复散列码,来阻止针对键的糟糕的哈希函数,因为这有可能会将所有的数据都放到内部数组的相同的索引(桶)上。

程序拿到重复后的散列码,并对其使用数组长度(最小是1)的位掩码(bit-mask)。这个操作可以保证索引不会大于数组的大小。你可以将其看做是一个经过计算的优化取模函数。

下面是生成索引的源代码:

// 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 & 16”的结果就是16或者0。这意味着长度为17的数组只能应用到两个桶上:一个是0,另外一个是16,这样不是很有效率。但是如果你将数组的长度设置为 2的幂值,例如16,那么按位索引的工作变成“H & 15”。15的二进制表示是0…001111,索引公式输出的值可以从0到15,这样长度为16的数组就可以被充分使用了。例如:

如果H = 952,它的二进制表示是0..01110111000,对应的索引是0…01000 = 8

如果H = 1576,它的二进制表示是0..011000101000,对应的索引是0…01000 = 8

如果H = 12356146,它的二进制表示是0..0101111001000101000110010,对应的索引是0…00010 = 2

如果H = 59843,它的二进制表示是0..01110100111000011,它对应的索引是0…00011 = 3

这种机制对于开发者来说是透明的:如果他选择一个长度为37的HashMap,Map会自动选择下一个大于37的2的幂值(64)作为内部数组的长度。

自动调整大小

在获取索引后,get()、put()或者remove()方法会访问对应的链表,来查看针对指定键的Entry对象是否已经存在。在不做修 改的情况下,这个机制可能会导致性能问题,因为这个方法需要迭代整个列表来查看Entry对象是否存在。假设内部数组的长度采用默认值16,而你需要存储 2,000,000条记录。在最好的情况下,每个链表会有125,000个Entry对象(2,000,000/16)。get()、remove()和 put()方法在每一次执行时,都需要进行125,000次迭代。为了避免这种情况,HashMap可以增加内部数组的长度,从而保证链表中只保留很少的 Entry对象。

当你创建一个HashMap时,你可以通过以下构造函数指定一个初始长度,以及一个loadFactor:

</pre>

public HashMap(int initialCapacity, float loadFactor)

<pre>

如果你不指定参数,那么默认的initialCapacity的值是16, loadFactor的默认值是0.75。initialCapacity代表内部数组的链表的长度。

当你每次使用put(…)方法向Map中添加一个新的键值对时,该方法会检查是否需要增加内部数组的长度。为了实现这一点,Map存储了2个数据:

Map的大小:它代表HashMap中记录的条数。我们在向HashMap中插入或者删除值时更新它。

阀值:它等于内部数组的长度*loadFactor,在每次调整内部数组的长度时,该阀值也会同时更新。

在添加新的Entry对象之前,put(…)方法会检查当前Map的大小是否大于阀值。 如果大于阀值,它会创建一个新的数组,数组长度是当前内部数组的两倍。因为新数组的大小已经发生改变,所以索引函数(就是返回“键的哈希值 & (数组长度-1)”的位运算结果)也随之改变。调整数组的大小会创建两个新的桶(链表),并且将所有现存Entry对象重新分配到桶上。调 整数组大小的目标在于降低链表的大小,从而降低put()、remove()和get()方法的执行时间。对于具有相同哈希值的键所对应的所有Entry 对象来说,它们会在调整大小后分配到相同的桶中。但是,如果两个Entry对象的键的哈希值不一样,但它们之前在同一个桶上,那么在调整以后,并不能保证 它们依然在同一个桶上。

Java 8 中的改进

在Java 8中,HashMap中的内部实现进行了很多修改。的确如此,Java 7使用了1000行代码来实现,而Java 8中使用了2000行代码。我在前面描述的大部分内容在Java 8中依然是对的,除了使用链表来保存Entry对象。在Java 8中,我们仍然使用数组,但它会被保存在Node中,Node中包含了和之前Entry对象一样的信息,并且也会使用链表:

下面是在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相比,到底有什么大的区别呢?好吧,Node可以被扩展成TreeNode。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)。

如你所见,我们在树中确实存储了比链表更多的数据。根据继承原则,内部表中可以包含Node(链表)或者TreeNode(红黑树)。Oracle决定根据下面的规则来使用这两种数据结构:

- 对于内部表中的指定索引(桶),如果node的数目多于8个,那么链表就会被转换成红黑树。

- 对于内部表中的指定索引(桶),如果node的数目小于6个,那么红黑树就会被转换成链表。

上一篇:苏州java培训学习管用的10条Java编程技巧
下一篇:苏州java培训学习理解Java面向对象

苏州达内java培训怎么样?达内java培训有什么优势?

苏州java培训哪家好 全方位对比java培训机构

达内与山东六所高校实行专业共建,开辟校企合作新纪元

达内Java高级实战课程重磅来袭,建立云移时代Java培训新标准

选择城市和中心
贵州省

广西省

海南省