散列，HashMap相关

电话面试

http://blog.csdn.net/paincupid/article/details/47670047

定义

把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值

解决碰撞

1. 链接
2. 开放寻址：线性探查，二次探查
3. 再哈希

时间复杂度

无冲突的hash table复杂度是O(1)，一般是O(c)，c为哈希关键字冲突时查找的平均长度，最坏情况仍然是O(N)

HashMap 的put方法的源码解析

（1）对key的hashcode进行hash计算，获取应该保存到数组中的index。
（2）判断index所指向的数组元素是否为空，如果为空则直接插入。
（3）如果不为空，则依次查找entry中next所指定的元素，判读key是否相等，如果相等，则替换久的值，返回。
（4）如果都不相等，则将此链表头元素赋值给待插入entry的next变量，让后将待插入元素插入到entry数组中去。
（5）当然HashMap里面也包含一些优化方面的实现，这里也说一下。比如：Entry[]的长度一定后，随着map里面数据的越来越长，这样同一个index的链就会很长，会不会影响性能？HashMap里面设置一个因子，随着map的size越来越大，Entry[]会以一定的规则加长长度。

PS: HashMap，也是先判断hashcode（hashcode相同，所以它们的table位置相同，‘碰撞’会发生。因为HashMap使用链表存储对象，这个Entry(包含有键值对的Map.Entry对象)会存储在链表中。），再判断equals，如果都相同，则表示：在集合添加中，认为是同一个"东西"，覆盖旧值。

HashMap的get方法源码解析

应该先从hashcode为什么要存在：提高速度
将对象放入到集合中时，就是先比较hashcode和后比较equals是否都相等

确定数组index：hashcode % table.length取模
按位取并，作用上相当于取模mod或者取余%。这意味着数组下标相同，并不表示hashCode相同。
return h & (length-1);

再散列rehash过程

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

你了解重新调整HashMap大小存在什么问题吗？（当多线程的情况下，可能产生条件竞争）
当重新调整HashMap大小的时候，确实存在条件竞争，因为如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部，而是放在头部，这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了，那么就死循环了。这个时候，你可以质问面试官，为什么这么奇怪，要在多线程的环境下使用HashMap呢？：）
Map m = Collections.synchronizedMap(new HashMap(...));

Hash应用例子

搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。），请你统计最热门的10个查询串，要求使用的内存不能超过1G。