永兴做网站,个人做网站费用,进入微信官方网站下载,未成年做网站本章为 《HashMap全B站最细致源码分析课程》 拉钩教育HashMap 学习笔记 文章目录1. HashMap的数据结构1. 数组2. 链表3. 哈希表3.1 Hash1. HashMap的数据结构
数据结构中有数组和链表来实现对数据的存储#xff0c;但这两者基本上是两个极端。
1. 数组
在生成数组的时候数…本章为 《HashMap全B站最细致源码分析课程》 拉钩教育HashMap 学习笔记 文章目录1. HashMap的数据结构1. 数组2. 链表3. 哈希表3.1 Hash1. HashMap的数据结构
数据结构中有数组和链表来实现对数据的存储但这两者基本上是两个极端。
1. 数组
在生成数组的时候数组的长度是固定的在增加元素时常常会遇到长度不足的问题此时就需要进行扩容——生成一个更长的数组并将原数组中所有元素复制到新数组中这个过程是很消耗资源的故插入操作比较困难。数组存储区间是连续的占用内存严重故空间复杂的很大。数组的二分查找时间复杂度小为O(1)数组的特点是寻址容易插入和删除困难
2. 链表
链表存储区间离散占用内存比较宽松故空间复杂度很小查询时必须从头节点一个个向后查询时间复杂度很大达ON。链表的特点是寻址困难插入和删除容易。
3. 哈希表
哈希表(Hash table既满足了数据的查找方便同时不占用太多的内容空间使用也十分方便哈希表有多种不同的实现方法我接下来解释的是最常用的一种方法—— 拉链法我们可以理解为“链表的数组” 如图 从上图我们可以发现哈希表是由数组链表组成的一个长度为16的数组中每个元素存储的是一个链表的头结点。HashMap里面实现一个静态内部类Entry其重要的属性有 key , value, next从属性 key,value 我们就能很明显的看出来Entry就是HashMap键值对实现的一个基础beanHashMap其实也是一个线性的数组实现的这个数组就是Entry[]Map里面的内容都保存在Entry[]里面。一般情况下存储规则为 hash(key)%len也就是元素的key的哈希值对数组长度取模得到
3.1 Hash
理论Hash 也称散列表, 基本原理就是把任意长度的输入通过Hash变成固定长度的输出。这个映射规则对应的就是 Hash算法而原始数据映射后的二进制串就是哈希值 特点 从 Hash值 不能反向推导出原始数据输入数据的微小变化会得到完全不一样的hash值。相同数据的得到的hash值完全一样Hash 算法执行效率高Hash 算法冲突概率较小 由于 Hash 的原理是将输入空间的值映射到Hash空间内 而由于Hash空间远小于输入空间根据抽屉原理一定会存在不同输入空间的值映射到相同的hash空间的情况
