美文网首页Java集合源码分析数据结构Java集合源码分析
Java集合源码分析之基础(二):哈希表

Java集合源码分析之基础(二):哈希表

作者: 大大纸飞机 | 来源:发表于2018-04-16 15:03 被阅读1396次

    无论是数组还是链表,其对数据的查询表现都比较无力,要想知道一个元素是否在数组或链表中,只能从前向后挨个对比。在后续将会分析的二叉排序树中,还会将数据排序以进行二分查找,将时间复杂度从O(n)降低到O(lg n)

    出现这个问题的根源在于,我们没有办法直接根据一个元素找到它存储的位置,那有没有办法消除这个对比的过程呢?哈希表就是解决查询问题的一种方案。

    什么是哈希表与Hash函数

    通俗来讲,哈希表就是通过关键字来获取数据的一种数据结构,它通过把关键字映射为表中的位置来获取元素,这种映射主要是使用Hash函数。

    因为不同需求需要的key类型不一致,可能是int,可能是String,也可能是其他任意对象。但是内存地址却不能以这些对象来寻址,因而Hash函数的作用就是把这些对象通过合理的方式转为int类型,从而完成数据的存储。Hash函数需要保证的是对于相同的key,其计算结果总是相同的。

    这个过程就好比我们用拼音查字典。如果要查一个字,我们不会从第一页到最后一页挨着看,这将需要很长的时间,而是根据其发音先在拼音表中找到对应的页数,直接定位到对应的页即可。当然,由于有许多发音一致的汉字,所以我们可能依然需要逐个对比,但这复杂度就小太多了。

    哈希表的过程就和上述例子一致,我们根据元素的key,通过hash函数直接定位其位置。然而类似于许多汉字的发音一致一样,也会有许多的key通过hash函数定位的结果一致,这就是发生了所谓的哈希碰撞

    解决哈希碰撞的方法

    目前比较通用的方法,就是使用数组+链表组合的方式。当出现哈希碰撞时,在该位置的数据就通过链表的方式链接起来,如下图所示:

    哈希表的结构示意图
    在JDK1.7及之前的版本中,HashMap的存储结构和上图是一致的,在JDK1.8之后还加入了红黑树以进一步优化,在后续文章中我们会对其进行详尽的分析。

    哈希表的优缺点

    哈希表是一种优化存储的思想,具体存储元素的依然是其他的数据结构。设计良好的哈希表,能同时兼备数组和链表的优点,它能在插入和查找时都具备良好的性能。然而设计不好的哈希表,有可能会出现较多的哈希碰撞,导致链表过长,从而哈希表会更像一个链表。还有当数据量很大时,为防止链表过长,就需要对数组进行扩容,这时就涉及到了数组的拷贝,其对性能的影响也很严重,所以需要提前对可能的情况有良好的预测,才能真正发挥哈希表的优势。

    相关文章

      网友评论

      • ZzzBj:看了评论发现大家困惑的地方都一样,发生哈希碰撞后取值都时候是怎么处理的,继续看下篇:smiley:
        大大纸飞机:@ZzzBj 想知道这个处理方式,可以直接看后续HashMap,碰撞后,存储在链表或者红黑树中,遍历即可。
      • d245956d0304:个人建议,每篇文章加上下一章的链接效果较好~
        大大纸飞机:@我就是马云飞 感谢建议哈,得空我就加上~
      • d245956d0304::joy: 把博主博客偷偷整理到自己有道云里去
        大大纸飞机:@我就是马云飞 不要在云里落灰就行
      • 小学留了三年:那张哈希表可以再讲的细致些,还有哈希碰撞,结合图讲会比较好。
        大大纸飞机:感谢建议,近期会进行修改哈
      • chendroid:哈希表是结合了数组和链表的长处,记得之前看过一篇文章说的是如何集成两者的优势
        大大纸飞机:是的,主要是利用了数组的RandomAccess特性,然后吸取了链表的无限扩容
      • g小志:第三篇打卡,我觉得应该对哈希碰撞多讲下,尤其是这个哈希表的结构示意图。我想问下,这个最后出现哈希碰撞后,形成的链表,之后的查询,就是按照链表的查询去走的吗?
        大大纸飞机:@g小志 感谢建议,这篇文章确实比较简略,过几天我会更新一下,如果着急看的话,可以读后续的hashmap,在那里你可以找到答案

      本文标题:Java集合源码分析之基础(二):哈希表

      本文链接:https://www.haomeiwen.com/subject/gnunhftx.html