关于HashMap的加载因子

看API的时候，突然看到HashMap里面有一句：
通常，默认加载因子 (.75) 在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数 HashMap 类的操作中，包括 get 和 put 操作，都反映了这一点）。
==========================================================================================================
想好久也不明白：加载因子过高为何会导致查询成本的增加？？？
望解答！

15 个解决方案

#1

答:加载因子是表示Hsah表中元素的填满的程度.若:加载因子越大,填满的元素越多,好处是,空间利用率高了,但: 冲突的机会加大了.反之,加载因子越小,填满的元素越少,好处是: 冲突的机会减小了,但:空间浪费多了.

冲突的机会越大,则查找的成本越高.反之,查找的成本越小.因而,查找时间就越小.

因此,必须在 "冲突的机会"与"空间利用率"之间寻找一种平衡与折衷. 这种平衡与折衷本质上是数据结构中有名的" 时-空"矛盾的 平衡与折衷.

以上仅供你参考

#2

冲突的机会?
========================
是指什么冲突？get和put操作

#3

引用 1 楼 jiangnaisong 的回复:

答:加载因子是表示Hsah表中元素的填满的程度.若:加载因子越大,填满的元素越多,好处是,空间利用率高了,但:冲突的机会加大了.反之,加载因子越小,填满的元素越少,好处是:冲突的机会减小了,但:空间浪费多了. 

冲突的机会越大,则查找的成本越高.反之,查找的成本越小.因而,查找时间就越小. 

因此,必须在 "冲突的机会"与"空间利用率"之间寻找一种平衡与折衷. 这种平衡与折衷本质上是数据结构中有名的"时-空"矛盾的平衡与折衷. 

…

dd

#4

引用 2 楼 fulianglove 的回复:

冲突的机会? 
======================== 
是指什么冲突？get和put操作

答:所有的Hash表都理论上都不可能避免冲突(无论Hash函数如何设计).当表中都 快填满时(加载因子大), 再填入新的元素时,冲突的机会将很大.
JAVA的HashMap当put(..)时若产生冲突(即:两个不同的对象,但其hadhCode相同,表明想占用表中同一个位置空间),则目前的实现中是:占用Hash表中同一个位置空间的冲突的元素,用一个链表来链起来.这样:当get(...)时, 若有冲突,就要访问链表了(这样,一旦有冲突,put(..)与get(...)都要和链表打交道,成本当然就高了)

因此:要尽最大努力,减少冲突的机会

#5

引用 4 楼 jiangnaisong 的回复:

引用 2 楼 fulianglove 的回复:
冲突的机会? 
======================== 
是指什么冲突？get和put操作 
 
答:所有的Hash表都理论上都不可能避免冲突(无论Hash函数如何设计).当表中都快填满时(加载因子大),再填入新的元素时,冲突的机会将很大. 
JAVA的HashMap当put(..)时若产生冲突(即:两个不同的对象,但其hadhCode相同,表明想占用表中同一个位置空间),则目前的实现中是:占用Hash表中同一个位置空间的冲突的元素,用一个链表…

谢谢！懂了些

#6

1楼和4楼的回答，让人受益！

#7

看数据结构课本，再理解下Hash表的基本概念。

#8

学习了 最近正在看相关的书（Java程序设计与数据结构导论） 嘿嘿

#9

LZ有机会可以看看我blog中有详细阐述。
http://yeshucheng.blogjava.net

#10

学习了

#11

引用 9 楼 yeshucheng 的回复:

LZ有机会可以看看我blog中有详细阐述。 
http://yeshucheng.blogjava.net

非常感谢！！！！

#12

很好，学习了，解释的很清楚

#13

学习了

#14

9楼的BLOG不错！
THANKS!

#15

一群小菜鸟....