内容简介:之前有过一篇介绍java中hashmap使用的,深入理解hashmap,比较侧重于 代码分析,没有从理论上分析hashmap,今天把hashmap的理论部分补充一下(之后应该还有两篇补充 一篇讲红黑树一篇讲多线程)。简单来说 散列函数主要就是:那么要设计一个散列函数还需要几个特性: 1.通过哈希值不能得到原始的值。 这个很多人都清楚,比方说我们的密码都是md5以后存在服务器的,否则数据库被盗, 大家的密码就都完蛋了,这个md5 其实就是一种哈希算法。
之前有过一篇介绍 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; } 复制代码
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- 【1】JavaScript 基础深入——数据类型深入理解与总结
- 深入理解java虚拟机(1) -- 理解HotSpot内存区域
- 深入理解 HTTPS
- 深入理解 HTTPS
- 深入理解 SecurityConfigurer
- 深入理解 HTTP 协议
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
JavaScript & jQuery
David Sawyer McFarland / O Reilly / 2011-10-28 / USD 39.99
You don't need programming experience to add interactive and visual effects to your web pages with JavaScript. This Missing Manual shows you how the jQuery library makes JavaScript programming fun, ea......一起来看看 《JavaScript & jQuery》 这本书的介绍吧!