dha*_*ram 17
问题中的最大阈值称为加载因子.
建议负载系数约为0.75.加载因子定义为(m/n),其中n是哈希表的总大小,m是在需要增加基础数据结构的大小之前可以插入的首选条目数.
可以在两种情况下进行重组:
当前的m'/ n比率增加超过负载系数
M'/ n比率下降到非常低的值,比如0.1
在两种情况下,m'是当前的条目数.此外,两种情况都要求将当前条目转移到更大或更小的哈希表中.
在问题的上下文中,重新散列是将哈希函数应用于条目以将它们移动到另一个哈希表的过程.可以使用之前使用的哈希函数或完全使用新函数.
请注意:发生碰撞时也会进行重新散列.(这也是处理碰撞的一种方式.)
要添加更多上下文和详细讨论,请访问我的博客Hashing Basics
小智 13
当地图中的元素数量达到最大阈值时,完成哈希映射的重新散列.
通常,载荷因子值为0.75,默认初始容量值为16.一旦元素数量达到或超过容量的0.75倍,则会发生地图的重新散列.在这种情况下,当元素的数量是12时,则发生重新散列.(0.75*16 = 12)
当发生重新散列时,可以使用新的散列函数或甚至相同的散列函数,但是存在值的桶可能会改变.基本上,当发生重新散列时,桶的数量大约加倍,因此必须放置值的新索引会发生变化.
在重新散列时,每个存储桶的链表按顺序颠倒过来.发生这种情况是因为HashMap不会在尾部附加新元素,而是将新元素附加到头部.因此,当发生重新散列时,它会读取每个元素并将其插入头部的新存储桶中,然后继续添加新地图头部的旧地图中的下一个元素,从而导致链接列表的反转.
如果有多个线程处理相同的哈希映射,则可能导致无限循环.
有关如何在上述情况下发生无限循环的详细说明,请参见:http://mailinator.blogspot.hu/2009/06/beautiful-race-condition.html
如果必须使用键对元素中插入的元素进行排序,则可以使用TreeMap.但是如果键的顺序无关紧要,HashMap会更有效.
小智 10
基本上,在创建哈希映射集时,请为其指定默认大小(10).在元素添加到地图中的后期阶段,在接近初始定义容量的某个阶段之后,需要ReHashing来保留性能.
为集合定义了LoadFactor(据说好.75),这指定了时间和空间的良好索引.
Java规范表明Good loadfactor值为0.75
因此假设您最多需要在哈希中存储10个元素,然后考虑Good Loadfactor .75 =在集合中添加7个元素后会发生重新散列.如果您在这种情况下的要求不会加入7,那么Rehashing永远不会发生.
如果在hashmap中存在非常大量的元素,那么创建具有足够容量的HashMap总是好的; 这比让它执行自动重组更有效.
RACE条件:在执行重新存储内部元素时,这些元素存储在给定存储桶的链接列表中.他们按顺序反转.假设有两个线程同时遇到竞争条件,那么第二个therad有可能在遍历时进入无限循环,因为订单已被更改.