美文网首页
4.数组、链表、散列表

4.数组、链表、散列表

作者: 小懒额 | 来源:发表于2018-05-28 22:15 被阅读0次

数据结构就是数据在内存中存储的一种方式,如果数据在内存中的存储是地址连续的,比如内存中从0到9的位置就用来存储1,2,3, ... 8,9,10这10个数字,那么这种存储方式就是数组。如果数据在内存中存储地址是不连续的,而是有空位就放的,但是每个位置都保存下一个存储位置的地址,那么这种存储方式就是链表。

数组 链表
读取 O(1) O(n)
插入 O(n) O(1)
删除 O(n) O(1)

如上表所示,在查找某个数据时,数组可以根据下标直接找出来,即O(1), 而链表需要遍历,挨个查过去,算法运行时间为O(n)。插入数据的时候,如果插入的不是首尾的位置,数组就需要相应的把插入位置后面的数据向后移,为O(n),而列表插入的时候只需要把上一个数据的指向位置改成插入的位置,再把插入位置指向下一个数据的位置即可。删除的时候,数组如果删除的不是最后一个,也是需要把相应的数据前移,而列表只需要把删除位置上一个位置指向删除位置的下一个位置的地址即可,为O(1)。

在存储数据时,还有一种映射的结构,叫做散列表。散列表就是一个键对应一个值,比如一斤苹果5块钱,把水果的名称苹果作为键,而水果的价格作为值,这两个形成一个映射关系,只要给出苹果这个键,就立马能够知道这个水果的价格是5块钱一斤。如果把所有水果都使用这种映射结构存储,每次只需要把水果名称输入进去,就可以立刻得到水果的价格,即算法运行时间是O(1)。

当然,散列表在使用的时候也会有其他问题,比如用来记录不同的人的投票情况,如果一个人已经投过票了,再次进行投票的话,就会和之前重复,这时应该不允许这个人再次投票。

还有如果两个键在散列表做映射的时候,映射的是同一个位置,就会产生冲突。比较简单的解决方法就是在这个位置,做一个链表,如果两个键映射到同一个位置的话,就把个两个键用链表保存起来。但这样又出现一个新问题,如果某个位置有特别多的映射,就是这个用来保存相同键位置的链表很长,而其他位置几乎没有保存键或者很少,这样这个散列表的性能反而不如链表和数组单独使用了。这里有一个解决方法就是尽量使散列函数可以把键均匀的分布在不同的位置上,还有就是计算当前散列表的散列因子(散列表包含的元素数/位置总数),如果散列因子超过 0.7,就开始调整散列表的长度。

相关文章

  • 4.数组、链表、散列表

    数据结构就是数据在内存中存储的一种方式,如果数据在内存中的存储是地址连续的,比如内存中从0到9的位置就用来存储1,...

  • HashMap实现原理分析及实现

    一.hashMap实现原理分析 HashMap底层实现方式:散列链表,即数组+链表 hash表:也叫散列表,是通过...

  • HashMap源码详解一篇就够

    概述 HashMap是基于哈希表(散列表),实现Map接口的双列集合,数据结构是“链表散列”,也就是数组+链表 ,...

  • hashMap源码分析

    hashMap是基于hash表(散列表),实现Map接口得双列集合,数据结构是--链表散列 也就是 数组+链表,k...

  • 2021超详细的HashMap原理分析,面试官就喜欢问这个!

    一、散列表结构 散列表结构就是数组+链表的结构 二、什么是哈希? Hash也称散列、哈希,对应的英文单词Hash,...

  • 2021-02-18 假期刚过,面试你准备了HashMap吗

    程序的本质是数据结构和算法(执行逻辑)数组栈队列链表树散列表堆图 图解HashMap 数组 + 链表 + 红黑树 ...

  • ARTS-第七周

    Algorithm 一、用链表和二叉树实现Set集合 GitHub地址 二、散列表 散列表就是使用数组下标随机访问...

  • 学习JavaScript数据结构与算法(第2版)

    二维和多维数组 栈数据结构 队列数据结构(排队) 链表数据结构 双向链表 集合 字典和散列表 散列表 树 二叉树 ...

  • Android 数据结构与特点

    Android数据结构有数组,栈,队列,链表,树,图,堆,散列表(hash表)。 数组图2 数组具有下标,下标从0...

  • 数据结构系列0-提纲

    线性列表基于数组、基于链表ArrayList、LinkedList 栈 队列 散列表 树二叉树、搜索二叉树、平衡二...

网友评论

      本文标题:4.数组、链表、散列表

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