HashMap 数据结构

  hashMap用了一个名字为table的数组；还有若干个名字为entry的链表。看hashMap是如何应用这些数据结构的。用插入<key,value>举例：hashMap首先会通过key得到其hashCode，具体的hash函数就不说了（因为没多大意义）；然后把key的hashCode%table.length，就是拿hashCode模table数组大小，得到的余数就是key所在table数组中的下标（实际不是key的下标，是entry类）；但这样做有个问题，可能不同key却有一样的hasdCode，所以求余后其必然会得到相同的下标，那如何存储了？有两个办法，一种是利用开放地址法，就是说后来相同的hashCode去找先来hashCode所在下标的相邻下标。说的有点绕口，举个例子，比如<1,2>已经存在table数组的31的位置上了，再来一个<101,102>，其通过哈希后说：我也应该在31的位置上，但是table说，你后来，你再在31附近找个空位安置下吧。当然，具体怎么找，有规则的。另外一种方式就是链地址法，还是拿以上的例子说，<101,102>来到时，发现31的位置已经被占了，这时table说：<1,2>，你带下<101,102>；其实就是要<1,2>把<101,102>的引用存储了。但是<1,2>说：我怎么存储<101,102>的引用了，我没位置呀。所以table说：我给你们每个壳(entry类)吧，把你们都封装了；于是就有了 entry类。

    那hashMap是使用那种方式了。先分析下开放地址和链地址法的优缺点。开放地址法一般需要2倍实际数据大小的空间，因为要留下一定的空闲地址去存储相同hashCode的<key,value>；并且查找相邻空闲地址也是一项比较费时间的任务；链地址法，就不需要2倍的空间（table数组），但是需要存储额外的信息，比如next信息；总体来看，链地址法好点（关键是节省了查找相邻地址的时间），所以，hashMap用的是链地址法。

还有问题，hashMap为什么用数组存储index（hashCode%table.length）了，而不用链表了？

因为数组有固定大小限制，而链表没有，而且map是没有限制大小的？这主要考虑了查找效率的问题。从前面的分析可以看到，因为key的hashCode%table.length直接做为entry的下标，所以其查询key的速度很快，只要O(1)的时间；如果是链表，要一个一个的排查对比，需要O(N)的时间；这之间的效率，相差太远了。所以，hashMap用了数组。

最后一个问题，那数组的固定大小如何解决了？

hashMap在每次插入数据前，会检查table数组的实际容量，如果实际容量>=初始容量，则把 table的初始容量扩为原来的2倍，这时，就需要一个一个复制原来的数据项了，这是比较费时的！所以，初始容量很重要。