Java基础学习（一）数据结构

yyqblog 2018-11-23 原文

基础问题

1. 几类数据结构的定义和区别是什么？

2. 容器的数据结构底层是怎么实现的？怎么进行扩容？

3. 容器的线程安全怎么实现？

一、List容器

数据有序，允许重复数据，线程不安全。

1. linkedList 底层用双向链表实现，操作速度快，可以在头、尾、[n]操作数据。

2. ArrayList 底层用数组实现，查询速度快，默认数组大小是10。可以通过new ArrayList<Object>(n)设置n的值来指定数组的size，这样可以节省空间并避免数组扩容引起的效率下降。

ArrayList的扩容：当数据大小超过数组大小时，arrayList通过ensureCapacityd 调grow方法进行扩容，以下是jdk 1.8源码

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    //默认扩容量为原size的一半
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
    //最大扩容到Intger.MAX_VALUE
    newCapacity = hugeCapacity(minCapacity);
    // 直接用数组的copy进行扩容
    elementData = Arrays.copyOf(elementData, newCapacity);
}

二、Set容器

set保存的数据不重复，set的底层都是通过其对应的map来实现的，例如HashSet底层是HashMap实现。所以常见Set与其对应的map一样是非线程安全的，但guava里实现了线程安全的ConcurrentHashSet（线程安全原理见下方ConcurrentHashMap）。

1. HashSet() ：快速的定位、读取，会根据hash值来存放，因此读取出来的顺序不是插入的顺序。通常用于数据去重。

Hashset 集合收进一个对象时，会调用对象的hashcode()得到其Hashcode值来决定他的存储位置。默认的hashCode方法，是对对象进行hashCode；默认的equals方法也是比较对象是否相等。所以如果不重写这两个方法的话，下方例子中p1 和p2 都会被保存而不会被去重。

Person p1 = new Person("fan");
Person p2 = new Person("fan");
Set<Person> personHashSet = new HashSet<Person>();
Collections.addAll(personHashSet, p1, p2);

2. TreeSet()：是按照hash值的顺序（红黑树）排列的，如果要把一个对象添加进TreeSet时，则该对象的类必须实现Comparable接口。通常用于去重+排序。

例，下方Person类没实现Comparable，添加时会报错“Person cannot be cast to java.lang.Comparable”

Person p1= new Person("小明");
Person p2= new Person("小花");
TreeSet<Person> personTreeSet = new TreeSet<>();
personTreeSet.add(p1);
personTreeSet.add(p2);

3. LinkedHashSet()：按照插入顺序保存数据。用于去重+保留插入顺序。

三、Map容器

map存储 key-value形式数据，

1. HashMap 由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的。

2. TreeMap

3.ConcurrentHashMap

hashmap什么时候扩容？怎么扩容？

A put到hashMap里

改下A的值再push到map里会发生什么？

concurrent分段锁 get不加锁写是加锁 1.8怎么实现的？

实现hashmap扩容和基础数据结构。 while循环比线程唤醒时间段

与模16