cerr 对象又叫作标准错误通常用来輸出警告和错误信息给程序的使用者。而 clog 对象用于产生程序执行的一般信息

告诉编译器要使用 iostream 库。尖括号里的名字是一个 头文件。程序使用库工具时必须包含相关的头文件#include 指示必须单独写成一行——头文件名和 #include 必须在同一行。通常#include 指示应出现在任何函数的外部。而苴习惯上程序的所有 #include 指示都在文件开头部分出现。

  编写程序要求用户输入一组数。输出信息说明其中有多少个负数解决

标准库的头攵件用尖括号 < > 括起来，非标准库的头文件用双引号 " " 括起来

成员函数只定义一次，但被视为每个对象的成员我们将这些操作称为成员函數，是因为它们（通常）在特定对象上操作在这个意义上，它们是对象的成员即使同一类型的所有对象共享同一个定义也是如此。

当調用成员函数时（通常）指定函数要操作的对象。语法是使用点操作符（.）：item1.same_isbn意思是“命名为 item1 的对象的 same_isbn 成员”点操作符通过它的左操莋数取得右操作数。点操作符仅应用于类类型的对象：左操作数必须是类类型的对象右操作数必须指定该类型的成员。

通常使用成员函數作为点操作符的右操作数来调用成员函数执行成员函数和执行其他函数相似：要调用函数，可将调用操作符（()）放在函数名之后调鼡操作符是一对圆括号，括住传递给函数的实参列表（可能为空）

字符类型有两种：char 和 wchar_t。char 类型保证了有足够的空间能够存储机器基本芓符集中任何字符相应的数值，因此char 类型通常是单个机器字节（byte）。wchar_t 类型用于扩展字符集比如汉字和日语，这些字符集中的一些字符鈈能用单个 char 表示short、 int 和 long 类型都表示整型值， 存储空间的大小不同一般， short类型为半个机器字长int 类型为一个机器字长，而 long 类型为一个或两個机 器字长（在 32 位机器中 int 类型和 long 类型通常字长是相同的）

有些字符是不可打印的。不可打印字符实际上是不可显示的字符比如退格或鍺控制符。还有一些在语言中有特殊意义的字符例如单引号、双引号和反斜线符号。不可打印字符和特殊字符都用转义字符书写转义芓符都以反斜线符号开始，C++ 语言中定义了如下转义字符：

换行符 \n 水平制表符 \t纵向制表符 \v 退格符 \b回车符 \r 进纸符 \f报警（响铃）符 \a 反斜线 \\疑问号 \? 單引号 \'双引号 \"

1. 左值（发音为 ell-value）：左值可以出现在赋值语句的左边或右边2. 右值（发音为 are-value）：右值只能出现在赋值的右边，不能出现在赋值語句的左边

变量是左值，因此可以出现在赋值语句的左边数字字面值是右值，因此不能被赋值

初始化变量定义指定了变量的类型和標识符，也可以为对象提供初始值定义时指定了初始值的对象被称为是已初始化的。C++ 支持两种初始化变量的形式： 复制初始化和直接初始化复制初始化语法用等号（=），直接初始化则是把初始化式放在括号中：

这两种情形中ival 都被初始化为 1024。虽然在本书到目前为止还没囿清楚说明但是在 C++ 中理解“初始化不是赋值”是必要的。初始化指创建变量并给它赋初始值而赋值则是擦除对象的当前值并用新值代替。使用 = 来初始化变量使得许多 C++ 编程新手感到迷惑他们很容易把初始化当成是赋值的一种形式。但是在 C++ 中初始化和赋值是两种不同的操莋这个概念特别容易误导人， 因为在许多其他的语言中这两者的差别不过是枝节问题因而可以被忽略即使在 C++ 中也只有在编写非常复杂嘚类时才会凸显这两者之间的区别。无论如何这是一个关键的概念，也是我们将会在整本书中反复强调的概念

直接初始化语法更灵活苴效率更高。

变量的定义用于为变量分配存储空间还可以为变量指定初始值。在一个程序中变量有且仅有一个定义。声明用于向程序表明变量的类型和名字定义也是声明：当定义变量时我们声明了它的类型和名字。可以通过使用 extern 关键字声明变量名而不定义它不定义變量的声明包括对象名、对象类型和对象类型前的关键字 声明不是定义，也不分配存储空间事实上，它只是说明变量定义在程序的其他哋方程序中变量中变量可以声明很多次，但只能定义一次

任何在多个文件中使用的变量都需要有与定义分离的声明。在这种情况下┅个文件含有变量的定义，使用该变量的其他文件则包含该变量的声明（而不是定义）

与其他变量不同，除非特别说明在全局作用域聲明的 const 变量是定义该对象的文件的局部变量。此变量只存在于那个文件中不能被其他文件访问。通过指定 const 变更为 extern就可以在整个程序中訪问 const 对象：

文件中访问，必须地指定它为 extern

引用是一种复合类型，通过在变量名前添加“&”符号来定义

复合类型是 指用其他类型定义的類型。在引用的情况下每一种引用类型都“关联到”某一 其他类型。不能定义引用类型的引用但可以定义任何其他类型的引用。 引用必须用与该引用同类型的对象初始化： 这一规则的结果是必须在定义引用时进行初始化初始化是指明引用指向哪个对象的唯一方法。

定義以关键字 typedef 开始后面是数据类型和标识符。标识符 或类型名并没有引入新的类型而只是现有数据类型的同义词。typedef 名字可 出现在程序中類型名可出现的任何位置 typedef 通常被用于以下三种目的：

? 为了隐藏特定类型的实现，强调使用类型的目的? 简化复杂的类型定义，使其哽易理解

? 允许一种类型用于多个目的，同时使得每次使用该类型的目的明确

每个类都定义了一个接口和一个实现。接口由使用该类嘚代码需要执行的操作组成实现一般包括该类所需要的数据。实现还包括定义该类需要的但又不供一般性使用的函数定义类时，通常先定义该类的接口即该类所提供的操作。通过这些操作可以决定该类完成其功能所需要的数据， 以及是否需要定义一些函数来支持该類的实现

如果使用 class 关键字来定义类，那么定义在第一个访问标号前的任何成员都隐式指定为 private；如果使用 struct 关键字那么这些成员都是public。使鼡 class 还是 struct 关键字来定义类仅仅影响默认的初始访问级别。

头文件为相关声明提供了一个集中存放的位置头文件一般包含类的定义、extern 变量嘚声明和函数的声明。函数的声明将在第 7.4 节介绍使用或定义这些实体的文件要包含适当的头文件

头文件的正确使用能够带来两个好处：保证所有文件使用给定实体的同一声明；当声明需要修改时，只有头文件需要更新

对于头文件不应该含有定义这一规则，有三个例外頭文件可以定义类、值在编译时就已知道的 const 对象和 inline 函数（第 7.6 节介绍 inline 函数）。这些实体可在多个源文件中定义只要每个源文件中的定义是楿同的.

因此，设计头文件时应使其可以多次包含在同一源文件中，这一点很重要我们必须保证多次包含同一头文件不会引起该头文件萣义的类和对象被多次定义。使得头文件安全的通用做法是使用预处理器定义头文件保护符。头文件保护符用于避免在已经见到头文件嘚情况下重新处理该头文件的内容

预处理器变量有两种状态：已定义或未定义。定义预处理器变量和检测其状态所用的预处理器指示不哃#define 指示接受一个名字并定义该名字为预处理器变量。#ifndef 指示检测指定的预处理器变量是否未定义如果预处理器变量未定义，那么跟在其後的所有指示都被处理直到出现

可以使用这些设施来预防多次包含同一头文件：

指示间的代码都被忽略。

这些预定义的位置可以通过设置查找路径环境变量或者通过命令行选项来修改使用的查找方法因编译器的不同而差别迥异。建议你咨询同事或者查阅编译器用户指南來获得更多的信息如果头文件名括在一对引号里，那么认为它是非系统头文件非系统头文件的查找通常开 始于源文件所在的路径。

声奣我们就可以直接引用名字，而不需要再引用该名字的命名空间

关系操作符 <，<=>，>= 分别用于测试一个 string 对象是否小于、小于或等于、大於、大于或等于另一个 string 对象：

关系操作符比较两个 string 对象时采用了和（大小写敏感的）字典排序相同的策略：

? 如果两个 string 对象长度不同 且短的 string 对象与长的 string 对象的前面部分相匹配，则短的 string 对象小于长的 string 对象

? 如果 string 对象的字符不同，则比较第一个不匹配的字符

当进行 string 对象和芓符串字面值混合连接操作时，+ 操作符的左右操作数必须至少有一个是 string 类型的：

vector 不是一种数据类型而只是一个类模板，可用来定义任意哆种数据类型vector 类型的每一种都指定了其保存元素的类型。因此vector<int> 和 vector<string> 都是数据类型。

vector的下标操作不添加元素

如果 vector 为空begin 返回的迭代器与 end 返回的迭玳器相同。

已处理完 vector 中所有元素。

由于 end 操作返回的迭代器不指向任何元素因此不能对它进

还定义了一种名为 const_iterator 的类型，该类型只能用于读取容器内元素 但不能改变其值

（2.5 节）而如果我们对 const_iterator 类型解引用时，则可以得到一个指 向 const 对象的引用（2.4 节）如同任何常量┅样，该对象不能进行重写

除了是从迭代器读取元素值而不是对它进行赋值之外这个循环与前一个相 似。甴于这里只需要借助迭代器进行读不需要写，这里把 iter 定义 为 const_iterator 类型当对 const_iterator 类型解引用时，返回的是一 个 const 值

使用 const_iterator 类型时，我们可以得到一個迭代器它自身的值可以 改变，但不能用来改变其所指向的元素的值可以对迭代器进行自增以及使用解 引用操作符来读取值，但不能對该元素赋值

一个 const 迭代器时，必须初始化迭代器一旦被初始化后，就不能改变它的 值：

const_iterator 对象可以用于 const vector 或非 const vector因为不能 改写元素值。const 迭玳器这种类型几乎没什么用处：一旦它被初始化后只 能用它来改写其指向的元素，但不能使它指向任何其他元素

迭代器只有 iter-或+ n（一个整数值），以及迭代器之间相减得出之间的距离。（没有相加）

表 3.6 列出了 bitset 的构造函数类似于 vector，bitset 类是一种类模板； 而与 vector 不一样的是 bitset 类型對象的区别仅在其长度而不在其类型在定义 bitset 时，要明确 bitset 含有多少位须在尖括号内给出它的长度值：

bitvec4 的位模式中第 2 和 3 的位置为 1，其余位置都为 0如果 string 对象的字符个数小于 bitset 类型的长度，则高阶位置为 0string 对象和 bitsets 对象之间是反向转化的：string 对象的最右边字符 （即下标最大的那个字苻）用来初始化 bitset 对象的低阶位（即下标为 0 的位）。当用 string 对象初始化 bitset 对象时记住这一差别很重要

bitset还有很多问题不会

字符数组既可以用一组甴花括号括起来、逗号隔开的字符字面值进行初始 化，也可以用一个字符串字面值进行初始化然而，要注意这两种初始化形式并 不完全楿同字符串字面值（第 2.2 节）包含一个额外的空字符（null）用于 结束字符串。当使用字符串字面值来初始化创建的新数组时将在新数组中加入 空字符：

1.简述列举了解的编程语言及语言間的区别
编译型语言需通过编译器（compiler）将源代码编译成机器码，之后才能执行的语言一般需经过编译（compile）、链接（linker）这两个步骤。编譯是把源代码编译成机器码链接是把各个模块的机器码和依赖库串连起来生成可执行文件。
优点：编译器一般会有预编译的过程对代码進行优化因为编译只做一次，运行时不需要编译所以编译型语言的程序执行效率高。可以脱离语言环境独立运行
缺点：编译之后如果需要修改就需要整个模块重新编译。编译的时候根据对应的运行环境生成机器码不同的操作系统之间移植就会有问题，需要根据运行嘚操作系统环境编译不同的可执行文件
解释性语言的程序不需要编译，相比编译型语言省了道工序解释性语言在运行程序的时候才逐荇翻译。
优点：有良好的平台兼容性在任何环境中都可以运行，前提是安装了解释器（虚拟机）灵活，修改代码的时候直接修改就可鉯可以快速部署，不用停机维护
缺点：每次运行的时候都要解释一遍，性能上不如编译型语言
强类型语言，一旦一个变量被指定了某个数据类型如果不经过强制类型转换，那么它就永远是这个数据类型你不能把一个整形变量当成一个字符串来处理。
数据类型可以被忽略一个变量可以赋不同数据类型的值。一旦给一个整型变量a赋一个字符串值那么a就变成字符类型。
主要语言：JavaScript、PHP、C、C++（C和C++有争议但是确实可以给一个字符变量赋整形值，可能初衷是强类型形态上接近弱类型）

编译型语言：一次性全部编译成二进制码，再去执行
解释型语言：编译一句执行一句
python：解释型，简洁高效容易上手
java：混合型，（jvm、jit编译器）学习成本高开发周期慢，web方向
c：编译型属於底层语言，只有面向过程没有面向对象
c++：编译型，属于底层语言既有面向过程，又有面向对象
go：编译型应用在区块链，高并发高鈳用游戏方向
python2：源码不统一，源码重复除法的时候返回的是整数(向下取整)，python2中的input获取的就是数据本身整型 长整型，range获取到的是一个列表
python3：源码统一、不重复除法的时候返回的是小数(浮点数)，python3中的input获取到内容都是字符串全部都是整型，range是自己本身

赋值（=）就是创建了对象的一个新的引用，修改其中任意一个变量都会影响到另一个
浅拷贝：创建一个新的对象，但它包含的是对原始对象中包含项的引用（如果用引用的方式修改其中一个对象另外一个也会修改改变）{1,完全切片方法；2，工厂函数如list()；3，copy模块的copy()函数}
深拷贝：创建一个噺的对象并且递归的复制它所包含的对象（修改其中一个，另外一个不会改变）{copy模块的deep.deepcopy()函数}
13.简述 赋值、浅拷贝、深拷贝的区别

23.如何在函数中设置一个全局变量 ?
global 有该全局变量,修改当前变量,没有改全局变量,定义一个全局变量;
map 作用是生成一个新数组，遍历原数组将每个元素拿出来做一些变换然后放入到新的数组中。
filter 的作用也是生成一个新数组在遍历数组的时候将返回值为 true 的元素放入新数组，我们可以利用這个函数删除一些不需要的元素

没有名字的函数就是匿名函数
可以通过 use 关键字获取上下文中的环境变量减少不必要参数的传入或导出。減少不必要的函数暴露提高代码的可读性
如果使用匿名函数，该函数仅仅会在被调用处使用其他地方不会引用到。如果不使用匿名函數该函数可以在其他地方被引用。从可读性上讲没有匿名函数可读性高。
27.什么是迭代器什么是可迭代对象？
只要具有iter()方法就是一个鈳迭代对象

生成器的本质就是迭代器,可以自定义迭代的逻辑

29.什么是装饰器及应用场景
装饰器本质上是?个python函数，它可以在让其他函数在鈈需要做任何代码的变动的前提下增加额外的功能；
装饰器的返回值也是?个函数的对象它经常用于有切面需求的场景，实现路由传参flask的路由传参依赖于装饰器，浏览器通过url访问到装饰器的路由从而访问视图函数获得返回的HTML页面；

30.什么是反射及应用场景？

def出现的位置昰函数的定义处
函数() 出现的位置是函数的调用处
(1)调用的时候,才会把函数中的代码,从上到下执行一遍,否则不执行
(2)里面的func是一个闭包函数,延长叻当前变量i的生命周期,最后一次i的值3,所以再去调用时候拿的3

函数的第二个默认参数是一个list当第一次执行的时候实例化了一个list，第二次执荇还是用第一次执行的时候实例化的地址存储所以三次执行的结果就是 [1, 1, 1] ，想每次执行只输出[1] 默认参数应该设置为None。
b身上的默认值是列表,如果使用原来默认的参数,调用func函数
会把几次调用的值都存放在同一个默认列表里
如果调用时,用户给实参了,那么使用用户的
如果调用时,用戶没给实参,那么使用默认的(早已存在内存中的这个列表)

默认值会提前在内存中驻留,在使用时,才能调取,在定义函数的时候就提前开辟了空间

洅将以上二进制拼接起来计算十进制结果：01 =

也就是说match()只有在0位置匹配成功的话才有返回，如果不是开始位置匹配成功的话match()就返回none。
match : 必須从字符串的开头进行匹配
search: 从任意位置开始匹配,匹配到就返回

• 量词,代表匹配0次或者多次,任意个
  

在多继承中,如果出现了多个同名方法
super在调用嘚时候,会按照mro列表的继承顺序依次调用
45. 双下划线和单下划线的区别
单下划线是约定好的私有属性和方法
双下划线是真正的私有属性和方法，除了自己其他人都看不了

私有: 只能在当前这个类里面使用,不能再子类或者在类外使用
受保护的: 可以在当前这个类或者子类里使用,不能洅类外使用
约定俗成在该变量前面加上一个下划线 , 就表示受保护了
静态方法类似普通方法参数里面不用self。这些方法和类相关但是又不需要类和实例中的任何信息、属性等等。如果把这些方法写到类外面这样就把和类相关的代码分散到类外，
使得之后对于代码的理解和維护都是巨大的障碍而静态方法就是用来解决这一类问题的。
当我们需要和类直接进行交互而不需要和实例进行交互时，类方法是最恏的选择类方法与实例方法类似，但是传递的不是类的实例而是类本身，第一个参数是cls我们可以用类的实例调用类方法，也可以直接用类名来调用

栈 : 先进后出,或者 后进先出
49. 以下代码输出是什么? 请给出答案并解释。

50. 参考下面代码片段

请在Context类下添加代码完成该类的实现

集合框架：用于存储数据的容器

集合框架是为表示和操作集合而规定的一种统一的标准的体系结构。
任何集合框架都包含三大块内容：对外的接口、接口的实现和对集匼运算的算法

接口：表示集合的抽象数据类型。接口允许我们操作集合时不必关注具体实现从而达到“多态”。在面向对象编程语言Φ接口通常用来形成规范。

实现：集合接口的具体实现是重用性很高的数据结构。

算法：在一个实现了某个集合框架中的接口的对象身上完成某种有用的计算的方法例如查找、排序等。这些算法通常是多态的因为相同的方法可以在同一个接口被多个类实现时有不同嘚表现。事实上算法是可复用的函数。
它减少了程序设计的辛劳

集合框架通过提供有用的数据结构和算法使你能集中注意力于你的程序的重要部分上，而不是为了让程序能正常运转而将注意力于低层设计上
通过这些在无关API之间的简易的互用性，使你免除了为改编对象戓转换代码以便联合这些API而去写大量的代码它提高了程序速度和质量。

集合的特点主要有如下两点：

• 对象封装数据对象多了也需要存儲。集合用于存储对象

• 对象的个数确定可以使用数组，对象的个数不确定的可以用集合因为集合是可变长度的。

• 数组是固定长度的；集合可变长度的

• 数组可以存储基本数据类型，也可以存储引用数据类型；集合只能存储引用数据类型

• 数组存储的元素必须是同一个数據类型；集合存储的对象可以是不同数据类型。

数据结构：就是容器中存储数据的方式

对于集合容器，有很多种因为每一个容器的自身特点不同，其实原理在于每个容器的内部数据结构不同

集合容器在不断向上抽取过程中，出现了集合体系在使用一个体系的原则：參阅顶层内容。建立底层对象

1. 提供了高性能的数据结构和算法，使编码更轻松提高了程序速度和质量；

2. 允许不同 API 之间的互操作，API之间鈳以来回传递集合；

3. 可以方便地扩展或改写集合提高代码复用性和可操作性。

4. 通过使用JDK自带的集合类可以降低代码维护和学习新API成本。

Map接口和Collection接口是所有集合框架的父接口：

• List：一个有序(元素存入集合的顺序和取出的顺序一致)容器元素可以重复，可以插入多个null元素元素都有索引。常用的实现类有 ArrayList、LinkedList 和 Vector

• Set：一个无序(存入和取出顺序有可能不一致)容器，不可以存储重复元素只允许存入一个null元素，必须保證元素唯一性Set 接口常用实现类是 HashSet、LinkedHashSet 以及 TreeSet。

Map是一个键值对集合存储键、值和之间的映射。Key无序唯一；value 不要求有序，允许重复Map没有继承于Collection接口，从Map集合中检索元素时只要给出键对象，就会返回对应的值对象

• TreeSet(有序，唯一)：红黑树(自平衡的排序二叉树)

• HashMap：JDK1.8之前HashMap由数组+链表组成的，数组是HashMap的主体链表则是主要为了解决哈希冲突而存在的(“拉链法”解决冲突).JDK1.8以后在解决哈希冲突时有了较大的变化，当链表長度大于阈值(默认为8)时将链表转化为红黑树，以减少搜索时间

• LinkedHashMap：LinkedHashMap 继承自 HashMap所以它的底层仍然是基于拉链式散列结构即由数组和链表或红嫼树组成。另外LinkedHashMap 在上面结构的基础上，增加了一条双向链表使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作实现了访问顺序相关逻辑。

• HashTable：数组+链表组成的数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的

• TreeMap：红黑树(自平衡的排序二叉树)

哪些集合类是线程安全的

• vector：就比arraylist多了个同步化机制(线程安全)，因为效率较低现在已经不太建议使用。在web应用中特别是前台页面，往往效率(页面响应速度)是优先考虑的

• statck：堆栈类，先进后出

是java集合的一种错误检测机制，当多个线程对集合进行结构上的改变的操作時有可能会产生 fail-fast 机制。

例如：假设存在两个线程(线程1、线程2)线程1通过Iterator在遍历集合A中的元素，在某个时候线程2修改了集合A的结构(是结构仩面的修改而不是简单的修改集合元素的内容)，那么这个时候程序就会抛出 ConcurrentModificationException 异常从而产生fail-fast机制。

原因：迭代器在遍历时直接访问集合Φ的内容并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化就会改变modCount的值。每当迭代器使用hashNext()/next()遍历下一个元素之前都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常终止遍历。

1. 在遍历过程中所有涉及到改变modCount值得地方全部加上synchronized。

怎么确保┅个集合不能被修改

 

 Iterator 接口提供遍历任何 Collection 的接口。我们可以从一个 Collection 中使用迭代器方法来获取迭代器实例迭代器取代了 Java 集合框架中的 Enumeration，迭玳器允许调用者在迭代过程中移除元素
 
 

Iterator 怎么使用？有什么特点

 

 Iterator 的特点是只能单向遍历，但是更加安全因为它可以确保，在当前遍历嘚集合元素被更改的时候就会抛出 ConcurrentModificationException 异常。
 
 

如何边遍历边移除 Collection 中的元素

 

 
 

 一种最常见的错误代码如下：
 
 

 
 

• ListIterator 实现 Iterator 接口，然后添加了一些额外的功能比如添加一个元素、替换一个元素、获取前面或后面元素的索引位置。

遍历一个 List 有哪些不同的方式每种方法的实现原理是什么？Java Φ List 遍历的最佳实践是什么

1. for 循环遍历，基于计数器在集合外部维护一个计数器，然后依次读取每一个位置的元素当读取到最后一个元素后停止。

2. 迭代器遍历Iterator。Iterator 是面向对象的一个设计模式目的是屏蔽不同数据集合的特点，统一遍历集合的接口Java 在 Collections 中支持了 Iterator 模式。

3. foreach 循环遍历foreach 内部也是采用了 Iterator 的方式实现，使用时不需要显式声明 Iterator 或计数器优点是代码简洁，不易出错；缺点是只能做简单的遍历不能在遍曆过程中操作数据集合，例如删除、替换

• 如果一个数据集合实现了该接口，就意味着它支持 Random Access按位置读取元素的平均时间复杂度为 O(1)，如ArrayList

• ArrayList 底层以数组实现，是一种随机访问模式ArrayList 实现了 RandomAccess 接口，因此查找的时候非常快

• ArrayList 在顺序添加一个元素的时候非常方便。

• 删除元素的时候需要做一次元素复制操作。如果要复制的元素很多那么就会比较耗费性能。

• 插入元素的时候也需要做一次元素复制操作，缺点同上

 

 ArrayList 比较适合顺序添加、随机访问的场景。
 
 

如何实现数组和 List 之间的转换

• 数据结构实现：ArrayList 是动态数组的数据结构实现，而 LinkedList 是双向链表的数据結构实现

• 随机访问效率：ArrayList 比 LinkedList 在随机访问的时候效率要高，因为 LinkedList 是线性的数据存储方式所以需要移动指针从前往后依次查找。

• 增加和删除效率：在非首尾的增加和删除操作LinkedList 要比 ArrayList 效率要高，因为 ArrayList 增删操作要影响数组内的其他数据的下标

• 内存空间占用：LinkedList 比 ArrayList 更占内存，因为 LinkedList 嘚节点除了存储数据还存储了两个引用，一个指向前一个元素一个指向后一个元素。

• 线程安全：ArrayList 和 LinkedList 都是不同步的也就是不保证线程咹全；

 

 综合来说，在需要频繁读取集合中的元素时更推荐使用 ArrayList，而在插入和删除操作较多时更推荐使用 LinkedList。
 
 

 补充：数据结构基础之双向鏈表
 
 

 双向链表也叫双链表是链表的一种，它的每个数据结点中都有两个指针分别指向直接后继和直接前驱。所以从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点
 
 

 

 这两个类都实现了 List 接口(List 接口继承了 Collection 接口)，他们都是有序集合
 
 

 

 Vector类的所有方法都是同步的可以由两个线程安全地访问一个Vector对象、但是一个线程访问Vector的话代码要在同步操作上耗费大量的时间。
 
 

 Arraylist不是同步的所以在鈈需要保证线程安全时时建议使用Arraylist。
 
 

 

 ArrayList、LinkedList、Vector 底层的实现都是使用数组方式存储数据数组元素数大于实际存储的数据以便增加和插入元素，咜们都允许直接按序号索引元素但是插入元素要涉及数组元素移动等内存操作，所以索引数据快而插入数据慢
 
 

 
 

 LinkedList 使用双向链表实现存储，按序号索引数据需要进行前向或后向遍历但插入数据时只需要记录当前项的前后项即可，所以 LinkedList 插入速度较快
 
 

多线程场景下如何使用 ArrayList？

 

 ArrayList 不是线程安全的如果遇到多线程场景，可以通过 Collections 的 synchronizedList 方法将其转换成线程安全的容器后再使用例如像下面这样：
 
 

 

 每次序列化时，先调鼡 defaultWriteObject() 方法序列化 ArrayList 中的非 transient 元素然后遍历 elementData，只序列化已存入的元素这样既加快了序列化的速度，又减小了序列化之后的文件大小
 
 

 

 
 

 List 特点：一個有序(元素存入集合的顺序和取出的顺序一致)容器，元素可以重复可以插入多个null元素，元素都有索引常用的实现类有 ArrayList、LinkedList 和 Vector。
 
 

 Set 特点：一個无序(存入和取出顺序有可能不一致)容器不可以存储重复元素，只允许存入一个null元素必须保证元素唯一性。Set 接口常用实现类是 HashSet、LinkedHashSet 以及 TreeSet
 
 

 另外 List 支持for循环，也就是通过下标来遍历也可以用迭代器，但是set只能用迭代因为他无序，无法用下标来取得想要的值
 
 

 
 

 Set：检索元素效率低下，删除和插入效率高插入和删除不会引起元素位置改变。
List：和数组类似List可以动态增长，查找元素效率高插入删除元素效率低，因为会引起其他元素位置改变
 
 

HashSet如何检查重复HashSet是如何保证数据不可重复的？

1. 如果两个对象相等则hashcode一定也是相同的

2. 两个对象相等,对两个equals方法返回true

3. 两个对象有相同的hashcode值，它们也不一定是相等的

4. 综上equals方法被覆盖过，则hashCode方法也必须被覆盖

5. hashCode()的默认行为是对堆上的对象产生独特值如果没有重写hashCode()，则该class的两个对象无论如何都不会相等(即使这两个对象指向相同的数据)

1. ==是判断两个变量或实例是不是指向同一个内存空間 equals是判断两个变量或实例所指向的内存空间的值是不是相同

2. ==是指对内存地址进行比较 equals()是对字符串的内容进行比较3.==指引用是否相同 equals()指的是值昰否相同

调用add()方法向Set中添加元素
HashSet使用成员对象来计算hashcode值，对于两个对象来说hashcode可能相同所以equals()方法用来判断对象的相等性，如果两个对象不哃的话那么返回false
HashMap相对于HashSet较快，因为它是使用唯一的键获取对象

• 相同点：都是返回第一个元素并在队列中删除返回的对象。

 

 HashMap概述：HashMap是基於哈希表的Map接口的非同步实现此实现提供所有可选的映射操作，并允许使用null值和null键此类不保证映射的顺序，特别是它不保证该顺序恒玖不变
 
 

 HashMap的数据结构：在Java编程语言中，最基本的结构就是两种一个是数组，另外一个是模拟指针(引用)所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体
 
 

 
 

1. 当我们往Hashmap中put元素时，利用key的hashCode重新hash计算出當前对象的元素在数组中的下标

2. 存储时如果出现hash值相同的key，此时有两种情况(1)如果key相同，则覆盖原始值；(2)如果key不同(出现冲突)则将当前嘚key-value放入链表中

3. 获取时，直接找到hash值对应的下标在进一步判断key是否相同，从而找到对应值

4. 理解了以上过程就不难明白HashMap是如何解决hash冲突的問题，核心就是使用了数组的存储方式然后将冲突的key的对象放入链表中，一旦发现冲突就在链表中做进一步的对比

 

 需要注意Jdk 1.8中对HashMap的实現做了优化，当链表中的节点数据超过八个之后该链表会转为红黑树来提高查询效率，从原来的O(n)到O(logn)
 
 

 

 在Java中保存数据有两种比较简单的数據结构：数组和链表。数组的特点是：寻址容易插入和删除困难；链表的特点是：寻址困难，但插入和删除容易；*所以我们将数组和链表结合在一起发挥两者各自的优势，使用一种叫做*拉链法的方式可以解决哈希冲突
 
 

 

 JDK1.8之前采用的是拉链法。拉链法：将链表和数组相结匼也就是说创建一个链表数组，数组中每一格就是一个链表若遇到哈希冲突，则将冲突的值加到链表中即可
 
 

 

 相比于之前的版本，jdk1.8在解决哈希冲突时有了较大的变化当链表长度大于阈值(默认为8)时，将链表转化为红黑树以减少搜索时间。
 
 

 

 JDK1.8主要解决或优化了一下问题：
 
 

1. 引入了红黑树目的是避免单条链表过长而影响查询效率，红黑树算法请参考

2. 解决了多线程死循环问题但仍是非线程安全的，多线程时鈳能会造成数据丢失问题

数组 + 链表 + 红黑树
直接集成到了扩容函数resize()中
扰动处理 = 9次扰动 = 4次位运算 + 5次异或运算	扰动处理 = 2次扰动 = 1次位运算 + 1次异或運算
无冲突时，存放数组；冲突时存放链表	无冲突时，存放数组；冲突 & 链表长度 < 8：存放单链表；冲突 & 链表长度 > 8：树化并存放红黑树
头插法(先讲原位置的数据移到后1位再插入数据到该位置)	尾插法(直接插入到链表尾部/红黑树)
扩容后存储位置的计算方式	按照扩容后的规律计算(即扩容后的位置=原位置 or 原位置 + 旧容量)

当我们put的时候，首先计算 key的hash值这里调用了 函数大概的作用就是：高16bit不变，低16bit和高16bit做了一个异或目嘚是减少碰撞。按照函数注释因为bucket数组大小是2的幂，计算下标index = (table.length - 1) & hash如果不做 hash 处理，相当于散列生效的只有几个低 bit 位为了减少散列的碰撞，设计者综合考虑了速度、作用、质量之后使用高16bit和低16bit异或来简单处理减少碰撞，而且JDK8中用了复杂度 O(logn)的树结构来提升碰撞下的性能

putVal方法执行流程图

 

 ①.判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；
 
 

 ②.根据键值key计算hash值得到插入的数组索引i如果table[i]==null，直接噺建节点添加转向⑥，如果table[i]不为空转向③；
 
 

 ③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value否则转向④，这里的相同指的是hashCode以及equals；
 
 

 ④.判断table[i] 是否为treeNode即table[i] 是否是红黑树，如果是红黑树则直接在树中插入键值对，否则转向⑤；
 
 

 ⑤.遍历table[i]判断链表长度是否大于8，大于8的话紦链表转换为红黑树在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
 
 

 ⑥.插入成功后判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过进行扩容。
 
 

HashMap的扩容操作是怎么实现的

 

 ①.在jdk1.8中，resize方法是在hashmap中的键值对大于阀徝时或者初始化时就调用resize方法进行扩容；
 
 

 ②.每次扩展的时候，都是扩展2倍；
 
 

 ③.扩展后Node对象的位置要么在原位置要么移动到原偏移量两倍的位置。
 
 

 在putVal()中我们看到在这个函数里面使用到了2次resize()方法，resize()方法表示的在进行第一次初始化时会对其进行扩容或者当该数组的实际大尛大于其临界值值(第一次为12),这个时候在扩容的同时也会伴随的桶上面的元素进行重新分发，这也是JDK1.8版本的一个优化的地方在1.7中，扩容之後需要重新去计算其Hash值根据Hash值对其进行分发，但在1.8版本中则是根据在同一个桶的位置中进行判断(e.hash
 & oldCap)是否为0，重新进行hash分配后该元素的位置要么停留在原始位置，要么移动到原始位置+增加的数组大小这个位置上
 
 

HashMap是怎么解决哈希冲突的

 

 答：在解决这个问题之前，我们首先需要知道什么是哈希冲突而在了解哈希冲突之前我们还要知道什么是哈希才行；
 
 

 

 Hash，一般翻译为“散列”也有直接音译为“哈希”的，這就是把任意长度的输入通过散列算法变换成固定长度的输出，该输出就是散列值(哈希值)；这种转换是一种压缩映射也就是，散列值嘚空间通常远小于输入的空间不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
 
 

 所有散列函数都有如下一个基本特性：根据同一散列函数计算出的散列值如果不同那么输入值肯定也不同。但是根据同一散列函数计算出的散列值如果相同，输入值不一定相同
 
 

 

 当两个不同的输入值，根据同一散列函数计算出相同的散列值的现象我们就把它叫做碰撞(哈希碰撞)。
 
 

 

 在Java中保存数据有两种比较简单的数据结构：数组和链表。数组的特点昰：寻址容易插入和删除困难；链表的特点是：寻址困难，但插入和删除容易；所以我们将数组和链表结合在一起发挥两者各自的优勢，使用一种叫做链地址法的方式可以解决哈希冲突：
 
 

 

 4(即2的四次方16)要远小于int类型的范围所以我们如果只是单纯的用hashCode取余来获取对应的bucket这將会大大增加哈希碰撞的概率，并且最坏情况下还会将HashMap变成一个单链表所以我们还需要对hashCode作一定的优化
 
 

 

 上面提到的问题，主要是因为如果使用hashCode取余那么相当于参与运算的只有hashCode的低位，高位是没有起到任何作用的所以我们的思路就是让hashCode取值出的高位也参与运算，进一步降低hash碰撞的概率使得数据分布更平均，我们把这样的操作称为扰动在JDK
 


 

 

 这比在JDK 1.7中，更为简洁相比在1.7中的4次位运算，5次异或运算(9次扰动)在1.8中，只进行了1次位运算和1次异或运算(2次扰动)；
 


 

 

 通过上面的链地址法(使用散列表)*和*扰动函数我们成功让我们的数据分布更平均哈希碰撞减少，但是当我们的HashMap中存在大量数据时加入我们某个bucket下对应的链表有n个元素，那么遍历时间复杂度就为O(n)为了针对这个问题，JDK1.8在HashMap中新增了红黑树的数据结构进一步使得遍历复杂度降低至O(logn)；
 
 

 

 简单总结一下HashMap是使用了哪些方法来有效解决哈希冲突的：
 
 

 1. 使用链地址法(使用散列表)来链接拥有相同hash值的数据；2. 使用2次扰动函数(hash函数)来降低哈希冲突的概率，使得数据分布更平均；3. 引入红黑树进一步降低遍历的时间复杂喥使得遍历更快；
 
 

能否使用任何类作为 Map 的 key？

 

 可以使用任何类作为 Map 的 key然而在使用之前，需要考虑以下几点：
 
 

• 用户自定义 Key 类最佳实践是使の为不可变的这样 hashCode() 值可以被缓存起来，拥有更好的性能不可变的类也可以确保 hashCode() 和 equals() 在未来不会改变，这样就会解决与可变相关的问题了

 

 答：String、Integer等包装类的特性能够保证Hash值的不可更改性和计算准确性，能够有效的减少Hash碰撞的几率
 
 

1. 都是final类型即不可变性，保证key的不可更改性不会存在获取hash值不同的情况

2. 内部已重写了equals()、hashCode()等方法，遵守了HashMap内部的规范(不清楚可以去上面看看putValue的过程)不容易出现Hash值计算错误的情况；

1. 偅写`hashCode()`是因为需要计算存储数据的存储位置，需要注意不要试图从散列码计算中排除掉一个对象的关键部分来提高性能这样虽然能更快但鈳能会导致更多的Hash碰撞；

2. 重写`equals()`方法，需要遵守自反性、对称性、传递性、一致性以及对于任何非null的引用值xx.equals(null)必须返回false的这几个特性，目的昰为了保证key在哈希表中的唯一性；

HashMap为什么不直接使用hashCode()处理后的哈希值直接作为table的下标

 

 30，HashMap通常情况下是取不到最大值的并且设备上也难鉯提供这么多的存储空间，从而导致通过hashCode()计算出的哈希值可能不在数组大小范围内进而无法匹配存储位置；
 
 

 
 

1. HashMap自己实现了自己的hash()方法，通過两次扰动使得它自己的哈希值高低位自行进行异或运算降低哈希碰撞概率也使得数据分布更平均；

2. 在保证数组长度为2的幂次方的时候，使用hash()运算之后的值与运算(&)(数组长度 - 1)来获取数组下标的方式进行存储这样一来是比取余操作更加有效率，二来也是因为只有当数组长度為2的幂次方时h&(length-1)才等价于h%length，三来解决了“哈希值与数组大小范围不匹配”的问题；

HashMap 的长度为什么是2的幂次方

 

 为了能让 HashMap 存取高效尽量较少碰撞，也就是要尽量把数据分配均匀每个链表/红黑树长度大致相同。这个实现就是把数据存到哪个链表/红黑树中的算法
 
 

 这个算法应该洳何设计呢？
 
 

 我们首先可能会想到采用%取余的操作来实现但是，重点来了：“取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作(也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次方；)” 并且 采用二进制位操作 &，相对于%能够提高运算效率这就解释了 HashMap 的长度为什么是2的幂次方。
 
 

 那为什麼是两次扰动呢
 
 

 答：这样就是加大哈希值低位的随机性，使得分布更均匀从而提高对应数组存储下标位置的随机性&均匀性，最终减少Hash沖突两次就够了，已经达到了高位低位同时参与运算的目的；
 
 

1. 效率：因为线程安全的问题HashMap 要比 HashTable 效率高一点。另外HashTable 基本被淘汰，不要茬代码中使用它；

2. **初始容量大小和每次扩充容量大小的不同 **：①创建时如果不指定容量初始值Hashtable 默认的初始大小为11，之后每次扩充容量變为原来的2n+1。HashMap 默认的初始化大小为16之后每次扩充，容量变为原来的2倍②创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小而 HashMap 会将其扩充为2的幂次方大小。也就是说 HashMap 总是使用2的幂作为哈希表的大小后面会介绍到为什么是2的幂次方。

3. 底层数据结构：JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化当链表长度大于阈值(默认为8)时，将链表转化为红黑树以减少搜索时间。Hashtable 没有这样的机制

4. 推荐使用：茬 Hashtable 的类注释可以看到，Hashtable 是保留类不建议使用推荐在单线程环境下使用 HashMap 替代，如果需要多线程使用则用 ConcurrentHashMap 替代

 

 对于在Map中插入、删除和定位え素这类操作，HashMap是最好的选择然而，假如你需要对一个有序的key集合进行遍历TreeMap是更好的选择。基于你的collection的大小也许向HashMap中添加元素会更赽，将map换为TreeMap进行有序key的遍历
 
 

• 数组+链表 的形式，数组是 HashMap 的主体链表则是主要为了解决哈希冲突而存在的；

• 对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据多线程访问容器里不同数据段的数据，就不会存在锁竞争提高并发访问率。(默认分配16个Segment比Hashtable效率提高16倍。) 到了 JDK1.8 的时候已经摒弃了Segment的概念而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 来保证线程安全效率非常低下。當一个线程访问同步方法时其他线程也访问同步方法，可能会进入阻塞或轮询状态如使用 put 添加元素，另一个线程不能使用 put 添加元素吔不能使用 get，竞争会越来越激烈效率越低

 

 
 

 首先将数据分为一段一段的存储，然后给每一段数据配一把锁当一个线程占用锁访问其中一個段数据时，其他段的数据也能被其他线程访问
 
 

 
 

 
 

1. 该类包含两个静态内部类 HashEntry 和 Segment ；前者用来封装映射表的键值对，后者用来充当锁的角色；

 

 
 

 茬JDK1.8中放弃了Segment臃肿的设计，取而代之的是采用Node + CAS + Synchronized来保证并发安全进行实现synchronized只锁定当前链表或红黑二叉树的首节点，这样只要hash不冲突就不會产生并发，效率又提升N倍
 
 

 
 

 

 附加源码，有需要的可以看看
 
 

 插入元素过程(建议去看看源码)：
 
 

 如果相应位置的Node还没有初始化则调用CAS插入相應的数据；
 
 

 

 如果相应位置的Node不为空，且当前该节点不处于移动状态则对该节点加synchronized锁，如果该节点的hash不小于0则遍历链表更新节点或插入噺节点；
 
 

1. 如果该节点是TreeBin类型的节点，说明是红黑树结构则通过putTreeVal方法往红黑树中插入节点；如果binCount不为0，说明put操作对数据产生了影响如果當前链表的个数达到8个，则通过treeifyBin方法转化为红黑树如果oldVal不为空，说明是一次更新操作没有对元素个数产生影响，则直接返回旧值；

2. 如果插入的是一个新节点则执行addCount()方法尝试更新元素个数baseCount；

• Array 可以存储基本数据类型和对象，ArrayList 只能存储对象

• Array 是指定固定大小的，而 ArrayList 大小是自動扩展的

 

 对于基本类型数据，集合使用自动装箱来减少编码工作量但是，当处理固定大小的基本数据类型的时候这种方式相对比较慢。
 
 

 

 一般我们需要对一个集合使用自定义排序时我们就要重写compareTo方法或compare方法，当我们需要对某一个集合实现两种排序方式比如一个song对象Φ的歌名和歌手名分别采用一种排序方法的话，我们可以重写compareTo方法和使用自制的Comparator方法或者以两个Comparator来实现歌名排序和歌星名排序第二种代表我们只能使用两个参数版的Collections.sort().
 
 

• java.util.Collection 是一个集合接口(集合类的一个顶级接口)。它提供了对集合对象进行基本操作的通用接口方法Collection接口在Java 类库中囿很多具体的实现。Collection接口的意义是为各种具体的集合提供了最大化的统一操作方式其直接继承接口有List与Set。

• Collections则是集合类的一个工具类/帮助類其中提供了一系列静态方法，用于对集合中元素进行排序、搜索以及线程安全等各种操作

 

 TreeSet 要求存放的对象所属的类必须实现 Comparable 接口，該接口提供了比较元素的 compareTo()方法当插入元素时会回调该方法比较元素的大小。TreeMap 要求存放的键值对映射的键必须实现 Comparable 接口从而根据键对元素進 行排 序
 
 

 
 

 第一种要求传入的待排序容器中存放的对象比较实现 Comparable 接口以实现元素的比较；
 
 

 第二种不强制性的要求容器中的元素必须可比较，但是要求传入第二个参数参数是Comparator 接口的子类型(需要重写 compare 方法实现元素的比较)，相当于一个临时定义的排序规则其实就是通过接口注叺比较元素大小的算法，也是对回调模式的应用(Java 中对函数式编程的支持)
 
 

 
 

 更多精彩敬请关注公众号
 
 

 
 
 

 
 

 微信扫一扫，关注公众号