HashMap原理简析

数据结构中的数组和链表被我们所熟知，其有优缺点刚好相反，HashMap综合了两者的特性，是一种寻址容易、插入/删除也容易的数据结构。

HashMap作为java中一种常用的数据结构，工作中会被经常使用，面试中问的也比较多。但一直只了解其特性，其实现原理也只停留在由数组、链接构成，key hash落在数组上，落在数组同一位置的以链表实现，但并没有深入思考，了解其具体实现。今天看到一篇博客，深入浅出的分析了HashMap的实现原理：

引用

http://blog.csdn.net/vking_wang/article/details/14166593

下面针对文章中的一些重点，做一些摘要和总结：
1、首先我们要注意到HashMap里面的一个静态内部类Entry，其重要的属性有 key、value、next，从其属性我们看出看出链表的影子

2、文中例子可以很好的理解HashMap的大致实现：第一个键值对A进来，通过计算其key的hash得到的index=0，记做:Entry[0] = A。一会后又进来一个键值对B，通过计算其index也等于0，现在怎么办？HashMap会这样做:B.next = A,Entry[0] = B,如果又进来C,index也等于0,那么C.next = B,Entry[0] = C；这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起。由此可以看出数组中存储的是最后插入的元素。

3、null key总是存放在Entry[]数组的第一个元素

4、确定数组index：hashcode % table.length取模

5、注意table初始大小并不是构造函数中的initialCapacity，而是>= initialCapacity的2的n次幂

6、散列rehash：当哈希表的容量超过默认容量时，必须调整table的大小。当容量已经达到最大可能值时，那么该方法就将容量调整到Integer.MAX_VALUE返回，这时，需要创建一张新表，将原表的映射到新表中。

7、哈希冲突：哈希计算就是努力的把比较大的数据存放到相对较小的空间中，HashMap中使用的是常用的哈希算法取模法。当哈希后落在了相同的位置，此时就产生了哈希冲突，HashMap中使用了链地址法。其它的解放方案还有：开放定址法（线性探测再散列，二次探测再散列，伪随机探测再散列）、再哈希法、建立一个公共溢出区。