- 浏览: 694696 次
- 性别:
- 来自: 北京
文章分类
最新评论
-
masuweng:
写的详细
Java中的枚举 -
zmwxiaoming:
java unix时间戳转换 -
g21121:
lhq1013 写道请问 我通过什么方式可以获取到tomca ...
tomcat优化 -
lhq1013:
请问 我通过什么方式可以获取到tomcat的qps值?
tomcat优化 -
zengshaotao:
condition的测试代码有问题,一个await的线程醒来之 ...
Java并发之Condition与Lock
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); }
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); }
/** * 将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); } } }
图示中Entry下标经过方法indexFor(int h, int length)进行了重新计算,所以结果下标是有可能变化的。
容量(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的文章均已结束,希望能给朋友们带来一些帮助,如文章中出现那些错误还请雅正。
发表评论
-
maven自定义archetype
2018-06-25 15:30 1248在开发过程中我们经常会创建一系列结构类似的 ... -
Linux下安装Haproxy、Tomcat、Keepalived
2018-04-27 19:37 0首先介绍一下环境: 1) ... -
Linux下安装Haproxy、Nginx、Tomcat、Keepalived
2018-04-27 19:44 1564首先介绍一下环境: 1) ... -
Java中的枚举
2018-04-24 09:43 2391Enum(“枚举”)全称为 enumera ... -
Java中的枚举
2018-04-23 17:56 14Enum(“枚举 ... -
Java并发之Executor
2016-05-21 17:12 2725在很多系统 ... -
Java并发之Callable,Future,FutureTask
2016-05-18 18:31 0在传统的多线程实现方式中(继承Thread ... -
TOMCAT优化
2016-05-16 14:44 0Tomcat是我们经常使用的 servle ... -
Java并发之LinkedBlockingQueue
2016-05-12 13:34 0上一篇我们已经学习过了 ArrayBloc ... -
Java并发之LinkedBlockingQueue
2016-05-12 17:50 8564上一篇我们已经学习过了 ArrayBloc ... -
Java并发之ArrayBlockingQueue
2016-05-10 11:44 5263ArrayBlockingQueue是一个 ... -
Java并发之BlockingQueue
2016-05-09 21:32 1474一、Queue Queu ... -
Java并发之ReentrantLock
2016-05-05 19:48 2682java.util.concurrent. ... -
Java并发之ReentrantLock
2016-05-05 18:21 8java.util.concurrent. ... -
ReentrantLock
2016-05-03 10:28 0java.util.concurrent. ... -
Condition与Lock
2016-05-03 00:18 7java.util.concurr ... -
原子操作(CAS)
2016-05-02 16:41 15218众所周知锁有两种:乐观锁与悲观锁。独占锁是 ... -
Java并发机制locks之接口
2016-04-28 10:45 0... -
Java多线程进阶篇
2016-04-20 14:57 237通过前文我 ... -
Java多线程基础篇
2016-04-20 14:52 228在并发编程 ...
相关推荐
哈希映射实现了常数时间的插入、查找和删除操作,常见于Java的`java.util.HashMap`和C++的`std::unordered_map`。理解哈希冲突及其解决方法(开放寻址法、链地址法)是掌握哈希映射的关键。 4. **拼图算法(Puzzle ...
List、ArrayList、Vector及map、HashTable、HashMap是Java容器类中的几个重要的接口和实现类,了解它们之间的区别是非常重要的。 首先,我们来看List和ArrayList的区别。List是一个接口,而ArrayList是一个实现了...
虽然JavaScript原生的`Map`对象提供了类似的功能,但在某些场景下,开发者可能需要自定义HashMap来满足特定的需求,例如优化性能或者实现特定的算法。本篇文章将深入探讨如何在JavaScript中实现HashMap以及如何进行...
在Rust编程语言中实现FlowMap算法,可以利用Rust的强大性能和内存安全特性,为处理大规模数据流提供高效解决方案。下面将详细介绍FlowMap算法的基本概念、Rust语言的特点以及如何在Rust中实现FlowMap。 FlowMap算法...
java 集合和泛型 1. Map接口 2. HashMap底层实现 3. Hash数据结构和算法 4. 红黑树数据结构和算法
在IT领域,高效的数据结构和算法是解决复杂问题的关键。本话题主要关注如何利用HashMap这一数据结构来实现词典查询,以提供快速、便捷的字典服务。HashMap是Java编程语言中的一种内置数据结构,它提供了O(1)的平均...
在多线程环境下,如果需要使用HashMap,可以使用Collections的synchronizedMap()方法将其转换为同步的Map,但这并不意味着所有操作都是线程安全的,尤其是迭代操作。为了防止“fail-fast”迭代器引发的...
3. **自定义或优化算法**:对于性能要求极高的应用,可以考虑开发新的算法或对现有算法进行优化,以适应特定需求。 ### 三、DFA算法实现敏感词过滤 #### 第一步:敏感词库初始化 在Java中,我们可以使用HashMap...
get(key) -> get value associated with key set(key,value) -> 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()
HashSet 和 HashMap 之间有很多相似之处,对于 HashSet 而言,系统采用 Hash 算法决定集合元素的存储位置,这样可以保证能快速存、取集合元素;对于 HashMap 而言,系统 key-value 当成一个整体进行处理,系统总是...
Java 8 HashMap 的扩容算法是通过 resize() 方法来实现的,该方法将旧的数组扩容到新的数组中,并对原有的数据进行转移。转移过程中使用 lo 链表和 hi 链表来存储元素,以确保元素的分布均匀,提高 HashMap 的性能。
HashMap 是 Java 集合框架中一个非常重要的类,它实现了 Map 接口,并提供了基于哈希表的存储方式。与其它 Map 实现不同的是,HashMap 允许使用 `null` 键和 `null` 值。这种灵活性使得 HashMap 成为许多应用程序中...
综上所述,构建一个无锁线程安全的HashMap需要理解并发编程的基本原理,熟悉Go的原子操作,以及对数据结构和哈希算法的深入掌握。通过这些知识,我们可以设计出一个为读取访问优化的HashMap,满足高并发场景的需求。
HashMap是Java集合框架的一个重要组成部分,它实现了Map接口,能够存储键值对映射。在Java编程语言中,最基本的数据结构有两种:数组和引用(模拟指针)。所有的复杂数据结构都可以基于这两种基本结构构建出来,...
LRU(Least Recently Used)算法是一种常见的页面替换算法,用于解决计算机内存有限而数据页数量过多的问题。...通过学习和理解LRU算法的实现,我们可以更好地理解和处理内存限制问题,提高系统的性能和效率。
"Java基于余弦方法实现的计算相似度算法示例" 本文主要介绍了Java基于余弦方法实现的计算相似度算法,简单说明了余弦相似性的概念、原理,并结合实例形式分析了Java实现余弦相似性算法的相关操作技巧。 一、余弦...
在实际开发中,根据具体需求,可以考虑使用更优化的数据结构或算法来提高性能。例如,如果需要频繁进行这种反向查询,可以维护一个额外的结构,如TreeMap或使用Guava库的BiMap,以支持高效的双向查找。
蚁群算法的参数调整非常重要,参数的设置会直接影响算法的性能。在本文中,我们讨论了信息素权重、路径权重和信息素蒸发率对结果的影响。通过实验,我们发现了 2/5/0.5 的参数设置能够达到较好的效果。但是,这只是...
在Go编程语言中,数据结构的选择对于程序性能至关重要,尤其是哈希映射(HashMap),它在许多场景下作为快速查找和存储数据的关键工具。本文将深入探讨标题提及的"Go-rhh",这是一个专为Go设计的简单而高效的HashMap...
Java实现的决策树算法完整实例 决策树算法是机器学习领域中的一种常见算法,主要用于分类和预测。Java实现的决策树算法完整实例中,主要介绍了决策树的概念、原理,并结合完整实例形式分析了Java实现决策树算法的...