Skip to content

Latest commit

 

History

History
1798 lines (1069 loc) · 80.6 KB

容器.md

File metadata and controls

1798 lines (1069 loc) · 80.6 KB
Raw

非常重要，也是必问的内容。基本上就是List、Map、Set，问的是各种实现类的底层实现原理，实现类的优缺点。

集合要掌握的是ArrayList、LinkedList、Hashtable、HashMap、ConcurrentHashMap、HashSet的实现原理，能流利作答，当然能掌握CopyOnWrite容器和Queue是再好不过的了。另外多说一句，ConcurrentHashMap的问题在面试中问得特别多，大概是因为这个类可以衍生出非常多的问题，关于ConcurrentHashMap，我给网友朋友们提供三点回答或者是研究方向：

§ ConcurrentHashMap的锁分段技术

§ ConcurrentHashMap的读是否要加锁，为什么

§ ConcurrentHashMap的迭代器是强一致性的迭代器还是弱一致性的迭代器

  • Collection
    • List
      • Abstraclist and AbstractSequentialist
      • ArrayList(数组)
      • Vector(数组实现，线程同步)
      • LinkList(链表)
      • Stack
    • Set
      • HashSet(Hash表)
      • TreeSet(二叉树)
      • LinkHashSet(HashSet + LinkedHashMap)
    • Queue
  • Map
    • AbstracMap SortedMap NavigableMap
    • HashMap(数组+链表+红黑树)
    • ConcurrentHashMap
    • HashTable(线程安全)
    • TreeMap(可排序)
    • LinkHashMap
    • WeakHashMap
    • Properties

基础类型(Primitives)

基础类型(Primitives)与封装类型(Wrappers)的区别在哪里？

1 传递方式不同

封装类是引用类型。基本类型（原始数据类型）在传递参数时都是按值传递，而封装类型是按引用传递的(其实“引用也是按值传递的”，传递的是对象的地址)。由于包装类型都是final修饰的不可变量，因此没有提供改变它值的方法，增加了对“按引用传递”的理解难度。 int是基本类型，直接存放数值；Integer是类，产生对象时用一个引用指向这个对象。

2 封装类可以有方法和属性

封装类可以有方法和属性，利用这些方法和属性来处理数据，如Integer.parseInt(Strings)。基本数据类型都是final修饰的，不能继承扩展新的类、新的方法。

3 默认值不同

基本类型跟封装类型的默认值是不一样的。如int i,i的预设为0；Integer j，j的预设为null,因为封装类产生的是对象，对象默认值为null。

4 存储位置

基本类型在内存中是存储在栈中，引用类型的引用（值的地址）存储在栈中，而实际的对象（值）是存在堆中。 基本数据类型的好处就是速度快（不涉及到对象的构造和回收），封装类的目的主要是更好的处理数据之间的转换。JDK5.0开始可以自动封包了，基本数据类型可以自动封装成封装类。

简述九种基本数据类型的大小，以及他们的封装类。
w 延伸关于Integer和int的比较 ：

由于Integer变量实际上是对一个Integer对象的引用，所以两个通过new生成的Integer变量永远是不相等的（因为new生成的是两个对象，其内存地址不同）。

Integer i = new Integer(100);
Integer j = new Integer(100);
System.out.print(i == j); //false

Integer变量和int变量比较时，只要两个变量的值是向等的，则结果为true（因为包装类Integer和基本数据类型int比较时，java会自动拆包装为int，然后进行比较，实际上就变为两个int变量的比较）

Integer i = new Integer(100);
int j = 100；
System.out.print(i == j); //true

非new生成的Integer变量和new Integer()生成的变量比较时，结果为false。（因为非new生成的Integer变量指向的是java常量池中的对象，而new Integer()生成的变量指向堆中新建的对象，两者在内存中的地址不同）

Integer i = new Integer(100);
Integer j = 100;
System.out.print(i == j); //false

对于两个非new生成的Integer对象，进行比较时，如果两个变量的值在区间-128到127之间，则比较结果为true，如果两个变量的值不在此区间，则比较结果为false

Integer i = 100;
Integer j = 100;
System.out.print(i == j); //true
Integer i = 128;
Integer j = 128;
System.out.print(i == j); //false

对于第4条的原因： java在编译Integer i = 100 ;时，会翻译成为Integer i = Integer.valueOf(100)；，而java API中对Integer类型的valueOf的定义如下：

public static Integer valueOf(int i){
    assert IntegerCache.high >= 127;
    if (i >= IntegerCache.low && i <= IntegerCache.high){
        return IntegerCache.cache[i + (-IntegerCache.low)];
    }
    return new Integer(i);
}

java对于-128到127之间的数，会进行缓存，Integer i = 127时，会将127进行缓存，下次再写Integer j = 127时，就会直接从缓存中取，就不会new了。

parseInt() parseInt()将把该字符之前的字符串转换成数字。parseInt()方法还有基模式，可以把二进制、八进制、十六进制或其他任何进制的字符串转换成整数。基是由parseInt()方法的第二个参数指定的，所以要解析十六进制的值，当然，对二进制、八进制，甚至十进制（默认模式），都可以这样调用parseInt()方法。 如果十进制数包含前导0，那么最好采用基数10，这样才不会意外地得到八进制的值。

static int parseInt(String s)
static int parseInt(String s, int radix)
如何去小数四舍五入保留小数点后两位？

//使用银行家算法 BigDecimal i = d.multiply(r).setScale(2,RoundingMode.HALF_EVEN);

推荐使用BigDecimal ，并且采用setScale方法来设置精确度，同时使用RoundingMode.HALF_UP表示使用最近数字舍入法则来近似计算。在这里我们可以看出BigDecimal和四舍五入是绝妙的搭配。

char 型变量中能不能存贮一个中文汉字，为什么？

char型变量是用来存储Unicode编码的字符的，unicode编码字符集中包含了汉字，所以char型变量中当然可以存储汉字啦。不过，如果某个特殊的汉字没有被包含在unicode编码字符集中，那么，这个char型变量中就不能存储这个特殊汉字。

补充说明：unicode编码占用两个字节，所以，char类型的变量也是占用两个字节。

类型转换

怎样将 bytes 转换为 long 类型 
  
  public static long bytes2long(byte[] b) {
    long temp = 0;
    long res = 0;
    for (int i=0;i<8;i++) {
        res <<= 8;
        temp = b[i] & 0xff;
        res |= temp;
    }
    return res;
}
.怎么将 string 转成 byte 
string s = "Hello!!";
byte[] b = new byte[1024*1024];
b = System.Text.Encoding.ASCII.GetBytes(s);
//当string含有中文字符时用 System.Text.Encoding.UTF8.GetBytes(s);
sock.Send(b);
.怎么将 byte 转换为 String 
byte[] b1 = new byte[1024*1024*2];
sock.Receive(b1);
string s1 = System.Text.Encoding.ASCII.GetString(b1);

// System.Text.Encoding.UTF8.GetString(b1);

注意： 在把byte数组转换成string的时候，由于byte数组有2M的字节，所以转换后得到的字符串s1也会填充到2M的字符（用\0来填充） 所以，为了避免这个问题，可以使用Receive返回的字节数来确定接收到byte的长度

int length = sock.Receive(b1);
string s1 = System.Text.Encoding.ASCII.GetString(b1, 0, length);
//这样，s1就为byte实际的值
如何将数值型字符转换为数字

string和int之间的转换

string转换成int : Integer.valueOf("12")

int转换成string : String.valueOf(12)

char转int之间的转换

首先将char转换成string

String str=String.valueOf('2')

Integer.valueof(str) 或者Integer.PaseInt(str)

Integer.valueof返回的是Integer对象，Integer.paseInt返回的是int

我们能将 int 强制转换为 byte 类型的变量吗？如果该值大于 byte 类型的范围，将会出现什么现象

1. Byte转int

public static int bytes2int(byte[] bytes) {
        int num = bytes[0] & 0xFF;
        num |= ((bytes[1] << 8) & 0xFF00);
        num |= ((bytes[2] << 16) & 0xFF0000);
        num |= ((bytes[3] << 24) & 0xFF000000);
        return num;
}

2. int转 byte

public static byte[] int2bytes(int i) {
        byte[] b = new byte[4];
        b[0] = (byte) (0xff&i);
        b[1] = (byte) ((0xff00&i) >> 8);
        b[2] = (byte) ((0xff0000&i) >> 16);
        b[3] = (byte) ((0xff000000&i) >> 24);
        return b;
}
能在不进行强制转换的情况下将一个 double 值赋值给 long 类型的变量吗? 
  public static void main(String[] args) {
    double d = 88.88;
    long l = Math.round(d);
    System.out.println(l);

    long ll = 100L;
    double dd = (double) ll;
    System.out.println(dd);
}

数组

如何权衡是使用无序的数组还是有序的数组

在数据偏向查找操作的时候用有序数组快一些，在数据偏向插入的时候，无序数组好一些。删除操作效率一样。

怎么判断数组是 null 还是为空

（无论使用哪种类型的数组，数组标识符其实只是一个引用，指向在堆中创建的一个真实对象 Int[] A =new int[10];new 一下就是实例化了，开辟了内存空间，基本数据类型的元素会被赋初始值，数组建立后长度不能改变，但是还是可以重新赋值）

有如下两个变量定义：

1 int[] zero = new int[0];

2 int[] nil = null;

这两种定义有什么区别呢？

zero是一个长度为0的数组，我们称之为“空数组”，空数组也是一个对象，只是包含元素个数为0。nil是一个数组类型的空引用。

Array 和 ArrayList有什么区别？什么时候应该使用Array而不是ArrayList?

1）精辟阐述：

可以将 ArrayList想象成一种“会自动扩增容量的Array”。

2）Array（[]）：最高效；但是其容量固定且无法动态改变；

ArrayList： 容量可动态增长；但牺牲效率；

3）建议： 基于效率和类型检验，应尽可能使用Array，无法确定数组大小时才使用ArrayList！

不过当你试着解决更一般化的问题时，Array的功能就可能过于受限。

4）Java中一切皆对象，Array也是对象。不论你所使用得Array型别为何，Array名称本身实际上是个reference，指向heap之内得某个实际对象。这个对象可经 由“Array初始化语法”被自动产生，也可以以new表达式手动产生。

5）Array可做为函数返回值，因为它本身是对象的reference；

6）对象数组与基本类型数组在运用上几乎一模一样，唯一差别在于，前者持有得是reference，后者直接持有基本型别之值；

例如：

string [] staff=new string[100];
int [] num=new int[10];

7）容器所持有的其实是一个reference指向Object，进而才能存储任意型别。当然这不包括基本型别，因为基本型别并不继承自任何classes。

8）面对Array，我们可以直接持有基本型别数值的Array（例如：int [] num;),也可以持有reference（指向对象）的Array；但是容器类仅能持有reference（指向对象），若要将基本型别置于容器内，需要使用wrapper类。但是wrapper类使用起来可能不很容易上手，此外，primitives Array的效率比起“容纳基本型别之外覆类（的reference）”的容器好太多了。

当然，如果你的操作对象是基本型别，而且需要在空间不足时自动扩增容量，Array便不适合，此时就得使用外覆类的容器了。

9）某些情况下，容器类即使没有转型至原来的型别，仍然可以运作无误。有一种情况尤其特别：编译器对String class提供了一些额外的支持，使它可以平滑运作。

10）对数组的一些基本操作，像排序、搜索与比较等是很常见的。因此在Java中提供了Arrays类协助这几个操作

sort(),binarySearch(),equals(),fill(),asList().

不过Arrays类没有提供删除方法，而ArrayList中有remove()方法，不知道是否是不需要在Array中做删除等操作的原因（因为此时应该使用链表）。

11）ArrayList的使用也很简单：产生ArrayList，利用add()将对象置入，利用get(i）配合索引值将它们取出。这一切就和Array的使用方式完全相同，只不过少了[]而已。

换一种简单说法：

1）效率：

数组扩容是对ArrayList效率影响比较大的一个因素。

每当执行Add、AddRange、Insert、InsertRange等添加元素的方法，都会检查内部数组的容量是否不够了，如果是，它就会以当前容量的两倍来重新构建一个数组，将旧元素Copy到新数组中，然后丢弃旧数组，在这个临界点的扩容操作，应该来说是比较影响效率的。

ArrayList是Array的复杂版本

ArrayList内部封装了一个Object类型的数组，从一般的意义来说，它和数组没有本质的差别，甚至于ArrayList的许多方法，如Index、IndexOf、Contains、Sort等都是在内部数组的基础上直接调用Array的对应方法。

2）类型识别：

ArrayList存入对象时，抛弃类型信息，所有对象屏蔽为Object，编译时不检查类型，但是运行时会报错。但是现在有jdk1.5后引入泛型来进行编译检查类型，如错存入了不同类型会直接报错。

ArrayList与数组的区别主要就是由于动态增容的效率问题了

3）ArrayList可以存任何Object，如String等。

数组和链表数据结构描述，各自的时间复杂度

数组是将元素在内存中连续存放，由于每个元素占用内存相同，可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一个元素，需要移动大量元素，在内存中空出一个元素的空间，然后将要增加的元素放在其中。同样的道理，如果想删除一个元素，同样需要移动大量元素去填掉被移动的元素。如果应用需要快速访问数据，很少插入和删除元素，就应该用数组。

链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针联系到一起，每个结点包括两个部分：一个是存储 数据元素的数据域，另一个是存储下一个结点地址的 指针。 如果要访问链表中一个元素，需要从第一个元素开始，一直找到需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了，只要修改元素中的指针就可以了。如果应用需要经常插入和删除元素你就需要用链表。

内存存储区别

数组从栈中分配空间, 对于程序员方便快速,但自由度小。链表从堆中分配空间, 自由度大但申请管理比较麻烦.　

逻辑结构区别

数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费。　

链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。（数组中插入、删除数据项时，需要移动其它数据项）　

总结 1、存取方式上，数组可以顺序存取或者随机存取，而链表只能顺序存取；　

2、存储位置上，数组逻辑上相邻的元素在物理存储位置上也相邻，而链表不一定；　

3、存储空间上，链表由于带有指针域，存储密度不如数组大；　

4、按序号查找时，数组可以随机访问，时间复杂度为O(1)，而链表不支持随机访问，平均需要O(n)；　

5、按值查找时，若数组无序，数组和链表时间复杂度均为O(1)，但是当数组有序时，可以采用折半查找将时间复杂度降为O(logn)；　

6、插入和删除时，数组平均需要移动n/2个元素，而链表只需修改指针即可；　

7、空间分配方面：

数组在静态存储分配情形下，存储元素数量受限制，动态存储分配情形下，虽然存储空间可以扩充，但需要移动大量元素，导致操作效率降低，而且如果内存中没有更大块连续存储空间将导致分配失败；

链表存储的节点空间只在需要的时候申请分配，只要内存中有空间就可以分配，操作比较灵活高效；

数组有没有length()这个方法? String有没有length()这个方法

为什麽数组从栈中分配空间？

队列

队列和栈是什么，列出它们的区别

队列（Queue）：是限定只能在表的一端进行插入和在另一端进行删除操作的线性表；

栈（Stack）：是限定只能在表的一端进行插入和删除操作的线性表。

区别如下：

规则不同

  1. 队列：先进先出（First In First Out）FIFO

  2. 栈：先进后出（First In Last Out ）FILO

对插入和删除操作的限定不同

  1. 队列：只能在表的一端进行插入，并在表的另一端进行删除；

  2. 栈：只能在表的一端插入和删除。

遍历数据速度不同

  1. 队列：基于地址指针进行遍历，而且可以从头部或者尾部进行遍历，但不能同时遍历，无需开辟空间，因为在遍历的过程中不影响数据结构，所以遍历速度要快；

  2. 栈：只能从顶部取数据，也就是说最先进入栈底的，需要遍历整个栈才能取出来，而且在遍历数据的同时需要为数据开辟临时空间，保持数据在遍历前的一致性

BlockingQueue是什么

阻塞队列（BlockingQueue）是一个支持两个附加操作的队列。这两个附加的操作是：在队列为空时，获取元素的线程会等待队列变为非空。当队列满时，存储元素的线程会等待队列可用。阻塞队列常用于生产者和消费者的场景，生产者是往队列里添加元素的线程，消费者是从队列里拿元素的线程。阻塞队列就是生产者存放元素的容器，而消费者也只从容器里拿元素。

Java里的7种阻塞队列是什么

JDK7提供了7个阻塞队列。分别是

  1. ArrayBlockingQueue ：一个由数组结构组成的有界阻塞队列。

  2. LinkedBlockingQueue ：一个由链表结构组成的有界阻塞队列。

  3. PriorityBlockingQueue ：一个支持优先级排序的无界阻塞队列。

  4. DelayQueue：一个使用优先级队列实现的无界阻塞队列。

  5. SynchronousQueue：一个不存储元素的阻塞队列。

  6. LinkedTransferQueue：一个由链表结构组成的无界阻塞队列。

  7. LinkedBlockingDeque：一个由链表结构组成的双向阻塞队列。

ArrayBlockingQueue

ArrayBlockingQueue是一个用数组实现的有界阻塞队列。此队列按照先进先出（FIFO）的原则对元素进行排序。默认情况下不保证访问者公平的访问队列，所谓公平访问队列是指阻塞的所有生产者线程或消费者线程，当队列可用时，可以按照阻塞的先后顺序访问队列，即先阻塞的生产者线程，可以先往队列里插入元素，先阻塞的消费者线程，可以先从队列里获取元素。通常情况下为了保证公平性会降低吞吐量。我们可以使用以下代码创建一个公平的阻塞队列：

1 ArrayBlockingQueue fairQueue = new ArrayBlockingQueue(1000,true); 访问者的公平性是使用可重入锁实现的，代码如下：

public ArrayBlockingQueue(int capacity, boolean fair) {
        if (capacity <= 0)
            throw new IllegalArgumentException();
        this.items = new Object[capacity];
        lock = new ReentrantLock(fair);
        notEmpty = lock.newCondition();
        notFull =  lock.newCondition();
}

LinkedBlockingQueue

LinkedBlockingQueue是一个用链表实现的有界阻塞队列。此队列的默认和最大长度为Integer.MAX_VALUE。此队列按照先进先出的原则对元素进行排序。

PriorityBlockingQueue

PriorityBlockingQueue是一个支持优先级的无界队列。默认情况下元素采取自然顺序排列，也可以通过比较器comparator来指定元素的排序规则。元素按照升序排列。

DelayQueue

DelayQueue是一个支持延时获取元素的无界阻塞队列。队列使用PriorityQueue来实现。队列中的元素必须实现Delayed接口，在创建元素时可以指定多久才能从队列中获取当前元素。只有在延迟期满时才能从队列中提取元素。我们可以将DelayQueue运用在以下应用场景：

缓存系统的设计：可以用DelayQueue保存缓存元素的有效期，使用一个线程循环查询DelayQueue，一旦能从DelayQueue中获取元素时，表示缓存有效期到了。 定时任务调度。使用DelayQueue保存当天将会执行的任务和执行时间，一旦从DelayQueue中获取到任务就开始执行，从比如TimerQueue就是使用DelayQueue实现的。 队列中的Delayed必须实现compareTo来指定元素的顺序。比如让延时时间最长的放在队列的末尾。实现代码如下：

public int compareTo(Delayed other) {
           if (other == this) // compare zero ONLY if same object
                return 0;
            if (other instanceof ScheduledFutureTask) {
                ScheduledFutureTask x = (ScheduledFutureTask)other;
                long diff = time - x.time;
                if (diff < 0)
                    return -1;
                else if (diff > 0)
                    return 1;
       else if (sequenceNumber < x.sequenceNumber)
                    return -1;
                else
                    return 1;
            }
            long d = (getDelay(TimeUnit.NANOSECONDS) -
                      other.getDelay(TimeUnit.NANOSECONDS));
            return (d == 0) ? 0 : ((d < 0) ? -1 : 1);
        }

如何实现Delayed接口

我们可以参考ScheduledThreadPoolExecutor里ScheduledFutureTask类。这个类实现了Delayed接口。首先：在对象创建的时候，使用time记录前对象什么时候可以使用，代码如下：

ScheduledFutureTask(Runnable r, V result, long ns, long period) {
            super(r, result);
            this.time = ns;
            this.period = period;
            this.sequenceNumber = sequencer.getAndIncrement();
}

然后使用getDelay可以查询当前元素还需要延时多久，代码如下：

public long getDelay(TimeUnit unit) {
            return unit.convert(time - now(), TimeUnit.NANOSECONDS);
        }

通过构造函数可以看出延迟时间参数ns的单位是纳秒，自己设计的时候最好使用纳秒，因为getDelay时可以指定任意单位，一旦以纳秒作为单位，而延时的时间又精确不到纳秒就麻烦了。使用时请注意当time小于当前时间时，getDelay会返回负数。

如何实现延时队列

延时队列的实现很简单，当消费者从队列里获取元素时，如果元素没有达到延时时间，就阻塞当前线程。

long delay = first.getDelay(TimeUnit.NANOSECONDS);
                    if (delay <= 0)
                        return q.poll();
                    else if (leader != null)
                        available.await();

SynchronousQueue

SynchronousQueue是一个不存储元素的阻塞队列。每一个put操作必须等待一个take操作，否则不能继续添加元素。SynchronousQueue可以看成是一个传球手，负责把生产者线程处理的数据直接传递给消费者线程。队列本身并不存储任何元素，非常适合于传递性场景,比如在一个线程中使用的数据，传递给另外一个线程使用，SynchronousQueue的吞吐量高于LinkedBlockingQueue 和 ArrayBlockingQueue。

LinkedTransferQueue

LinkedTransferQueue是一个由链表结构组成的无界阻塞TransferQueue队列。相对于其他阻塞队列LinkedTransferQueue多了tryTransfer和transfer方法。

transfer方法。如果当前有消费者正在等待接收元素（消费者使用take()方法或带时间限制的poll()方法时），transfer方法可以把生产者传入的元素立刻transfer（传输）给消费者。如果没有消费者在等待接收元素，transfer方法会将元素存放在队列的tail节点，并等到该元素被消费者消费了才返回。transfer方法的关键代码如下：

Node pred = tryAppend(s, haveData);
return awaitMatch(s, pred, e, (how == TIMED), nanos);

第一行代码是试图把存放当前元素的s节点作为tail节点。第二行代码是让CPU自旋等待消费者消费元素。因为自旋会消耗CPU，所以自旋一定的次数后使用Thread.yield()方法来暂停当前正在执行的线程，并执行其他线程。

tryTransfer方法。则是用来试探下生产者传入的元素是否能直接传给消费者。如果没有消费者等待接收元素，则返回false。和transfer方法的区别是tryTransfer方法无论消费者是否接收，方法立即返回。而transfer方法是必须等到消费者消费了才返回。

对于带有时间限制的tryTransfer(E e, long timeout, TimeUnit unit)方法，则是试图把生产者传入的元素直接传给消费者，但是如果没有消费者消费该元素则等待指定的时间再返回，如果超时还没消费元素，则返回false，如果在超时时间内消费了元素，则返回true。

LinkedBlockingDeque

LinkedBlockingDeque是一个由链表结构组成的双向阻塞队列。所谓双向队列指的你可以从队列的两端插入和移出元素。双端队列因为多了一个操作队列的入口，在多线程同时入队时，也就减少了一半的竞争。相比其他的阻塞队列，LinkedBlockingDeque多了addFirst，addLast，offerFirst，offerLast，peekFirst，peekLast等方法，以First单词结尾的方法，表示插入，获取（peek）或移除双端队列的第一个元素。以Last单词结尾的方法，表示插入，获取或移除双端队列的最后一个元素。另外插入方法add等同于addLast，移除方法remove等效于removeFirst。但是take方法却等同于takeFirst，不知道是不是Jdk的bug，使用时还是用带有First和Last后缀的方法更清楚。在初始化LinkedBlockingDeque时可以初始化队列的容量，用来防止其再扩容时过渡膨胀。另外双向阻塞队列可以运用在“工作窃取”模式中。

阻塞队列的实现原理

如果队列是空的，消费者会一直等待，当生产者添加元素时候，消费者是如何知道当前队列有元素的呢？如果让你来设计阻塞队列你会如何设计，让生产者和消费者能够高效率的进行通讯呢？让我们先来看看JDK是如何实现的。

使用通知模式实现。所谓通知模式，就是当生产者往满的队列里添加元素时会阻塞住生产者，当消费者消费了一个队列中的元素后，会通知生产者当前队列可用。通过查看JDK源码发现ArrayBlockingQueue使用了Condition来实现，代码如下：

private final Condition notFull;
private final Condition notEmpty;
 
public ArrayBlockingQueue(int capacity, boolean fair) {
        //省略其他代码
        notEmpty = lock.newCondition();
        notFull =  lock.newCondition();
    }
 
public void put(E e) throws InterruptedException {
        checkNotNull(e);
        final ReentrantLock lock = this.lock;
        lock.lockInterruptibly();
        try {
            while (count == items.length)
                notFull.await();
            insert(e);
        } finally {
            lock.unlock();
        }
}
 
public E take() throws InterruptedException {
        final ReentrantLock lock = this.lock;
        lock.lockInterruptibly();
        try {
            while (count == 0)
                notEmpty.await();
            return extract();
  } finally {
            lock.unlock();
        }
}
 
private void insert(E x) {
        items[putIndex] = x;
        putIndex = inc(putIndex);
        ++count;
        notEmpty.signal();
    }

当我们往队列里插入一个元素时，如果队列不可用，阻塞生产者主要通过LockSupport.park(this);来实现

public final void await() throws InterruptedException {
            if (Thread.interrupted())
                throw new InterruptedException();
            Node node = addConditionWaiter();
            int savedState = fullyRelease(node);
            int interruptMode = 0;
            while (!isOnSyncQueue(node)) {
                LockSupport.park(this);
                if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
                    break;
            }
            if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
                interruptMode = REINTERRUPT;
            if (node.nextWaiter != null) // clean up if cancelled
                unlinkCancelledWaiters();
            if (interruptMode != 0)
 
reportInterruptAfterWait(interruptMode);
        }

继续进入源码，发现调用setBlocker先保存下将要阻塞的线程，然后调用unsafe.park阻塞当前线程。

public static void park(Object blocker) {
        Thread t = Thread.currentThread();
        setBlocker(t, blocker);
        unsafe.park(false, 0L);
        setBlocker(t, null);
    }

unsafe.park是个native方法，代码如下：

1 public native void park(boolean isAbsolute, long time); park这个方法会阻塞当前线程，只有以下四种情况中的一种发生时，该方法才会返回。

与park对应的unpark执行或已经执行时。注意：已经执行是指unpark先执行，然后再执行的park。 线程被中断时。 如果参数中的time不是零，等待了指定的毫秒数时。 发生异常现象时。这些异常事先无法确定。 我们继续看一下JVM是如何实现park方法的，park在不同的操作系统使用不同的方式实现，在linux下是使用的是系统方法pthread_cond_wait实现。实现代码在JVM源码路径src/os/linux/vm/os_linux.cpp里的 os::PlatformEvent::park方法，代码如下：

void os::PlatformEvent::park() {
             int v ;
         for (;;) {
        v = _Event ;
         if (Atomic::cmpxchg (v-1, &_Event, v) == v) break ;
         }
         guarantee (v >= 0, "invariant") ;
         if (v == 0) {
         // Do this the hard way by blocking ...
         int status = pthread_mutex_lock(_mutex);
         assert_status(status == 0, status, "mutex_lock");
         guarantee (_nParked == 0, "invariant") ;
         ++ _nParked ;
         while (_Event < 0) {
         status = pthread_cond_wait(_cond, _mutex);
         // for some reason, under 2.7 lwp_cond_wait() may return ETIME ...
         // Treat this the same as if the wait was interrupted
         if (status == ETIME) { status = EINTR; }
         assert_status(status == 0 || status == EINTR, status, "cond_wait");
         }
         -- _nParked ;
 
         // In theory we could move the ST of 0 into _Event past the unlock(),
         // but then we'd need a MEMBAR after the ST.
         _Event = 0 ;
         status = pthread_mutex_unlock(_mutex);
         assert_status(status == 0, status, "mutex_unlock");
         }
         guarantee (_Event >= 0, "invariant") ;
         }
 
     }

pthread_cond_wait是一个多线程的条件变量函数，cond是condition的缩写，字面意思可以理解为线程在等待一个条件发生，这个条件是一个全局变量。这个方法接收两个参数，一个共享变量_cond，一个互斥量_mutex。而unpark方法在linux下是使用pthread_cond_signal实现的。park 在windows下则是使用WaitForSingleObject实现的。

当队列满时，生产者往阻塞队列里插入一个元素，生产者线程会进入WAITING (parking)状态。我们可以使用jstack dump阻塞的生产者线程看到这点：

"main" prio=5 tid=0x00007fc83c000000 nid=0x10164e000 waiting on condition [0x000000010164d000]
   java.lang.Thread.State: WAITING (parking)
        at sun.misc.Unsafe.park(Native Method)
        - parking to wait for  <0x0000000140559fe8> (a java.util.concurrent.locks.AbstractQueuedSynchronizer$ConditionObject)
        at java.util.concurrent.locks.LockSupport.park(LockSupport.java:186)
        at java.util.concurrent.locks.AbstractQueuedSynchronizer$ConditionObject.await(AbstractQueuedSynchronizer.java:2043)
        at java.util.concurrent.ArrayBlockingQueue.put(ArrayBlockingQueue.java:324)
        at blockingqueue.ArrayBlockingQueueTest.main(ArrayBlockingQueueTest.java:11)
简述 ConcurrentLinkedQueue LinkedBlockingQueue 的用处和不同之处

阻塞队列：线程安全

按 FIFO（先进先出）排序元素。队列的头部是在队列中时间最长的元素。队列的尾部是在队列中时间最短的元素。新元素插入到队列的尾部，并且队列检索操作会获得位于队列头部的元素。链接队列的吞吐量通常要高于基于数组的队列，但是在大多数并发应用程序中，其可预知的性能要低。

注意：

1、必须要使用take()方法在获取的时候达成阻塞结果

2、使用poll()方法将产生非阻塞效果

非阻塞队列

基于链接节点的、无界的、线程安全。此队列按照 FIFO（先进先出）原则对元素进行排序。队列的头部 是队列中时间最长的元素。队列的尾部 是队列中时间最短的元素。新的元素插入到队列的尾部，队列检索操作从队列头部获得元素。当许多线程共享访问一个公共 collection 时，ConcurrentLinkedQueue是一个恰当的选择。此队列不允许 null 元素。

在并发编程中，一般推荐使用阻塞队列，这样实现可以尽量地避免程序出现意外的错误。阻塞队列使用最经典的场景就是socket客户端数据的读取和解析，读取数据的线程不断将数据放入队列，然后解析线程不断从队列取数据解析。还有其他类似的场景，只要符合生产者-消费者模型的都可以使用阻塞队列。

使用非阻塞队列，虽然能即时返回结果（消费结果），但必须自行编码解决返回为空的情况处理（以及消费重试等问题）。另外他们都是线程安全的，不用考虑线程同步问题。

ArrayList、Vector、LinkedList的存储性能和特性

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

Vector中的方法由于添加了synchronized修饰，因此Vector是线程安全的容器，但性能上较ArrayList差，因此已经是Java中的遗留容器。

LinkedList使用双向链表实现存储（将内存中零散的内存单元通过附加的引用关联起来，形成一个可以按序号索引的线性结构，这种链式存储方式与数组的连续存储方式相比，内存的利用率更高），按序号索引数据需要进行前向或后向遍历，但是插入数据时只需要记录本项的前后项即可，所以插入速度较快。

Vector属于遗留容器（Java早期的版本中提供的容器，除此之外，Hashtable、Dictionary、BitSet、Stack、Properties都是遗留容器），已经不推荐使用，但是由于ArrayList和LinkedListed都是非线程安全的，如果遇到多个线程操作同一个容器的场景，则可以通过工具类Collections中的synchronized List方法将其转换成线程安全的容器后再使用（这是对装潢模式的应用，将已有对象传入另一个类的构造器中创建新的对象来增强实现）。

String

ByteBuffer 与 StringBuffer有什么区别

Collections

介绍Java中的Collection FrameWork。集合类框架的基本接口有哪些？

总共有两大接口：Collection 和Map ，一个元素集合，一个是键值对集合；

其中List和Set接口继承了Collection接口，一个是有序元素集合，一个是无序元素集合；

ArrayList和LinkedList实现了List接口，HashSet实现了Set接口，这几个都比较常用；

HashMap和HashTable实现了Map接口，并且HashTable是线程安全的，但是HashMap性能更好；

集合类框架的最佳实践有哪些

根据应用的需要合理的选择集合的类型对性能非常重要

假如元素的大小是固定的，而且能事先知道，我们就该用Array而不是ArrayList.

有些集合类允许指定初始容量。因此，如果我们能估计出存储元素的数目，我们可以设置初始容量来避免重新计算hash值或者扩容.

为了类型安全，可读性和健壮性的原因总要使用翻新。同时，使用泛型还能皮面运行时的ClassCastException.

使用JDK提供的不变类（immutable class）作为Map的键可以避免为我们自己的类实现hashCode()和equals()方法。

编程的时候接口优于实现。

底层的集合实际上是空的情况下返回长度是0的集合或者是数组，不要返回null.

为什么 Collection 不从 Cloneable 和 Serializable 接口继承?

Collection接口指定一组对象，对象即为它的元素。如何维护这些元素由Collection的具体实现决定。例如，一些如List的Collection实现允许重复的元素，而其它的如Set就不允许。很多Collection实现有一个公有的clone方法。然而，把它放到集合的所有实现中也是没有意义的。这是因为Collection是一个抽象表现。

重要的是实现，克隆（cloning）或者序列化（serialization）的语义和含义是跟具体的实现相关的。因此应该由集合类的具体实现类来决定如何被克隆或者序列化。

说出几点 Java 中使用 Collections 的最佳实践？

）使用正确的集合类，例如，如果不需要同步列表，使用 ArrayList 而不是 Vector。

b）优先使用并发集合，而不是对集合进行同步。并发集合提供更好的可扩展性。

c）使用接口代表和访问集合，如使用List存储 ArrayList，使用 Map 存储 HashMap 等等。

d）使用迭代器来循环集合。

e）使用集合的时候使用泛型

你了解哪些集合类型？
  • ArrayList
  • LinkedList
  • HashMap
  • HashSet 之后，你可能会被问到这样一些问题，比如应该何时使用此种特定类型，它比其他的好在哪里，它是怎么存储数据的以及隐匿在背后的数据结构是什么。最好的方法是尽可能多地了解这些集合类型，因为这类问题几乎是无穷尽的
HashMap 有什么特点？

HashMap 基于Map接口实现，存储键值对时，可以接收 null 为键值。HashMap 是非同步的。

HashMap 的工作原理是怎样的？

HashMap 在 Map.Entry 静态内部类实现中存储键值对，使用哈希算法。在 put 和 get 方法中，使用 hashCode() 和 equals() 方法。

调用 put 方法时，使用键值对中的 Key hashCode() 和哈希算法找出存储键值对索引。键值对 Entry 存储在 LinkedList 中，如果存在 Entry，使用 equals() 方法来检查 Key 是否已经存在：如果存在，则覆盖 value；如果不存在，会创建一个新的 Entry 然后保存。 调用 get 方法时，HashMap 使用键值 Key hashCode() 来找到数组中的索引，然后使用 equals() 方法找出正确的 Entry，返回 Entry 中的 Value。 分析：HashMap 中容量、负荷系数和阀值是重要的参数。HashMap 默认的初始容量是16，负荷系数是0.75。阀值 = 负荷系数 x 容量。添加 Entry时，如果 Map 的大小 > 阀值，HashMap 会对 Map 的内容重新哈希，使用更大的容量（容量总是2的幂）。关于 JDK 中的 hash 算法实现以及由此引发的哈希碰撞现象（DDos攻击）都可能是面试的延伸问题。

更新：HashMap初始容量16，static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

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

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

如果类重写了 equals() 方法，也应该重写 hashCode() 方法。 类的所有实例需要遵循与 equals() 和 hashCode() 相关的规则。 如果一个类没有使用 equals()，不应该在 hashCode() 中使用它。 用户自定义 Key 类最佳实践是使之为不可变的，这样 hashCode() 值可以被缓存起来，拥有更好的性能。不可变的类也可以确保 hashCode() 和 equals() 在未来不会改变，这样就会解决与可变相关的问题了。 分析：如果有一个类 MyKey，在 HashMap 中使用它：

HashMap<MyKey, String> myHashMap = new HashMap<MyKey, String>();
 
//传递给 MyKey 的 name 参数被用于 equals() 和 hashCode() 中
MyKey key = new MyKey("Pankaj"); // 假设 hashCode=1234
myHashMap.put(key, "Value");
 
// 以下的代码会改变 key 的 hashCode() 和 equals() 值
key.setName("Amit"); // 假设新的 hashCode=7890
 
//下面会返回 null，因为 HashMap 会尝试查找存储同样索引的 key，而 key 已被改变了，匹配失败，返回 null
System.out.println(myHashMap.get(new MyKey("Pankaj")));

这就是为什么 String 通常会用作 HashMap 的 Key，因为 String 的设计是不可变的（immutable）。

插入数据时，ArrayList、LinkedList、Vector谁速度较快？

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

  • Vector 中的方法由于加了 synchronized 修饰，因此 Vector 是线程安全容器，但性能上较ArrayList差。
  • LinkedList 使用双向链表实现存储，按序号索引数据需要进行前向或后向遍历，但插入数据时只需要记录当前项的前后项即可，所以 LinkedList 插入速度较快。
多线程场景下如何使用 ArrayList？

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

List<String> synchronizedList = Collections.synchronizedList(list);
synchronizedList.add("aaa");
synchronizedList.add("bbb");
for (int i = 0; i < synchronizedList.size(); i++)
{
    System.out.println(synchronizedList.get(i));
}
说一下 ArrayList 的优缺点

ArrayList的优点如下：

  1. ArrayList 底层以数组实现，是一种随机访问模式。ArrayList 实现了 RandomAccess 接口，因此查找的时候非常快。
  2. ArrayList 在顺序添加一个元素的时候非常方便。

ArrayList 的缺点如下：

  1. 删除元素的时候，需要做一次元素复制操作。如果要复制的元素很多，那么就会比较耗费性能。
  2. 插入元素的时候，也需要做一次元素复制操作，缺点同上。 ArrayList 比较适合顺序添加、随机访问的场景。
为什么 ArrayList 的 elementData 加上 transient 修饰？

ArrayList 中的数组定义如下：

private transient Object[] elementData;

再看一下 ArrayList 的定义：

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

可以看到 ArrayList 实现了 Serializable 接口，这意味着 ArrayList 支持序列化。transient 的作用是说不希望 elementData 数组被序列化，重写了 writeObject 实现：

private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    s.defaultWriteObject();
        // Write out array length
    s.writeInt(elementData.length);
        // Write out all elements in the proper order.
    for (int i=0; i<size; i++)
        s.writeObject(elementData[i]);
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }

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

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

遍历方式有以下几种：

for 循环遍历，基于计数器。在集合外部维护一个计数器，然后依次读取每一个位置的元素，当读取到最后一个元素后停止。 迭代器遍历，Iterator。Iterator 是面向对象的一个设计模式，目的是屏蔽不同数据集合的特点，统一遍历集合的接口。Java 在 Collections 中支持了 Iterator 模式。 foreach 循环遍历。foreach 内部也是采用了 Iterator 的方式实现，使用时不需要显式声明 Iterator 或计数器。优点是代码简洁，不易出错；缺点是只能做简单的遍历，不能在遍历过程中操作数据集合，例如删除、替换。 最佳实践：Java Collections 框架中提供了一个 RandomAccess 接口，用来标记 List 实现是否支持 Random Access。

如果一个数据集合实现了该接口，就意味着它支持 Random Access，按位置读取元素的平均时间复杂度为 O(1)，如ArrayList。 如果没有实现该接口，表示不支持 Random Access，如LinkedList。 推荐的做法就是，支持 Random Access 的列表可用 for 循环遍历，否则建议用 Iterator 或 foreach 遍历。

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

边遍历边修改 Collection 的唯一正确方式是使用 Iterator.remove() 方法，如下：

Iterator<Integer> it = list.iterator();
while(it.hasNext()){
    // do something
    it.remove();
}

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

for(Integer i : list){
    list.remove(i)
}

运行以上错误代码会报 ConcurrentModificationException 异常。这是因为当使用 foreach(for(Integer i : list)) 语句时，会自动生成一个iterator 来遍历该 list，但同时该 list 正在被 Iterator.remove() 修改。Java 一般不允许一个线程在遍历 Collection 时另一个线程修改它

Hashcode 的作用

对于包含容器类型的程序设计语言来说，基本上都会涉及到 hashCode。在Java中也一样，hashCode方法的主要作用是为了配合基于散列的集合一起正常运行，这样的散列集合包括HashSet、HashMap以及HashTable。 为什么这么说呢？考虑一种情况，当向集合中插入对象时，如何判别在集合中是否已经存在该对象了？（注意：集合中不允许重复的元素存在） 也许大多数人都会想到调用equals方法来逐个进行比较，这个方法确实可行。但是如果集合中已经存在一万条数据或者更多的数据，如果采用equals方法去逐一比较，效率必然是一个问题。此时hashCode方法的作用就体现出来了，当集合要添加新的对象时，先调用这个对象的hashCode方法，得到对应的hashcode值，实际上在HashMap的具体实现中会用一个table保存已经存进去的对象的hashcode值，如果table中没有该hashcode值，它就可以直接存进去，不用再进行任何比较了；如果存在该hashcode值， 就调用它的equals方法与新元素进行比较，相同的话就不存了，不相同就散列其它的地址，所以这里存在一个冲突解决的问题，这样一来实际调用equals方法的次数就大大降低了，说通俗一点：Java中的hashCode方法就是根据一定的规则将与对象相关的信息（比如对象的存储地址，对象的字段等）映射成一个数值，这个数值称作为散列值。

//java.util.HashMap的中put方法的具体实现：

public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
}

put方法是用来向HashMap中添加新的元素，从put方法的具体实现可知，会先调用hashCode方法得到该元素的hashCode值，然后查看table中是否存在该hashCode值，如果存在则调用equals方法重新确定是否存在该元素，如果存在，则更新value值，否则将新的元素添加到HashMap中。从这里可以看出，hashCode方法的存在是为了减少equals方法的调用次数，从而提高程序效率。

有没有可能两个不相等的对象有相同的 hashcode？当两个对象hashcode 相同怎么办？如何获取值对象？

对于两个对象：

如果调用equals方法得到的结果为true，则两个对象的hashcode值必定相等；

如果equals方法得到的结果为false，则两个对象的hashcode值不一定不同；

如果两个对象的hashcode值不等，则equals方法得到的结果必定为false；

如果两个对象的hashcode值相等，则equals方法得到的结果未知。

总之一句话：等价对象产生相同整数的哈希码，不同对象不一定要不同的哈希码。后面两个命题其实就是这句话的逆否命题。

所以，针对上面问题提到的，两个不相等的对象其实就是问的equals为false，那么hashcode不一定是不同，也就是有可能会相同了。为什呢会这样呢？hashCode是所有java对象的固有方法，如果不重载的话，返回的实际上是该对象在jvm的堆上的内存地址，而不同对象的内存地址肯定不同，所以这个hashCode也就肯定不同了。如果重载了的话，由于采用的算法的问题，有可能导致两个不同对象的hashCode相同。 后面的问题其实会比较多的出现在Map的面试考察中， 当我们调用Map的get()方法，HashMap会使用键对象的hashcode找到bucket位置，然后获取值对象。面试官提醒他如果有两个值对象储存在同一个bucket，他给出答案：将会遍历链表直到找到值对象。面试官会问因为你并没有值对象去比较，你是如何确定确定找到值对象的？除非面试者直HashMap在链表中存储的是键值对，否则他们不可能回答出这一题。其中一些记得这个重要知识点的面试者会说，找到bucket位置之后，会调用keys.equals()方法去找到链表中正确的节点，最终找到要找的值对象。完美的答案！

为什么在重写 equals 方法的时候需要重写 hashCode 方法？equals与hashCode 的异同点在哪里?

这里头牵扯到另外隐含的问题，一并拿出来解决：

1、首先我们为什么需要重写hashCode()方法和equals()方法

2、为什么在重写 equals 方法的时候需要重写 hashCode 方法？

3、如何重写这两个方法?

回答第一个问题： Java中的超类Object类中定义的equals()方法是用来比较两个引用所指向的对象的内存地址是否一致，Object类中equals()方法的源码

public boolean equals(Object obj) {
       return (this == obj);
}

Object类中的hashCode()方法，用native关键字修饰，说明这个方法是个原生函数，也就说这个方法的实现不是用java语言实现的，是使用c/c++实现的，并且被编译成了DLL，由java去调用，jdk源码中不包含。对于不同的平台它们是不同的，java在不同的操作系统中调用不同的native方法实现对操作系统的访问，因为java语言不能直接访问操作系统底层，因为它没有指针。

Java的API文档对hashCode()方法做了详细的说明，这也是我们重写hashCode()方法时的原则【Object类】

public native int hashCode();

我们在定义类时，我们经常会希望两个不同对象的某些属性值相同时就认为他们相同，所以我们要重写equals()方法，但同时也要改写hashCode()方法，所以java中的很多类都重写了这两个方法,例如String类，包装类。

第二个问题：为什么在重写 equals 方法的时候需要重写 hashCode 方法？

Java 对于hashCode方法的规约：

在java应用程序运行时，无论何时多次调用同一个对象时的hsahCode()方法，这个对象的hashCode()方法的返回值必须是同一个int值

如果两个对象equals()返回值为true,则他们的hashCode()也必须返回相同的int值

如果两个对象根据equals()比较是不等的，则hashCode()方法不一定得返回不同的整数。

根据规约，为了保证同一个对象，equals相同的情况下hashcode值必定相同，如果重写了equals而未重写hashcode方法，可能就会出现两个对象equals相同的（因为equal都是根据对象的特征进行重写的），但hashcode确实不相同的。如果不这样做程序也可以执行，只不过会隐藏bug。比如重写了equals方法，属性相同就认为相同，但不重写hashcode，那么我们再new一个新的对象，当原对象equals（新对象）等于true时，两者的hashcode却是不一样的，由此将产生了理解的不一致，如在存储散列集合时（如Set类），将会存储了两个值一样的对象，导致混淆，因此就也需要重写hashcode()。【一句话，容易在要求散列存储的时候，把相同对象给放到一个集合】

有这个要求的症结在于，要考虑到类似HashMap、HashTable、HashSet的这种散列的数据类型的运用。

hashCode() 有什么用？与 a.equals(b) 有什么关系？

如果调用equals方法得到的结果为true，则两个对象的hashcode值必定相等；

如果equals方法得到的结果为false，则两个对象的hashcode值不一定不同；

如果两个对象的hashcode值不等，则equals方法得到的结果必定为false；

如果两个对象的hashcode值相等，则equals方法得到的结果未知。

总之一句话：等价对象产生相同整数的哈希码，不同对象不一定要不同的哈希码。后面两个命题其实就是这句话的逆否命题。

hashCode() 和 equals() 方法的重要性体现在什么地方？

散列存储集合如HashMap的很多函数要基于equal()函数和hashCode()函数。hashCode()用来定位要存放的位置，equal()用来判断是否相等。

那么，相等的概念是什么？

Object版本的equal只是简单地判断是不是同一个实例。但是有的时候，我们想要的的是逻辑上的相等。比如有一个学生类student，有一个属性studentID，只要

studentID相等，不是同一个实例我们也认为是同一学生。当我们认为判定equals的相等应该是逻辑上的相等而不是只是判断是不是内存中的同一个东西的时候，就需要

重写equal()。而涉及到HashMap的时候，重写了equals()，就需要重写hashCode()

Object类hashcode,equals 设计原则？ sun为什么这么设计？

在程序执行期间，只要equals方法的比较操作用到的信息没有被修改，那么对这同一个对象调用多次，hashCode方法必须始终如一地返回同一个整数。

如果两个对象根据equals方法比较是相等的，那么调用两个对象的hashCode方法必须返回相同的整数结果。

如果两个对象根据equals方法比较是不等的，则hashCode方法不一定得返回不同的整数。

以上是摘自Effective Java的原话，下面进行具体解读：

1.同一个对象（没有发生过修改）无论何时调用hashCode()得到的返回值必须一样。

如果一个key对象在put的时候调用hashCode()决定了存放的位置，而在get的时候调用hashCode()得到了不一样的返回值，这个值映射到了一个和原来不一样的地方，那么肯定就找不到原来那个键值对了。

2.hashCode()的返回值相等的对象不一定相等，通过hashCode()和equals()必须能唯一确定一个对象

不相等的对象的hashCode()的结果可以相等。hashCode()在注意关注碰撞问题的时候，也要关注生成速度问题，完美hash不现实。

3.一旦重写了equals()函数（重写equals的时候还要注意要满足自反性、对称性、传递性、一致性），就必须重写hashCode()函数。而且hashCode()的生成哈希值的依据应该是equals()中用来比较是否相等的字段 。如果两个由equals()规定相等的对象生成的hashCode不等，对于hashMap来说，他们很可能分别映射到不同位置，没有调用equals()比较是否相等的机会，两个实际上相等的对象可能被插入不同位置，出现错误。其他一些基于哈希方法的集合类可能也会有这个问题。

Object有哪些公用方法？Object类的概述?

Object是所有类的父类，任何类都默认继承Object。

clone：保护方法，实现对象的浅复制，只有实现了Cloneable接口才可以调用该方法，否则抛出CloneNotSupportedException异常

equals：在Object中与==是一样的，子类一般需要重写该方法

hashCode：该方法用于哈希查找，重写了equals方法一般都要重写hashCode方法。这个方法在一些具有哈希功能的Collection中用到

getClass：final方法，获得运行时类型

wait：使当前线程等待该对象的锁，当前线程必须是该对象的拥有者，也就是具有该对象的锁。wait()方法一直等待，直到获得锁或者被中断。wait(long timeout)设定一个超时间隔，如果在规定时间内没有获得锁就返回。 调用该方法后当前线程进入睡眠状态，直到以下事件发生：

其他线程调用了该对象的notify方法

其他线程调用了该对象的notifyAll方法

其他线程调用了interrupt中断该线程

时间间隔到了，此时该线程就可以被调度了，如果是被中断的话就抛出一个InterruptedException异常

notify：唤醒在该对象上等待的某个线程

notifyAll：唤醒在该对象上等待的所有线程

toString：转换成字符串，一般子类都有重写，否则打印句柄

Collections类是什么？Collection 和 Collections的区别？Collection、Map的实现

Collection是单列集合

List元素是有序的、可重复。有序的collection，可以对列表中每个元素的插入位置进行精确地控制。可以根据元素的整数索引（在列表中的位置）访问元素，并搜索列表中的元素。 可存放重复元素，元素存取是有序的。

List接口中常用类

Vector：线程安全，但速度慢，已被ArrayList替代。底层数据结构是数组结构；

ArrayList：线程不安全，查询速度快。底层数据结构是数组结构；

LinkedList：线程不安全。增删速度快。底层数据结构是列表结构；

Set(集) 元素无序的、不可重复。取出元素的方法只有迭代器。不可以存放重复元素，元素存取是无序的。

Set接口中常用的类

HashSet：线程不安全，存取速度快。它是如何保证元素唯一性的呢？依赖的是元素的hashCode方法和euqals方法。

TreeSet：线程不安全，可以对Set集合中的元素进行排序。它的排序是如何进行的呢？通过compareTo或者compare方法中的来保证元素的唯一性。元素是以二叉树的形式存放的。

Map 是一个双列集合

Hashtable:线程安全，速度快。底层是哈希表数据结构。是同步的。不允许null作为键，null作为值。

Properties:用于配置文件的定义和操作，使用频率非常高，同时键和值都是字符串。是集合中可以和IO技术相结合的对象。

HashMap:线程不安全，速度慢。底层也是哈希表数据结构。是不同步的。允许null作为键，null作为值。替代了Hashtable.

LinkedHashMap: 可以保证HashMap集合有序。存入的顺序和取出的顺序一致。

TreeMap：可以用来对Map集合中的键进行排序.

Collection是集合类的上级接口，子接口主要有Set 和List。

Collections是针对集合类的一个帮助类，提供了操作集合的工具方法：一系列静态方法实现对各种集合的搜索、排序、线程安全化等操作。

介绍Collection框架的结构；Collection 和 Collections的区别

Set

Set 里的元素是不能重复的，那么用什么方法来区分重复与否呢？是用 == 还是 equals()？ 它们有何区别?

如果hash码值不相同，说明是一个新元素，存；

如果没有元素和传入对象（也就是add的元素）的hash值相等，那么就认为这个元素在table中不存在，将其添加进table；

如果hash码值相同，且equles判断相等，说明元素已经存在，不存；如果hash码值相同，且equles判断不相等，说明元素不存在，存；

java中的数据类型，可分为两类：

1.基本数据类型

也称原始数据类型。byte,short,char,int,long,float,double,boolean,他们之间的比较，应用双等号（==），比较的是他们的值。基本数据类型没有equals方法哦。

2.复合数据类型(类)

当他们用（==）进行比较的时候，比较的是他们在内存中的存放地址，所以，除非是同一个new出来的对象，他们的比较后的结果为true，否则比较后结果为false。 JAVA当中所有的类都是继承于Object这个基类的，在Object中的基类中定义了一个equals的方法，这个方法的初始行为是比较对象的内存地址，但在一些类库当中这个方法被覆盖掉了，如String,Integer,Date在这些类当中equals有其自身的实现，而不再是比较类在堆内存中的存放地址了。 对于复合数据类型之间进行equals比较，在没有覆写equals方法的情况下，他们之间的比较还是基于他们在内存中的存放位置的地址值的，因为Object的equals方法也是用双等号（==）进行比较的，所以比较后的结果跟双等号（==）的结果相同。

TreeMap：TreeMap 是采用什么树实现的？TreeMap、HashMap、LindedHashMap的区别。

TreeMap 是一个有序的key-value集合，它是通过红黑树实现的。 TreeMap 继承于AbstractMap，所以它是一个Map，即一个key-value集合。TreeMap 实现了NavigableMap接口，意味着它支持一系列的导航方法。比如返回有序的key集合。TreeMap 实现了Cloneable接口，意味着它能被克隆。 TreeMap 实现了java.io.Serializable接口，意味着它支持序列化。

TreeMap基于红黑树（Red-Black tree）实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。 TreeMap的基本操作 containsKey、get、put 和 remove 的时间复杂度是 log(n) 。 另外，TreeMap是非同步的。 它的iterator 方法返回的迭代器是fail-fastl的。

TreeMap和TreeSet在排序时如何比较元素？Collections工具类中的sort()方法如何比较元素？

TreeSet要求存放的对象所属的类必须实现Comparable接口，该接口提供了比较元素的compareTo()方法，当插入元素时会回调该方法比较元素的大小。TreeMap要求存放的键值对映射的键必须实现Comparable接口从而根据键对元素进行排序。Collections工具类的sort方法有两种重载的形式，第一种要求传入的待排序容器中存放的对象必须实现Comparable接口以实现元素的比较；第二种不强制性的要求容器中的元素必须可比较，但是要求传入第二个参数，参数是Comparator接口的子类型（需要重写compare方法实现元素的比较），相当于一个临时定义的排序规则，其实就是通过接口注入比较元素大小的算法，也是对回调模式的应用（Java中对函数式编程的支持）。

TreeSet：一个已经构建好的 TreeSet，怎么完成倒排序。

1、自然顺序

即类要实现Comparable接口，并重写compareTo()方法，TreeSet对象调用add()方法时，会将存入的对象提升为Comparable类型，然后调用对象中的compareTo()方法进行比较，根据比较的返回值进行存储。

因为TreeSet底层是二叉树，当compareTo方法返回0时，不存储；当compareTo方法返回正数时，存入二叉树的右子树；当compareTo方法返回负数时，存入二叉树的左子树。如果一个类没有实现Comparable接口就将该类对象存入TreeSet集合，会发生类型转换异常。

2、比较器顺序Comparator

创建TreeSet对象的时候可以指定一个比较器，即传入一个Comparator对象，那么TreeSet会优先按照Comparator中的compare()方法排序，compare方法中有两个参数，第一个是调用该方法的对象，第二个值集合中已经存入的对象。

.HashSet和TreeSet有什么区别?

底层存储的数据结构不同

HashSet底层用的是HashMap哈希表结构存储，而TreeSet底层用的是TreeMap树结构存储

存储时保证数据唯一性依据不同

HashSet是通过复写hashCode()方法和equals()方法来保证的，而HashSet通过Compareable接口的compareTo()方法来保证的

有序性不一样

HashSet无序，TreeSet有序

.HashSet 内部是如何工作的

HashSet:底层数据结构是哈希表，本质就是对哈希值的存储，通过判断元素的hashCode方法和equals方法来保证元素的唯一性，当hashCode值不相同，就直接存储了，不用在判断equals了，当hashCode值相同时，会在判断一次euqals方法的返回值是否为true，如果为true则视为用一个元素，不用存储，如果为false，这些相同哈希值不同内容的元素都存放一个bucket桶里（当哈希表中有一个桶结构，每一个桶都有一个哈希值）

TreeSet:底层的数据结构是二叉树，可以对Set集合中的元素进行排序,这种结构，可以提高排序性能, 根据比较方法的返回值确定的,只要返回的是0.就代表元素重复

EnumSet 是什么？
WeakHashMap 是怎么工作的？

list

List, Set, Map三个接口，存取元素时各有什么特点？

List与Set都是单列元素的集合，它们有一个功共同的父接口Collection。

Set里面不允许有重复的元素，

存元素：add方法有一个boolean的返回值，当集合中没有某个元素，此时add方法可成功加入该元素时，则返回true；当集合含有与某个元素equals相等的元素时，此时add方法无法加入该元素，返回结果为false。

取元素：没法说取第几个，只能以Iterator接口取得所有的元素，再逐一遍历各个元素。

List表示有先后顺序的集合，

存元素：多次调用add(Object)方法时，每次加入的对象按先来后到的顺序排序，也可以插队，即调用add(int index,Object)方法，就可以指定当前对象在集合中的存放位置。

取元素：

方法1：Iterator接口取得所有，逐一遍历各个元素

方法2：调用get(index i)来明确说明取第几个。使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引（元素在List中的位置，类似于数组下标）来访问List中的元素，这类似于Java的数组。

Map是双列的集合，存放用put方法:put(obj key,obj value)，每次存储时，要存储一对key/value，不能存储重复的key，这个重复的规则也是按equals比较相等。 取元素：用get(Object key)方法根据key获得相应的value。

也可以获得所有的key的集合，还可以获得所有的value的集合，

还可以获得key和value组合成的Map.Entry对象的集合。

List以特定次序来持有元素，可有重复元素。Set无法拥有重复元素,内部排序。Map 保存key-value值，value可多值

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

List和Set是的，而Map不是。

遍历一个 List 有哪些不同的方式 
Iterator it1 = list.iterator();
while(it1.hasNext()){
    System.out.println(it1.next());
}

//方法2
for(Iterator it2 = list.iterator();it2.hasNext();){
     System.out.println(it2.next());
}

//方法3
for(String tmp:list){
    System.out.println(tmp);
}

//方法4
for(int i = 0;i < list.size(); i ++){
    System.out.println(list.get(i));
}

LinkedList

LinkedList 是单向链表还是双向链表

Linkedlist，双向链表，优点，增加删除，用时间很短，但是因为没有索引，对索引的操作，比较麻烦，只能循环遍历，但是每次循环的时候，都会先判断一下，这个索引位于链表的前部分还是后部分，每次都会遍历链表的一半 ，而不是全部遍历。

双向链表，都有一个previous和next， 链表最开始的部分都有一个fiest和last指向第一个元素，和最后一个元素。增加和删除的时候，只需要更改一个previous和next，就可以实现增加和删除，所以说，LinkedList对于数据的删除和增加相当的方便。

LinkedList 与 ArrayList 有什么区别?

因为Array是基于索引(index)的数据结构，它使用索引在数组中搜索和读取数据是很快的。Array获取数据的时间复杂度是O(1),但是要删除数据却是开销很大的，因为这需要重排数组中的所有数据。

相对于ArrayList，LinkedList插入是更快的。因为LinkedList不像ArrayList一样，不需要改变数组的大小，也不需要在数组装满的时候要将所有的数据重新装入一个新的数组，这是ArrayList最坏的一种情况，时间复杂度是O(n)，而LinkedList中插入或删除的时间复杂度仅为O(1)。ArrayList在插入数据时还需要更新索引（除了插入数组的尾部）。

类似于插入数据，删除数据时，LinkedList也优于ArrayList。

LinkedList需要更多的内存，因为ArrayList的每个索引的位置是实际的数据，而LinkedList中的每个节点中存储的是实际的数据和前后节点的位置。

插入数据时，ArrayList, LinkedList, Vector谁速度较快？

ArrayList和Vector都是数组实现，但不同的是，Vector是线程安全，加了同步，所以原则上ArrayList比Vector比快； LinkekList是链表实现，增删快，查找慢，所以你要是插入数据时，显然LinkedList是最快的，其次是ArrayList，再者Vector属于遗留容器（Java早期的版本中提供的容器，除此之外，Hashtable、Dictionary、BitSet、Stack、Properties都是遗留容器），已经不推荐使用，但是由于ArrayList和LinkedListed都是非线程安全的，如果遇到多个线程操作同一个容器的场景，则可以通过工具类Collections中的synchronizedList方法将其转换成线程安全的容器后再使用（这是对装潢模式的应用，将已有对象传入另一个类的构造器中创建新的对象来增强实现）。

ArrayList

ArrayList 和 HashMap 的默认大小是多数?

这里要讨论这些常用的默认初始容量和扩容的原因是：

当底层实现涉及到扩容时，容器或重新分配一段更大的连续内存（如果是离散分配则不需要重新分配，离散分配都是插入新元素时动态分配内存），要将容器原来的数据全部复制到新的内存上，这无疑使效率大大降低。

加载因子的系数小于等于1，意指 即当元素个数 超过 容量长度*加载因子的系数 时，进行扩容。另外，扩容也是有默认的倍数的，不同的容器扩容情况不同。

ArrayList、Vector默认初始容量为10。

Vector：线程安全，但速度慢。底层数据结构是数组结构，加载因子为1：即当 元素个数 超过 容量长度 时，进行扩容。扩容增量：原容量的 1倍。如 Vector的容量为10，一次扩容后是容量为20。

ArrayList：线程不安全，查询速度快。底层数据结构是数组结构，扩容增量：原容量的 0.5倍+1，如 ArrayList的容量为10，一次扩容后是容量为16。

Set(集) 元素无序的、不可重复。

HashSet：线程不安全，存取速度快。

底层实现是一个HashMap（保存数据），实现Set接口

默认初始容量为16（为何是16，见下方对HashMap的描述）

加载因子为0.75：即当 元素个数 超过 容量长度的0.75倍 时，进行扩容

扩容增量：原容量的1倍

如 HashSet的容量为16，一次扩容后是容量为32。

Map是一个双列集合

HashMap：默认初始容量为16

（为何是16：16是2^4，可以提高查询效率，另外，32=16<<1 –>至于详细的原因可另行分析，或分析源代码）

加载因子为0.75：即当 元素个数 超过 容量长度的0.75倍 时，进行扩容

扩容增量：原容量的 1倍

如 HashSet的容量为16，一次扩容后是容量为32。

ArrayList 和 Set 的区别？

Set 集合是无序不可以重复的的、List集合是有序可以重复的。

ArrayList是数组存储的方式，HashSet存储会先进行HashCode值得比较(hashcode和equals方法)，若相同就不会再存储。

补充一下：Hashset就是采用哈希算法存取对象的集合，对象用完之后没有回收就是内存泄漏。一个对象一旦hashCode生成之后，再对属性值修改后其Hashcode值就会发生改变，再通过hashSet删除就删除不掉了。

以上的问题还可以继续有如下变形，理解了就能融会贯通：

ArrayList, LinkedList, Vector的区别

ArrayList是如何实现的，ArrayList 和 LinkedList 的区别

ArrayList如何实现扩容

Array 和 ArrayList 有何区别？什么时候更适合用Array？

ArrayList可以算是Array的加强版，（对array有所取舍的加强）。

存储内容比较：

•Array数组可以包含基本类型和对象类型，

•ArrayList却只能包含对象类型。

但是需要注意的是：Array数组在存放的时候一定是同种类型的元素。ArrayList就不一定了，因为ArrayList可以存储Object。

空间大小比较：

• 它的空间大小是固定的，空间不够时也不能再次申请，所以需要事前确定合适的空间大小。

• ArrayList的空间是动态增长的，如果空间不够，它会创建一个空间比原空间大一倍的新数组，然后将所有元素复制到新数组中，接着抛弃旧数组。而且，每次添加新的元素的时候都会检查内部数组的空间是否足够。（比较麻烦的地方）。

方法上的比较： ArrayList作为Array的增强版，当然是在方法上比Array更多样化，比如添加全部addAll()、删除全部removeAll()、返回迭代器iterator()等。

适用场景：

如果想要保存一些在整个程序运行期间都会存在而且不变的数据，我们可以将它们放进一个全局数组里，但是如果我们单纯只是想要以数组的形式保存数据，而不对数据进行增加等操作，只是方便我们进行查找的话，那么，我们就选择ArrayList。而且还有一个地方是必须知道的，就是如果我们需要对元素进行频繁的移动或删除，或者是处理的是超大量的数据，那么，使用ArrayList就真的不是一个好的选择，因为它的效率很低，使用数组进行这样的动作就很麻烦，那么，我们可以考虑选择LinkedList。

Collection集合接口和Map接口有什么关系？
HashMap是线程安全的吗？线程安全的Map都有哪些？性能最好的是哪个？
使用HashMap有什么性能问题吗？
HashMap的数据结构是怎样的？默认大小是多少？内部是怎么扩容的？
怎么按添加顺序存储元素？怎么按A-Z自然顺序存储元素？怎么自定义排序？
HashMap的链表结构设计是用来解决什么问题的？
HashMap的键、值可以为NULL吗？HashTable呢？
HashMap使用对象作为key，如果hashcode相同会怎么处理？
HashMap中的get操作是什么原理？
HashMap 和 HashTable 区别
HashCode 作用，如何重载hashCode方法
ArrayList与LinkList区别与联系
HashMap原理
Hash冲突
并发集合
线程安全集合及实现原理

这几道Java集合框架面试题在面试中几乎必问

18.java 容器都有哪些？

19.Collection 和 Collections 有什么区别？

20.List、Set、Map 之间的区别是什么？

21.HashMap 和 Hashtable 有什么区别？

22.如何决定使用 HashMap 还是 TreeMap？

23.说一下 HashMap 的实现原理？

24.说一下 HashSet 的实现原理？

25.ArrayList 和 LinkedList 的区别是什么？

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

27.ArrayList 和 Vector 的区别是什么？

28.Array 和 ArrayList 有何区别？

29.在 Queue 中 poll()和 remove()有什么区别？

30.哪些集合类是线程安全的？

31.迭代器 Iterator 是什么？

32.Iterator 怎么使用？有什么特点？

33.Iterator 和 ListIterator 有什么区别？

34.怎么确保一个集合不能被修改？

2.HashMap的源码，实现原理，底层结构。

3.说说你知道的几个Java集合类：list、set、queue、map实现类咯。。。

4.描述一下ArrayList和LinkedList各自实现和区别

5.Java中的队列都有哪些，有什么区别。 21.Hash冲突怎么办？哪些解决散列冲突的方法？

22.HashMap冲突很厉害，最差性能，你会怎么解决?从O（n）提升到log（n）咯，用二叉排序树的思路说了一通

19.Hashtable,HashMap,ConcurrentHashMap底层实现原理与线程安全问题（建议熟悉jdk源码，才能从容应答）

23.rehash

24.hashCode()与equals()生成算法、方法怎么重写 2.HashMap的源码，实现原理，底层结构。

3.说说你知道的几个Java集合类：list、set、queue、map实现类咯。。。

4.描述一下ArrayList和LinkedList各自实现和区别

5.Java中的队列都有哪些，有什么区别。 11.hashtable和hashmap的区别

20.如果不让你用JavaJdk提供的工具，你自己实现一个Map，你怎么做。说了好久，说了HashMap源代码，如果我做，就会借鉴HashMap的原理，说了一通HashMap实现