今天面试的时候突然被问到hashMap的具体实现，一脸懵逼的感觉，平时经常用的也不过是直接new一个hashMap，然后进行put(key,value)，get(key)和remove(key)操作，突然问道原理，所以还是需要恶补一下的。
首先说一下一些常用的数据结构
(1) 数组：数组的话一般需要开辟连续的空间，因此占用的内存严重，空间复杂度很大。但是查找的时候比较方便，可以使用二分查找，复杂度大概就是O（l）。当然删除和插入操作就比较复杂了，因为需要元素的移动
(2) 链表：不需要连续的存储空间，可以离散化存储。所以占用内存比较宽松，空间复杂度很小。但是查找的话比较复杂，需要从head开始遍历，判断是否是需要的元素。
(3) 栈：栈的话其实是从Vector扩展来的，而Vector则是implements 了List这个接口，因此其实上栈是基于链表来实现的。不过由于其特殊性，只有push(object)和pop()两个函数，因此操作的时间复杂度也是O(1)。
(4) hashMap：这个就是接下来的重点了。既然数组的查找方便，而链表的存储方便，那有没有一种方式，可以结合两者的优点。hashMap就是这样被实现出来的。
原文：http://www.cnblogs.com/dong-liu/p/7470739.html