阅读 419

深入理解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;
    }
复制代码

关注下面的标签,发现更多相似文章
评论