03.Java数据结构问题

目录介绍

• 3.0.0.1 在arrayList中System.arraycopy()和Arrays.copyOf()方法区别联系？System.arraycopy()和Arrays.copyOf()代码说明？
• 3.0.0.2 SparseArray基本介绍，相比HashMap为什么性能会好？
• 3.0.0.3 Arrays和Collections 对于sort的不同实现原理？说一说它们的区别……
• 3.0.0.4 Java集合框架中有哪些类？都有什么特点？Java集合的快速失败机制 “fail-fast”？
• 3.0.0.5 ArrayList，Vector和LinkList的区别，底层分别是怎么实现的，存储空间是如何扩容的？什么是加载因子？
• 3.0.0.6 如何理解ArrayList的扩容消耗？Arrays.asList方法后的List可以扩容吗？ArrayList如何序列化？
• 3.0.0.7 如何理解list集合读写机制和读写效率？什么是CopyOnWriteArrayList，它与ArrayList有何不同？
• 3.0.1.0 HashSet和TreeSet的区别？是如何保证唯一值的，底层怎么做到的？
• 3.0.1.5 HashMap和Hashtable的区别？HashMap在put、get元素的过程？体现了什么数据结构？
• 3.0.1.6 如何保证HashMap线程安全？底层怎么实现的？HashMap是有序的吗？如何实现有序？
• 3.0.1.7 HashMap存储两个对象的hashcode相同会发生什么？如果两个键的hashcode相同，你如何获取值对象？
• 3.0.1.8 HashMap为什么不直接使用hashCode()处理后的哈希值直接作为table的下标？
• 3.0.1.9 为什么HashMap中String、Integer这样的包装类适合作为K？为啥不用其他作key值？
• 3.0.2.0 HashMap是如何扩容的？如何理解HashMap的大小超过了负载因子定义的容量？重新调整HashMap大小存在什么问题吗？

好消息

• 博客笔记大汇总【15年10月到至今】，包括Java基础及深入知识点，Android技术博客，Python学习笔记等等，还包括平时开发中遇到的bug汇总，当然也在工作之余收集了大量的面试题，长期更新维护并且修正，持续完善……开源的文件是markdown格式的！同时也开源了生活博客，从12年起，积累共计500篇[近100万字]，将会陆续发表到网上，转载请注明出处，谢谢！
• 链接地址：https://github.com/yangchong211/YCBlogs
• 如果觉得好，可以star一下，谢谢！当然也欢迎提出建议，万事起于忽微，量变引起质变！所有博客将陆续开源到GitHub！

3.0.0.1 在arrayList中System.arraycopy()和Arrays.copyOf()方法区别联系？System.arraycopy()和Arrays.copyOf()代码说明？

• System.arraycopy()和Arrays.copyOf()方法区别？
  • 比如下面add(int index, E element)方法就很巧妙的用到了arraycopy()方法让数组自己复制自己实现让index开始之后的所有成员后移一个位置:

    /**
     * 在此列表中的指定位置插入指定的元素。 
     * 先调用 rangeCheckForAdd 对index进行界限检查；然后调用 ensureCapacityInternal 方法保证capacity足够大；
     * 再将从index开始之后的所有成员后移一个位置；将element插入index位置；最后size加1。
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index);
        ensureCapacityInternal(size + 1); 
        //arraycopy()方法实现数组自己复制自己
        //elementData:源数组;index:源数组中的起始位置;elementData：目标数组；index + 1：目标数组中的起始位置； size - index：要复制的数组元素的数量；
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        elementData[index] = element;
        size++;
    }

  • 如toArray()方法中用到了copyOf()方法

    /**
     *以正确的顺序（从第一个到最后一个元素）返回一个包含此列表中所有元素的数组。 
     *返回的数组将是“安全的”，因为该列表不保留对它的引用。 （换句话说，这个方法必须分配一个新的数组）。
     *因此，调用者可以自由地修改返回的数组。 此方法充当基于阵列和基于集合的API之间的桥梁。
     */
    public Object[] toArray() {
    //elementData：要复制的数组；size：要复制的长度
        return Arrays.copyOf(elementData, size);
    }

  • 两者联系与区别
    • 看了上面的两者源代码可以发现copyOf()内部调用了System.arraycopy()方法
    • 技术博客大总结
    • 区别：
      • 1.arraycopy()需要目标数组，将原数组拷贝到你自己定义的数组里，而且可以选择拷贝的起点和长度以及放入新数组中的位置
      • 2.copyOf()是系统自动在内部新建一个数组，并返回该数组。

• System.arraycopy()和Arrays.copyOf()代码说明？

  

  创新互联坚持“要么做到，要么别承诺”的工作理念，服务领域包括：成都网站制作、成都网站建设、企业官网、英文网站、手机端网站、网站推广等服务，满足客户于互联网时代的馆陶网站设计、移动媒体设计的需求，帮助企业找到有效的互联网解决方案。努力成为您成熟可靠的网络建设合作伙伴！

  • 使用System.arraycopy()方法

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] a = new int[10];
        a[0] = 0;
        a[1] = 1;
        a[2] = 2;
        a[3] = 3;
        System.arraycopy(a, 2, a, 3, 3);
        a[2]=99;
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }
    
    //结果：
    //0 1 99 2 3 0 0 0 0 0 

  • 使用Arrays.copyOf()方法。技术博客大总结

    public static void main(String[] args) {
        int[] a = new int[3];
        a[0] = 0;
        a[1] = 1;
        a[2] = 2;
        int[] b = Arrays.copyOf(a, 10);
        System.out.println("b.length"+b.length);
        //结果：
        //10
    }

  • 得出结论
    • arraycopy() 需要目标数组，将原数组拷贝到你自己定义的数组里或者原数组，而且可以选择拷贝的起点和长度以及放入新数组中的位置 copyOf() 是系统自动在内部新建一个数组，并返回该数组。

3.0.0.2 SparseArray基本介绍，相比HashMap为什么性能会好？

• 位于android.util，Android 中的数据结构，针对移动端做了优化，在数据量比较少的情况下，性能会好过 HashMap，类似于 HashMap，key:int ,value:object 。
• 1.key 和 value 采用数组进行存储。存储 key 的数组是 int 类型，不需要进行装箱操作。提供了速度。
• 2.采用二分查找法，在插入进行了排序，所以两个数组是按照从小到大进行排序的。
• 3.在查找的时候，进行二分查找，数据量少的情况下，速度比较快。

3.0.0.3 Arrays和Collections 对于sort的不同实现原理？说一说它们的区别……

• 1、Arrays.sort()
  • 该算法是一个经过调优的快速排序，此算法在很多数据集上提供N*log(N)的性能，这导致其他快速排序会降低二次型性能。
• 2、Collections.sort()
  • 该算法是一个经过修改的合并排序算法（其中，如果低子列表中的最高元素效益高子列表中的最低元素，则忽略合并）。此算法可提供保证的N*log(N)的性能，此实现将指定列表转储到一个数组中，然后再对数组进行排序，在重置数组中相应位置处每个元素的列表上进行迭代。
• 它们的区别
  • 技术博客大总结

3.0.0.4 Java集合框架中有哪些类？都有什么特点？Java集合的快速失败机制 “fail-fast”？

• 可将Java集合框架大致可分为Set、List、Queue 和Map四种体系
  • Set：代表无序、不可重复的集合，常见的类如HashSet、TreeSet
  • List：代表有序、可重复的集合，常见的类如动态数组ArrayList、双向链表LinkedList、可变数组Vector
  • Map：代表具有映射关系的集合，常见的类如HashMap、LinkedHashMap、TreeMap
  • Queue：代表一种队列集合
• Java集合的快速失败机制 “fail-fast”
  • 技术博客大总结
  • java集合的一种错误检测机制，当多个线程对集合进行结构上的改变的操作时，有可能会产生 fail-fast 机制。
    • 例如：假设存在两个线程（线程1、线程2），线程1通过Iterator在遍历集合A中的元素，在某个时候线程2修改了集合A的结构（是结构上面的修改，而不是简单的修改集合元素的内容），那么这个时候程序就会抛出 ConcurrentModificationException 异常，从而产生fail-fast机制。
  • 原因：
    • 迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化，就会改变modCount的值。每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历。
  • 解决办法：
    • 1.在遍历过程中，所有涉及到改变modCount值得地方全部加上synchronized。
    • 2.使用CopyOnWriteArrayList来替换ArrayList

3.0.0.5 ArrayList，Vector和LinkList的区别，底层分别是怎么实现的？存储空间是如何扩容的？什么是加载因子？

• ArrayList
  • ArrayList的底层结构是数组，可用索引实现快速查找；是动态数组，相比于数组容量可实现动态增长。
  • ArrayList非线程安全，建议在单线程中才使用ArrayList，而在多线程中可以选择Vector或者CopyOnWriteArrayList；默认初始容量为10，每次扩容为原来的1.5倍
• Vector
  • 和ArrayList几乎是一样的，Vector使用了synchronized关键字，是线程安全的，比ArrayList开销更大，访问更慢；默认初始容量为10，默认每次扩容为原来的2倍，可通过capacityIncrement属性设置
• LinkList
  • LinkedList底层结构是链表，增删速度快；是一个双向循环链表，也可以被当作堆栈、队列或双端队列

3.0.0.6 如何理解ArrayList的扩容消耗？Arrays.asList方法后的List可以扩容吗？ArrayList如何序列化？

• 如何理解ArrayList的扩容消耗
  • 由于ArrayList使用elementData = Arrays.copyOf(elementData, newCapacity);进行扩容，而每次都会重新创建一个newLength长度的数组，所以扩容的空间复杂度为O(n),时间复杂度为O(n)

    public static  T[] copyOf(U[] original, int newLength, Class newType) {
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
    }

• Arrays.asList方法后的List可以扩容吗？
  • 不能，asList返回的List为只读的。其原因为：asList方法返回的ArrayList是Arrays的一个内部类，并且没有实现add，remove等操作
• List怎么实现排序？
  • 实现排序，可以使用自定义排序：list.sort(new Comparator(){...})
  • 或者使用Collections进行快速排序：Collections.sort(list)

• ArrayList如何序列化？

  • ArrayList 基于数组实现，并且具有动态扩容特性，因此保存元素的数组不一定都会被使用，那么就没必要全部进行序列化。
  • 技术博客大总结
  • 保存元素的数组 elementData 使用 transient 修饰，该关键字声明数组默认不会被序列化。

    transient Object[] elementData; // non-private to simplify nested class access

  • ArrayList 实现了 writeObject() 和 readObject() 来控制只序列化数组中有元素填充那部分内容。

    
    private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    elementData = EMPTY_ELEMENTDATA;
    s.defaultReadObject();
    s.readInt(); // ignored
    if (size > 0) {
        ensureCapacityInternal(size);
        Object[] a = elementData;
        for (int i=0; i

  private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
int expectedModCount = modCount;
s.defaultWriteObject();
s.writeInt(size);
for (int i=0; is.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}

  - 序列化时需要使用 ObjectOutputStream 的 writeObject() 将对象转换为字节流并输出。而 writeObject() 方法在传入的对象存在 writeObject() 的时候会去反射调用该对象的 writeObject() 来实现序列化。反序列化使用的是 ObjectInputStream 的 readObject() 方法，原理类似。

  ArrayList list = new ArrayList();
ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream(file));
oos.writeObject(list);

3.0.0.7 如何理解list集合读写机制和读写效率？什么是CopyOnWriteArrayList，它与ArrayList有何不同？