数据结构-hash表

hash表功能

hash表是一种表,用于快速查找。在程序运行时,可以通过空间来换取时间,hash表就是这样一种,使用空间来换取时间的数据结构。hash表通过<key-value>的键值对的方式来访问数据。通过key值来访问数据,实现最快的访问。
hash表本质上,就是数组。链表也是可以用数组的方式来实现的,本质也是数组。

hash表的构成

思考一下,如果hash表的key就是从1、2、3的方式排序,那么查找value值是不是很简单。然而实际使用的时候并不容易这么刚好的情况,如果可以把key的值转换为1、2、3这样的中间值,通过中间值来进行排序,再去数组的对应位置找数据岂不是更快了呢。
即将原本的key-value,加一个中间商 hash值,对应关系就变为


hash函数.jpg

hash值是为了更快查找到目标数据而来的。

hash表的查找

hash表的查找.jpg

这是一个简单的hash表,hash函数为取十位作为hash值,通过这样的hash转换后,每个值都有一个更容易查找的位置。

hash表冲突

由于hash值是通过hash函数转换而来的,无法保证每个key都会有独一无二的hash值,可能有多个key对应同一个hash值,这种情况就叫做hash冲突,hash冲突有多种解决方案。

后移法

如果想要放置的key位置被放置了,则将当前的key对应数据放在后面最近的一个位置上。记住,hash的本质就是数组,此时的数组并不是每个位置都是满的,会有空位,这个位置被占了,就往后面一个位置挪就好了。


hash表-后移法.jpg
链表法

将对应同一个hash值的key都放在同一个节点后续,使用链表的方式进行保存。


hash-链表法.jpg

hash表查找

hash查找,最终目的是通过key查找到目标value,先通过hash值快速定位大概位置。如果hash值位置的key值与查找key是一致的,则查找到了。如果不对,则根据保存方法,去下一个节点查找,直到对应key的位置,就找到了对应value。
以链表法的hash方式为例,如要查找key为15的数据
第一步,先去hash值为1的位置查找。发现此处key不为15,则去下一个链表节点查找。
第二步,查找到此处key为15,查找完成,否则继续去链表下一个节点查找。

hash表的扩容

hash本质是数组,这个数组大小是变化的,不能够让这个数组塞得满满的,数组不够大的话,每个位置下面链表很长,那还是需要一个个遍历,就无法达到快速查找的目的了。HashMap的扩容方式,是当负载因子达到0.75的时候,将数组扩大为原来的两倍,再重新排列hash表。负载因子表示占用位置/总位置的比例,比如数组大小10,被占用7个,则负载因子为0.7。

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 什么是哈希表 哈希表是以 Key-Value 形式存储的的数据结构,当我们需要查找某个值,只需要输入相应的Key值...
    tanghomvee阅读 535评论 2 1
  • 1. 什么是Hash表 先看一下hash表的结构图: 数组 + 链表 哈希表(Hash table,也叫散列表),...
    酱油瓶2阅读 13,385评论 0 14
  • 前言 哈希(散列)技术既是一种存储方法,也是一种查找方法。然而它与线性表、树、图等结构不同的是,前面几种结构,数据...
    羽裳有涯阅读 260评论 0 0
  • 一些概念 数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系,并对这种结构定义相应的运算,而且确保经过这...
    Winterfell_Z阅读 5,979评论 0 13
  • 不要听,接收。 声音是震动,震动是能量。 何止十万八千里!那恳切的信息,估计来自无限远的远方。 大音,稀声。 不要...
    思考空间阅读 298评论 0 3