java面试题整理(3)

JAVA常考点3

目录

1. 讲下JAVA的运行时区域 1

2、简单说下垃圾回收机制 2

3、TCP和UDP的区别 7

4、项目是怎样预防sql注入的 7

5、 MySQL存储引擎中的MyISAM和InnoDB区别 7

6、B树与B+树简明扼要的区别 11

6、 解决哈希冲突的三种方法(拉链法、开放地址法、再散列法) 14

7、forward(转发)和redirect(重定向)有什么区别 16

8、set、list、map 16

9、 HashMap、Hashtable、ConcurrentHashMap的原理与区别 19

 

 

 

 

 

1. 讲下JAVA的运行时区域

 

回答:运行时数据区整体分为两类 线程私有和线程共享。

 

线程私有的包括:

 

(1)程序计数器

 

若正在执行的是java方法,则计数器记录的是正在执行的字节码指令的地址

若正在执行的是native方法,则计数器为空

该区域是唯一一个不会导致outofmemoryError的区域

 

(2)虚拟机栈

 

描述的是Java方法执行的内存模型:每个方法都会创建一个栈帧用于存储局部变量表,操作数栈,动态链接,方法出口等信息

 

局部变量表存放了编译期可知的基本数据类型,对象引用,和returnAddress类型(指向一条字节码指令地址),局部变量表的内存空间在编译器确定,在运行期不变

可导致两种异常:线程请求的栈深度大于虚拟机允许的深度-StackOverflowError;虚拟机无法申请到足够的内存-OutOfMemoryError

 

(3)本地方法栈

和虚拟机栈类似,但它是为Native方法服务的

 

 

线程共享的包括:

 

(1)堆

 

java堆是被所有线程共享的内存区域,在虚拟机启动时创建,用来分配对象实例和数组

堆是垃圾回收器主要管理的区域,堆可分为新生代和老年代

从内存分配角度看,堆可划分出多个线程私有的分配缓冲区(TLAB)

大小可通过 -Xmx 和 -Xms 控制

 

(2)方法区

 

用来存放虚拟机加载的类信息,常量,静态变量,即时编译器编译后的代码等信息

GC会回收该区域的常量池和进行类型的卸载 *运行时常量池

♣ Class文件的常量池用于存放编译期生成的各种字面量和符号引用,这部分内容将在类加载后存放在运行时常量池中

♣ 还把翻译出来的直接引用也放在运行时常量池中,运行时产生的常量也放在里面

 

 

 

2、简单说下垃圾回收机制

大致思路: 要进行垃圾回收,首先要判断一个对象是否活着,这就引出了两种方法…

 

引用计数法和可达性分析法

 

gc roots 类型

 

引用类型

 

两次标记过程

 

垃圾回收算法

 

内存分配策略

 

触发垃圾回收

 

垃圾回收器

 

也会回收方法区

 

 

回答:要进行垃圾回收,首先要判断对象是否存活,引出了两个方法:

 

  •  

引用计数法

    • 思想:给对象设置引用计数器,没引用该对象一次,计数器就+1,引用失效时,计数器就-1,当任意时候引用计数器的值都为0时,则该对象可被回收
    • Java不适用原因:无法解决对象互相循环引用的问题
  •  

可达性分析法

    • 以GC Roots为起点,从这些起点开始向下搜索,经过的路径称为引用链。若一个对象到GC Roots之间没有任何引用链,则该对象是不可达的。
    • 那么可作为GC Roots的对象有
      • 虚拟机栈(栈帧中的局部变量表)中引用的对象
      • 方法区中类静态属性引用的对象
      • 方法区中常量引用的对象
      • 本地方法栈中JNI(Native方法)引用的对象
  •  

在可达性分析过程中,对象引用类型会对对象的生命周期产生影响,JAVA中有这几种类型的引用:

    • 强引用:只要该引用还有效,GC就不会回收
    • 软引用:内存空间足够时不进行回收,在内存溢出发生前进行回收、用SoftReference类实现
    • 弱引用:弱引用关联的对象只能存活到下一次Gc收集、用WeakReference类实现
    • 虚引用:无法通过虚引用获得对象实例,也不会对对象的生存时间产生影响、唯一目的:当该对象被Gc收集时,收到一个系统通知。用PhantomReference类实现
    •  

一个对象真正不可用,要经历两次标记过程:

  • 首先进行可达性分析,筛选出与GC Roots没用引用链的对象,进行第一次标记
  • 第一次标记后,再进行一次筛选,筛选条件是是否有必要执行finalize()方法。若对象有没有重写finalize()方法,或者finalize()是否已被jvm调用过,则没必要执行,GC会回收该对象
  • 若有必要执行,则该对象会被放入F-Queue中,由jvm开启一个低优先级的线程去执行它(但不一定等待finalize执行完毕)。
  • Finalize()是对象最后一次自救的机会,若对象在finalize()中重新加入到引用链中,则它会被移出要回收的对象的集合。其他对象则会被第二次标记,进行回收

JAVA中的垃圾回收算法有:

  • 标记-清除(Mark-Sweep)
    • 两个阶段:标记, 清除
    • 缺点:两个阶段的效率都不高;容易产生大量的内存碎片
  • 复制(Copying)
    • 把内存分成大小相同的两块,当一块的内存用完了,就把可用对象复制到另一块上,将使用过的一块一次性清理掉
    • 缺点:浪费了一半内存
  • 标记-整理(Mark-Compact)
    • 标记后,让所有存活的对象移到一端,然后直接清理掉端边界以外的内存
  • 分代收集
    • 把堆分为新生代和老年代
    • 新生代使用复制算法
    • 将新生代内存分为一块大的Eden区和两块小的Survivor;每次使用Eden和一个Survivor,回收时将Eden和Survivor存活的对象复制到另一个Survivor(HotSpot的比例Eden:Survivor = 8:1)
    • 老年代使用标记-清理或者标记-整理
    •  

触发GC又涉及到了内存分配规则: (对象主要分配在Eden,若启动了本地线程分配缓冲,将优先在TLAB上分配)

  • 对象优先在Eden分配
    • 当Eden区没有足够的空间时就会发起一次Minor GC
  • 大对象直接进入老年代
    • 典型的大对象是很长的字符串和数组
  • 长期存活的对象进入老年代
    • 每个对象有年龄计数器,每经过一次GC,计数器值加一,当到达一定程度时(默认15),就会进入老年代
    • 年龄的阈值可通过参数 -XX:MaxTenuringThreshold设置
  • 对象年龄的判定
    • Survivor空间中相同年龄所有对象大小的总和大于Survivor空间的一半,年龄大于等于该年龄的对象就可直接进入老年代,无须等到MaxTenuringThreshold要求的年龄
  • 空间分配担保
    • 发生Minor GC前,jvm会检查老年代最大可用的连续空间是否大于新生代所有对象总空间,若大于,则Minor GC是安全的
    • 若不大于,jvm会查看HandlePromotionFailure是否允许担保失败,若不允许,则改为一次Full GC
    • 若允许担保失败,则检查老年代最大可用的连续空间是否大于历次晋升到老年代对象的平均大小,若大于,则尝试进行Minor GC;若小于,则要改为Full GC

垃圾收集器:

  •  

Serial(串行收集器)

    • 特性:单线程,stop the world,采用复制算法
    • 应用场景:jvm在Client模式下默认的新生代收集器
    • 优点:简单高效
  •  

ParNew

    • 特点:是Serial的多线程版本,采用复制算法
    • 应用场景:在Server模式下常用的新生代收集器,可与CMS配合工作
  •  

Parallel Scavenge

    • 特点:并行的多线程收集器,采用复制算法,吞吐量优先,有自适应调节策略
    • 应用场景:需要吞吐量大的时候
  •  

SerialOld

    • 特点:Serial的老年代版本,单线程,使用标记-整理算法
  •  

Parallel Old

    • Parallel Scavenge的老年代版本,多线程,标记-整理算法
  •  

CMS

    • 特点:以最短回收停顿时间为目标,使用标记-清除算法
    • 过程:
      • 初始标记:stop the world 标记GC Roots能直接关联到的对象
      • 并发标记:进行GC Roots Tracing
      • 重新标记:stop the world;修正并发标记期间因用户程序继续运作而导致标记产生变动的 那一部分对象的标记记录
      • 并发清除:清除对象
    • 优点:并发收集,低停顿
    • 缺点:
      • 对CPU资源敏感
      • 无法处理浮动垃圾(并发清除 时,用户线程仍在运行,此时产生的垃圾为浮动垃圾)
      • 产生大量的空间碎片
  •  

G1

    • 特点:面向服务端应用,将整个堆划分为大小相同的region。
      • 并行与并发
      • 分代收集
      • 空间整合:从整体看是基于“标记-整理”的,从局部(两个region之间)看是基于“复制”的。
      • 可预测的停顿:使用者可明确指定在一个长度为M毫秒的时间片段内,消耗在垃圾收集上的时间不得超过N毫秒。
    • 执行过程:
      • 初始标记:stop the world 标记GC Roots能直接关联到的对象
      • 并发标记:可达性分析
      • 最终标记:修正在并发标记期间因用户程序继续运作而导致标记产生变动的那一部分标记记录
      • 筛选回收:筛选回收阶段首先对各个Region的回收价值和成本进行排序,根据用户所期望的GC停顿时间来制定回收计划
  •  

GC自适应调节策略 Parallel Scavenge收集器有一个参数-XX:+UseAdaptiveSizePolicy。当这个参数打开之后,就不需要手工指定新生代的大小、Eden与Survivor区的比例、晋升老年代对象年龄等细节参数了,虚拟机会根据当前系统的运行情况收集性能监控信息,动态调整这些参数以提供最合适的停顿时间或者最大的吞吐量,这种调节方式称为GC自适应的调节策略(GC Ergonomics)。

  •  

(垃圾回收器部分重点讲CMS和G1)

最后提一下也会回收方法区:

  • 永久代中主要回收两部分内容:废弃常量和无用的类
  • 废弃常量回收和对象的回收类似
  • 无用的类需满足3个条件
    • 该类的所有实例对象已被回收
    • 加载该类的ClassLoader已被回收
    • 该类的Class对象没有在任何地方被引用,无法在任何地方通过反射访问该类的方法

上面的知识点在你多刷几遍书,脑中形成相应的知识网后能很全面的说出来。

3、TCP和UDP的区别

  • TCP面向连接(如打电话要先拨号建立连接) UDP是无连接的,即发送数据之前不需要建立连接
  • TCP提供可靠的服务。也就是说,通过TCP连接传送的数据,无差错,不丢失,不重复,且按序到达;UDP尽最大努力交付,即不保证可靠交付
  • TCP面向字节流,实际上是TCP把数据看成一连串无结构的字节流;UDP是面向报文的
  • UDP没有拥塞控制,因此网络出现拥塞不会使源主机的发送速率降低(对实时应用很有用,如IP电话,实时视频会议等)
  • 每一条TCP连接只能是点到点的;UDP支持一对一,一对多,多对一和多对多的交互通信
  • TCP首部开销20字节;UDP的首部开销小,只有8个字节
  • TCP的逻辑通信信道是全双工的可靠信道,UDP则是不可靠信道

 

 

4、项目是怎样预防sql注入的

回答:用的是mybatis,sql语句中用#{},#{}表示一个占位符号,通过#{}可以实现preparedStatement向占位符中设置值,jdbc有个预编译的过程可以有效预防sql注入,尽量不用${},它是个拼接符,用来拼接sql字符串。

 

 

 

 

  1. MySQL存储引擎中的MyISAM和InnoDB区别

在使用MySQL的过程中对MyISAM和InnoDB这两个概念存在了些疑问,到底两者引擎有何分别一直是存在我心中的疑问。为了解开这个谜题,搜寻了网络,找到了如下信息:

 

MyISAM是MySQL的默认数据库引擎(5.5版之前),由早期的ISAM(Indexed Sequential Access Method:有索引的顺序访问方法)所改良。虽然性能极佳,但却有一个缺点:不支持事务处理(transaction)。不过,在这几年的发展下,MySQL也导入了InnoDB(另一种数据库引擎),以强化参考完整性与并发违规处理机制,后来就逐渐取代MyISAM。

 

InnoDB,是MySQL的数据库引擎之一,为MySQL AB发布binary的标准之一。InnoDB由Innobase Oy公司所开发,2006年五月时由甲骨文公司并购。与传统的ISAM与MyISAM相比,InnoDB的最大特色就是支持了ACID兼容的事务(Transaction)功能,类似于PostgreSQL。目前InnoDB采用双轨制授权,一是GPL授权,另一是专有软件授权。

 

MyISAM与InnoDB的区别是什么?

 

存储结构

 

MyISAM:每个MyISAM在磁盘上存储成三个文件。第一个文件的名字以表的名字开始,扩展名指出文件类型。.frm文件存储表定义。数据文件的扩展名为.MYD (MYData)。索引文件的扩展名是.MYI (MYIndex)。

InnoDB:所有的表都保存在同一个数据文件中(也可能是多个文件,或者是独立的表空间文件),InnoDB表的大小只受限于操作系统文件的大小,一般为2GB。

 

存储空间

 

MyISAM:可被压缩,存储空间较小。支持三种不同的存储格式:静态表(默认,但是注意数据末尾不能有空格,会被去掉)、动态表、压缩表。

InnoDB:需要更多的内存和存储,它会在主内存中建立其专用的缓冲池用于高速缓冲数据和索引。

 

可移植性、备份及恢复

 

MyISAM:数据是以文件的形式存储,所以在跨平台的数据转移中会很方便。在备份和恢复时可单独针对某个表进行操作。

InnoDB:免费的方案可以是拷贝数据文件、备份 binlog,或者用 mysqldump,在数据量达到几十G的时候就相对痛苦了。

 

事务支持

 

MyISAM:强调的是性能,每次查询具有原子性,其执行数度比InnoDB类型更快,但是不提供事务支持。

InnoDB:提供事务支持事务,外部键等高级数据库功能。 具有事务(commit)、回滚(rollback)和崩溃修复能力(crash recovery capabilities)的事务安全(transaction-safe (ACID compliant))型表。

 

AUTO_INCREMENT

 

MyISAM:可以和其他字段一起建立联合索引。引擎的自动增长列必须是索引,如果是组合索引,自动增长可以不是第一列,他可以根据前面几列进行排序后递增。

InnoDB:InnoDB中必须包含只有该字段的索引。引擎的自动增长列必须是索引,如果是组合索引也必须是组合索引的第一列。

 

表锁差异

 

MyISAM:只支持表级锁,用户在操作myisam表时,select,update,delete,insert语句都会给表自动加锁,如果加锁以后的表满足insert并发的情况下,可以在表的尾部插入新的数据。

InnoDB:支持事务和行级锁,是innodb的最大特色。行锁大幅度提高了多用户并发操作的新能。但是InnoDB的行锁,只是在WHERE的主键是有效的,非主键的WHERE都会锁全表的。

 

全文索引

 

MyISAM:支持 FULLTEXT类型的全文索引

InnoDB:不支持FULLTEXT类型的全文索引,但是innodb可以使用sphinx插件支持全文索引,并且效果更好。

 

表主键

 

MyISAM:允许没有任何索引和主键的表存在,索引都是保存行的地址。

InnoDB:如果没有设定主键或者非空唯一索引,就会自动生成一个6字节的主键(用户不可见),数据是主索引的一部分,附加索引保存的是主索引的值。

 

表的具体行数

 

MyISAM:保存有表的总行数,如果select count(*) from table;会直接取出出该值。

InnoDB:没有保存表的总行数,如果使用select count(*) from table;就会遍历整个表,消耗相当大,但是在加了wehre条件后,myisam和innodb处理的方式都一样。

 

CURD操作

 

MyISAM:如果执行大量的SELECT,MyISAM是更好的选择。

InnoDB:如果你的数据执行大量的INSERT或UPDATE,出于性能方面的考虑,应该使用InnoDB表。DELETE 从性能上InnoDB更优,但DELETE FROM table时,InnoDB不会重新建立表,而是一行一行的删除,在innodb上如果要清空保存有大量数据的表,最好使用truncate table这个命令。

 

外键

 

MyISAM:不支持

InnoDB:支持

通过上述的分析,基本上可以考虑使用InnoDB来替代MyISAM引擎了,原因是InnoDB自身很多良好的特点,比如事务支持、存储 过程、视图、行级锁定等等,在并发很多的情况下,相信InnoDB的表现肯定要比MyISAM强很多。另外,任何一种表都不是万能的,只用恰当的针对业务类型来选择合适的表类型,才能最大的发挥MySQL的性能优势。如果不是很复杂的Web应用,非关键应用,还是可以继续考虑MyISAM的,这个具体情况可以自己斟酌。

 

 

在MySQL数据库中,常用的引擎主要就是2个:Innodb和MyIASM。

 

 

 

其他的解释:   首先:

 

(1)简单介绍这两种引擎,以及该如何去选择。

(2)这两种引擎所使用的数据结构是什么。

 

 

a.Innodb引擎,Innodb引擎提供了对数据库ACID事务的支持。并且还提供了行级锁和外键的约束。它的设计的目标就是处理大数据容量的数据库系统。它本身实际上是基于Mysql后台的完整的系统。Mysql运行的时候,Innodb会在内存中建立缓冲池,用于缓冲数据和索引。但是,该引擎是不支持全文搜索的。同时,启动也比较的慢,它是不会保存表的行数的。当进行Select count(*) from table指令的时候,需要进行扫描全表。所以当需要使用数据库的事务时,该引擎就是首选。由于锁的粒度小,写操作是不会锁定全表的。所以在并发度较高的场景下使用会提升效率的。

 

b.MyIASM引擎,它是MySql的默认引擎,但不提供事务的支持,也不支持行级锁和外键。因此当执行Insert插入和Update更新语句时,即执行写操作的时候需要锁定这个表。所以会导致效率会降低。不过和Innodb不同的是,MyIASM引擎是保存了表的行数,于是当进行Select count(*) from table语句时,可以直接的读取已经保存的值而不需要进行扫描全表。所以,如果表的读操作远远多于写操作时,并且不需要事务的支持的。可以将MyIASM作为数据库引擎的首先。

 

补充2点:

 

c.大容量的数据集时趋向于选择Innodb。因为它支持事务处理和故障的恢复。Innodb可以利用数据日志来进行数据的恢复。主键的查询在Innodb也是比较快的。

 

d.大批量的插入语句时(这里是INSERT语句)在MyIASM引擎中执行的比较的快,但是UPDATE语句在Innodb下执行的会比较的快,尤其是在并发量大的时候。

 

两种引擎所使用的索引的数据结构是什么?

 

答案:都是B+树!

 

MyIASM引擎,B+树的数据结构中存储的内容实际上是实际数据的地址值。也就是说它的索引和实际数据是分开的,只不过使用索引指向了实际数据。这种索引的模式被称为非聚集索引。

 

Innodb引擎的索引的数据结构也是B+树,只不过数据结构中存储的都是实际的数据,这种索引有被称为聚集索引。

 

 

 

6、B树与B+树简明扼要的区别

看了很多讲B树和B+树的文章,大多都是围绕各自的特性讲的,第一,树中每个结点最多含有m个孩子(m>=2);第二,……我也是从这些文章里弄懂了各种树的联系与区别,要真写,我可能还不如人家写得好。所以就在这里简明扼要的用几张图记录一下主要区别吧。 

 

  为了便于说明,我们先定义一条数据记录为一个二元组[key,data],key为记录的键值,key唯一;data为数据记录除key外的数据。

 

 

B树

 

  每个节点都存储key和data,所有节点组成这棵树,并且叶子节点指针为null。

 

  

 

B+树

 

  只有叶子节点存储data,叶子节点包含了这棵树的所有键值,叶子节点不存储指针。

  

 

  后来,在B+树上增加了顺序访问指针,也就是每个叶子节点增加一个指向相邻叶子节点的指针,这样一棵树成了数据库系统实现索引的首选数据结构。 

 

  原因有很多,最主要的是这棵树矮胖,呵呵。一般来说,索引很大,往往以索引文件的形式存储的磁盘上,索引查找时产生磁盘I/O消耗,相对于内存存取,I/O存取的消耗要高几个数量级,所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的时间复杂度。树高度越小,I/O次数越少。 

 

  那为什么是B+树而不是B树呢,因为它内节点不存储data,这样一个节点就可以存储更多的key。

 

 

 

  在MySQL中,最常用的两个存储引擎是MyISAM和InnoDB,它们对索引的实现方式是不同的。

 

 

 

MyISAM 

 

  data存的是数据地址。索引是索引,数据是数据。

InnoDB

 

  data存的是数据本身。索引也是数据。

  

 

  了解了数据结构再看索引,一切都不费解了,只是顺着逻辑推而已。

 

 

 

  1. 解决哈希冲突的三种方法(拉链法、开放地址法、再散列法)

上篇博客我们说到了,什么是哈希冲突,其实就是再采用哈希函数对输入域进行映射到哈希表的时候,因为哈希表的位桶的数目远小于输入域的关键字的个数,所以,对于输入域的关键字来说,很可能会产生这样一种情况,也就是,一个关键字会映射到同一个位桶中的情况,这种情况就就叫做哈希冲突,解决哈希冲突的有三种方案,一种叫做拉链法(也叫作链接法、链地址法,一个意思),另外三种分别为开发地址法和再散列法。

 

(1)拉链法

 

上篇博文我们举的例子,HashMap,HashSet其实都是采用的拉链法来解决哈希冲突的,就是在每个位桶实现的时候,我们采用链表(jdk1.8之后采用链表+红黑树)的数据结构来去存取发生哈希冲突的输入域的关键字(也就是被哈希函数映射到同一个位桶上的关键字)。首先来看使用拉链法解决哈希冲突的几个操作:

 

①插入操作:在发生哈希冲突的时候,我们输入域的关键字去映射到位桶(实际上是实现位桶的这个数据结构,链表或者红黑树)中去的时候,我们先检查带插入元素x是否出现在表中,很明显,这个查找所用的次数不会超过装载因子(n/m:n为输入域的关键字个数,m为位桶的数目),它是个常数,所以插入操作的最坏时间复杂度为O(1)的。

 

②查询操作:和①一样,在发生哈希冲突的时候,我们去检索的时间复杂度不会超过装载因子,也就是检索数据的时间复杂度也是O(1)的

 

③删除操作:如果在拉链法中我们想要使用链表这种数据结构来实现位桶,那么这个链表一定是双向链表,因为在删除一个元素x的时候,需要更改x的前驱元素的next指针的属性,把x从链表中删除。这个操作的时间复杂度也是O(1)的。

 

 

 

拉链法的优点

 

与开放定址法相比,拉链法有如下几个优点:

 

①拉链法处理冲突简单,且无堆积现象,即非同义词决不会发生冲突,因此平均查找长度较短;

 

②由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况;

 

③开放定址法为减少冲突,要求装填因子α较小,故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1,且结点较大时,拉链法中增加的指针域可忽略不计,因此节省空间;

 

④在用拉链法构造的散列表中,删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。

 

 

 

拉链法的缺点

 

指针需要额外的空间,故当结点规模较小时,开放定址法较为节省空间,而若将节省的指针空间用来扩大散列表的规模,可使装填因子变小,这又减少了开放定址法中的冲突,从而提高平均查找速度。

 

使用例子:

 

HashMap

 

(2)开发地址法

 

开放地址法有个非常关键的特征,就是所有输入的元素全部存放在哈希表里,也就是说,位桶的实现是不需要任何的链表来实现的,换句话说,也就是这个哈希表的装载因子不会超过1。它的实现是在插入一个元素的时候,先通过哈希函数进行判断,若是发生哈希冲突,就以当前地址为基准,根据再寻址的方法(探查序列),去寻找下一个地址,若发生冲突再去寻找,直至找到一个为空的地址为止。所以这种方法又称为再散列法。

 

有几种常用的探查序列的方法:

 

①线性探查

 

dii=1,2,3,…,m-1;这种方法的特点是:冲突发生时,顺序查看表中下一单元,直到找出一个空单元或查遍全表。

 

(使用例子:ThreadLocal里面的ThreadLocalMap)

 

②二次探查

 

di=12,-12,22,-22,…,k2,-k2    ( k<=m/2 );这种方法的特点是:冲突发生时,在表的左右进行跳跃式探测,比较灵活。

 

③ 伪随机探测

 

di=伪随机数序列;具体实现时,应建立一个伪随机数发生器,(如i=(i+p) % m),生成一个位随机序列,并给定一个随机数做起点,每次去加上这个伪随机数++就可以了。

 

(3)再散列法

 

再散列法其实很简单,就是再使用哈希函数去散列一个输入的时候,输出是同一个位置就再次散列,直至不发生冲突位置

 

缺点:每次冲突都要重新散列,计算时间增加。

 

 

7、forward(转发)和redirect(重定向)有什么区别

 

forward和redirect是什么?

是servlet种的两种主要的跳转方式。forward又叫转发,redirect叫做重定向。

 

forward(转发):

1.是服务器内部的重定向,服务器直接访问目标地址的 url网址,把里面的东西读取出来,但是客户端并不知道,因此用forward的话,客户端浏览器的网址是不会发生变化的。

2.关于request: 由于在整个定向的过程中用的是同一个request,因此forward会将request的信息带到被重定向的jsp或者servlet中使用。

 

redirect(重定向):

1.是客户端的重定向,是完全的跳转。即服务器返回的一个url给客户端浏览器,然后客户端浏览器会重新发送一次请求,到新的url里面,因此浏览器中显示的url网址会发生变化。

2.因为这种方式比forward多了一次网络请求,因此效率会低于forward。

 

 

 

8、set、list、map

List,Set,Map是否继承自Collection接口? 

答:List,Set是,Map不是。 Collection是最基本的集合接口,一个Collection代表一组Object,即Collection的元素。一些Collection允许相同的元素而另一些不行。一些能排序而另一些不行。Java JDK不能提供直接继承自Collection的类,Java JDK提供的类都是继承自Collection的"子接口",如:List和Set。 

注意:Map没有继承Collection接口,Map提供key到value的映射。一个Map中不能包含相同key,每个key只能映射一个value。Map接口提供3种集合的视图,Map的内容可以被当做一组key集合,一组value集合,或者一组key-value映射。 

List按对象进入的顺序保存对象,不做排序或编辑操作。Set对每个对象只接受一次,并使用自己内部的排序方法(通常,你只关心某个元素是否属于Set,而不关心它的顺序--否则应该使用List)。Map同样对每个元素保存一份,但这是基于"键"的,Map也有内置的排序,因而不关心元素添加的顺序。如果添加元素的顺序对你很重要,应该使用 LinkedHashSet或者LinkedHashMap.

 

详细介绍: 

List特点:元素有放入顺序,元素可重复 

Map特点:元素按键值对存储,无放入顺序 

Set特点:元素无放入顺序,元素不可重复(注意:元素虽然无放入顺序,但是元素在set中的位置是有该元素的HashCode决定的,其位置其实是固定的) 

List接口有三个实现类:LinkedList,ArrayList,Vector 

LinkedList:底层基于链表实现,链表内存是散乱的,每一个元素存储本身内存地址的同时还存储下一个元素的地址。链表增删快,查找慢 

ArrayList和Vector的区别:ArrayList是非线程安全的,效率高;Vector是基于线程安全的,效率低 

Set接口有两个实现类:HashSet(底层由HashMap实现),LinkedHashSet 

SortedSet接口有一个实现类:TreeSet(底层由平衡二叉树实现) 

Query接口有一个实现类:LinkList 

Map接口有三个实现类:HashMap,HashTable,LinkeHashMap 

  HashMap非线程安全,高效,支持null;HashTable线程安全,低效,不支持null 

SortedMap有一个实现类:TreeMap 

其实最主要的是,list是用来处理序列的,而set是用来处理集的。Map是知道的,存储的是键值对 

set 一般无序不重复.map kv 结构 list 有序 。

 

 

List的功能方法

 

  实际上有两种List: 一种是基本的ArrayList,其优点在于随机访问元素,另一种是更强大的LinkedList,它并不是为快速随机访问设计的,而是具有一套更通用的方法。

 

List : 次序是List最重要的特点:它保证维护元素特定的顺序。List为Collection添加了许多方法,使得能够向List中间插入与移除元素(这只推荐LinkedList使用。)一个List可以生成ListIterator,使用它可以从两个方向遍历List,也可以从List中间插入和移除元素。

 

ArrayList : 由数组实现的List。允许对元素进行快速随机访问,但是向List中间插入与移除元素的速度很慢。ListIterator只应该用来由后向前遍历ArrayList,而不是用来插入和移除元素。因为那比LinkedList开销要大很多。

 

LinkedList : 对顺序访问进行了优化,向List中间插入与删除的开销并不大。随机访问则相对较慢。(使用ArrayList代替。)还具有下列方法:addFirst(), addLast(), getFirst(), getLast(), removeFirst() 和 removeLast(), 这些方法 (没有在任何接口或基类中定义过)使得LinkedList可以当作堆栈、队列和双向队列使用。

 

Set的功能方法

 

Set具有与Collection完全一样的接口,因此没有任何额外的功能,不像前面有两个不同的List。实际上Set就是Collection,只是行为不同。(这是继承与多态思想的典型应用:表现不同的行为。)Set不保存重复的元素(至于如何判断元素相同则较为负责)

 

Set : 存入Set的每个元素都必须是唯一的,因为Set不保存重复元素。加入Set的元素必须定义equals()方法以确保对象的唯一性。Set与Collection有完全一样的接口。Set接口不保证维护元素的次序。

 

HashSet : 为快速查找设计的Set。存入HashSet的对象必须定义hashCode()。

 

TreeSet : 保存次序的Set, 底层为树结构。使用它可以从Set中提取有序的序列。

 

LinkedHashSet : 具有HashSet的查询速度,且内部使用链表维护元素的顺序(插入的次序)。于是在使用迭代器遍历Set时,结果会按元素插入的次序显示。

 

Map的功能方法

 

  方法put(Object key, Object value)添加一个“值”(想要得东西)和与“值”相关联的“键”(key)(使用它来查找)。方法get(Object key)返回与给定“键”相关联的“值”。可以用containsKey()和containsValue()测试Map中是否包含某个“键”或“值”。标准的Java类库中包含了几种不同的Map:HashMap, TreeMap, LinkedHashMap, WeakHashMap, IdentityHashMap。它们都有同样的基本接口Map,但是行为、效率、排序策略、保存对象的生命周期和判定“键”等价的策略等各不相同。

 

  执行效率是Map的一个大问题。看看get()要做哪些事,就会明白为什么在ArrayList中搜索“键”是相当慢的。而这正是HashMap提高速度的地方。HashMap使用了特殊的值,称为“散列码”(hash code),来取代对键的缓慢搜索。“散列码”是“相对唯一”用以代表对象的int值,它是通过将该对象的某些信息进行转换而生成的。所有Java对象都能产生散列码,因为hashCode()是定义在基类Object中的方法。

 

HashMap就是使用对象的hashCode()进行快速查询的。此方法能够显著提高性能。

 

Map : 维护“键值对”的关联性,使你可以通过“键”查找“值”

 

HashMap : Map基于散列表的实现。插入和查询“键值对”的开销是固定的。可以通过构造器设置容量capacity和负载因子load factor,以调整容器的性能。

 

LinkedHashMap : 类似于HashMap,但是迭代遍历它时,取得“键值对”的顺序是其插入次序,或者是最近最少使用(LRU)的次序。只比HashMap慢一点。而在迭代访问时发而更快,因为它使用链表维护内部次序。

 

TreeMap : 基于红黑树数据结构的实现。查看“键”或“键值对”时,它们会被排序(次序由Comparabel或Comparator决定)。TreeMap的特点在于,你得到的结果是经过排序的。TreeMap是唯一的带有subMap()方法的Map,它可以返回一个子树。

 

WeakHashMao : 弱键(weak key)Map,Map中使用的对象也被允许释放: 这是为解决特殊问题设计的。如果没有map之外的引用指向某个“键”,则此“键”可以被垃圾收集器回收。

 

IdentifyHashMap : 使用==代替equals()对“键”作比较的hash map。专为解决特殊问题而设计。

 

 

 

  1. HashMap、Hashtable、ConcurrentHashMap的原理与区别

如果你去面试,面试官不问你这个问题,你来找我^_^

下面直接来干货,先说这三个Map的区别:

HashTable

  • 底层数组+链表实现,无论key还是value都不能为null,线程安全,实现线程安全的方式是在修改数据时锁住整个HashTable,效率低,ConcurrentHashMap做了相关优化
  • 初始size为11,扩容:newsize = olesize*2+1
  • 计算index的方法:index = (hash & 0x7FFFFFFF) % tab.length

HashMap

  • 底层数组+链表实现,可以存储null键和null值,线程不安全
  • 初始size为16,扩容:newsize = oldsize*2,size一定为2的n次幂
  • 扩容针对整个Map,每次扩容时,原来数组中的元素依次重新计算存放位置,并重新插入
  • 插入元素后才判断该不该扩容,有可能无效扩容(插入后如果扩容,如果没有再次插入,就会产生无效扩容)
  • 当Map中元素总数超过Entry数组的75%,触发扩容操作,为了减少链表长度,元素分配更均匀
  • 计算index方法:index = hash & (tab.length – 1)

 

HashMap的初始值还要考虑加载因子:

  •  哈希冲突:若干Key的哈希值按数组大小取模后,如果落在同一个数组下标上,将组成一条Entry链,对Key的查找需要遍历Entry链上的每个元素执行equals()比较。
  • 加载因子:为了降低哈希冲突的概率,默认当HashMap中的键值对达到数组大小的75%时,即会触发扩容。因此,如果预估容量是100,即需要设定100/0.75=134的数组大小。
  • 空间换时间:如果希望加快Key查找的时间,还可以进一步降低加载因子,加大初始大小,以降低哈希冲突的概率。

HashMap和Hashtable都是用hash算法来决定其元素的存储,因此HashMap和Hashtable的hash表包含如下属性:

  • 容量(capacity):hash表中桶的数量
  • 初始化容量(initial capacity):创建hash表时桶的数量,HashMap允许在构造器中指定初始化容量
  • 尺寸(size):当前hash表中记录的数量
  • 负载因子(load factor):负载因子等于“size/capacity”。负载因子为0,表示空的hash表,0.5表示半满的散列表,依此类推。轻负载的散列表具有冲突少、适宜插入与查询的特点(但是使用Iterator迭代元素时比较慢)

除此之外,hash表里还有一个“负载极限”,“负载极限”是一个0~1的数值,“负载极限”决定了hash表的最大填满程度。当hash表中的负载因子达到指定的“负载极限”时,hash表会自动成倍地增加容量(桶的数量),并将原有的对象重新分配,放入新的桶内,这称为rehashing。

HashMap和Hashtable的构造器允许指定一个负载极限,HashMap和Hashtable默认的“负载极限”为0.75,这表明当该hash表的3/4已经被填满时,hash表会发生rehashing。

“负载极限”的默认值(0.75)是时间和空间成本上的一种折中:

  • 较高的“负载极限”可以降低hash表所占用的内存空间,但会增加查询数据的时间开销,而查询是最频繁的操作(HashMap的get()与put()方法都要用到查询)
  • 较低的“负载极限”会提高查询数据的性能,但会增加hash表所占用的内存开销

程序猿可以根据实际情况来调整“负载极限”值。

ConcurrentHashMap

  • 底层采用分段的数组+链表实现,线程安全
  • 通过把整个Map分为N个Segment,可以提供相同的线程安全,但是效率提升N倍,默认提升16倍。(读操作不加锁,由于HashEntry的value变量是 volatile的,也能保证读取到最新的值。)
  • Hashtable的synchronized是针对整张Hash表的,即每次锁住整张表让线程独占,ConcurrentHashMap允许多个修改操作并发进行,其关键在于使用了锁分离技术
  • 有些方法需要跨段,比如size()和containsValue(),它们可能需要锁定整个表而而不仅仅是某个段,这需要按顺序锁定所有段,操作完毕后,又按顺序释放所有段的锁
  • 扩容:段内扩容(段内元素超过该段对应Entry数组长度的75%触发扩容,不会对整个Map进行扩容),插入前检测需不需要扩容,有效避免无效扩容

 

Hashtable和HashMap都实现了Map接口,但是Hashtable的实现是基于Dictionary抽象类的。Java5提供了ConcurrentHashMap,它是HashTable的替代,比HashTable的扩展性更好。

HashMap基于哈希思想,实现对数据的读写。当我们将键值对传递给put()方法时,它调用键对象的hashCode()方法来计算hashcode,然后找到bucket位置来存储值对象。当获取对象时,通过键对象的equals()方法找到正确的键值对,然后返回值对象。HashMap使用链表来解决碰撞问题,当发生碰撞时,对象将会储存在链表的下一个节点中。HashMap在每个链表节点中储存键值对对象。当两个不同的键对象的hashcode相同时,它们会储存在同一个bucket位置的链表中,可通过键对象的equals()方法来找到键值对。如果链表大小超过阈值(TREEIFY_THRESHOLD,8),链表就会被改造为树形结构。

在HashMap中,null可以作为键,这样的键只有一个,但可以有一个或多个键所对应的值为null。当get()方法返回null值时,即可以表示HashMap中没有该key,也可以表示该key所对应的value为null。因此,在HashMap中不能由get()方法来判断HashMap中是否存在某个key,应该用containsKey()方法来判断。而在Hashtable中,无论是key还是value都不能为null。

Hashtable是线程安全的,它的方法是同步的,可以直接用在多线程环境中。而HashMap则不是线程安全的,在多线程环境中,需要手动实现同步机制。

Hashtable与HashMap另一个区别是HashMap的迭代器(Iterator)是fail-fast迭代器,而Hashtable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构(增加或者移除元素),将会抛出ConcurrentModificationException,但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并不是一个一定发生的行为,要看JVM。

先看一下简单的类图:

  

从类图中可以看出来在存储结构中ConcurrentHashMap比HashMap多出了一个类Segment,而Segment是一个可重入锁。

ConcurrentHashMap是使用了锁分段技术来保证线程安全的。

锁分段技术:首先将数据分成一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据的时候,其他段的数据也能被其他线程访问。 

ConcurrentHashMap提供了与Hashtable和SynchronizedMap不同的锁机制。Hashtable中采用的锁机制是一次锁住整个hash表,从而在同一时刻只能由一个线程对其进行操作;而ConcurrentHashMap中则是一次锁住一个桶。

ConcurrentHashMap默认将hash表分为16个桶,诸如get、put、remove等常用操作只锁住当前需要用到的桶。这样,原来只能一个线程进入,现在却能同时有16个写线程执行,并发性能的提升是显而易见的。