`
g21121
  • 浏览: 694696 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

Map实现之HashMap(性能及算法)

 
阅读更多
        上一篇重点介绍的是HashMap的实现原理、设计思想与相关具体操作,本篇就深入HashMap实现中进一步了解其内部的一些算法及相关性能指标。
        HashMap实例中table的length是在初始化时就被指定的,无论采用默认值还是其他指定值,table数组的大小就已经确定,随着添加元素的增多在一定时机下下会对table数组进行扩容呢。
        HashMap实例通过put方法设置元素,HashMap实例首先会计算该key所对应的下标位置,然后遍历寻找该key,如果找到则直接更新,当该key为原实例中不存在时则会调用addEntry方法添加新的元素,此时Map实例的size属性就会+1,并且进行扩容判断:
void addEntry(int hash, K key, V value, int bucketIndex) {
	Entry<K, V> e = table[bucketIndex];
	table[bucketIndex] = new Entry<K, V>(hash, key, value, e);
	//进行判断,是否扩容
	if (size++ >= threshold)
		resize(2 * table.length);
}
 
        其中 threshold=(int)(capacity * loadFactor);(数组长度*负载因子),当table默认长度为16时,threshold就为12,所以当size达到或超过12时就会调用resize方法进行扩容。扩容后table长度变为原来的两倍。
        以下是resize方法的源代码:
void resize(int newCapacity) {
	Entry[] oldTable = table;
	int oldCapacity = oldTable.length;
	if (oldCapacity == MAXIMUM_CAPACITY) {
		threshold = Integer.MAX_VALUE;
		return;
	}

	Entry[] newTable = new Entry[newCapacity];
	transfer(newTable);
	table = newTable;
	threshold = (int) (newCapacity * loadFactor);
}
 
        resize方法核心就是创建一个新的数组newTable,该数组大小为newCapacity(newCapacity=2 * table.length),也就是两倍于原数组大小。然后调用transfer(newTable)方法进行重新指向,通俗一点讲就是把table里面的东西倒腾到newTable里。
        transfer将原table中的Entry元素重新分配至新的newTable数组中,并且原table数组中的元素所在下标顺序可能发生变化,以下为transfer源代码:
/**
 * 将table中所有Entry元素转移至newTable
 */
void transfer(Entry[] newTable) {
	Entry[] src = table;
	int newCapacity = newTable.length;
	for (int j = 0; j < src.length; j++) {
		Entry<K, V> e = src[j];
		if (e != null) {
			src[j] = null;
			do {
				Entry<K, V> next = e.next;
				int i = indexFor(e.hash, newCapacity);
				e.next = newTable[i];
				newTable[i] = e;
				e = next;
			} while (e != null);
		}
	}
}
 
        从源代码int i = indexFor(e.hash, newCapacity);可以看出,这里根据新数组长度重新计算了Entry元素插入的下标位置,所以在进行resize之后Entry所在下标位置可能发生变化,如图所示:


        图示中Entry下标经过方法indexFor(int h, int length)进行了重新计算,所以结果下标是有可能变化的。
        最后将table的引用指向了newTable,所以原table的数组实例就变为了垃圾,等待GC进行处理
        总结:避免频繁出现这种操作是有必要的,这样既有利于合理利用内存空间,避免不必要的垃圾产生,又可以提高HashMap实例的性能,那么又该如何提高HashMap实例的性能呢?
 
        HashMap实例性能 
        HashMap 实例有两个参数(上一篇的属性中介绍过)影响其性能:“初始容量”和“负载因子”。

        容量(capacity):哈希表中容器的数量,初始容量只是哈希表在创建时的容量。

        负载因子(load factor):哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了负载因子与当前容量的乘积时,则要对该哈希表进行 rehash 操作(即重建内部数据结构),从而哈希表将具有大约两倍的容器数量。

 

        可以说容量与负载因子的合理设置与否直接影响着HashMap的性能指标,我们在初始化时可以指定这两个参数:

//capacity=32,load factor=0.75
Map map=new HashMap<String,String>(32,0.75f);

        此时HashMap会调用重载构造方法进行初始化,重载构造函数源代码如下:

/**
 * 使用指定容量和负载因子构建一个空的HashMap实例
 */
public HashMap(int initialCapacity, float loadFactor) {
	if (initialCapacity < 0)
		throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
	if (initialCapacity > MAXIMUM_CAPACITY)
		initialCapacity = MAXIMUM_CAPACITY;
	if (loadFactor <= 0 || Float.isNaN(loadFactor))
		throw new IllegalArgumentException("Illegal load factor: " + loadFactor);

	// Find a power of 2 >= initialCapacity
	int capacity = 1;
	while (capacity < initialCapacity)
		capacity <<= 1;

	this.loadFactor = loadFactor;
	threshold = (int) (capacity * loadFactor);
	table = new Entry[capacity];
	init();
}

 

        重载构造方法会根据我们指定的容量与负载因子进行了初始化操作。

 

 

        我们通过以下几个实验来探究下容量与负载因子对HashMap实例性能的影响:

 

        1)实验一

        实验原理:创建几个HashMap实例,初始化时指定不同的容量大小,并且它们采用默认相同的负载因子,向每个HashMap实例中添加1000000个元素,计算总用时,每个实验进行一定次数,得出对比分析图。

 

        实验结果:


        图中蓝色部分代表指定较小容量值;图中红色部分代表指定中等容量值;图中绿色部分代表指定合理容量值;

 

        实验局限性:实验过程中会与使用机器硬件及相关参数设置是否合理有关,而且实验过程中可能会出现垃圾收集导致返回时间较长的情况,所以需要更大范围与更多次数的对比分析。但实验的结果方向性是正确的,可以作为参考。

 

        实验结论:从实验结果可以很直观的看出,当我们指定的HashMap实例大小越接近实际使用大小,HashMap的性能越好。所以在加载因子不变的情况下,指定更合理的大小值可以有效的提高HashMap实例的性能。

 

        2)实验二

        实验原理:创建几个HashMap实例,初始化时指定相同的容量大小,不同的负载因子,向每个HashMap实例中添加1000000个元素,计算总用时,每个实验进行一定次数,得出对比分析图。

        实验过程:

        (1)默认长度为16,创建4个HashMap实例,它们的负载因子分别为0.25,0.5,0.75和1,代码如下:

Map map1 = new HashMap<String, String>(16,0.25f);
Map map2 = new HashMap<String, String>(16,0.5f);
Map map3 = new HashMap<String, String>(16,0.75f);
Map map4 = new HashMap<String, String>(16,1f);

        (2)不断向几个实例中填充元素,得到实验结果:


        图中几条曲线是指定初始化容量较小时,不同负载因子对实例性能的影响,从中可以看出负载因子为0.5时这个HashMap的实例性能最好。负载因子为1时性能最差。

        (3)指定HashMap实例初始容量为1232896,创建4个HashMap实例,它们的负载因子分别为0.25,0.5,0.75和1,代码如下:

Map map1 = new HashMap<String, String>(1232896,0.25f);
Map map2 = new HashMap<String, String>(1232896,0.5f);
Map map3 = new HashMap<String, String>(1232896,0.75f);
Map map4 = new HashMap<String, String>(1232896,1f);

        (4)不断向几个实例中填充元素,得到实验结果:


        图中几条曲线是指定初始化容量较大时,不同负载因子对实例性能的影响,从中可以看出负载因子为0.25时这个HashMap的实例性能最差,其他负载因子的性能差不多。

 

        实验结果:当添加元素较少时可以使用默认负载因子,此时性能差异并不明显;当添加元素较多时,可以通过测试或估算取得较佳的负载因子值。

 

        实验局限性:实验过程中受添加元素数量的影响较大,元素数量级越大加载因子影响越大。

 

        实验结论: 测试受多方面因素影响,添加不同数量元素的情况下相同的负载因子在性能影响上并不一致,只有根据实际运用情况来合理配置容量与负载因子的乘积才会使HashMap实例的性能更优,无法判断的情况下以默认值为最佳。

 

        综合结论:为了提高HashMap实例的性能,我们可以在初始化时估算出要添加元素的数量,从而指定足以容纳这些元素的HashMap容量数值,负载因子在元素个数不同的情况下对HashMap实例的影响较大,再未通过测试的情况下可以采用默认值(未必是最优值),否则将降低实例的性能。

 

 

        HashMap中的相关计算方法

        在HashMap实现中有一些特定的方法,诸如计算下标,计算hash值等,这些方法被用于特定的场合,虽算不上比较复杂的算法,但重要性不可小看。

 

        1.indexFor方法

        indexFor(int h, int length)方法根据指定hash值和数组长度计算出该hash值所对应数组下标。indexFor在获取、添加元素等方法中担任重要角色。

        以下是indexFor方法的源代码:

/**
 * 根据hash值h与数组长度length计算下标位置
 */
static int indexFor(int h, int length) {
	return h & (length - 1);
}

 

        核心代码只有一行,但是却不要小看它。indexFor采用的是“按位与”的方式来计算出下标位置,“&”的操作其实就是将十进制的数转换成二进制后两个二进制数按相同位进行“与”计算,相同值“与”计算后结果不变,不同值“与”计算后结果为0.

        注意:因为下标是从0开始的,以长度16为例,下标范围为0-15,所以代码中使用的是length-1

 

        以length=16为例,计算hash值为12,15,46,90的index值

        几个hash值对应二进制表示为:

十进制hash值 二进制值
12 1100
15 1111
90 1011010
234 11101010

 

        此时h & (length - 1)结果即为(以hash为12为例):

        12 & 15:



        结果:12

 

        类似的其他结果如下:

十进制hash值 二进制值 计算结果
12 1100 12
15 1111 15
90 1011010 10
234 11101010 10

 

        总结:indexFor方法采用“&”操作最大的优点就是在计算出下标位置的同时又注重了高效率。

 

        2.hash方法

        HashMap为什么要单独提供一个hash方法?这个hash方法又有什么不同?

        以下是hash方法的源代码:

static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

        hash方法是对已给出hashCode值的补充,用于防止那些质量较差的hash函数。并且将此hash函数作为已给定的hashCode的一个补充,可以提高hash值的质量。hash质量的好坏是非常重要,

HashMap用2的次幂作为表的hash长度,这就容易产生冲突。注意:Null 的key的hash值总是0,即他在

table的索引值永远为0。

        hash方法如何提高hash值的质量,通过以下实例就会很好的了解。

        1)初始化一个HashMap实例,指定容量为16:

Map map=HashMap(16);

        2)向此实例中添加几个元素,它们key的hashcode分别为12,28,44和92。

        3)通过indexFor方法可以计算出该key所应存储的下标位置,如果只是通过key的hashcode来计算的话,得出结果为:

key的hashCode 二进制值 length-1二进制值 计算后下标位置
12 1100 1111 12
28 11100 1111 12
44 101100 1111 12
92 1011100 1111 12

        4)从结果可以看出虽然每个key拥有不同的hashCode,但是通过计算后它们却被分配到了同一下标位置,这显而易见不是我们想要的结果。

        原因就在于indexFor方法的设计思路是“按位与”,这样计算过程中无论是0&1还是1&0结果都是0.所以几个key的二进制值与15的二进制值(1111)进行“与”操作时,实际就相当于只计算了最后四位有效位(红色部分),最终出现了上述结果。

 

        hash函数正是为了避免这一点:

key的hashCode 二进制值 hash计算后 length-1二进制值 计算后下标位置
12 1100 1100 1111 12
28 11100 11101 1111 13
44 101100 101110 1111 14
92 1011100 1011001 1111 9

        这样就可以很好避免了冲突,以致于所添加的元素能够均匀的分布在整个table数组里,从而提高了HashMap的性能。

 

        至此两篇关于HashMap的文章均已结束,希望能给朋友们带来一些帮助,如文章中出现那些错误还请雅正。

4
0
分享到:
评论
1 楼 在世界的中心呼喚愛 2015-03-29  
算法解释的不错

相关推荐

    树tree、动态数组dyArray、hashMap、拼图算法.zip

    哈希映射实现了常数时间的插入、查找和删除操作,常见于Java的`java.util.HashMap`和C++的`std::unordered_map`。理解哈希冲突及其解决方法(开放寻址法、链地址法)是掌握哈希映射的关键。 4. **拼图算法(Puzzle ...

    List、ArrayList、Vector及map、HashTable、HashMap分别的区别

    List、ArrayList、Vector及map、HashTable、HashMap是Java容器类中的几个重要的接口和实现类,了解它们之间的区别是非常重要的。 首先,我们来看List和ArrayList的区别。List是一个接口,而ArrayList是一个实现了...

    Javascript实现和操作HashMap

    虽然JavaScript原生的`Map`对象提供了类似的功能,但在某些场景下,开发者可能需要自定义HashMap来满足特定的需求,例如优化性能或者实现特定的算法。本篇文章将深入探讨如何在JavaScript中实现HashMap以及如何进行...

    FlowMap技术映射算法(WIP) 的Rust实现_rust_代码_下载

    在Rust编程语言中实现FlowMap算法,可以利用Rust的强大性能和内存安全特性,为处理大规模数据流提供高效解决方案。下面将详细介绍FlowMap算法的基本概念、Rust语言的特点以及如何在Rust中实现FlowMap。 FlowMap算法...

    java 集合和泛型 1. Map接口 2. HashMap底层实现 3. Hash数据结构和算法 4. 红黑树数据结构和算法

    java 集合和泛型 1. Map接口 2. HashMap底层实现 3. Hash数据结构和算法 4. 红黑树数据结构和算法

    用hashmap实现词典查询

    在IT领域,高效的数据结构和算法是解决复杂问题的关键。本话题主要关注如何利用HashMap这一数据结构来实现词典查询,以提供快速、便捷的字典服务。HashMap是Java编程语言中的一种内置数据结构,它提供了O(1)的平均...

    HashMap底层实现原理HashMap与HashTable区别HashMap与HashSet区别.docx

    在多线程环境下,如果需要使用HashMap,可以使用Collections的synchronizedMap()方法将其转换为同步的Map,但这并不意味着所有操作都是线程安全的,尤其是迭代操作。为了防止“fail-fast”迭代器引发的...

    java利用DFA算法实现敏感词过滤功能

    3. **自定义或优化算法**:对于性能要求极高的应用,可以考虑开发新的算法或对现有算法进行优化,以适应特定需求。 ### 三、DFA算法实现敏感词过滤 #### 第一步:敏感词库初始化 在Java中,我们可以使用HashMap...

    MATLAB哈希映射实现_hashmap_algorithm

    get(key) -&gt; get value associated with key set(key,value) -&gt; set new element in map by key...map = HashMap({'a','b','c'},{1,2,3}); map.size map.has('d') map.delete('a'); map.has('a') map.size map.values()

    Java HashMap类详解

    HashSet 和 HashMap 之间有很多相似之处,对于 HashSet 而言,系统采用 Hash 算法决定集合元素的存储位置,这样可以保证能快速存、取集合元素;对于 HashMap 而言,系统 key-value 当成一个整体进行处理,系统总是...

    Java8 HashMap扩容算法实例解析

    Java 8 HashMap 的扩容算法是通过 resize() 方法来实现的,该方法将旧的数组扩容到新的数组中,并对原有的数据进行转移。转移过程中使用 lo 链表和 hi 链表来存储元素,以确保元素的分布均匀,提高 HashMap 的性能。

    HashMap的实现原理

    HashMap 是 Java 集合框架中一个非常重要的类,它实现了 Map 接口,并提供了基于哈希表的存储方式。与其它 Map 实现不同的是,HashMap 允许使用 `null` 键和 `null` 值。这种灵活性使得 HashMap 成为许多应用程序中...

    Go-Golang无锁线程安全的HashMap为最快的读取访问进行了优化

    综上所述,构建一个无锁线程安全的HashMap需要理解并发编程的基本原理,熟悉Go的原子操作,以及对数据结构和哈希算法的深入掌握。通过这些知识,我们可以设计出一个为读取访问优化的HashMap,满足高并发场景的需求。

    HashMap介绍和使用

    HashMap是Java集合框架的一个重要组成部分,它实现了Map接口,能够存储键值对映射。在Java编程语言中,最基本的数据结构有两种:数组和引用(模拟指针)。所有的复杂数据结构都可以基于这两种基本结构构建出来,...

    Java实现LRU算法.zip

    LRU(Least Recently Used)算法是一种常见的页面替换算法,用于解决计算机内存有限而数据页数量过多的问题。...通过学习和理解LRU算法的实现,我们可以更好地理解和处理内存限制问题,提高系统的性能和效率。

    Java基于余弦方法实现的计算相似度算法示例

    "Java基于余弦方法实现的计算相似度算法示例" 本文主要介绍了Java基于余弦方法实现的计算相似度算法,简单说明了余弦相似性的概念、原理,并结合实例形式分析了Java实现余弦相似性算法的相关操作技巧。 一、余弦...

    HashMap通过VALUE反向求KEY的方法

    在实际开发中,根据具体需求,可以考虑使用更优化的数据结构或算法来提高性能。例如,如果需要频繁进行这种反向查询,可以维护一个额外的结构,如TreeMap或使用Guava库的BiMap,以支持高效的双向查找。

    蚁群算法_java实现.pdf

    蚁群算法的参数调整非常重要,参数的设置会直接影响算法的性能。在本文中,我们讨论了信息素权重、路径权重和信息素蒸发率对结果的影响。通过实验,我们发现了 2/5/0.5 的参数设置能够达到较好的效果。但是,这只是...

    Go-rhh一个简单而高效的Go的hashmap包

    在Go编程语言中,数据结构的选择对于程序性能至关重要,尤其是哈希映射(HashMap),它在许多场景下作为快速查找和存储数据的关键工具。本文将深入探讨标题提及的"Go-rhh",这是一个专为Go设计的简单而高效的HashMap...

    Java实现的决策树算法完整实例

    Java实现的决策树算法完整实例 决策树算法是机器学习领域中的一种常见算法,主要用于分类和预测。Java实现的决策树算法完整实例中,主要介绍了决策树的概念、原理,并结合完整实例形式分析了Java实现决策树算法的...

Global site tag (gtag.js) - Google Analytics