Jam*_*zba 8 java cpu optimization hashmap data-structures
代码说的不仅仅是文字,因此:
final int size = 100;
Map<Integer, String> m = new HashMap<>(size);
for (int i = 0; i < size; i++) m.put(i, String.valueOf(i));
为什么HashMap内部调用时间!resize() 212(感谢Andreas在内部确认JVM使用HashMaps,21个cals中的19个来自其他进程)
resize()我的申请仍然无法接受两次通话.我需要对此进行优化.
如果我是一个新的java开发人员,我首先直观地猜测HashMap构造函数中的"容量"意味着它是我(HashMap的使用者)将要放入Map中的元素数量的容量.但是这是错误的.
如果我想优化我对HashMap的使用,以便它根本不需要自己调整大小,那么我需要非常了解HashMap的内部结构,以确切知道HashMap存储桶阵列需要多么稀疏.这在我看来很奇怪.HashMap应隐式为您执行此操作.这是OOP中封装的全部要点.
注意:我已经确认resize()是我的应用程序用例的瓶颈,所以这就是为什么我的目标是减少调用resize()的次数.
问题:
如果我知道我要预先在地图中输入的确切数量.我选择了什么容量,以防止任何额外的呼叫resize()操作？有点像size * 10？我还想了解为什么这样HashMap设计的背景.
编辑:我被问到很多为什么这个优化是必要的.我的应用程序在hashmap.resize()中花费了大量的CPU时间.我的应用程序使用的哈希映射被初始化,其容量等于我们放入其中的元素数量.因此,如果我们可以减少resize()调用(通过选择更好的初始容量),那么我的应用程序性能会得到改善.
And*_*eas 10
默认的加载因子是0.75,即3/4,这意味着当添加了100个值中的75个时,将调整内部哈希表的大小.
仅供参考: resize()只被叫两次.一旦添加第一个值,一旦它达到75%满.
要防止调整大小,您需要确保第100个值不会导致调整大小,即size <= capacity * 0.75aka size <= capacity * 3/4aka size * 4/3 <= capacity,所以要确保:
capacity = size * 4/3 + 1
有size = 100,这意味着capacity = 134.
如有疑问,请阅读文档.对于文档HashMap解释的折衷initial capacity和load-factor相当不错.
根据文档,如果initCapacity = (maxEntries / loadFactor) + 1在添加条目时不会发生重新操作操作.凡在此情况下,maxEntries是100因为你指定和loadFactor会默认加载因子.75.
但除了设置初始大小以避免重新散列(resize())之外,您应该仔细阅读文档HashMap以便正确调整它,同时考虑初始容量和负载因子.
如果您关心查找成本而不是空间,那么如果您愿意,可以尝试使用较低的loadFactors .5或更低的s .在这种情况下,您将使用以下两个参数创建哈希映射:
final float loadFactor = 0.5;
final int maxEntries = 100;
final int initCapacity = (int) maxEntries / loadFactor + 1;
new HashMap<>(initCapacity, loadFactor);
(强调我的)
HashMap的一个实例有两个影响其性能的参数:初始容量和负载因子.容量是哈希表中的桶数,初始容量只是创建哈希表时的容量.加载因子是在自动增加容量之前允许哈希表获取的完整程度的度量.当哈希表中的条目数超过加载因子和当前容量的乘积时,哈希表将被重新哈希(即,重建内部数据结构),以便哈希表具有大约两倍的桶数.
......
作为一般规则,默认负载系数(.75)在时间和空间成本之间提供了良好的折衷.较高的值会减少空间开销,但会增加查找成本(反映在HashMap类的大多数操作中,包括get和put).在设置其初始容量时,应考虑映射中的预期条目数及其加载因子,以便最小化重新散列操作的数量.如果初始容量大于最大条目数除以加载因子,则不会发生重新加载操作.