网站开发网上教学,百度网站怎么做,宝安做棋牌网站建设哪家便宜,公司网页如何建立线性数据结构 数组链表栈使用场景 队列应用场景 哈希表特点哈希函数#xff0c;哈希值#xff0c;哈希冲突键值对 Entry 开放寻址法和拉链法 参考文档 数组 数组(Array) 是一种很常见的数据结构。由相同类型的元素组成#xff0c;并且是使用一块连续的内存来存储的。 在数组… 线性数据结构 数组链表栈使用场景 队列应用场景 哈希表特点哈希函数哈希值哈希冲突键值对 Entry 开放寻址法和拉链法 参考文档 数组 数组(Array) 是一种很常见的数据结构。由相同类型的元素组成并且是使用一块连续的内存来存储的。 在数组中 我们可以直接利用元素的索引index计算出该元素对应的存储地址。 数组的特点是随机访问但容量有限 int[] arr new int[n];访问O1//访问特定元素插入/删除On//插入到数组头或删除数组头元素--》都需要将数组中所有元素进行移动操作链表 有趣的理解只是便于理解 可以这么理解链表 把链表看成一个家庭关系只查单线哈把链表中的数据看成家庭里的人。有一天啊来你家做人口调查怎么查呢按常理--》从最年长的开始比如爷爷爷爷的孩子--》爸爸爸爸的孩子--》你你--》null这里每个人就相当于链表中的一个数据元素它包括了爷爷本身 和 从爷爷出发找爸爸的指针同理爸爸 也包括了它自身 和 指向你的指针你没有孩子所以指针为空这就是单链表链表分类常见 单链表双向链表循环链表双向循环链表 链表由一系列节点链表中每一个元素成为节点组成节点在运行时动态生成每个节点包括两个部分 - 数据域存储数据元素- 指针域存储下一个节点地址单链表 循环链表 尾节点不指向null而是指向头结点 双向链表 包含两个指针一个prev指向前一个节点一个next指向后一个节点 双向循环 链表LinkedList 虽然是一种线性表但它和数组不同它不是顺序存储的而是使用不连续的内存空间存储数据链表的结点一般都有后继指针next–》指向后面的元素存储位置。因此插入和删除操作O1查找On这种结构可以克服数组需要预先知道数据大小的缺点充分利用计算机的内存空间实现灵活的内存动态管理。同时也因此 链表不具有数组的随机读取的特点必须知道目标位置元素的上一个元素 数组VS链表 数组可以随机访问链表不可以随机访问如果需要存储的数据元素的个数不确定并且需要经常添加和删除数据的话使用链表比较合适如果需要存储的数据元素的个数确定并且不需要经常添加和删除数据的话使用数组比较合适数组使用的是连续的内存空间对CPU的缓存机制友好链表则相反数组大小固定而链表天然支持动态扩容。如果声明的数组过小需要另外申请一个更大的内存空间放数组元素然后将原数组拷贝进去这个操作是比较耗时的
栈
栈Stack就像个无顶的盒子 只允许在有序的线性数据集合的一端称为栈顶top进行加入数据push和移除数据pop的操作。 因而按照后进先出LIFOlast in first out的原理运作。 在栈中push和pop的操作都发生在栈顶 栈 常用一维数组或链表来实现用数组实现的栈叫做顺序栈用链表实现的栈叫做链式栈。
使用场景
eg.实现浏览器的回退和前进功能
队列 可以把队列看做是食堂打饭的队伍 队列Queue是先进先出FIFOfirst int first out的线性表。
应用场景
当我们需要按照一定顺序来处理数据的时候可以考虑使用队列这个数据结构。
哈希表
百科解释 散列表Hash table也叫哈希表是根据键Key而直接访问在内存存储位置的数据结构。也就是说它通过计算一个关于键值的函数将所需查询的数据映射到表中一个位置来访问记录这加快了查找速度。这个映射函数称做散列函数存放记录的数组称做散列表。 特点
提炼一下
哈希表也叫散列表。哈希表本质是一种数据结构----》特点可以根据一个key值直接访问数据因此查找速度快
提到数据结构特点是查找速度快的还有什么呢
数组—》所以Hash Table本质就是一个数组 那它跟数组有什么区别呢
哈希函数哈希值哈希冲突 这有一个例子 eg.在电话表里找“王三”这个人- 如果是数组怎么找呢---》遍历for(...){ if(...)... }- 那哈希表呢我们把电话表中的数据按照首字母进行分类然后查找 ‘w’ 里面的数据从而找到 “王二”这里我们把按首字母排序这个方法叫做哈希函数散列函数
键值对 Entry 这还有个 不算例子 我们都知道哈希表经常存放的是一些键值对keyvaluejdk中把键值对叫做Entry。这是啥意思呢就是key对应着value也就是value是由key通过哈希函数映射来的value就叫做哈希值hash值啥玩应 这是个例子 eg. 王二的学生信息002王二我们根据之前说的要有一个哈希函数假设哈希函数的作用是 将002--》0那么 key 0value 王二0王二就是一个键值对(key,value)根据 0我们可以查找出 王二 来那 如何把kv对存到哈希表中呢 我们说了哈希表本质还是个数组嘞根据 key 的值就可以把value存到对应的位置上去那这就有个问题了 如果 还有个学生 007翠花key0 value翠花那不就和 王二的key冲突了吗这个就叫做哈希冲突也叫做哈希碰撞 怎么解决
开放寻址法和拉链法 开放寻址法 这里 会一直找不到空位置吗 不会的对于HashMap来说当它的增长因子也叫负载因子到达0.7--》比如一共10个位置被占了7位那就要扩容了扩容 是create一个数组是原来的2倍然后把原数组的所有Entry都重新Hash一遍放到新数组中重新hash 就是把之前的数据通过新的哈希函数计算出新的位置来存放。因为数组扩大了所以一般哈希函数也会有变化就需要重新hash一遍拉链法常用
参考文档
github——JavaGuide项目来吧一文彻底搞定哈希表
