散列表

散列表是最有用的数据结构之一。

散列函数:

散列函数是这样的函数,无论你给它什么数据,他都给你返回数字。用专业术语来表示的话,就是,散列函数“将输入映射到数字”。

散列函数必须满足的要求:

  1. 它必须是一致的。假如你输入的apple得到的是4,那么你每次输入apple得到的都是4.
  2. 它应将不同的输入映射到不同的数字。如果你每次输入都能得到相同的数字,那么这就不是一个好的散列函数。

散列函数的用处:

假如说你现在创建一个空数组,0-4,你将在这个数组中存储商品价格。你第一次将apple作为输入交给散列函数,散列函数输出3,我们就知道apple的价格存储在数组的索引3处;然后你将milk交给散列函数,散列函数输入0,我们就知道milk的价格存储在数组的索引0处。如此下去,直至将数组填充完。

现在,加入你要知道avocado的价格,你给avocado输入交给散列函数,散列函数输出2,就相当于告诉你avocado的价格位于数组的索引2处,直接查找就能获取到。

散列函数之所以能准备的指出价格的存储位置,具体原因如下:

  • 散列函数总是将相同的输入映射到相同的索引。每次你输入apple,得到的都是同一个数字。因此,你可以首先使用它来确定将apple存储在什么地方,并在以后使用它来确定apple的价格存储在什么地方。
  • 散列函数将不同的输入映射到不同的索引。apple映射到索引4,milk映射到索引0.每种商品都映射到数组的不同位置,让你能够将价格存储到这里。
  • 散列函数知道数组有多大,只返回有效索引。如果数组包含5个元素,散列函数就不会返回无效索引100.

使用散列函数和数组创建的数据结构就叫做散列表(hash table)。数组和链表都被直接映射到内存,但散列表更复杂,它使用散列函数来确定元素的存储位置。散列表也被成为散列映射、映射、字典和关联数组。散列表的速度很快!数组可以立刻获取数组中的元素,而散列表也使用数组来存储数据,因此获取元素的速度与数组一样快。

作为开发人员,根本不需要自己去实现散列表,任何一个优秀的语言都提供了散列表的实现。比如python的dict(字典)类型,php的array(数组)类型.散列表是由键和值组成的,比如说上面自己构建的散列表中商品就是键,而价格就是值。

对于同样的输入,散列表必须返回同样的输出,这一点很重要。如果不是这样的,那么就无法查找到你在散列表中添加的元素。

散列表适合用于:

  • 模拟映射关系;
  • 防止重复;
  • 缓存/记住数据,以免服务器再通过处理来生成它们。

散列表的冲突

如果给两个键分配的位置相同,这种情况称为冲突(collision)。处理冲突的方式很多,最简单的办法就是:如果两个键映射到了同一个位置,就在这个位置存储一个链表。但是如果一个散列表中将所有元素存储到一个链表中的时候,散列表的速度将会很慢。所以这里面就有两个经验教训:

  1. 散列函数很重要。前面的散列函数将所有的键都映射到一个位置,而最理想的情况是,散列函数将键均匀地映射到散列表的不同位置。
  2. 如果散列表存储的链表很长,散列表的速度将急剧下降。然而,如果使用的散列函数很好,这些链表就不会很长。

散列表的性能:

  • 较低的填装因子。
  • 良好的散列函数。

填装因子:

散列表的填装因子=(散列表包含的元素数)➗(位置总数);散列表使用数组来存储数据,因此你需要计算数组中被占用的位置数。填装因子大于1意味着商品的数量超过了数组的位置数。一旦填装因子开始增大,就需要在散列表中添加位置,这被称为调整长度(resizing)。如果你有一个相当满的散列表,你需要调整他的长度,为此,你首先需要创建一个更长的数组:通常将数组增长一倍。接下来,你需要使用函数hash将所有元素都插入到这个新的散列表中。填装因子越低,发生冲突的可能性越小,散列表的性能越高。一个不错的经验规则是:一旦填装因子大于0.7,就调整散列表的长度。

良好的散列函数

良好的散列函数让数组中的值呈均匀分布,糟糕的散列函数让数值扎堆,导致大量的冲突。

小结:

散列表是一种功能强大的数据结构,其操作速度快,还能让你以不同的方式建立数据模型。

  1. 可以结合散列函数和数组来创建散列表。
  2. 冲突很糟糕,应该使用可以最大限度的减少冲突的散列函数。
  3. 散列表的查找、删除、插入都非常快。
  4. 散列表适合用于模拟映射关系。
  5. 一旦填装因子超过0.7,就该调整散列表的长度。
  6. 散列表可用于缓存数据。

 

暂无评论

发送评论 编辑评论


|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇