我是川川,有问题留言or加我扣扣私聊:2835809579 原题: 定义一个函数int isprime(int n),用来判别一个正整数n是否为素数。...在主函数中输入两个正整数m和n(m>=1,n>m),统计并输出m和n之间的素数的个数以及这些素数的和。...输入输出示例 输入:2 10 输出:count = 4 ,sum = 17 代码: 在这里插入代码片 ```c #include int isprime(int n) { int i=2;...for(i;i<n;i++) { if(n%i==0) break; } if(i==n) return 1;...else return 0; } int main() { int m,n,count=0; int sum=0; scanf("%d %d",&m,&n);
在 put(K key, V value) 的情况下,如果条目存在,则函数将其替换为新值,否则它会在单链表的头部创建一个新条目(根据参数中的键和值)。...但是,之前在同一个桶中的 2 个具有不同哈希键的条目在转换后可能不在同一个桶中。 图片 图片显示了调整内部数组大小之前和之后的表示。...密钥不变性 为什么字符串和整数是 HashMap 键的良好实现?主要是因为它们是不可变的!如果您选择创建自己的 Key 类并且不使其不可变,则可能会丢失 HashMap 中的数据。...如您所见,树实际上比链表占用更多的空间(我们将在下一部分讨论它)。 通过继承,内表可以同时包含Node(链表)和TreeNode(红黑树)。...如果在 JAVA 7 上运行相同的测试,第一种和第二种情况的结果会更糟(因为 put 的时间复杂度在 JAVA 7 中为 O(n),而在 JAVA 8 中为 O(log(n))) 使用 HashMap
Set 的具体实现类 HashSet 我们来看看 Java API 中对 HashSet 的定义。 此类实现 Set 接口,由哈希表(实际上是一个 HashMap 实例)支持。...上面说了 HashSet 是基于哈希表(实际上是一个 HashMap 实例)支持。可能有些同学又会问了,HashMap 是什么数据结构,为什么无序?...这个,我们下次分享的时候再说,同学们可以提前了解一下散列表(Java 中叫哈希表)。 不能包含重复的元素:为什么不能?刚刚我们说了,由哈希表(实际上是一个 HashMap 实例)支持的元素存储。...此实现与 HashSet 的不同之外在于,后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序,即按照将元素插入到 set 中的顺序(插入顺序)进行迭代。...mmp,这个API 竟然说维护着运行于所有条目的双重链接列表,为什么不和前面一样,基于“LinkedHashMap 的双重链接表实现”~~~ LinkedHashMap Map 接口的哈希表和链接列表实现
3.值: HashMap可以让你将空值作为一个表的条目的key或value Hashtable是不能放入空值(null)的 ArrayList和Vector的区别: ArrayList与Vector都是...(在JAVA1.5中,collection有queue来实现队列。) Set-HashSet实现类: 遍历一个Set的方法只有一个:迭代器(interator)。...Int I=hc%n;(n为数组的长度),取得余数后,利用余数向数组中相应的位置添加数据,以n为6为例,如果I=0则放在数组a[0]位置,如果I=1,则 放在数组a[1]位置。...在实例中,定义student对象时覆盖它的hashcode。 因为String类是自动覆盖的,所以当比较String类的对象的时候,就不会出现有两个相同的string对象的情况。...因为hashSet查询和删除和增加元素的效率都非常高。 但是hashSet增删的高效率是通过花费大量的空间换来的:因为空间越大,取余数相同的情况就越小。HashSet这种算法会建立许多无用的空间。
下面我们举例分析下: 我们拿类型是 String 的 name 来举例,如果一个用户的名字叫做“abcd”,它本应该只占用 4 个字节,但在 JVM 的对象存储中,“abcd”会消耗总共 48 个字节,...位则用于在堆外空间中直接寻址操作系统的内存空间。...结合上面的示意图我们不难发现,存储数据的对象值只占整个 HashMap 一半的存储空间,另外一半的存储空间用来存储引用和指针,这 50% 的存储开销还是蛮大的。...而且我们发现,图中每一个 Key、Value 和链表元素都是 JVM 对象。假设,我们用 HashMap 来存储一百万条数据条目,那么 JVM 对象的数量至少是三百万。...其次,Tungsten HashMap 的存储单元是内存页,内存页本质上是 Java Object,一个内存页可以存储多个数据条目。
重载是同一个类中多个同名方法根据不同的传参执行不同的逻辑处理。 重写:是当子类继承自父类的相同方法,输入数据一样,但是要做出的和父类不一样的响应时,就要重写父类方法。...对象存于堆内存,如果局部变量类型为基本数据类型,那么存储在栈内存,如果为引用数据类型,那存放的是指向堆内存对象的引用或是指向常量池中的地址。...哈希码在HashSet中应用:当把对象加入HashSet时,HashSet会先计算对象的hashcode来判断对象加入的位置,同时也会与该位置其他加入对象的hashcode作比较,若没有相符的hashcode...内存空间占用 ArrayList的空间主要浪费在了list列表的结尾会预留一定的容量空间,而LinkedList主要花费在每一个元素都要比ArrayList更多的空间,因为存前驱后继节点及数据等。...HashMap和HashTable image.png HashMap的长度为什么是2的幂次方? 为了能让HashMap减少碰撞高效存储,要尽量把数据分配均匀。
与字典类似,键在集合中必须是唯一的——试图添加具有相同键的另一个项将失败并抛出异常。...向SortedDictionary中的平衡树添加项总是相当廉价(复杂度为O(log n)),但在堆上会为每个条目分配一个树节点,这将使开销和内存碎片比使用SortedList键值条目的数组要更多...HashMap默认加载因子为什么选择0.75?...(阿里) Hashtable 初始容量是11 ,扩容 方式为2N+1; HashMap 初始容量是16,扩容方式为2N; 阿里的人突然问我为啥扩容因子是0.75,回来总结了一下;提高空间利用率和 减少查询成本的折中...选择0.75作为默认的加载因子,完全是时间和空间成本上寻求的一种折衷选择, 正文 前几天在一个群里看到有人讨论hashmap中的加载因子为什么是默认0.75。
桶及桶数组 散列表使用的桶数组(Bucket array ),其实就是一个容量为 N 的普通数组,只不过在这里,我们将其中的每个单元都想象为一个“桶”(Bucket),每个桶单元里都可以存放一个条目。...比如,所有的关键码都是整数,我们就可以直接将 key 为关键码的那个条目存放在桶单元 A[key]内;为了节省空间,空闲的单元都被置为 null。...Java中的哈希结构 在Java的刷题中,我们有两种常用的哈希结构。 一种是HashMap,型的Hash结构。 一种是HashSet,没有重复元素的集合。...描述: 给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。 注意:若 s 和 t 中每个字符出现的次数都相同,则称 s 和 t 互为字母异位词。...思路: 我们的思路是四个数组分两组,一组存HashMap,另一组和HashMap比较。 首先定义 一个HashMap,key放A和B两数之和,value 放A和B两数之和出现的次数。
AbstractSet是一个实现Set接口的抽象类,Set接口有三个具体实现类,分别是散列集HashSet、链式散列集LinkedHashSet和树形集TreeSet。...先看下面这张图: 在之前的版本中,HashMap采用数组+链表实现,即使用链表处理冲突,同一hash值的链表都存储在一个链表里。...但是,“模”运算的消耗还是比较大的,在HashMap中,(n – 1) & hash用于计算对象应该保存在table数组的哪个索引处。...HashMap底层数组的长度总是2的n次方,当数组长度为2的n次幂的时候,(n – 1) & hash 算得的index相同的几率较小,数据在数组上分布就比较均匀,也就是说碰撞的几率小,相对的,查询的时候就不用遍历某个位置上的链表...2.LinkedHashMap LinkedHashMap继承自HashMap,它主要是用链表实现来扩展HashMap类,HashMap中条目是没有顺序的,但是在LinkedHashMap中元素既可以按照它们插入图的顺序排序
HashMap 的实例有两个参数影响其性能:初始容量 和加载因子。容量 是哈希表中桶的数量,初始容量只是哈希表在创建时的容量。...通常,默认加载因子 (.75) 在时间和空间成本上寻求一种折衷。...加载因子过高虽然减少了空间开销,但同时也增加了查询成本(在大多数 HashMap 类的操作中,包括 get 和 put 操作,都反映了这一点)。...在上面的例子中,我们期望new Element(i) (i=5)与 Element test=new Element(5)是相同的,而实际上这是两个不同的对象,尽管它们的内容相同,但它们在内存中的地址不同...这就需要我们在自己的程序中重写它们,其实java类库中也重写了千千万万个这样的方法。
接下来,使用equals()方法检查桶中的每个条目是否与键相等。...在HashMap这个数据结构中,有一个方面尤其重要:具有相同equals方法比较结果的对象,必须返回相同的哈希值。...然而,反之则不一定成立,也就是说,具有相同哈希值的对象,并不一定具有相同的equals方法比较结果。这也是为什么我们可以将多个对象存储在HashMap的同一个桶中的原因。...因此,在大多数情况下,该解决方案并不推荐。 自定义类(`推荐使用`) 我们还可以自己的定义一个类,用来完全控制哈希码计算和相等性。这样,我们可以确保解决方案快速,并且没有太大的内存占用。...它们都是具有可比性和可哈希性的数据结构,能够保证唯一性。但这种方法并不是完美的解决方案,因为使用String或List作为键会带来一些性能上的开销,或者占用不必要的内存空间。
Hashtable 没有这样的机制。 HashMap 和 HashSet 区别 如果你看过 HashSet 源码的话就应该知道:HashSet 底层就是基于 HashMap 实现的。...(HashSet 的源码非常非常少,因为除了 clone()、writeObject()、readObject()是 HashSet 自己不得不实现之外,其他方法都是直接调用 HashMap 中的方法。...== 与 equals 的区别 对于基本类型来说,== 比较的是值是否相等; 对于引用类型来说,== 比较的是两个引用是否指向同一个对象地址(两者在内存中存放的地址(堆内存地址)是否指向同一个地方);...也就是说创建一个链表数组,数组中每一格就是一个链表。若遇到哈希冲突,则将冲突的值加到链表中即可。...这个数组下标的计算方法是“ (n - 1) & hash”。(n 代表数组长度)。这也就解释了 HashMap 的长度为什么是 2 的幂次方。 我们首先可能会想到采用%取余的操作来实现。
,则加入元素;否则HashSet会调用equals()方法来判断二者是否完全相同,若相同则添加失败。...是否支持快速访问 ArrayList由于是数组存储,因而支持快速访问;而LinkedList则不支持 内存空间的占用 ArrayList的空间浪费体现在list列表的结尾会预留一定的容量空间;LinkedList...主要包括两个阶段: 新建一个node[]数组,数组长度为原数组的2倍 将原数组中的元素rehash到新的数组中 注:在创建数组时若要指定数组长度,最好使要指定的数组长度小于2^n与负载因子的乘积。...为什么HashMap中数组的长度需要是$2^n$ 因为在计算存入元素位置时,采用的公式是hashcode(key) % n,其中n为数组的长度。...--> 如果一个叶子节点是红色,那么其子节点必须都是黑色的 红黑树的特征--> 从一个节点到该节点的子孙节点的所有路径上包括相同数目的黑节点
移动缓存数据在链表中的位置等价于先把节点删除,再把节点移动到表头位置,删除时,我们需要同时知道节点的前驱节点和后驱节点分别是哪个,才能将他们相连。...redis近似LRU实现 上面的LRU实现用到了一个双向链表来记录数据的最近访问情况,每个链表节点需要维护一个前驱指针和一个后驱指针,当缓存量较大时,两个指针额外占用的内存也是不可忽视的。...所以,在缓存数据库redis中,为了节省内存的占用,实现了一种基于采样的近似LRU置换算法。 缓存数据依然通过一个哈希表管理,通过key可以快速找到对应的数据。...,我们可以额外维护一个大小为M的大顶堆,堆中数据按照last_read_time的值排序,这样,堆中最新的数据将会处于堆顶。...这里我们给出一种方案,在经过哈希计算出一个位置a后,可以在a开始的往后N个位置中查找数据。这N个位置的数据组成一个选择组。例如缓存总容量100,选择组大小设置为8。
因为在进行上述操作的时候,集合中第 i 个元素和第 n- i 个之后的元素都要向后/向前移一位。 ② ....快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法) 内存占用空间:ArrayList的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间,而 LinkedList...的空间花费则体现在它的每一个元素都需要消耗比 ArrayList更多的空间(因 为要存放直接后继和直接前驱以及数据)。...但是在HashTable中 put 中的键值只有一个 null,直接抛出 NullPointerException 初始化容量大小和每次扩充容量的大小不同: ① ....这个数组下标的计算方法是“(n - 1)& hash”。(n代表数组⻓度),这也就解释了HashMap的⻓度为什么是2的幂次方。 那么,如何设计这个算法呢? 我们首先可能会想到采用%取余的操作来实现。
当我们需要保存一组类型相同的数据的时候,我们应该是用一个容器来保存,这个容器就是数组,但是,使用数组存储对象具有一定的弊端, 因为我们在实际开发中,存储的数据的类型是多种多样的,于是,就出现了“集合”,...因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。...内存空间占用: ArrayList 的空 间浪费主要体现在在 list 列表的结尾会预留一定的容量空间,而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间...在openjdk8中,HashSet的add()方法只是简单的调用了HashMap的put()方法,并且判断了一下返回值以确保是否有重复元素。...==与 equals 的区别 对于基本类型来说,== 比较的是值是否相等; 对于引用类型来说,== 比较的是两个引用是否指向同一个对象地址(两者在内存中存放的地址(堆内存地址)是否指向同一个地方); 对于引用类型
HashSet应该是你在没有特殊要求下的默认选择 这个类为基本操作(添加,删除,包含和大小)提供了恒定的时间性能,假设散列函数在桶之间正确地分散元素。...这个实现与HashSet的不同之处在于它保持了一个双向链表,它贯穿其所有条目。 此链接列表定义迭代排序,即元素插入到集合中的顺序(插入顺序)。 请注意,如果元素重新插入到集合中,则插入顺序不受影响。...通常,默认的加载因子(.75)在时间和空间成本之间提供了一个很好的折衷。 从Java 2平台v1.2开始,该类被改型为实现Map接口,使其成为Java集合框架的成员。...以弱键 实现的基于哈希表的 Map。 在 WeakHashMap 中,当某个键不再正常使用时,将自动移除其条目。...换句话说,在 IdentityHashMap 中,当且仅当 (k1==k2) 时,才认为两个键 k1 和 k2 相等 (在正常 Map 实现(如 HashMap)中,当且仅当满足下列条件时才认为两个键
数组长度 java.util.Radom Random() 构建一个新的随机数生成器 int nextInt(int n) 返回一个 0 ~ n-1之间的随机数 java.lang.Object String...堆是一个可以自我调整的二叉树,对树执行添加和删除操作,可以让最小元素移动到根(最小堆),而不必花费时间对元素进行排序 4、Map接口 Map,图,是一种存储键值对映射的容器类,在Map中键可以是任意类型的对象...,但不能有重复的键,每个键都对应一个值,真正存储在图中的是键值构成的条目。...在之前的版本中,HashMap采用数组+链表实现,即使用链表处理冲突,同一hash值的链表都存储在一个链表里。但是当链表中的元素较多,即hash值相等的元素较多时,通过key值依次查找的效率较低。...java.util.LinkedHashMap LinkedHashMap继承自HashMap,它主要是用链表实现来扩展HashMap类,HashMap中条目是没有顺序的,但是在LinkedHashMap
在第一步,该算法使用提供的数组来构建这个堆,并将其转换为一个最大堆(该堆由另一个数组表示)。因为这是一个最大堆,所以最大的元素是堆的根。...在下一步中,根与堆中的最后一个元素交换,堆大小减少 1(从堆中删除最后一个节点)。堆顶部的元素按顺序排列。最后一步由建堆(以自顶向下的方式构建堆的递归过程)和堆的根(重构最大堆)组成。...例如,让我们考虑两个具有相同条目的瓜映射(在Melon类中必须存在equals()和hashCode(): public class Melon { private final String type...由于 BIT 存储给定数组的部分和,因此通过避免索引之间的循环和计算和,它是计算给定数组中两个给定索引(范围和/查询)之间的元素和的非常有效的解决方案。 位可以在线性时间或O(n log n)中构造。...因此,在位中,在索引 8 处,我们存储值的和,13+17=30。 算法将以相同的方式继续,直到位完成。
容器是Java语言学习中重要的一部分。泥瓦匠我的感觉是刚开始挺难学的,但等你熟悉它,接触多了,也就“顺理成章”地知道了。Java的容器类主要由两个接口派生而出:Collection和Map。...类型单参数构造方法,用于创建一个具有其参数相同元素新的Collection及其实现类等。...3,如果查找一个指定位置的数据,vector和arraylist使用的时间是相同的,都是0(1),这个时候使用vector和arraylist都可以。...集合框架”提供两种常规的Map实现:HashMap和TreeMap (TreeMap实现SortedMap接口)。 3、在Map 中插入、删除和定位元素,HashMap 是最好的选择。...2、同步性:Hashtable是线程安全的,也就是说是同步的,而HashMap是线程序不安全的,不是同步的 。 3、值:只有HashMap可以让你将空值作为一个表的条目的key或value 。 ?
领取专属 10元无门槛券
手把手带您无忧上云