下面通过一张List、map、set图,让大家回想起如何使用这些类
列表,该接口的用户可以精确控制列表中每个元素的插入位置。用户可以通过整数索引(列表中的位置)访问元素,并搜索列表中的元素。与集合不同,列表通常允许重复元素。
我们看看List的实现类
有很多类实现了List接口,我们比较熟悉的 ArrayList、LinkedList、Stack等等,我们从中选区ArrayList类观察一下源码,看看是怎么实现的。
Java中ArrayList的添加元素方法,简要分析
package java.util.ArrayList;
transient Object[] elementData; // non-private to simplify nested class access
public ArrayList() { //构造函数
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
private int size;
public boolean add(E e) { //添加方法
ensureCapacityInternal(size + 1); //必要检查步骤,如下 下标、数组大小
elementData[size++] = e; //实际存入数组中
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private static int calculateCapacity(Object[] elementData, int minCapacity) {//检查数组下标
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { //首次返回1
return Math.max(DEFAULT_CAPACITY, minCapacity); //int DEFAULT_CAPACITY=10
}
return minCapacity; //后续返回当前值
}
private void ensureExplicitCapacity(int minCapacity) { //检查是否需要扩容数组
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0) //当前下标是否大于数组已有长度
grow(minCapacity); //自动扩容
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
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); //拷贝数组,增加长度
}
这就是ArrayList的添加元素的方法,通过必要的检查和扩容数组,下标从0开始自增,下标和元素一一对应存储在数组中。
这个类是不同步的,非线程安全的。
将键映射到值的数据结构。Map不能包含重复的键; 每个键最多可以映射一个值。
我们通过查看Map的实现类,熟悉一下Map
我们比较熟悉的HashMap、Hashtable、treeMap
Java中HashMapt的添加元素方法,简要分析
package java.util.HashMap;
static final float DEFAULT_LOAD_FACTOR = 0.75f; //在构造函数中未指定时使用的加载因子
static class Node<K,V> implements Map.Entry<K,V> { //感觉是一个具有键值的链表
final int hash;
final K key;
V value;
Node<K,V> next;
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
...... //里面有一些方法getKey、getValue、toString、setValue
}
public HashMap() { //构造函数
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) { //获取Key的哈希值
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); //调用key的对象哈希值,>>>为无符号右移运算符
}
//第一个参数:Key的哈希值。第二个参数:key。第三个参数:值。
//第四:默认为true,改变key所映射的值。第五个参数:默认为false,哈希表已经创建。
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) //transient Node<K,V>[] table;
n = (tab = resize()).length; //resize()是初始化或加倍表格大小
if ((p = tab[i = (n - 1) & hash]) == null) //链表数组是否为空
tab[i] = newNode(hash, key, value, null); //创建具有保存键值的链表并保存数据进去,但是最后一个为null也就不是链表了
else { //发生哈希冲突
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p; //让e非空
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);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key //e非空,更改Node对象的值
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold) //Node数组不够了
resize(); //扩容
afterNodeInsertion(evict); //默认true
return null;
}
看起来就很复杂,但是也比较容易弄懂,通过一个Node对象存储键值对 和哈希值,创建一个Node数组,假如Node数组为空则创建数组(扩容),假如没有发生哈希冲突,则创建Node对象存入数据;假如发生哈希冲突,则依此判断键值对是否改变,是否红黑树,否则就迭代链表。 java的树(TreeMap)是怎么实现的?
不包含重复元素的集合。更明确的说法是,集合不包含相同元素e1和e2,使得e1.equals(E2)为真,并且至多一个null元素。
我们看一下Set接口的实现类
我们通过比较熟悉的HashSet熟悉一下Set接口,同样的我们先看看添加元素方法
package java.util.HashSet;
public HashSet() { //构造方法
map = new HashMap<>(); //创建一个hashMap保存元素
}
private static final Object PRESENT = new Object();//与后面Map中的对象值关联的虚拟值
public boolean add(E e) {
return map.put(e, PRESENT)==null; //只传递Key,不传递值
}
//后面map.put(e,obj)的实现,可以看前面map的详细介绍
我们可以知道,HashSet利用到HashMap类,在创建Set对象的时候,也创建了HashMap对象,add添加元素方法,只传递Key进去和一个共同对象,后面生成哈希值,存储到Node节点中都由HashMap实现。