Java基础篇之五：深入探索Java中的集合核心原理
小标题 ： Java集合类探秘：探索Java集合算法的核心原理
在Java编程的世界中，集合类无疑是最重要的一部分之一。它们提供了存储和操作对象组的机制，涵盖了从简单的列表到复杂的映射等各种数据结构。本文将深入探讨Java中的所有主要集合类，并提供其内部实现算法的伪代码，帮助你更好地理解它们的工作原理。
1. List集合类
List是一个有序的集合，允许重复元素。Java中最常用的List实现类是ArrayList和LinkedList。
1.1 ArrayList ArrayList基于动态数组实现，支持快速随机访问。
伪代码：
class ArrayList<E> {
private Object[] elements;
private int size;
public ArrayList() {
elements = new Object[10]; // 初始容量
size = 0;
}
public void add(E element) {
if (size == elements.length) {
resizeArray(); // 扩容
}
elements[size++] = element;
}
private void resizeArray() {
Object[] newElements = new Object[elements.length * 2];
for (int i = 0; i < elements.length; i++) {
newElements[i] = elements[i];
}
elements = newElements;
}
public E get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
return (E) elements[index];
}
}
1.2 LinkedList LinkedList基于双向链表实现，支持高效的插入和删除操作。
伪代码：
class LinkedList<E> {
private Node<E> head;
private Node<E> tail;
private int size;
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;
}
}
public void add(E element) {
final Node<E> l = tail;
final Node<E> newNode = new Node<>(l, element, null);
tail = newNode;
if (l == null)
head = newNode;
else
l.next = newNode;
size++;
}
public E get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
return node(index).item;
}
private Node<E> node(int index) {
if (index < (size >> 1)) {
Node<E> x = head;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = tail;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
}
2. Set集合类
Set是一个不包含重复元素的集合。Java中最常用的Set实现类是HashSet和TreeSet。
2.1 HashSet HashSet基于哈希表实现，提供常数时间的插入、删除和查找操作。
伪代码：
class HashSet<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;
}
public boolean contains(Object k) {
return map.containsKey(k);
}
}
2.2 TreeSet TreeSet基于红黑树实现，元素按升序排列。
伪代码：
class TreeSet<E> {
private transient NavigableMap<E, Object> m;
private static final Object PRESENT = new Object();
public TreeSet() {
m = new TreeMap<>();
}
public boolean add(E e) {
return m.put(e, PRESENT) == null;
}
public boolean contains(Object k) {
return m.containsKey(k);
}
}
3. Map集合类
Map存储键值对，键是唯一的。Java中最常用的Map实现类是HashMap和TreeMap。
3.1 HashMap HashMap基于哈希表实现，提供常数时间的插入、删除和查找操作。
伪代码：
class HashMap<K, V> {
transient Node<K,V>[] table;
static class Node<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
public V put(K key, V value) {
int hash = hash(key);
int n = table.length;
if (n == 0)
n = (n < 64) ? 16 : 64;
if (table == null || table.length == 0)
resize();
int i = (n - 1) & hash;
for (Node<K,V> p = table[i]; p != null; p = p.next) {
if (p.hash == hash && (p.key == key || (key != null && key.equals(p.key))))
return p.value;
}
addEntry(hash, key, value, i);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex]))
resize();
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Node<K,V> e = table[bucketIndex];
table[bucketIndex] = new Node<>(hash, key, value, e);
size++;
}
}
3.2 TreeMap TreeMap基于红黑树实现，键值对按键的升序排列。
伪代码：
class TreeMap<K, V> {
private final NavigableMap<K, V> m;
public TreeMap() {
m = new TreeMap<>();
}
public V put(K key, V value) {
return m.put(key, value);
}
public V get(Object key) {
return m.get(key);
}
}
4. Queue集合类
Queue是一个先进先出（FIFO）的集合。Java中最常用的Queue实现类是ArrayDeque和LinkedList。
4.1 ArrayDeque ArrayDeque基于动态数组实现，支持高效的插入和删除操作。
伪代码：
class ArrayDeque<E> {
transient Object[] elements;
transient int head;
transient int tail;
public ArrayDeque() {
elements = new Object[16];
}
public void add(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
private void doubleCapacity() {
assert head == tail;
int p = head;
int n = elements.length;
int r = n - p; // number of elements to the right of p
int newCapacity = n << 1;
if (newCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
Object[] a = new Object[newCapacity];
System.arraycopy(elements, p, a, 0, r);
System.arraycopy(elements, 0, a, r, p);
elements = a;
head = 0;
tail = n;
}
}
4.2 LinkedList LinkedList也实现了Queue接口，基于双向链表实现。
伪代码：
class LinkedList<E> {
// 省略其他代码
public boolean offer(E e) {
return add(e);
}
public E poll() {
final Node<E> f = head;
return (f == null) ? null : unlinkFirst(f);
}
}
结语
通过深入了解Java集合类的内部实现和算法伪代码，你可以更好地掌握它们的性能特点和使用场景。无论是需要高效的随机访问、快速的插入和删除，还是有序的键值对存储，Java集合类都能为你提供合适的解决方案。
最近观察微信公众号发文已经到了接近50了，阅读量峰最高到了300+，技术文章阅读量最高也有70+，总体数据还有上升的趋势。咱们已经开始拥抱变化了，正在拥抱流行的AI技术，为自己腾出了更多的时间去处理其他的业务，通过其他业务赚钱，为咱们公众号的公益化运营提供了资金保障！当然后续还会更加优化AI方面内容，争取能够做出更好的成绩！ 欢迎大家多多关注和支持！ 我们一直会保持不定期更新，绝对不会放弃，让我们都遇到更好的自己！