Java 基础 16 集合（ArrayList、LinkedList，linux 操作系统教程电子版

transient Object[] elementData;

数组初始长度是多少？10

private static final int DEFAULT_CAPACITY = 10;

ArrayList 是如何动态扩容的？如果数据的个数超过原来的容量，就将容量扩展为原来的 1.5 倍，然后复制数据到新数组中。

private void grow(int minCapacity) {

// overflow-conscious code

int oldCapacity = elementData.length;

int newCapacity = oldCapacity + (oldCapacity >> 1); //扩容 1.5 倍

if (newCapacity - minCapacity < 0)

newCapacity = minCapacity;

if (newCapacity - MAX_ARRAY_SIZE > 0)

newCapacity = hugeCapacity(minCapacity);

// minCapacity is usually close to size, so this is a win:

elementData = Arrays.copyOf(elementData, newCapacity); //复制数据到新数组中

}

[](

)Vector 集合

Vector 集合与 ArrayList 相似：

1. 数据结构都是一维数组

2. 方法完全相同

不同点：

1. ArrayList 是非线程安全，Vector 是线程安全

2. ArrayList 性能更高

[](

)泛型集合

==================================================================

下面代码可能出现什么问题?

List list = new ArrayList();

list.add(100);

list.add("123");

int n = (int)list.get(1); //存在类型转换的错误

String s = (String)list.get(0); //存在类型转换的错误

非泛型的集合，添加数据的类型没有限制，在取出数据进行类型转换时，存在类型不兼容的问题。

使用泛型集合，就能解决这个问题。

创建方法：

ArrayList<类型> arrayList = new ArrayList<类型>();

例如：

ArrayList<String> arrayList = new ArrayList<String>();

ArrayList<Integer> arrayList = new ArrayList<Integer>();

后面的类型可以省略

ArrayList<Integer> arrayList = new ArrayList<>();

优点：

1. 只能添加一种类型的数据，不容易出错

2. 不用类型转换，提升性能

ArrayList<Person> arrList = new ArrayList<Person>();

arrList.add(new Person("张三",20));

arrList.add(new Person("张大三",21));

arrList.add(new Person("张小三",23));

arrList.add(new Person("张三三",26));

arrList.add(100); //编译错误，不允许添加其他类型

//读取 Person 对象

Person person = arrList.get(3);

person.hello();

//删除

arrList.remove(0);

//遍历

for(Person per : arrList){

per.hello();

}

[](

)LinkedList

LinkedList 的数据结构是：

双向链表

LinkedList 的优缺点：

• 优点：删除和插入速度快，只需要修改前后的指向，不需要移动数据

• 缺点：访问速度慢，需要依次向前向后，效率低。

LinkedList 的方法

| 方法 | 介绍 |

| --- | --- |

| void addFirst(Object obj) | 在第一个位置上添加对象 |

| void addLast(Object obj) | 在最后位置上添加对象 |

| Object removeFirst() | 删除第一个位置上的对象 |

| Object removeLast() | 删除最后位置上的对象 |

| Object getFirst() | 获得第一个位置的对象 |

| Object getLast() | 获得最后位置的对象 |

| void push(Object obj) | 入栈，先进后出 |

| Object pop() | 出栈，先进后出 |

LinkedList 源码探究

//内部类，保存数据和前后指针

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;

}

}

插入元素

//在 succ 节点前，插入新节点

void linkBefore(E e, Node<E> succ) {

final Node<E> pred = succ.prev; //succ 前一个节点

//创建新节点，prev 指向 succ 前面节点，next 指向 succ

final Node<E> newNode = new Node<>(pred, e, succ);

succ.prev = newNode; //succ 的 prev 指向新节点

if (pred == null)

first = newNode; //前面没有节点，新节点就是首节点

else

pred.next = newNode; //否则 succ 前面节点的 next 指向新节点

size++; //数量加 1

modCount++;

}

插入元素

//删除 x 节点

E unlink(Node<E> x) {

final E element = x.item;

final Node<E> next = x.next;

final Node<E> prev = x.prev;

if (prev == null) { //x 前面节点的 next 指向 x 节点的后面节点

first = next;

} else {

prev.next = next;

x.prev = null;

}

if (next == null) { //x 后面节点的 prev 指向 x 节点的前面节点

last = prev;

} else {

next.prev = prev;

x.next = null;

}

x.item = null;

size--;

modCount++;

return element;

}

[](

)Set 接口

===================================================================

Set 不能添加重复的数据，里面的数据也不能单独访问

Set 接口的常用实现类有：

• HashSet 无序的 Set

• TreeSet 会自动排序的 Set

• LinkedHashSet 可以保留添加顺序的 Set

[](

)HashSet

无序，以哈希算法计算保存位置

添加到集合中的数据必须实现 hashCode 和 equals 方法

底层实现是 HashMap，数据都是存到 HashMap 的键中

public class HashSet<E> extends AbstractSet<E>

{

private transient HashMap<E,Object> map;

private static final Object PRESENT = new Object();

public HashSet() {

map = new HashMap<>();

}

public boolean add(E e) {

return map.put(e, PRESENT)==null;

}

...

}

[](

)Map 接口

===================================================================

键值对结构存取数据，查找方便而且高效

常用方法：

| 方法 | 介绍 |

| --- | --- |

| V put(K key, V value) | 将指定的"键-值"对存入 Map 中 |

| V get(Object key) | 返回指定键所映射的值 |

| V remove(Object key) | 根据指定的键把此"键-值"对从 Map 中移除 |

| boolean containsKey(Object key) | 判断此 Map 是否包含指定键 |

| boolean containsValue(Object value) | 判断此 Map 是否包含指定值 |

| boolean isEmpty() | 判断此 Map 中是否有元素 |

| int size() | 获得 Map 中"键-值"对的数量 |

| void clear() | 清空 Map 中的所有"键-值"对 |

| Set keySet() | 返回此 Map 中包含的键的集合 |

| Collection values() | 返回此 Map 中值的集合 |

[](

)HashMap

以哈希表方式存取数据，是使用非常多的集合。

创建方法：

HashMap<键类型,值类型> hashmap = new HashMap<>();

使用方法:

//创建 HashMap 保存人的对象

HashMap<String,Person> map = new HashMap<String,Person>();

Person person1 = new Person("张三",20);

Person person2 = new Person("李四",22);

Person person3 = new Person("王五",20);

//添加人到集合中

map.put(person1.getName(), person1);

map.put(person2.getName(), person2);

map.put(person3.getName(), person3);

//通过键访问值

map.get("张三").hello();

//删除

map.remove("李四");

//添加重复的键,将新的值覆盖原来的值

map.put("李四", new Person("李四",33));

System.out.println("长度：" + map.size());

//遍历所有的键

for(String key : map.keySet()){

System.out.println("键： " + key);

}

//遍历所有的值

for(Person per : map.values()){

per.hello();

}

//遍历所有的键和值

for(String key : map.keySet()){

System.out.println("键： " + key);

map.get(key).hello();

}

HashMap 的特点

1. 如果添加了重复的键，后面添加的值会替换前面的值。

2. 数据是用哈希算法计算存储位置，不是添加顺序

3. 添加的键必须实现 hashCode 和 equals 方法

HashMap 的数据结构

一维数组 + 单向链表 + 红黑树

HashMap 保存数据的过程

1. 添加键值对数据时，首先会调用键的 hashCode 方法，计算出数组下标

2. 如果该下标上的数据为空，就直接存入数据

3. 如果该下标上存在数据，就调用键的 equals 和该位置上的键进行比较

4. 如果 equals 返回 true，就用新的数据将旧的数据覆盖掉

5. 如果 equals 返回 false，将新的数据放在旧的数据后面，就形成链表

6. 当链表的长度超过 8，自动转换为红黑树（java8 的优化）

HashMap 源码解析

//添加数据

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

boolean evict) {

Node<K,V>[] tab; Node<K,V> p; int n, i;

if ((tab = table) == null || (n = tab.length) == 0)

n = (tab = resize()).length; // 获得数组长度

if ((p = tab[i = (n - 1) & hash]) == null) //hashCode 对数组长度-1 取模获得下标 i

tab[i] = newNode(hash, key, value, null); //该位置为空就直接添加数据

else {

Node<K,V> e; K k;

if (p.hash == hash &&

((k

【一线大厂Java面试题解析+核心总结学习笔记+最新架构讲解视频+实战项目源码讲义】
浏览器打开：qq.cn.hn/FTf 免费领取

= p.key) == key || (key != null && key.equals(k)))) //不为空就调用 equals 比较键

e = p; //键相同就赋值给 e，后面直接覆盖 value

else if (p instanceof TreeNode)

e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

else {

for (int binCount = 0; ; ++binCount) {

if ((e = p.next) == null) {

p.next = newNode(hash, key, value, null); //键不相同就放到后面，形成链表

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st

treeifyBin(tab, hash); //链表长度超过 8，转换为红黑树

break;

}

if (e.hash == hash &&

((k = e.key) == key || (key != null && key.equals(k))))