Java教程

算法学习(四)—— 散列表

本文主要是介绍算法学习(四)—— 散列表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

系列文章目录

第一章:二分查找及大O表示法

第二章:选择排序

第三章:递归和快速排序

第四章:散列表


文章目录

  • 系列文章目录
  • 前言
  • 一、散列表是什么
  • 二、散列表用途
  • 三、散列表内部机制
    • 1、冲突
    • 2、性能
  • 四、总结


前言

积累算法,记录学习


一、散列表是什么

散列表是最有用的基本数据结构之一。
前面所提及的简单查找和二分查找的运行时间分别是O(n)和O(logn),虽然二分查找已经很优美的节省时间了,但我们总期望查找时间更短,期望查找时间为0!!!因此散列表出现满足了我们的要求。

从数据结构来看散列表:我们需要每个元素包含两项内容,包括索引名字和该元素的值,即Key和Value。相信到这小伙伴就明白了,Python中给出了散列表的实现形式就是:字典dict

关于字典的讲解请参考我的Pythonic编程(六)——关于字典(dict)那些事

对于字典结构的数据,查询程序的运行时间是O(1)

二、散列表用途

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

三、散列表内部机制

1、冲突

当散列表过大时,同一个Key可能会来不同的value,程序自己的处理会使后来的值覆盖之前的值,但当我们不想这样做时,显然就变成了一个冲突。

处理它也简单,就是将重复映射的位置也存储为一个链表
在这里插入图片描述

2、性能

散列表(平均情况)数组链表
查找O(1)O(1)O(n)
插入O(1)O(n)O(1)
删除O(1)O(n)O(1)

在平均情况下,散列表的查找(获取给定索引处的值)速度与数组一样快,而插入和删除速度与链表一样快,因此它兼具两者的优点!但在最糟情况下,散列表的各种操作的速度都很慢。因此,在使用散列表时,避开最糟情况至关重要。为此,需要避免冲突。而要避免冲突,需要有:

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

四、总结

一般的编程语言都提供了散列表的实现形式,比如python的dict。
散列表是一种功能强大的数据结构,其操作速度快,还能让你以不同的方式建立数据模型。

这篇关于算法学习(四)—— 散列表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!