java面试—(List和Set)(ArrayList和LinkedList)(hashCode和equals)(HashMap和HashTable)

List和Set的区别

List和Set的区别哔哩哔哩

  1. List有序可以重复,按对象进入的顺序来保存对象,允许多个null元素对象,可以使用Iterator取出所有元素,在逐一遍历,还可以使用get(int index)获取指定下标的元素。
  2. Set无序不可重复,最多允许一个null元素对象,取元素时只能用Iterator接口取得所有元素,在逐一遍历各个元素。

hashCode 与 equals

hashCode 与 equals哔哩哔哩

equals

equals是Object类中的方法,Object中的equals方法就直接使用的双等号“==”作比较,如果没有进行重写,那么euqals和双等号其实是一样的,但是API中的类大部分都重写了equals方法,使得equals比较的的是具体的内容,(八种基本数据类型、String类,Date类等等都重写了,只有一部分不需要使用equals方法的没有重写),对于自己的编写的类,自己没有重写的话就是继承Object中的equals方法。

所以,一般说==和equals的比较方式不同指的是重写后的equals不同

hashCode介绍

hashCode()作用是获取哈希码,也称为散列码,他实际上是返回一个int整数,这个哈希码的作用是确定该对象在哈希表中的索引位置。hashCode()定义在JDK的Object.java中,也就是说Java中的任何类都包含有hashCode()函数。散列表存储的是键值对(key-vaule),它的特点是:能根据“键”快速的检索出对应的“值”。这其中就利用了散列码,总的来说就是通过hashCode可以快速找到所需要的对象

为什么要有hasCode,以HashSet如何检索重复的例子来说明

对象加入HashSet时,会先计算对象的hashCode值来判断对象加入的位置,看该位置是否有值,如果没有,那说明HashSet中没有重复对象,可以直接存入,如果发现hashCode判断的位置存在值,那说明HashSet中可能存在与将要放入的对象相同的对象(相同的对象得出的hashCode肯定相同,对于不同的两个对象得出的hashCode值也有可能是相同的),这时可以通过调用eqals()方法来检查两个对象是否真的相同,如果相同就是重复了不会让其加入,如果不同的话,就会重新散列到其他位置,这样就大大减少了equals的次数,相应就大大提高了执行速度。

如果仅仅是通过equals方法去遍历对比HashSet中的对象,这样显然会大大降低系统的性能。


  • 如果两个对象相等,则hashCode一定相同
  • 两个对象相等,通过equals判断两个对象一定返回true
  • 两个对象的hashCode值相同,他们不一定是相等的
  • 因此equals方法被调用时,hashCode方法必定调用过且hashCode值相等
  • hashCode()默认认为对堆上的对象产生独特值,如果没有重写hashCode(),这该类的两个实例对象无论如何都不会相等,即使这两个对象指向相同的数据。

ArrayList和LinkedList的区别(高频)

ArrayList和LinkedList的区别bilibili

ArrayList:

基于动态数组,连续内存存储,适合下标访问(随机访问)

扩容机制:超出数组的长度后,会根据一定的算法,新建一个更长的数组,将原来的数组的值全部拷贝到新的数组中,同时也将超出下标的数据插入新建数组中。这里扩容存在大量消耗

ArrayList插入数据时,如果不是尾部插入,那就还涉及到数组数据的移动,如果有大量数据需要移动就会造成大量的消耗,而LInkedList则通过改变每个节点指向来插入数据,不涉及数据的移动,相对来说消耗更小

如果我们使用ArrayList时,能很好的把握将要存放数据的大小,指定一个足够使用的初始容量,并且插入时使用尾插法,这样就基本没有扩容消耗和数据移动的消耗,系统性能就可以得到很大的提升,甚至能超过LinkedList(LinkedList存在大量node对象创建消耗),所以在判定ArrayList和LinkedList的性能时要分情况


LinkedList:

就链表,可以存储在分散的内存中,适合做数据插入及删除操作,不适合查询,查询时要逐一遍历,遍历LinkedList必须使用Iterator,非常不建议使用for循环,因为每次for循环体内通过get(int index)取得某一元素时都要对它重新进行遍历,性能消耗极大。

另外不要试图使用indexOf等返回元素所以,并利用其进行遍历,使得indexOf(Object obj)对list进行遍历,当结果为空时会遍历这个列表(如果某个元素不存在LinkedList中,要遍历这个list才能知道这个元素不存在)。


HashMap和HashTable的区别?底层实现是什么?

HashMap和HashTable哔哩哔哩

区别:

1.HashMap和HashTable中的方法和功能其实都是差不多的,最主要的区别是HashTable中的每个方法都是使用synchronized修饰的,HashTable是线程安全的,而HashMap是线程不安全的。由于保证线程安全,HashTable的效率很低。

2.HashMap允许Key和value为null(只能存在一个key为null),而HashTable不允许。

底层实现:数组+链表

JDK8开始链表高度达到8,数组长度超过64时,会将链表转化成红黑树,元素内部以Node节点存在。

  • 第一次put时进行初始化,根据设定的数组长度计算数组应该取多长(tableSizeFor()方法会将计算出数组长度,一定是2的N次方的一个数据)

java面试—(List和Set)(ArrayList和LinkedList)(hashCode和equals)(HashMap和HashTable)

  • 初始化后,计算key 的hash值,通过hash值与数组长度取模,找到数组的下标。

  • 如果没有产生hash冲突(下标处没有元素),直接创建一个Node存入数据。

  • 如果产生hash冲突,当前key与数组下标处的所有节点key进行equals比较。当key相同在比较vaule,value不同就覆盖,相同就丢弃;当key不存相同时,就在这个桶中接着创建新的Node存储数据。

  • 链表长度达到8,数组长度达到64,链表转化成红黑树,链表长度低于6,红黑树转回链表。

  • HashMap中有一个int类型的binCount,没对HaspMap的结构修改一次,binCount就增加一。

  • key为null时,存在数组下标为0的位置。

  • 扩容时,要创建新的更大的数组,数组的长度同样是2的N次的一个数据,扩容后要将原来的数据放到新的数组中(不是简单的下标对应放进去,而是通过算法计算(hash值与新数组长度取模)得到的数组下标的位置…)的长度同样是2的N次的一个数据,扩容后要将原来的数据放到新的数组中(不是简单的下标对应放进去,而是通过算法计算(hash值与新数组长度取模)得到的数组下标的位置…)

上一篇:Set小测


下一篇:【秋招冲刺-面试题每日五道】java集合篇