转载

深入理解hashmap理论篇

之前有过一篇介绍java中hashmap使用的，深入理解hashmap，比较侧重于代码分析，没有从理论上分析hashmap，今天把hashmap的理论部分补充一下（之后应该还有两篇补充一篇讲红黑树一篇讲多线程）。

散列（哈希）函数到底是干嘛的？和哈希表是啥关系？其主要作用和应用场景到底在哪里？

简单来说散列函数主要就是：将一个二进制串通过一定的算法计算以后得到一个新的二进制串。这个计算的方法就是散列函数。也叫哈希函数，得到的值就是哈希值

那么要设计一个散列函数还需要几个特性： 1.通过哈希值不能得到原始的值。这个很多人都清楚，比方说我们的密码都是md5以后存在服务器的，否则数据库被盗，大家的密码就都完蛋了，这个md5 其实就是一种哈希算法。

2.对于原始值来说，因为计算机中的任何对象，都是一串二进制值，所以要求哪怕是有一个bit的不同，得出来的哈希值也应该不同。

3.满足上面2个条件以后，最好散列冲突的概率要小，并且这个算法的速度要快。

那么哈希表和哈希函数的关系就显而易见：利用数组这种结构随机访问数据的时间复杂度为o(1)的优点，我们将数据经过哈希算法计算以后得到一个key值，这个key值就对应的数组的位置。这样以后我们查找数据只要把数据计算出来 key值就可以得到想要数组的位置，自然查找的效率就是o（1）了。

所以哈希表其主要目的其实就是为了解决快速查找的问题。其应用场景也主要围绕这个功能展开。这里简单举个例子：

1.负载均衡

最简单的负载均衡我们可以想到，无非就是建立一张表，表里面对应着客户ip地址和服务器ip地址。那这样每次有客户端请求进来，我们都去这个表里面查到对应应该分配的服务器ip，然后再把客户请求发到这个服务器ip上。那么很明显这样做非常不好，第一这个表会无限大，消耗存储空间，第二表大的时候查询效率也会变低，第三服务器扩容以后处理起来很麻烦。

那这里如果用散列函数来做就简单多了，我们只要把客户ip地址经过散列算法以后得出一个值，然后对服务器的个数取模就可以很快的建立这个 key-value关系。

更多的例子比如网络协议里面的crc校验，p2p的下载算法，甚至git中的commit id都是利用散列函数来做。

散列函数的碰撞冲突是怎么回事，一定发生吗？

简单来说，散列函数不管设计的有多优秀，散列冲突都一定无法避免。因为我们容量是有限的。大家可以百度下抽屉原理，举个例子，我们有5个橘子，你只有4个抽屉，那你必定会有一个抽屉里面有2个橘子。

对于哈希算法也是一样，因为我们哈希算法的出来的值是固定长度，所以肯定数量是有限的，比如说md5出来的值就是128个bit。固定长度。如果你有超过这个长度的数据要经过md5算法计算哈希值，那么肯定至少会有重复的！

散列函数的碰撞冲突如何解决？

主要有两种方法，一种是开放寻址法（java中的ThreadLocalMap），一种是链表法（hashmap）。其中前者现在用的不多，有兴趣的同学可以学学看。我们重点讲链表法。所谓链表法其实就是在发生散列冲突的时候，把相同哈希值的数据存放在链表中。

链表大家都知道的，查找复杂度就是o(n)了，所以可想而知，如果你脸不好哈希冲突的次数过多，那我们o（1）的哈希表的查找效率就会下降到o(n)，jdk新版本优化的hashmap就是优化了这个问题，当这个解决冲突的链表长度大于8的时候，就会自动转成红黑树（二叉搜索树的一种），红黑树的查找效率是o(logn),大家之前看二分查找的时候应该知道这个效率是很高的。查找大概42亿的数据也不过就32次左右。（红黑树后面我们再单独讲）

装载因子和动态扩容的关系是什么？如何理解

一般而言，装载因子这个值越大，那么就意味着对于一个哈希表来说，如果元素过多的情况下，装载因子大的哈希表空闲位置就越少，那么哈希冲突的概率就越大。对于大部分采用链表法来解决哈希冲突的哈希表来说，哈希冲突概率大那么就会导致链表过长，这样查找的效率就会无限变低。

所以当我们发现装载因子已经过大的时候，我们就可以扩容这个哈希表，比如java里的hashmap扩容就是扩容一倍的大小，比方说数组长度一开始16，扩容以后就变成32.

对于数组扩容来说，其实没啥好说的，大家都会，但是哈希表的扩容还涉及到重新计算哈希值，这样数据在扩容以后的哈希表里的位置和之前的位置就有可能不同。这个步骤叫做重新计算哈希值。

所以动态扩容是一个比较耗时的操作：重新申请新的数组空间，重新申请计算哈希值（也就是得出在数组中的位置），最后把老数组的数据拷贝到新数组（解决哈希冲突的链表里的值也可能要搬迁到新数组里面）

java中的LinkedHashMap是用链表实现的哈希表吗，不然为啥带个Linked的关键字？

废话，当然不是。哈希表的基础存储一定是用数组，否则无法实现o(1)的查询效率。但是LinkedHashMap和普通hashmap最大的区别就是LinkedHashMap除了维护了一个数组以外，还维护了一个额外的双向链表。熟悉android的人都知道，很多开源的图片缓存框架里面的LRU算法都是用的LinkedHashMap来做数据结构，比方说对于一个图片缓存框架来说，当缓存到达MAX的时候，就需要把最近最少使用的图片移出缓存。然后把新来的放进缓存中，这个过程就是一个简单的LRU算法，而用LinkedHashMap则可以轻松的完成这个需求（LinkedHashMap具体怎么调用就不说了，这里只说实现的原理以及和hashmap有什么不同）

简单来说，HashMap的结构如下：

基础存储用数组，如果有同样的哈希值的数据那么就用单链表串起来。所以hashmap的存储基本结构就是四个字段

hash值---------->key------>value------->next

其中next指针就是用来如果出现重复hash值哈希冲突的情况，用于构造单链表的。

而LinkedHashMap，为了实现LRU，还额外实现了一套双链表来保证。也就是说：

LinkedHashMap的基础存储也是用数组，只不过，除了用数组，他还单独维护了一个双向链表，这个双向链表就把整个（数组+单链表是java中哈希表的基础实现）给串起来，而实现LRU的数据结构就是双向链表。

所以大家可以猜到LinkedHashMap的存储基本结构是

双链表中的before指针-->hash值---------->key------>value------->next---->双链表中的after指针。

哈希表还有什么妙用？

额，生产环境上其实有很多地方都在用hashmap，大家可以自行搜索一下，这里仅奉送一个简单的leetcode算法题。

两数求和问题：

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]

正常情况我们想的是双循环暴力遍历来解决，复杂度很容易就O(n2),其实用hashmap 可以很方便的解决两数，三数，甚至是四数求和问题。对于两数求和问题来说，用map的复杂度就仅仅只有o(n)了。

既然想速度快一点只遍历一次，那么其实既然已经确定了target的值，那么遍历一次，我们只要找一下是否有target-数组[i]的值即可。

/**
     *  算法核心思想：new一个map，map的key是数组元素的值，value是数组元素的位置也就是俗称的index
     *  然后我们遍历数组的时候 用target的值 --当前数组的值（wanted的值） 就是我们想要的值。如果在map里面找到了，
     *  那么就直接返回当前数组的index和 map里面这个wanted的值的value（value就是数组的index）即可。
     *
     *  如果map里找不到这个wanted的值，那么就把当前这个数组的元素放到map里面即可
     * @return
     */
    public int[] twoSum(int[] nums, int target) {
        Map map = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            int wanted = target - nums[i];
            if (map.containsKey(wanted)) {
                return new int[]{i, (int) map.get(wanted)};
            }
            map.put(nums[i], i);
        }
        return null;
    }
复制代码