java
集合类主要分为两大体系,继承自Collection
的List
和Set
,还有自己作为根的Map
.大体的结构如下.
Collection
├List
│├LinkedList
│├ArrayList
│└Vector
│ └Stack
└Set
├HashSet
├TreeSet
Map
├Hashtable
├HashMap
└TreeMap
└WeakHashMap
Map
HashMap
通过hash表实现的key-value存储,按照key的hashCode存储,可以有null key,
TreeMap
是有序的,通过key的Comparable比较器实现key-value的有序存储
LinkedHashMap
也是有序的,也是通过key的hashCode存储,但是遍历是增加了有序属性,即与加入的顺序保持一致
HashMap
HashMap
是基于hash
算法实现的,通过hash因子的作用,将元素"比较平均"的分散,以提高元素查找的命中率.具体的实现原理如下图:
HashMap
是非线程安全的,允许null key
,当threshold=capacity*loadfactor
时会扩容为capacity<<1
,这里capacity
为桶的数量.
以下是put<k,v>()
方法:
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
可以看到优先判断null key
,然后计算key
的hash
值,通过hash
值与capacity
结合判断位于Hash桶
的位置,然后判断是否有当前key
的Entry
,如果存在,替换value
为新值,并返回旧的value
,否则添加一个新的Entry
,并且返回null
,如果一个桶已有至少一个Entry
,则会作为链表的第一个元素插入.
HashTable
HashTable
的原理与HashMap
原理类似,只是比较特殊的所有操作加上了对当前对象操作的synchronized
,以达到同步锁的功能,从而实现线程同步.
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry tab[] = table;
int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
V old = e.value;
e.value = value;
return old;
}
}
modCount++;
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();
tab = table;
hash = hash(key);
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
Entry<K,V> e = tab[index];
tab[index] = new Entry<>(hash, key, value, e);
count++;
return null;
}
private int hash(Object k) {
// hashSeed will be zero if alternative hashing is disabled.
return hashSeed ^ k.hashCode();
}
从上可知,HashTable
不允许加入null key
,null value
.
还有一个就是,HashTable
初始容量是11.
Collection
Hashset
Hashset
本应不在map
系列,但由于Hashset
的实现是基于HashMap
实现的,所以这里列出,
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
/**
* Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
* default initial capacity (16) and load factor (0.75).
*/
public HashSet() {
map = new HashMap<>();
}
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
从上可以看出,每次add
一个元素,其实是将该元素当做一个key
存入Hashmap
中,value
为一个"dummy value"(一个Object
对象).所以其实是通过Hashmap
保证了元素的唯一.
LinkedList与Queue
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
可知LinkedList
实现了Deque
,而Deque
是丰富了父接口Queue
,
Queue
是Collection接口的子类,Collection
实现了Iterable
,所以是可遍历的。
而Map
没有实现Iterable
,但是通过一系列方法如entrySet()
等转换成集合类Set
来实现遍历功能.
Arraylist
Arraylist
的实现是基于数组的,初始数组大小为10,容量不足时扩展为原来的1.5
倍.
Collections
Collections
主要是作为集合方法的一些扩展,有大量的static方法,来帮助我们方便的处理集合,在其中主要摘两点做一些研究:
不变的empty集合
Collections
含有很多的静态空集合方法,其实我们使用这些特性的地方无非有两处:
- 在自己的方法中
return null
处return Collections.emptyList()
,这样可以避免上层调用使用时发生NullPointException
.
2.返回一个不可变(引用不可变)的集合实例.
@SuppressWarnings("unchecked")
public static final <T> List<T> emptyList() {
return (List<T>) EMPTY_LIST;
}
@SuppressWarnings("unchecked")
public static final List EMPTY_LIST = new EmptyList<>();
上面是返回emptyList
的源码.
不变的empty迭代器
大多数空方法返回的是不变空集合,但是有以下三个方法返回的是空迭代器:<T> Enumeration<T> emptyEnumeration() (classic iteration method), <T> Iterator<T> emptyIterator(), and <T> ListIterator<T> emptyListIterator()
作用也无非上面返回空集合的那些作用.
@SuppressWarnings("unchecked")
public static <T> Iterator<T> emptyIterator() {
return (Iterator<T>) EmptyIterator.EMPTY_ITERATOR;
}
private static class EmptyIterator<E> implements Iterator<E> {
static final EmptyIterator<Object> EMPTY_ITERATOR
= new EmptyIterator<>();
public boolean hasNext() { return false; }
public E next() { throw new NoSuchElementException(); }
public void remove() { throw new IllegalStateException(); }
}
综上,我们可以得出结论,这些空方法可以帮助我们让编码更安全,防止空引用的发生。