数据结构|解析数据结构-散列表
散列表
数组
操作数据(增加): 是将原数组的数据复制一份,再加上增加的对应位置的数据,形成一个新的数组。所以较慢。
查找数据:数组是有下标的,根据下标进行查找。
形式:
文章图片
链表
一个链表的数据单元,结构是存储着一个数据,以及下一个链表单元数据的地址。
- 操作数据(增加):如 a-b。在ab之间增加一个c,增加c这个单元,并修改c的“下一个链表单元的地址”为b的地址,并将a的“下一个链表单元的地址”修改为c的地址即可。
- 取出数据,根据上一个数据,才能找到下一个数据。比数组慢
文章图片
散列表
前面的两个数据结构是我们在数据结构中经常接触的各种结构的基础,散列表就是他们的结合
形式:
文章图片
Hash冲突:
当重复的值要插入时发现已经被占用时,就出现了冲突问题,如何解决?
散列函数:Hash函数(解决hash冲突问题)
- 开放寻址
缺点
- 体积局限,装不下时需要进行扩容
文章图片
- 拉链
优点
- 使用简单
- 插入方便
- 体积局限,装不下时需要进行扩容
文章图片
例子
【数据结构|解析数据结构-散列表】java中的hashmap就使用到了散列表
推荐阅读
- 有些人真的走着走着就散了
- Quartz|Quartz 源码解析(四) —— QuartzScheduler和Listener事件监听
- 离散之悟
- Java内存泄漏分析系列之二(jstack生成的Thread|Java内存泄漏分析系列之二:jstack生成的Thread Dump日志结构解析)
- [源码解析]|[源码解析] NVIDIA HugeCTR,GPU版本参数服务器---(3)
- Android系统启动之init.rc文件解析过程
- 《数据结构与算法之美》——队列
- 小程序有哪些低成本获客手段——案例解析
- 【散文诗】河流
- Spring源码解析_属性赋值