|
|
|
数组和链表数据结构描述，各自的时间复杂度。
数组是将元素在内存中连续存放，由于每个元素占用内存相同，可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一个元素，需要移动大量元素，在内存中空出一个元素的空间，然后将要增加的元素放在其中。同样的道理，如果想删除一个元素，同样需要移动大量元素去填掉被移动的元素。如果应用需要快速访问数据，很少插入和删除元素，就应该用数组。
链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针联系到一起，每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针。
如果要访问链表中一个元素，需要从第一个元素开始，一直找到需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了，只要修改元素中的指针就可以了。如果应用需要经常插入和删除元素你就需要用链表。
内存存储区别
[list,
[*,l 数组从栈中分配空间, 对于程序员方便快速,但自由度小。
[*,l 链表从堆中分配空间, 自由度大但申请管理比较麻烦.
[/list,逻辑结构区别
[list,
[*,l 数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费。
[*,l 链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。（数组中插入、删除数据项时，需要移动其它数据项）
[/list,总结
[list=1,
[*,存取方式上，数组可以顺序存取或者随机存取，而链表只能顺序存取；
[*,存储位置上，数组逻辑上相邻的元素在物理存储位置上也相邻，而链表不一定；
[*,存储空间上，链表由于带有指针域，存储密度不如数组大；
[*,按序号查找时，数组可以随机访问，时间复杂度为O(1)，而链表不支持随机访问，平均需要O(n)；
[*, 按值查找时，若数组无序，数组和链表时间复杂度均为O(1)，但是当数组有序时，可以采用折半查找将时间复杂度降为O(logn)；
[*,6插入和删除时，数组平均需要移动n/2个元素，而链表只需修改指针即可；
[*,空间分配方面：
[*, 数组在静态存储分配情形下，存储元素数量受限制，动态存储分配情形下，虽然存储空间可以扩充，但需要移动大量元素，导致操作效率降低，而且如果内存中没有更大块连续存储空间将导致分配失败；
[*, 链表存储的节点空间只在需要的时候申请分配，只要内存中有空间就可以分配，操作比较灵活高效；
[/list,error和exception的区别，CheckedException，RuntimeException的区别。
Error（错误）是系统中的错误，程序员是不能改变的和处理的，是在程序编译时出现的错误，只能通过修改程序才能修正。一般是指与虚拟机相关的问题，如系统崩溃，虚拟机错误，内存空间不足，方法调用栈溢等。对于这类错误的导致的应用程序中断，仅靠程序本身无法恢复和和预防，遇到这样的错误，建议让程序终止。
Exception（异常）表示程序可以处理的异常，可以捕获且可能恢复。遇到这类异常，应该尽可能处理异常，使程序恢复运行，而不应该随意终止异常。
Exception又分为两类
CheckedException：（编译时异常） 需要用try——catch显示的捕获，对于可恢复的异常使用CheckedException。
UnCheckedException（RuntimeException）：（运行时异常）不需要捕获，对于程序错误（不可恢复）的异常使用RuntimeException。
常见的RuntimeException异常
[list=1,
[*, illegalArgumentException：此异常表明向方法传递了一个不合法或不正确的参数。
[*,NullpointerException：空指针异常（我目前遇见的最多的）
[*,IndexOutOfBoundsException：索引超出边界异常
[*,illegalStateException：在不合理或不正确时间内唤醒一方法时出现的异常信息。即 Java 环境或 Java 应用不满足请求操作。
[/list,常见的CheckedException异常
[list=1,
[*,我们在编写程序过程中try——catch捕获到的一场都是CheckedException。
[*,io包中的IOExecption及其子类，都是CheckedException。
[/list,举个简单的例子（看别人的，觉得很形象，很好理解）
Error和Exception就像是水池和水池里的水的区别
“水池”，就是代码正常运行的外部环境，如果水池崩溃（系统崩溃），或者池水溢出（内存溢出）等，这些都是跟水池外部环境有关。这些就是java中的error
“水池里的水”，就是正常运行的代码，水污染了、有杂质了，浑浊了，这些影响水质的因素就是Exception。
请列出5个运行时异常。
java运行时异常是可能在java虚拟机正常工作时抛出的异常。java提供了两种异常机制。一种是运行时异常(RuntimeExepction)，一种是检查式异常(checked execption)。
[list,
[*,l 检查式异常：我们经常遇到的IO异常及sql异常就属于检查式异常。对于这种异常，java编译器要求我们必须对出现的这些异常进行catch 所以 面对这种异常不管我们是否愿意，只能自己去写一堆catch来捕捉这些异常。
[*,l 运行时异常：我们可以不处理。当出现这样的异常时，总是由虚拟机接管。比如：我们从来没有人去处理过NullPointerException异常，它就是运行时异常，并且这种异常还是最常见的异常之一。
[/list,RuntimeExecption在java.lang包下。
常见的几种如下：
[list=1,
[*,ClassCastException(类转换异常)
[*,IndexOutOfBoundsException(下标越界异常)
[*,NullPointerException(空指针异常)
[*,ArrayStoreException(数据存储异常，操作数组时类型不一致)
[*, BufferOverflowException(还有IO操作的,缓冲溢出异常)
[*, IllegalArgumentException - 传递非法参数异常。
[*, ArithmeticException - 算术运算异常
[*,ArrayStoreException - 向数组中存放与声明类型不兼容对象异常
[*,NegativeArraySizeException - 创建一个大小为负数的数组错误异常
[*, NumberFormatException - 数字格式异常
[*,SecurityException - 安全异常
[*, UnsupportedOperationException - 不支持的操作异常
[/list,在自己的代码中，如果创建一个java.lang.String类，这个类是否可以被类加载器加载？为什么？
java是一种类型安全的语言,它的四类成为安全沙箱机制的安全机制来保证语言的安全性,这四类安全沙箱分别是:
[list=1,
[*,类加载体系
[*,class文件检验器
[*, 内置于Java虚拟机(及语言)的安全特性
[*, 安全管理器及Java API
[/list,Java程序中的.java文件编译完成会生成.class文件,而.class文件就是用过被称为类加载器的ClassLoader加载的,而ClassLoder在加载过程中会使用"双亲委派机制"来加载.class文件.
类加载器就是Java运行时环境（Java Runtime Environment）的一部分，负责动态加载Java类到Java虚拟机的内存空间中。恩看了这个介绍就知道了~~~原来平常的.class文件是通过这个加载器，加载到内存中的。
1.Bootstrap ClassLoader
负责加载$JAVA_HOME中jre/lib/rt.jar里所有的class，由C++实现，不是ClassLoader子类
2、Extension ClassLoader
负责加载java平台中扩展功能的一些jar包，包括$JAVA_HOME中jre/lib/*.jar或-Djava.ext.dirs指定目录下的jar包
3、App ClassLoader（SystemClassLoader）
负责记载classpath中指定的jar包及目录中class
4、Custom ClassLoader
属于应用程序根据自身需要自定义的ClassLoader，如tomcat、jboss都会根据j2ee规范自行实现ClassLoader
OK那么好了，我们现在知道了什么是类加载器以及它的种类及作用了，那么现在问题来了，为什么我们自己写的Sring类能否被加载到呢？我们自己写一个来看看
首先，写了一个跟JAVA自带的String类一个一样的String，包名也一样就是在构造方法里面多了一行输出。
[indent,[i, public String {[/i,[i, this.value = new char[0];[/i,[i, System.out.println[/i,[i, }[/i,[/indent,也就是说只要调用了我们自己写的String类得话应该是有输出的，接下来我们来试试：
[indent,[i,import java.lang.String;[/i,[i,public class Test { [/i,[i,public static void main(String args) {[/i,[i, String test =new String;[/i,[i, test = "[/i,[i,测试[/i,[i,"; [/i,[i, System.out.println(test);[/i,[i,} [/i,[i,}[/i,[/indent,运行结果如下：
1
可以看到调用的是系统的String类，没有输出。
这是为什么呢？这就是类加载器的委托机制。
3.类加载器的委托机制
从JDK1.2开始，类的加载过程采用父亲委托机制。这种机制能更好的保证java平台的安全。在此委托机制中，除了Java虚拟机自带的根类加载器以外，其余的类加载器都有且只有一个父加载器。当Java程序请求加载器loader1加载Sample类时，loader1首先委托自己的父加载器去加载Sample类，若父加载器能加载，则由父加载器完成加载任务，否则才由加载器loader1本身加载Sample类。
好吧~~~这下看明白了类加载器有个加载顺序我们来看一下这个加载顺序
加载过程中会先检查类是否被已加载，检查顺序是自底向上，从Custom ClassLoader到BootStrap ClassLoader逐层检查，只要某个classloader已加载就视为已加载此类，保证此类只所有ClassLoader加载一次。而加载的顺序是自顶向下，也就是说当发现这个类没有的时候会先去让自己的父类去加载，父类没有再让儿子去加载，那么在这个例子中我们自己写的String应该是被Bootstrap ClassLoader加载了，所以App ClassLoader就不会再去加载我们写的String类了，导致我们写的String类是没有被加载的。
说说你对java.lang.Object对象中hashCode和equals方法的理解。在什么场景下需要重新实现这两个方法。
在程序设计中，有很多的“公约”，遵守约定去实现你的代码，会让你避开很多坑，这些公约是前人总结出来的设计规范。Object类是Java中的万类之祖，其中，equals和hashCode是2个非常重要的方法。
public boolean equals(Object obj)
Object类中默认的实现方式是 : return this == obj 。那就是说，只有this 和 obj引用同一个对象，才会返回true。
而我们往往需要用equals来判断 2个对象是否等价，而非验证他们的唯一性。这样我们在实现自己的类时，就要重写equals.
按照约定，equals要满足以下规则。
[list,
[*,l 自反性: x.equals(x) 一定是true
[*,l 对null: x.equals(null) 一定是false
[*,l 对称性: x.equals(y) 和 y.equals(x)结果一致
[*,l 传递性: a 和 b equals , b 和 c equals，那么 a 和 c也一定equals。
[*,l 一致性: 在某个运行时期间，2个对象的状态的改变不会不影响equals的决策结果，那么，在这个运行时期间，无论调用多少次equals，都返回相同的结果。
[/list,一个例子
[indent,[i,class Test[/i,[i,{[/i,[i, private int num;[/i,[i, private String data;[/i,[i, public boolean equals(Object obj)[/i,[i, {[/i,[i, if (this == obj)[/i,[i, return true;[/i,[i, if ((obj == null) || (obj.getClass != this.getClass))[/i,[i, return false;[/i,[i, //[/i,[i,能执行到这里，说明[/i,[i,obj[/i,[i,和[/i,[i,this[/i,[i,同类且非[/i,[i,null[/i,[i,。[/i,[i, Test test = (Test) obj;[/i,[i, return num == test.num&& (data == test.data || (data != null && data.equals(test.data)));[/i,[i, }[/i,[i, public int hashCode[/i,[i, {[/i,[i, //[/i,[i,重写[/i,[i,equals[/i,[i,，也必须重写[/i,[i,hashCode[/i,[i,。具体后面介绍。[/i,[i, } [/i,[i,}[/i,[/indent,equals编写指导
[list=1,
[*,Test类对象有2个字段，num和data，这2个字段代表了对象的状态，他们也用在equals方法中作为评判的依据。
[*,在第8行，传入的比较对象的引用和this做比较，这样做是为了 save time ，节约执行时间，如果this 和 obj是 对同一个堆对象的引用，那么，他们一定是qeuals 的。
[*,接着，判断obj是不是为null，如果为null，一定不equals，因为既然当前对象this能调用equals方法，那么它一定不是null，非null 和 null当然不等价。
[*,然后，比较2个对象的运行时类，是否为同一个类。不是同一个类，则不equals。getClass返回的是 this 和obj的运行时类的引用。如果他们属于同一个类，则返回的是同一个运行时类的引用。注意，一个类也是一个对象。
[/list,1、有些程序员使用下面的第二种写法替代第一种比较运行时类的写法。应该避免这样做。
[indent,[i,if((obj == null) || (obj.getClass != this.getClass)) [/i,[i, return false; [/i,[i,if(!(obj instanceof Test)) [/i,[i, return false; // avoid [/i,[i,避免！[/i,它违反了公约中的对称原则。例如：假设Dog扩展了Aminal类。[i,dog instanceof Animal [/i,[i,得到[/i,[i,true[/i,[i,animal instanceof Dog [/i,[i,得到[/i,[i,false[/i,这就会导致[i,animal.equls(dog) [/i,[i,返回[/i,[i,true[/i,[i,dog.equals(animal) [/i,[i,返回[/i,[i,false[/i,[/indent,仅当Test类没有子类的时候，这样做才能保证是正确的。
2、按照第一种方法实现，那么equals只能比较同一个类的对象，不同类对象永远是false。但这并不是强制要求的。一般我们也很少需要在不同的类之间使用equals。
3、在具体比较对象的字段的时候，对于基本值类型的字段，直接用 == 来比较（注意浮点数的比较，这是一个坑）对于引用类型的字段，你可以调用他们的equals，当然，你也需要处理字段为null 的情况。对于浮点数的比较，我在看Arrays.binarySearch的源代码时，发现了如下对于浮点数的比较的技巧：
[indent,[i,if ( Double.doubleToLongBits(d1) == Double.doubleToLongBits(d2) ) //d1 [/i,[i,和[/i,[i, d2 [/i,[i,是[/i,[i,double[/i,[i,类型[/i,[i,if( Float.floatToIntBits(f1) == Float.floatToIntBits(f2) ) //f1 [/i,[i,和[/i,[i, f2 [/i,[i,是[/i,[i,d2[/i,[i,是[/i,[i,float[/i,[i,类型[/i,[/indent,4、并不总是要将对象的所有字段来作为equals 的评判依据，那取决于你的业务要求。比如你要做一个家电功率统计系统，如果2个家电的功率一样，那就有足够的依据认为这2个家电对象等价了，至少在你这个业务逻辑背景下是等价的，并不关心他们的价钱啊，品牌啊，大小等其他参数。
5、最后需要注意的是，equals 方法的参数类型是Object，不要写错！
[indent,public int hashCode[/indent,这个方法返回对象的散列码，返回值是int类型的散列码。
对象的散列码是为了更好的支持基于哈希机制的Java集合类，例如 Hashtable] HashMap] HashSet 等。
关于hashCode方法，一致的约定是：
重写了euqls方法的对象必须同时重写hashCode方法。
[list,
[*,如果2个对象通过equals调用后返回是true，那么这个2个对象的hashCode方法也必须返回同样的int型散列码
[*,如果2个对象通过equals返回false，他们的hashCode返回的值允许相同。(然而，程序员必须意识到，hashCode返回独一无二的散列码，会让存储这个对象的hashtables更好地工作。)
[/list,在上面的例子中，Test类对象有2个字段，num和data，这2个字段代表了对象的状态，他们也用在equals方法中作为评判的依据。那么， 在hashCode方法中，这2个字段也要参与hash值的运算，作为hash运算的中间参数。这点很关键，这是为了遵守：2个对象equals，那么 hashCode一定相同规则。
也是说，参与equals函数的字段，也必须都参与hashCode 的计算。
合乎情理的是：同一个类中的不同对象返回不同的散列码。典型的方式就是根据对象的地址来转换为此对象的散列码，但是这种方式对于Java来说并不是唯一的要求的的实现方式。通常也不是最好的实现方式。
相比于 equals公认实现约定，hashCode的公约要求是很容易理解的。有2个重点是hashCode方法必须遵守的。约定的第3点，其实就是第2点的细化，下面我们就来看看对hashCode方法的一致约定要求。
[list,
[*,第一：在某个运行时期间，只要对象的（字段的）变化不会影响equals方法的决策结果，那么，在这个期间，无论调用多少次hashCode，都必须返回同一个散列码。
[*,第二：通过equals调用返回true 的2个对象的hashCode一定一样。
[*,第三：通过equasl返回false 的2个对象的散列码不需要不同，也就是他们的hashCode方法的返回值允许出现相同的情况。
[/list, 总结一句话：等价的(调用equals返回true)对象必须产生相同的散列码。不等价的对象，不要求产生的散列码不相同。
hashCode编写指导
在编写hashCode时，你需要考虑的是，最终的hash是个int值，而不能溢出。不同的对象的hash码应该尽量不同，避免hash冲突。
那么如果做到呢？下面是解决方案。
1、定义一个int类型的变量 hash,初始化为 7。
接下来让你认为重要的字段（equals中衡量相等的字段）参入散列运，算每一个重要字段都会产生一个hash分量，为最终的hash值做出贡献（影响）
最后把所有的分量都总和起来，注意并不是简单的相加。选择一个倍乘的数字31，参与计算。然后不断地递归计算，直到所有的字段都参与了。
[indent,[i,int hash = 7;[/i,[i,hash = 31 * hash + [/i,[i,字段[/i,[i,1[/i,[i,贡献分量[/i,[i,;[/i,[i,hash = 31 * hash + [/i,[i,字段[/i,[i,2[/i,[i,贡献分量[/i,[i,;[/i,[i,.....[/i,[i,return hash[/i,[i,；[/i,[/indent,在jdk1.5中，引入了泛型，泛型的存在是用来解决什么问题。
1. 泛型提供了编译时类型安全检测机制
该机制允许程序员在编译时检测到非法的类型。泛型的本质是参数化类型，也就是说所操作的数据类型被指定为一个参数。比如我们要写一个排序方法，能够对整型数组、字符串数组甚至其他任何类型的数组进行排序，我们就可以使用 Java 泛型。拥有Java1.4或更早版本的开发背景的人都知道，在集合中存储对象并在使用前进行类型转换是多么的不方便。泛型防止了那种情况的发生。它提供了编译期的类型安全，确保你只能把正确类型的对象放入集合中，避免了在运行时出现ClassCastException。
Java 中的泛型基本上都是在编译器这个层次来实现的。在生成的 Java 字节代码中是不包含泛型中的类型信息的。使用泛型的时候加上的类型参数，会被编译器在编译的时候去掉，所以在运行时不存在任何类型相关的信息。这个过程就称为类型擦除。如在代码中定义的 List<Object>和 List<String>等类型，在编译之后都会变成 List。JVM 看到的只是 List，而由泛型附加的类型信息对 JVM 来说是不可见的。这样做的目的，是确保能和Java 5之前的版本开发二进制类库进行兼容。你无法在运行时访问到类型参数，因为编译器已经把泛型类型转换成了原始类型。类型擦除的基本过程也比较简单，首先是找到用来替换类型参数的具体类。这个具体类一般是 Object。如果指定了类型参数的上界的话，则使用这个上界。把代码中的类型参数都替换成具体的类。泛型的本质是参数化类型，也就是说所操作的数据类型被指定为一个参数，泛型的好处是在编译的时候检查类型安全，并且所有的强制转换都是自动和隐式的，以提高代码的重用率.
2. Java的泛型是如何工作的 ? 什么是类型擦除 ?
这是一道更好的泛型面试题。泛型是通过类型擦除来实现的，编译器在编译时擦除了所有类型相关的信息，所以在运行时不存在任何类型相关的信息。例如List<String>在运行时仅用一个List来表示。这样做的目的，是确保能和Java 5之前的版本开发二进制类库进行兼容。你无法在运行时访问到类型参数，因为编译器已经把泛型类型转换成了原始类型。根据你对这个泛型问题的回答情况，你会得到一些后续提问，比如为什么泛型是由类型擦除来实现的或者给你展示一些会导致编译器出错的错误泛型代码。请阅读我的Java中泛型是如何工作的来了解更多信息。
3. 什么是泛型中的限定通配符和非限定通配符 ?
这是另一个非常流行的Java泛型面试题。限定通配符对类型进行了限制。有两种限定通配符，一种是<? extends T>它通过确保类型必须是T的子类来设定类型的上界，另一种是<? super T>它通过确保类型必须是T的父类来设定类型的下界。泛型类型必须用限定内的类型来进行初始化，否则会导致编译错误。另一方面<?>表示了非限定通配符，因为<?>可以用任意类型来替代。更多信息请参阅我的文章泛型中限定通配符和非限定通配符之间的区别。
4. List<? extends T>和List <? super T>之间有什么区别 ?
这和上一个面试题有联系，有时面试官会用这个问题来评估你对泛型的理解，而不是直接问你什么是限定通配符和非限定通配符。这两个List的声明都是限定通配符的例子，List<? extends T>可以接受任何继承自T的类型的List，而List<? super T>可以接受任何T的父类构成的List。例如List<? extends Number>可以接受List<Integer>或List<Float>。在本段出现的连接中可以找到更多信息。
5. 如何编写一个泛型方法，让它能接受泛型参数并返回泛型类型?
编写泛型方法并不困难，你需要用泛型类型来替代原始类型，比如使用T, E or K,V等被广泛认可的类型占位符。泛型方法的例子请参阅Java集合类框架。最简单的情况下，一个泛型方法可能会像这样:
[indent,[i,public V put(K key, V value) {[/i,[i,return cache.put(key, value);[/i,[i,}[/i,[/indent,6. Java中如何使用泛型编写带有参数的类?
这是上一道面试题的延伸。面试官可能会要求你用泛型编写一个类型安全的类，而不是编写一个泛型方法。关键仍然是使用泛型类型来代替原始类型，而且要使用JDK中采用的标准占位符。
7. 编写一段泛型程序来实现LRU缓存?
对于喜欢Java编程的人来说这相当于是一次练习。给你个提示，LinkedHashMap可以用来实现固定大小的LRU缓存，当LRU缓存已经满了的时候，它会把最老的键值对移出缓存。LinkedHashMap提供了一个称为removeEldestEntry的方法，该方法会被put和putAll调用来删除最老的键值对。当然，如果你已经编写了一个可运行的JUnit测试，你也可以随意编写你自己的实现代码。
8. 你可以把List<String>传递给一个接受List<Object>参数的方法吗？
对任何一个不太熟悉泛型的人来说，这个Java泛型题目看起来令人疑惑，因为乍看起来String是一种Object，所以List<String>应当可以用在需要List<Object>的地方，但是事实并非如此。真这样做的话会导致编译错误。如果你再深一步考虑，你会发现Java这样做是有意义的，因为List<Object>可以存储任何类型的对象包括String, Integer等等，而List<String>却只能用来存储Strings。
[indent,[i,List<Object> objectList;[/i,[i, List<String> stringList;[/i,[i, objectList = stringList; //compilation error incompatible types[/i,[/indent,9. Array中可以用泛型吗?
这可能是Java泛型面试题中最简单的一个了，当然前提是你要知道Array事实上并不支持泛型，这也是为什么Joshua Bloch在Effective Java一书中建议使用List来代替Array，因为List可以提供编译期的类型安全保证，而Array却不能。
10. 如何阻止Java中的类型未检查的警告?
如果你把泛型和原始类型混合起来使用，例如下列代码，Java 5的javac编译器会产生类型未检查的警告，例如
[indent,[i,List<String> rawList = new ArrayList[/i,[/indent,这样的a.hashcode 有什么用，与a.equals(b)有什么关系。
hashcode方法提供了对象的hashCode值，是一个native方法，返回的默认值与System.identityHashCode(obj)一致。
通常这个值是对象头部的一部分二进制位组成的数字，具有一定的标识对象的意义存在，但绝不定于地址
作用是：用一个数字来标识对象。比如在HashMap、HashSet等类似的集合类中，如果用某个对象本身作为Key，即要基于这个对象实现Hash的写入和查找，那么对象本身如何实现这个呢？就是基于hashcode这样一个数字来完成的，只有数字才能完成计算和对比操作。
hashcode是否唯一
hashcode只能说是标识对象，在hash算法中可以将对象相对离散开，这样就可以在查找数据的时候根据这个key快速缩小数据的范围，但hashcode不一定是唯一的，所以hash算法中定位到具体的链表后，需要循环链表，然后通过equals方法来对比Key是否是一样的。
equals与hashcode的关系
equals相等两个对象，则hashcode一定要相等。但是hashcode相等的两个对象不一定equals相等。
有没有可能2个不相等的对象有相同的hashcode。
有
Java中的HashSet内部是如何工作的。
[list,
[*, HashSet 的内部采用 HashMap来实现。由于 Map 需要 key 和 value，所以HashSet中所有 key 的都有一个默认 value。类似于HashMap，HashSet 不允许重复的 key，只允许有一个null key，意思就是 HashSet 中只允许存储一个 null 对象。
[*,HashSet实现了Set接口。HashSet依赖的数据结构是哈希表因为实现的是Set接口，所以不允许有重复的值插入到HashSet中的对象不保证与插入的顺序保持一致。对象的插入是根据它的hashcode。HashSet中允许有NULL值。HashSet也实现了Searlizable和Cloneable两个接口
[/list,HashSet的构造函数：
[indent,[i, HashSet h = new HashSet; [/i,[i,默认初始化大小是[/i,[i,16[/i,[i,，默认装载因子是[/i,[i,0.75.[/i,[i, HashSet h = new HashSet(int initialCapacity); [/i,[i,默认装载因子是[/i,[i,0.75[/i,[i, HashSet h = new HashSet(int initialCapacity, float loadFactor);[/i,[i, HashSet h = new HashSet(Collection C);[/i,[/indent,什么是初始化大小与装载因子：
初始化尺寸就是当创建哈希表（HashSet内部用哈希表的数据结构）的时候桶（buckets）的数量。如果当前的尺寸已经满了，那么桶的数量会自动增长。
装载因子衡量的是在HashSet自动增长之前允许有多满。当哈希表中实体的数量已经超出装载因子与当前容量的积，那么哈希表就会再次进行哈希（也就是内部数据结构重建），这样哈希表大致有两倍桶的数量。
表中已经存储的元素的数量
装载因子 =
哈希表的大小
例如：如果内部容量为16，装载因子为0.75，那么当表中有12个元素的时候，桶的数量就会自动增长。
性能影响：
装载因子和初始化容量是影响HashSet操作的两个主要因素。装载因子为0.75的时候可以提供关于时间和空间复杂度方面更有效的性能。如果我们加大这个装载因子，那么内存的上限就会减小（因为它减少了内部重建的操作），但是将影响哈希表中的add与查询的操作。为了减少再哈希操作，我们应该选择一个合适的初始化大小。如果初始化容量大于实体的最大数量除以装载因子，那么就不会有再哈希的动作发生了。
[list,
[*,Ø HashSet中的一些重要方法：
[*,Ø boolean add(E e)：如果不存在则添加，存在则返回false。
[*,Ø void clear ：移除Set中所有的元素
[*,Ø boolean contains(Object o)：如果这个元素在set中存在，那么返回true。
[*,Ø boolean remove(Object o)：如果这个元素在set中存在，那么从set中删除。
[*,Ø Iterator iterator：返回set中这个元素的迭代器。
[/list,简单的程序：
[indent,[i,// Java program to demonstrate working of HashSet[/i,[i,import java.util.*;[/i,[i,class Test[/i,[i,{[/i,[i, public static void main(Stringargs)[/i,[i, {[/i,[i, HashSet<String> h = new HashSet<String>;[/i,[i, // adding into HashSet[/i,[i, h.add("India");[/i,[i, h.add("Australia");[/i,[i, h.add("South Africa");[/i,[i, h.add("India");// adding duplicate elements[/i,[i, // printing HashSet[/i,[i, System.out.println(h);[/i,[i, System.out.println("List contains India or not:" +[/i,[i, h.contains("India"));[/i,[i, // Removing an item[/i,[i, h.remove("Australia");[/i,[i, System.out.println("List after removing Australia:"+h);[/i,[i, // Iterating over hash set items[/i,[i, System.out.println("Iterating over list:");[/i,[i, Iterator<String> i = h.iterator;[/i,[i, while (i.hasNext)[/i,[i, System.out.println(i.next);[/i,[i, }[/i,[i,}[/i,[/indent,上述代码的输出：
[indent,[i,[Australia, South Africa, India,[/i,[i,List contains India or not:true[/i,[i,List after removing Australia:[South Africa, India,[/i,[i,Iterating over list:[/i,[i,South Africa[/i,[i,India[/i,[/indent,HashSet内部是如何工作的？
所有Set接口的类内部都是由Map做支撑的。HashSet用HashMap对它的内部对象进行排序。你一定好奇输入一个值到HashMap，我们需要的是一个键值对，但是我们传给HashSet的是一个值。
那么HashMap是如何排序的？
实际上我们插入到HashSet中的值在map对象中起的是键的作用，因为它的值Java用了一个常量。所以在键值对中所有的键的值都是一样的。
如果我们在Java Doc中看一下HashSet的实现，大致是这样的：
[indent,[i,private transient HashMap map;[/i,[i,// Constructor - 1[/i,[i,// All the constructors are internally creating HashMap Object.[/i,[i,public HashSet[/i,[i,{[/i,[i, // Creating internally backing HashMap object[/i,[i, map = new HashMap<>;[/i,[i,}[/i,[i,// Constructor - 2[/i,[i,public HashSet(int initialCapacity)[/i,[i,{[/i,[i, // Creating internally backing HashMap object[/i,[i, map = new HashMap<>(initialCapacity);[/i,[i,}[/i,[i,// Dummy value to associate with an Object in Map[/i,[i,private static final Object PRESENT = new Object;[/i,[/indent,如果我们看下HashSet中的add方法：
[indent,[i,public boolean add(E e)[/i,[i,{[/i,[i, return map.put(e, PRESENT) == null;[/i,[i,}[/i,[/indent,我们可以注意到，HashSet类的add方法内部调用的是HashMap的put方法，通过你指定的值作为key，常量“PRESENT”作为值传过去。
remove也是用类似的方法工作。它内部调用的是Map接口的remove。
[indent,[i,public boolean remove(Object o)[/i,[i,{[/i,[i, return map.remove(o) == PRESENT;[/i,[i,}[/i,[/indent,HashSet操作的时间复杂度：
HashSet底层的数据结构是哈希表，所以HashSet的add，remove与查询（包括contain方法）的分摊（平均或者一般情况）时间复杂度是O(1)。
31.什么是序列化，怎么序列化，为什么序列化，反序列化会遇到什么问题，如何解决。
[list,
[*,l 把对象转换为字节序列的过程称为对象的序列化。
[*,l 把字节序列恢复为对象的过程称为对象的反序列化。
[/list,对象的序列化主要有两种用途：
[list,
[*,1、 把对象的字节序列永久地保存到硬盘上，通常存放在一个文件中；
[*,2、 在网络上传送对象的字节序列。
[/list,在很多应用中，需要对某些对象进行序列化，让它们离开内存空间，入住物理硬盘，以便长期保存。比如最常见的是Web服务器中的Session对象，当有 10万用户并发访问，就有可能出现10万个Session对象，内存可能吃不消，于是Web容器就会把一些seesion先序列化到硬盘中，等要用了，再把保存在硬盘中的对象还原到内存中。
当两个进程在进行远程通信时，彼此可以发送各种类型的数据。无论是何种类型的数据，都会以二进制序列的形式在网络上传送。发送方需要把这个Java对象转换为字节序列，才能在网络上传送；接收方则需要把字节序列再恢复为Java对象。
写出三种单例模式实现 。
单例模式：单例模式的意思就是只有一个实例。单例模式确保某一个类只有一个实例，而且自行实例化并向整个系统提供这个实例。这个类称为单例类。
单例模式有三种：懒汉式单例，饿汉式单例，登记式单例，双重校验锁。
单例模式的好处
[list=1,
[*, 对于频繁使用的对象，可以省略new操作花费的时间，这对于那些重量级对象而言，是非常可观的一笔系统开销；
[*,由于new操作的次数减少，因而对系统内存的使用频率也会降低，这将减轻GC压力，缩短GC停顿时间。
[/list,1.懒汉式单例
[indent,[i,public class Singleton {[/i,[i, private static Singleton singleton;[/i,[i, private Singleton {} //[/i,[i,此类不能被实例化[/i,[i, public static synchronized Singleton getInstance {[/i,[i, if (singleton == null) {[/i,[i, singleton = new Singleton;[/i,[i, }[/i,[i, return singleton;[/i,[i, }[/i,[i,}[/i,优点：第一次调用才初始化，避免内存浪费。[/indent,缺点：必须加锁synchronized 才能保证单例，（如果两个线程同时调用getInstance方法，会chuxia）但加锁会影响效率。
2.饿汉式单例
[indent,[i,public class Singleton {[/i,[i, private static final Singleton SINGLETON = new Singleton;[/i,[i, private Singleton {} //[/i,[i,此类不能被实例化[/i,[i, public static Singleton getInstance {[/i,[i, return SINGLETON;[/i,[i, }[/i,[i,}[/i,[/indent,优点：没有加锁，执行效率会提高。
缺点：类加载时就初始化，浪费内存。
3.登记式模式（holder）
[indent,[i,public class Singleton {[/i,[i, private Singleton {} //[/i,[i,构造方法是私有的，从而避免外界利用构造方法直接创建任意多实例。[/i,[i, public static Singleton getInstance {[/i,[i, return Holder.SINGLETON;[/i,[i, }[/i,[i, private static class Holder {[/i,[i, private static final Singleton SINGLETON = new Singleton;[/i,[i, }[/i,[i,}[/i,[/indent, 内部类只有在外部类被调用才加载，产生SINGLETON实例；又不用加锁。此模式有上述两个模式的优点，屏蔽了它们的缺点，是最好的单例模式。
4.双重校验锁-懒汉式(jdk1.5)
[indent,[i,public class Singleton {[/i,[i, private volatile static Singleton singleton;[/i,[i, private Singleton {}[/i,[i, public static Singleton getSingleton {[/i,[i, if (singleton == null) {[/i,[i, synchronized (Singleton.class) {[/i,[i, if (singleton == null) {[/i,[i, singleton = new Singleton;[/i,[i, }[/i,[i, }[/i,[i, }[/i,[i, return singleton;[/i,[i, }[/i,[i,}[/i,[/indent, 这样方式实现线程安全地创建实例，而又不会对性能造成太大影响。它只是第一次创建实例的时候同步，以后就不需要同步了。
由于volatile关键字屏蔽了虚拟机中一些必要的代码优化，所以运行效率并不是很高，因此建议没有特别的需要不要使用。双重检验锁方式的单例不建议大量使用，根据情况决定。
总结
有两个问题需要注意：
[list=1,
[*,如果单例由不同的类装载器装入，那便有可能存在多个单例类的实例。假定不是远端存取，例如一些servlet容器对每个servlet使用完全不同的类装载器，这样的话如果有两个servlet访问一个单例类，它们就都会有各自的实例。
[*, 如果Singleton实现了java.io.Serializable接口，那么这个类的实例就可能被序列化和复原。不管怎样，如果你序列化一个单例类的对象，接下来复原多个那个对象，那你就会有多个单例类的实例。
[/list,对第一个问题修复的办法是：
[indent,[i,private static Class getClass(String classname) [/i,[i, throws ClassNotFoundException { [/i,[i, ClassLoader classLoader = Thread.currentThread.getContextClassLoader; [/i,[i, if(classLoader == null) [/i,[i, classLoader = Singleton.class.getClassLoader; [/i,[i, return (classLoader.loadClass(classname)); [/i,[i, } [/i,[i,}[/i,[/indent,对第二个问题修复的办法是：
[indent,[i,public class Singleton implements java.io.Serializable { [/i,[i, public static Singleton INSTANCE = new Singleton; [/i,[i, protected Singleton { [/i,[i, } [/i,[i, private Object readResolve { [/i,[i, return INSTANCE; [/i,[i, } [/i,[i,}[/i,[/indent,如何在父类中为子类自动完成所有的hashcode和equals实现？这么做有何优劣。
同时复写hashcode和equals方法，优势可以添加自定义逻辑，且不必调用超类的实现。
请结合OO设计理念，谈谈访问修饰符public、private、protected、default在应用设计中的作用。
访问修饰符，主要标示修饰块的作用域，方便隔离防护
|
|
发表于 2020-7-10 01:03:21
