Home 集合框架

为什么?为什么?
是为了提高效率,采取重写hashcode方法,先进行hashcode比较,如果不同,那么就没必要在进行equals的比较了,这样就大大减少了equals比较的次数,这对比需要比较的数量很大的效率提高是很明显的,一个很好的例子就是在集合中的使用;

我们都知道java中的List集合是有序的,因此是可以重复的,而set集合是无序的,因此是不能重复的,那么怎么能保证不能被放入重复的元素呢,但靠equals方法一样比较的话,如果原来集合中以后又10000个元素了,那么放入10001个元素,难道要将前面的所有元素都进行比较,看看是否有重复,欧码噶的,这个效率可想而知,因此hashcode就应遇而生了,java就采用了hash表,利用哈希算法(也叫散列算法),就是将对象数据根据该对象的特征使用特定的算法将其定义到一个地址上,那么在后面定义进来的数据只要看对应的hashcode地址上是否有值,那么就用equals比较,如果没有则直接插入,只要就大大减少了equals的使用次数,执行效率就大大提高了。

同事也是为了保证同一个对象,保证在equals相同的情况下hashcode值必定相同,如果重写了equals而未重写hashcode方法,可能就会出现两个没有关系的对象equals相同的(因为equal都是根据对象的特征进行重写的),但hashcode确实不相同的。
总结来说就是两点
1.使用hashcode方法提前校验,可以避免每一次比对都调用equals方法,提高效率
2.保证是同一个对象,如果重写了equals方法,而没有重写hashcode方法,会出现equals相等的对象,hashcode不相等的情况,重写hashcode方法就是为了避免这种情况的出现。

只是用文字来表示太空洞,我们直接上代码,
创建一个Personsa类
public class Personsa { private String name; public int age;  public Personsa(String name, int age) { super(); this.name = name; this.age = age; }  public String getName() { return name; }  public void setName(String name) { this.name = name; }  public int getAge() { return age; }  public void setAge(int age) { this.age = age; }}
然后写个测试类
import java.util.HashSet;import java.util.Set; public class HashCodeTest { public static void main(String[] args) { Personsa person1 = new Personsa(“wulinfei”,1); Personsa person2 = new Personsa(“wulinfei”,1); System.out.println(“stu:” + person1.equals(person2)); Set<Personsa> set = new HashSet<>(); set.add(person1); System.out.println(“s1 hashCode:” + person1.hashCode()); System.out.println(“add s1 size:” + set.size()); set.add(person2); System.out.println(“s2 hashCode:” + person2.hashCode()); System.out.println(“add s2 size::” + set.size()); }}运行测试类,可以看出来,两个对象是不相同,所以返回false

 

然后我们在重写Personsa类中重写equals方法,这个时候就是只需要name属性相同,equals方法就会返回true

 

重写equals方法之后,我们修改下age属性

 

然后运行测试类

 

然后我们把equals方法去掉,只重写hashcode方法,运行结果:hashcode值一样,但是返回值是false。

 

然后我们在同时重写hashcode和equals方法,可以看到返回值是true,同时,hashcode值也是相等的。

 

结合上面引用的案例,可以类推,hash类存储结构(HashSet、HashMap等等)添加元素会有重复性校验,校验的方式就是先取hashCode判断是否相等(找到对应的位置,该位置可能存在多个元素),然后再取equals方法比较(极大缩小比较范围,高效判断),最终判定该存储结构中是否有重复元素。
小总结:
hashCode主要用于提升查询效率,来确定在散列结构中对象的存储地址;

重写equals()必须重写hashCode(),二者参与计算的自身属性字段应该相同;

hash类型的存储结构,添加元素重复性校验的标准就是先取hashCode值,后判断equals();

equals()相等的两个对象,hashcode()一定相等;

反过来:hashcode()不等,一定能推出equals()也不等;

hashcode()相等,equals()可能相等,也可能不等。(哈希冲突)

————————————————

版权声明:本文为CSDN博主「这辈子_安静的努力着」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。原文链接:https://blog.csdn.net/qq_35868412/article/details/89380409

接着上一篇博客,上一篇博客说明了HashMap的初始容量都是2的n次幂的形式存在的,而扩容也是2倍的原来的容量进行扩容,也就是扩容后的容量也是2的n次幂的形式存在的,下面就来说明一下为什么是2的n次幂的形式!

先来看一下源码,也就是向HashMap中添加元素,或者扩容时是怎么存放元素的。

 

第一个截图是向HashMap中添加元素putVal()方法的部分源码,可以看出,向集合中添加元素时,会使用(n – 1) & hash的计算方法来得出该元素在集合中的位置;而第二个截图是HashMap扩容时调用resize()方法中的部分源码,可以看出会新建一个tab,然后遍历旧的tab,将旧的元素进过e.hash & (newCap – 1)的计算添加进新的tab中,也就是(n – 1) & hash的计算方法,其中n是集合的容量,hash是添加的元素进过hash函数计算出来的hash值。

HashMap的容量为什么是2的n次幂,和这个(n – 1) & hash的计算方法有着千丝万缕的关系,符号&是按位与的计算,这是位运算,计算机能直接运算,特别高效,按位与&的计算方法是,只有当对应位置的数据都为1时,运算结果也为1,当HashMap的容量是2的n次幂时,(n-1)的2进制也就是1111111***111这样形式的,这样与添加元素的hash值进行位运算时,能够充分的散列,使得添加的元素均匀分布在HashMap的每个位置上,减少hash碰撞,面举例进行说明。

当HashMap的容量是16时,它的二进制是10000,(n-1)的二进制是01111,与hash值得计算结果如下:

上面四种情况我们可以看出,不同的hash值,和(n-1)进行位运算后,能够得出不同的值,使得添加的元素能够均匀分布在集合中不同的位置上,避免hash碰撞。

下面就来看一下HashMap的容量不是2的n次幂的情况,当容量为10时,二进制为01010,(n-1)的二进制是01001,向里面添加同样的元素,结果为:

可以看出,有三个不同的元素进过&运算得出了同样的结果,严重的hash碰撞了。

终上所述,HashMap计算添加元素的位置时,使用的位运算,这是特别高效的运算;另外,HashMap的初始容量是2的n次幂,扩容也是2倍的形式进行扩容,是因为容量是2的n次幂,可以使得添加的元素均匀分布在HashMap中的数组上,减少hash碰撞,避免形成链表的结构,使得查询效率降低!
————————————————
版权声明:本文为CSDN博主「猿人小郑」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/apeopl/article/details/88935422

前言

今天介绍一下Java的两个集合类,ArrayList和LinkedList,这两个集合的知识点几乎可以说面试必问的。

对于这两个集合类,相信大家都不陌生,ArrayList可以说是日常开发中用的最多的工具类了,也是面试中几乎必问的,LinkedList可能用的少点,但大多数的面试也会有所涉及,尤其是关于这两者的比较可以说是家常便饭,所以,无论从使用上还是在面试的准备上,对于这两个类的知识点我们都要有足够的了解。

ArrayList

ArrayList是List接口的一个实现类,底层是基于数组实现的存储结构,可以用于装载数据,数据都是存放到一个数组变量中,

transient Object[] elementData;

transient是一个关键字,它的作用可以总结为一句话:将不需要序列化的属性前添加关键字transient,序列化对象的时候,这个属性就不会被序列化。 你可能会觉得奇怪,ArrayList可以被序列化的啊,源码可是实现了java.io.Serializable接口啊,为什么数组变量还要用transient定义呢?

别急,关于这个问题,我们后面会讨论到,不卖个关子,你们怎么会看到最后,然后给我点在看呢?

当我们新建一个实例时,ArrayList会默认帮我们初始化数组的大小为10(补充:1.8之后,新建实例并没有初始化为10。只有通过无参构造,添加第一个元素的时候才会扩容到10。)

/**
 * Default initial capacity.
 */
private static final int DEFAULT_CAPACITY = 10;

但请注意,这个只是数组的容量大小,并不是List真正的大小,List的大小应该由存储数据的数量决定,在源码中,获取真实的容量其实是用一个变量size来表示,

private int size;

在源码中,数据默认是从数组的第一个索引开始存储的,当我们添加数据时,ArrayList会把数据填充到上一个索引的后面去,所以,ArrayList的数据都是有序排列的。而且,由于ArrayList本身是基于数组存储,所以查询的时候只需要根据索引下标就可以找到对于的元素,查询性能非常的高,这也是我们非常青睐ArrayList的最重要的原因。

但是,数组的容量是确定的啊,如果要存储的数据大小超过了数组大小,那不就有数组越界的问题?

关于这点,我们不用担心,ArrayList帮我们做了动态扩容的处理,如果发现新增数据后,List的大小已经超过数组的容量的话,就会新增一个为原来1.5倍容量的新数组,然后把原数组的数据原封不动的复制到新数组中,再把新数组赋值给原来的数组对象就完成了。

扩容之后,数组的容量足够了,就可以正常新增数据了。

除此之外,ArrayList提供支持指定index新增的方法,就是可以把数据插入到设定的索引下标,比如说我想把元素4插入到3后面的位置,也就是现在5所在的地方,

插入数据的时候,ArrayList的操作是先把3后面的数组全部复制一遍,然后将这部分数据往后移动一位,其实就是逐个赋值给后移一位的索引位置,然后3后面就可以空出一个位置,把4放入就完成了插入数据的操作了

删除的时候也是一样,指定index,然后把后面的数据拷贝一份,并且向前移动,这样原来index位置的数据就删除了。

到这里我们也不难发现,这种基于数组的查询虽然高效,但增删数据的时候却很耗性能,因为每增删一个元素就要移动对应index后面的所有元素,数据量少点还无所谓,但如果存储上千上万的数据就很吃力了,所以,如果是频繁增删的情况,不建议用ArrayList。

既然ArrayList不建议用的话,这种情况下有没有其他的集合可用呢?

当然有啊,像我这样的暖男肯定是第一时间告诉你们的,这就引出了我们下面要说的LinkedList

LinkedList

LinkedList 是基于双向链表实现的,不需要指定初始容量,链表中任何一个存储单元都可以通过向前或者向后的指针获取到前面或者后面的存储单元。在 LinkedList 的源码中,其存储单元用一个Node类表示:

private static class Node<E> {
    E item;
    Node<E> next;       
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

Node中包含了三个成员,分别是存储数据的item,指向前一个存储单元的点 prev 和指向后一个存储单元的节点 next ,通过这两个节点就可以关联前后的节点,组装成为链表的结构,

因为有保存前后节点的地址,LinkedList增删数据的时候不需要像ArrayList那样移动整片的数据,只需要通过引用指定index位置前后的两个节点即可,比如我们要在李白和韩信之间插入孙悟空的节点,只需要像这样处理下节点之间的指向地址:

删除数据也是同样原理,只需要改变index位置前后两个节点的指向地址即可。

这样的链表结构使得LinkedList能非常高效的增删数据,在频繁增删的情景下能很好的使用,但不足之处也是有的。

虽然增删数据很快,但查询就不怎么样了,LinkedList是基于双向链表存储的,当查询对应index位置的数据时,会先计算链表总长度一半的值,判读index是在这个值的左边还是右边,然后决定从头结点还是从尾结点开始遍历,

Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

虽然根据index位置做了查询优化,但依然会有遍历一半链表长度的情况,如果是数据量非常多的话,这样的查询无疑是非常慢的。

这也是LinkedList最无奈的地方,鱼和熊掌不可兼得,我们既想查的快,又想增删快,这样的好事怎么可能都让我们遇到呢?所以,一般建议LinkedList使用于增删多,查询少的情景。

除此之外,LinkedList对内存的占用也是比较大的,毕竟每个Node都维护着前后指向地址的节点,数据量大的话会占用不少内存空间。

两者哪个更占空间?

讲到这,你是不是对标题的那个问题成竹在胸了?

下次有面试官问你,ArrayList和LinkedList哪个更占空间时,你就可以信誓旦旦的说,LinkedList更占空间,我看了薛大佬的文章,肯定不会错。说完你就可以安心坐着,等待面试官露出满意的笑容,告诉你通过面试的消息,成功拿下offer指日可待。

如果你真的这么答的话,我也相信面试官一定会被你的回答所征服,他听完一定会点点头,嘴角开始上扬,然后笑容满面的告诉你,

感谢你今天过来面试,你可以回去等通知了。。。。

哈哈,开个玩笑,不凑多点字可不是我的风格。

言归正传,表面上看,LinkedList的Node存储结构似乎更占空间,但别忘了前面介绍ArrayList扩容的时候,它会默认把数组的容量扩大到原来的1.5倍的,如果你只添加一个元素的话,那么会有将近原来一半大小的数组空间被浪费了,如果原先数组很大的话,那么这部分空间的浪费也是不少的,

所以,如果数据量很大又在实时添加数据的情况下,ArrayList占用的空间不一定会比LinkedList空间小,这样的回答就显得谨慎些了,听上去也更加让人容易认同,但你以为这样回答就完美了吗?非也

还记得我前面说的那个transient变量吗?它的作用已经说了,不想序列化的对象就可以用它来修饰,用transient修饰elementData意味着我不希望elementData数组被序列化。为什么要这么做呢?

这是因为序列化ArrayList的时候,ArrayList里面的elementData,也就是数组未必是满的,比方说elementData有10的大小,但是我只用了其中的3个,那么是否有必要序列化整个elementData呢? 显然没有这个必要,因此ArrayList中重写了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 size as capacity for behavioural compatibility with clone()
    s.writeInt(size);

    // 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这个数组对象不去序列化它,而是遍历elementData,只序列化数组里面有数据的元素这样一来,就可以加快序列化的速度,还能够减少空间的开销。

加上这个知识点后,我们对上面那个问题就可以有更加全面的回答了,如果你下次也遇到这个问题的话,你可以参考一下我的说法:

一般情况下,LinkedList的占用空间更大,因为每个节点要维护指向前后地址的两个节点,但也不是绝对,如果刚好数据量超过ArrayList默认的临时值时,ArrayList占用的空间也是不小的,因为扩容的原因会浪费将近原来数组一半的容量,不过,因为ArrayList的数组变量是用transient关键字修饰的,如果集合本身需要做序列化操作的话,ArrayList这部分多余的空间不会被序列化。

怎么样,这样的回答是不是更加的说服力,不仅更加全面,还可能会给面试官留下好印象,让他觉得你是个有自己思考的求职者,说不定当场就让你面试通过了呢。就冲这点,你们是不是应该给我点个赞啊,哈哈。