一个小问题，对于HashMap的困惑。

Question

先说一下自己对HashMap的理解：
    HashMap数据结构是，数组（数组的角标就是hash码），数组中放List。get()方法是通过计算hash码来寻找，所以寻找非常快。（如果List中有多个就用eques()方法，做线性查询）。问题就是，
1.在HashMap初始化的时候不是要构建一个庞大的数组?
虽然大部分元素为null,难道就是用空间复杂度来换取时间复杂度？ 2.这个数组的长度要如何制定？主要是第1个问题。

Answer 1

你的理解基本正确。
HashMap的数据结构是一个Entry数组，数组的缺省长度是16
也就是说你用new HashMap()的时候，它会创建一个长度为16的Entry数组
而Entry的数据结构是一个单向链表当你put的时候，它先用key对象的hashCode计算应当放到这16个中的哪一个，HashMap用的方法是位与(&)，其实跟求模差不多。
当你get的时候，也先要计算会放在哪个Entry中，然后再顺序查找。从理论上讲Entry数组的长度越大，查找就会越快，但耗费的内存就会越多。
但如果要存入的对象非常多，那么Entry数组的缺省长度很显然是不够的，你可以用new HashMap(xxx)来指定长度，不超过2的30次方都是允许的。

Answer 2

http://blog.csdn.net/ZangXT/archive/2008/11/25/3371973.aspx曾经分析过一点，可以看看

Answer 3

Hash的目的就是为了分组，提高查找效率。所以肯定要牺牲大量的空间。是值得的。

Answer 4

HashMap
public HashMap()构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap。 

Answer 5

谢谢，原来不是直接hash码来的，啊还要求模的啊。终于知道了谢谢2楼。

Answer 6

看来这个hashMap的查询速度，关键点还是在 散列函数的算法。 其次就是负载因子了。 看来初始长度是最次要的了。

Answer 7

这你就片面了,HashMap在构造函数中有一个loadFactor的参数，这个参数的代表哈希表的负载量。系统默认的是0.75，所以在当哈希表里边包含的对象多于 内置Entry数组的长度的0.75倍时，Entry数组就会自动扩大（创建一个新的更大的数组，把旧的数组里边的东西拷贝到新的里边），诚然，负载参数越大，越节省空间，但是查找的速度越慢（接近于线性）。所以任何的东西都有其两面性的。