《数据结构》笔记-期末复习知识点
26页1、数据结构整理知识点笔记1.单线程集合1.1 ArrayListl ArrayList 实际上是通过一个数组去保存数据的。当我们构造ArrayList时;若使用默认构造函数,则ArrayList的默认容量大小是10。l 当ArrayList容量不足以容纳全部元素时,ArrayList会重新设置容量:新的容量=“(原始容量x3)/2 + 1”。l ArrayList的克隆函数,即是将全部元素克隆到一个数组中。l ArrayList实现java.io.Serializable的方式。当写入到输出流时,先写入“容量”,再依次写入“每一个元素”;当读出输入流时,先读取“容量”,再依次读取“每一个元素”。l ArrayList中的操作不是线程安全的。1.2 LinkedListl LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。l LinkedList的克隆函数,即是将全部元素克隆到一个新的LinkedList对象中。l LinkedList 实现java.io.Serializable接口,这意味着Linked
2、List支持序列化,能通过序列化去传输。l LinkedList中的操作不是线程安全的。1.3 HashMapHashMap的主体是一个数组,数组中的每个元素是一个单向链表,链表的一个节点是嵌套类Entry的实例,Entry 包含四个属性:key, value, hash 值和用于单向链表的 next。 capacity:当前数组容量,始终保持 2n,可以扩容,扩容后数组大小为当前的 2 倍。默认的初始容量为16。 loadFactor:负载因子,默认为 0.75。 threshold:扩容的阈值,等于 capacity * loadFactor。当HashMap的大小=阈值,并且新值要插入的数组位置已经有元素了,则进行扩容。Put方法:HashMap会对null值key进行特殊处理,总是放到table0位置。put过程是先计算key的hash然后通过hash与table.length取模计算index值,然后将键值对放到tableindex位置,当tableindex已存在其它元素时,会在tableindex位置形成一个单向链表,将新添加的元素放在tableindex所对应链表的头部
3、,原来的元素通过Entry的next进行链接,这样以链表形式解决hash冲突问题,当元素数量达到临界值(capactiy*factor)时,则进行扩容,是table数组长度变为table.length*2get方法:同样当key为null时会进行特殊处理,在table0的链表上查找key为null的元素。get的过程是先计算key的hash然后通过hash与table.length取摸计算index值,然后遍历tableindex上的链表,直到找到目标值,然后返回。resize方法:这个方法实现了非常重要的hashmap扩容,具体过程为:先创建一个容量为table.length*2的新数组,修改临界值,然后把table里面元素计算hash值并使用hash与table.length*2重新计算index放入到新的table里面。这里需要注意下是用每个元素的hash全部重新计算index,而不是简单的把原table对应index位置元素简单的移动到新table对应位置。clear方法:遍历table然后把每个位置置为null,同时修改元素个数为0。需要注意的是clear方法只会清除里面的元
4、素,并不会重置capactiy。containsKey和containsValue:containsKey方法是先计算hash然后使用hash和table.length取模得到index值,遍历tableindex元素查找是否包含key相同的值。containsValue方法就比较粗暴了,就是直接遍历所有元素直到找到value。Java8 对 HashMap 进行了一些修改,最大的不同就是利用了红黑树,所以其由 数组+链表+红黑树 组成。在 Java8 中,当链表中的元素超过了 8 个以后,会将链表转换为红黑树,在这些位置进行查找的时候可以降低时间复杂度为 O(logN)。1.4 HashSetHashSet实现Set接口,不能有重复的元素,不保证Set的迭代顺序,特别是它不保证该顺序恒久不变。HashSet允许使用null元素。HashSet是基于HashMap实现的,在HashSet中,元素都存到HashMap键值对的Key上面,而Value都是一个统一的值private static final Object PRESENT = new Object();。1. 多线程集合2.1
《《数据结构》笔记-期末复习知识点》由会员fuc****277分享,可在线阅读,更多相关《《数据结构》笔记-期末复习知识点》请在金锄头文库上搜索。
精品解析:北京五十七中2020--2021学年高二上学期数学期中考试试题(解析版)
精品解析:北京五十七中2020--2021学年高二上学期数学期中考试试题(原卷版)
北京五十七中2017-2018学年第一学期高二期中考试数学试卷
北京市第五十七中学2019-2020学年高二上学期期中考试数学试卷
精品解析:北京市第五十七中学2024届高三暑期检测(开学考试)数学试题(原卷版)
精品解析:北京市第五十七中学2024届高三暑期检测(开学考试)数学试题(解析版)
更有文化!四级翻译写作成语精选
北京交通大学《操作系统》笔记-知识点总结
2024届统编版高中语文高三第一轮复习教学质量D级检测题(八)(解析版)
2024届统编版高中语文高三第一轮复习教学质量E级检测题(九)(解析版)
2024届统编版高中语文高三第一轮复习教学质量D级检测题(三)(解析版)
2024届统编版高中语文高三第一轮复习教学质量D级检测题(六)(解析版)
2024届统编版高中语文高三第一轮复习教学质量D级检测题(七)(解析版)
《计算机组成原理》笔记-各章复习要点
北京交通大学《操作系统》笔记-知识点总结B
湖南大学《计算机网络》笔记-复习要点
深圳大学《C语言程序设计》笔记-重点笔记
北京师范大学《数据库原理》笔记知识点总结
南开大学《计算机组成原理》笔记-随堂笔记
北京林业大学《计算机组成原理》笔记-总结期末复习资料
2023-09-25 37页
2023-09-25 10页
2023-09-25 33页
2023-04-03 8页
2023-04-03 4页
2023-04-03 8页
2023-03-29 10页
2023-03-22 10页
2023-03-20 8页