Java基础学习(一)数据结构

基础问题 

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

 

Q和stack的实现原理?

实现一个BlockingQ。new一个线程池

实现一个线程池

list扩容要多久